Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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

• 1: Vicente Arnau , Sergio Mars , Ignacio Marín, Iterative Cluster Analysis of Protein Interaction Data, Bioinformatics, v.21 n.3, p.364-378, February 2005 [doi>10.1093/bioinformatics/bti021]
• 2: S. Brohee and J. van Helden. Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics, 7, 2006.
• 3: Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132954]
• 4: Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Weighted Graph Cuts without Eigenvectors A Multilevel Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.11, p.1944-1957, November 2007 [doi>10.1109/TPAMI.2007.1115]
• 5: S. V. Dongen. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, 2000.
• 6: Shantanu Dutt , Wenyong Deng, Cluster-aware iterative improvement techniques for partitioning large VLSI circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.91-121, January 2002 [doi>10.1145/504914.504918]
• 7: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 8: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 9: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 10: B. Kernighan and S. Lin. An Efficient Heuristic Procedure for partitioning graphs. The Bell System Technical J., 49, 1970.
• 11: J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. CoRR, abs/0810.1355, 2008.
• 12: Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , Michael W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367591]
• 13: L. Li, C. J. Stoeckert, and D. S. Roos. OrthoMCL: identification of ortholog groups for eukaryotic genomes. Genome Res, 13(9):2178--2189, September 2003.
• 14: M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E, 69(2):026113, Feb 2004.
• 15: V. Satuluri and S. Parthasarathy. Scalable Graph Clustering Using Stochastic Flows: Applications to Community Discovery. Technical Report OSU-CISRC-4/09-TR10, The Ohio State University.
• 16: R. Sharan, I. Ulitsky, and R. Shamir. Network-based prediction of protein function. Molecular Systems Biology, 3, 2007.
• 17: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 18: The Gene Ontology Consortium. Gene Ontology: tool for the unification of biology. Nature Genetics, 25:25--29, 2000.
• 19: Koji Tsuda, Propagating distributions on a hypergraph by dual information regularization, Proceedings of the 22nd international conference on Machine learning, p.920-927, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102467]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance

Keywords:
clustering, communities, graphs, networks