  Truss decomposition is a method used to analyze large sparse graphs in order
to identify successively better connected subgraphs. Since in many domains the
underlying graph changes over time, its associated truss decomposition needs to
be updated as well. This work focuses on the problem of incrementally updating
an existing truss decomposition and makes the following three significant
contributions. First, it presents a theory that identifies how the truss
decomposition can change as new edges get added. Second, it develops an
efficient incremental algorithm that incorporates various optimizations to
update the truss decomposition after every edge addition. These optimizations
are designed to reduce the number of edges that are explored by the algorithm.
Third, it extends this algorithm to batch updates (i.e., where the truss
decomposition needs to be updated after a set of edges are added), which
reduces the overall computations that need to be performed. We evaluated the
performance of our algorithms on real-world datasets. Our incremental algorithm
achieves over 250000x average speedup for inserting an edge in a graph with 10
million edges relative to the non-incremental algorithm. Further, our
experiments on batch updates show that our batch algorithm consistently
performs better than the incremental algorithm.
