New Journal of Physics · 2010 · 785 citations · 32 references
ComputingComputer ScienceDistributed SystemsGraph VisualizationNetwork BiologyCommunity DetectionCommunity StructureGraph AlgorithmsGraph LabelingNetwork PropagationBipartite NetworksLabel PropagationNetwork Community DetectionNetwork Community StructureOverlapping Community Detection
Label propagation is a well‑known community detection method, but it traditionally does not identify overlapping communities. The study proposes an algorithm to detect overlapping community structure in very large networks. The algorithm extends label propagation by allowing each vertex to hold up to v community labels, propagating these labels among neighbors, and supporting weighted and bipartite networks. Benchmarks and real‑world tests demonstrate that the algorithm accurately recovers overlapping communities and processes large, dense networks rapidly.
We propose an algorithm for finding overlapping community structure in very large networks. The algorithm is based on the label propagation technique of Raghavan, Albert and Kumara, but is able to detect communities that overlap. Like the original algorithm, vertices have labels that propagate between neighbouring vertices so that members of a community reach a consensus on their community membership. Our main contribution is to extend the label and propagation step to include information about more than one community: each vertex can now belong to up to v communities, where v is the parameter of the algorithm. Our algorithm can also handle weighted and bipartite networks. Tests on an independently designed set of benchmarks, and on real networks, show the algorithm to be highly effective in recovering overlapping communities. It is also very fast and can process very large and dense networks in a short time.
32
Finding and evaluating community structure in networks
Michelle G. Newman, Michelle Girvan · Physical Review E · 2004 · 14.1K citations · Full text
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text
Lawrence J. Hubert, Phipps Arabie · Journal of Classification · 1985 · 7.7K citations