We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs

Formal Metadata

Title
Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Due to the ubiquity of graphs, graph analytics has attracted much attention from both research and industry communities. The notion of k-truss is widely used in graph analytics. Since graphs are continuously evolving in real applications and it is costly to compute trusses from scratch, we study the problem of truss maintenance which aims at designing efficient incremental algorithms to update trusses when graphs are updated with changes. An incremental algorithm is desired to be bounded; that is, its cost is of O(f(|CHANGED|_c)) for some polynomial function f and some positive integer c, where CHANGED comprises the changes to both the graph and the result and |CHANGED|_c is the size of the c-hop neighborhood of CHANGED. An incremental problem is bounded if it has a bounded incremental algorithm and is unbounded otherwise. Under the model of locally persistent algorithms, we prove that truss maintenance is bounded under edge removals but is unbounded even for unit edge insertions. To address the unboundedness, we formulate a new notion AFF^preceq which, as a practically effective alternative to CHANGED, represents a set of edges affected by the changes to the graph, and devise an insertion algorithm that is bounded with respect to AFF^preceq, while retaining the boundedness for edge removals. More specifically, our insertion algorithm runs in O(f(|AFF^preceq|_c)) time for some polynomial function f and some positive integer c with |AFF^preceq|_c being the size of the c-hop neighborhood of AFF^preceq. Our extensive performance studies show that our new algorithms can significantly outperform the state-of-the-art by up to 3 orders of magnitude for the 12 large real graphs tested and are more efficient than computing trusses from scratch even for changes of non-trivial size. We report our findings in this paper.