2009 · 198 citations · 15 references
ComputingComputational EngineeringComputational Fluid DynamicsFlow VisualizationFluid DynamicsGraph AlgorithmsGraph AnalyticsNetwork Flow AlgorithmsNetwork FlowsNatural BoundariesScalable Graph AlgorithmsStochastic FlowsStochastic Network Flows
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.
15
Gene Ontology: tool for the unification of biology
Michael Ashburner, Catherine A. Ball, Judith A. Blake et al. · Nature Genetics · 2000 · 44.6K citations · Full text
Finding and evaluating community structure in networks
Michelle G. Newman, Michelle Girvan · Physical Review E · 2004 · 14.1K citations · Full text
OrthoMCL: Identification of Ortholog Groups for Eukaryotic Genomes
Li Li, Christian J. Stoeckert, David S. Roos · Genome Research · 2003 · 6.1K citations · Full text