Paper Info
Title
Cracker: Crumbling large graphs into connected components.
Abstract
The problem of finding connected components in a graph is common to several applications dealing with graph analytics, such as social network analysis, web graph mining and image processing. The exponentially growing size of graphs requires the definition of appropriated computational models and algorithms for their processing on high throughput distributed architectures. In this paper we present cracker, an efficient iterative algorithm to detect connected components in large graphs. The strategy of cracker is to iteratively grow a spanning tree for each connected component of the graph. Nodes added to such trees are discarded from the computation in the subsequent iterations. We provide an extensive experimental evaluation considering a wide variety of synthetic and real-world graphs. The experimental evaluation shows that cracker consistently outperforms state-of-the-art approaches both in terms of total computation time and volume of messages exchanged.
Year
DOI
Venue
2015
10.1109/ISCC.2015.7405576
ISCC
Keywords
Field
DocType
cracker,crumbling large graph,connected component,graph analytics,social network analysis,Web graph mining,image processing,computational model,throughput distributed architecture,iterative algorithm,spanning tree,experimental evaluation,synthetic graph,real-world graph,computation time
Modular decomposition,Algorithm design,Computer science,Theoretical computer science,SPQR tree,Connected component,Spanning tree,Graph rewriting,Graph bandwidth,Graph (abstract data type),Distributed computing
Conference
Citations 
PageRank 
References 
13
0.67
20
Authors
5
Name
Order
Citations
PageRank
Alessandro Lulli18210.35
Laura Ricci215114.12
Emanuele Carlini316620.15
Patrizio Dazzi424924.78
Claudio Lucchese5110473.76