2009 ScalableGraphClusteringUsingSto

• (Satuluri et al., 2009) ⇒ Venu Satuluri, and Srinivasan Parthasarathy. (2009). “Scalable Graph Clustering Using Stochastic Flows: Applications to Community Discovery.” In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2009). doi:10.1145/1557019.1557101

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Scalable+graph+clustering+using+stochastic+flows%3A+applications+to+community+discovery%22+2009
• http://portal.acm.org/citation.cfm?doid=1557019.1557101&preflayout=flat#citedby

Quotes

Author Keywords

Graphs, Clustering, Communities, Networks

Abstract

Algorithms based on simulating stochastic flows are a simple and natural solution for the problem of clustering graphs, but their widespread use has been hampered by their lack of scalability and fragmentation of output. In this article we present a multi-level algorithm for graph clustering using flows that delivers significant improvements in both quality and speed. The graph is first successively coarsened to a manageable size, and a small number of iterations of flow simulation is performed on the coarse graph. The graph is then successively refined, with flows from the previous graph used as initializations for brief flow simulations on each of the intermediate graphs. When we reach the final refined graph, the algorithm is run to convergence and the high-flow regions are clustered together, with regions without any flow forming the natural boundaries of the clusters. Extensive experimental results on several real and synthetic datasets demonstrate the effectiveness of our approach when compared to state-of-the-art algorithms.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 ScalableGraphClusteringUsingSto	Srinivasan Parthasarathy Venu Satuluri			Scalable Graph Clustering Using Stochastic Flows: Applications to Community Discovery		KDD-2009 Proceedings		10.1145/1557019.1557101		2009