Scalable graph clustering using stochastic flows: applications to community discovery Export

@inproceedings{citeulike:5043999, 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.}, address = {New York, NY, USA}, author = {Satuluri, Venu and Parthasarathy, Srinivasan}, booktitle = {KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining}, citeulike-article-id = {5043999}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1557019.1557101}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1557019.1557101}, doi = {10.1145/1557019.1557101}, isbn = {978-1-60558-495-9}, keywords = {clustering, graph}, location = {Paris, France}, pages = {737--746}, posted-at = {2009-07-03 09:26:57}, priority = {2}, publisher = {ACM}, title = {Scalable graph clustering using stochastic flows: applications to community discovery}, url = {http://dx.doi.org/10.1145/1557019.1557101}, year = {2009} }

TY - CONF ID - citeulike:5043999 L3 - citeulike-article-id:5043999 N2 - 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. CY - Paris, France SN - 978-1-60558-495-9 AD - New York, NY, USA EP - 746 TI - Scalable graph clustering using stochastic flows: applications to community discovery PB - ACM T2 - KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining SP - 737 KW - clustering KW - graph AU - Satuluri, Venu AU - Parthasarathy, Srinivasan PY - 2009/// UR - http://dx.doi.org/10.1145/1557019.1557101 ER -