Junming Shao
ABSTRACT
In this paper, we introduce a new community detection algorithm, called Attractor, which automatically spots communities in a network by examining the changes of "distances" among nodes (i.e. distance dynamics). The fundamental idea is to envision the target network as an adaptive dynamical system, where each node interacts with its neighbors. The interaction will change the distances among nodes, while the distances will affect the interactions. Such interplay eventually leads to a steady distribution of distances, where the nodes sharing the same community move together and the nodes in different communities keep far away from each other. Building upon the distance dynamics, Attractor has several remarkable advantages: (a) It provides an intuitive way to analyze the community structure of a network, and more importantly, faithfully captures the natural communities (with high quality). (b) Attractor allows detecting communities on large-scale networks due to its low time complexity (O(|E|)). (c) Attractor is capable of discovering communities of arbitrary size, and thus small-size communities or anomalies, usually existing in real-world networks, can be well pinpointed. Extensive experiments show that our algorithm allows the effective and efficient community detection and has good performance compared to state-of-the-art algorithms.
Supplemental Material
- Nir Ailon, Yudong Chen, and Huan Xu. Breaking the small cluster barrier of graph clustering. In ICML, pages 995--1003, 2013.Google Scholar
Digital Library
- Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, 2008.Google ScholarCross Ref
- Santo Fortunato. Community detection in graphs. Physics Reports, 486(3):75--174, 2010.Google ScholarCross Ref
- Santo Fortunato and Marc Barthélemy. Resolution limit in community detection. PNAS, 104(1):36--41, 2007.Google ScholarCross Ref
- Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821--7826, 2002.Google ScholarCross Ref
- Christian Hennig and Bernhard Hausdorf. Design of dissimilarity measures: A new dissimilarity between species distribution areas. In Data Science and Classification, pages 29--37. Springer, 2006.Google ScholarCross Ref
- Paul James, Yaso Nadarajah, Karen Haive, and Victoria Stead. Sustainable communities, sustainable development: Other paths for papua new guinea. Hawaiian Journal of History, 48, 2014.Google Scholar
- George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):359--392, 1998. Google ScholarDigital Library
- George Karypis and Vipin Kumar. Multilevelk-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed computing, 48(1):96--129, 1998. Google ScholarDigital Library
- Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms. Physical review E, 78(4):046110, 2008.Google Scholar
- Mark EJ Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577--8582, 2006.Google ScholarCross Ref
- William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 66(336):846--850, 1971.Google ScholarCross Ref
- Martin Rosvall and Carl T Bergstrom. Maps of random walks on complex networks reveal community structure. PNAS, 105(4):1118--1123, 2008.Google ScholarCross Ref
- Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27--64, 2007. Google ScholarDigital Library
- Junming Shao, Xiao He, Qinli Yang, Claudia Plant, and Christian Boehm. Robust synchronization-based graph clustering. In PAKDD, pages 249--260, 2013.Google ScholarCross Ref
- Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE TPAMI, 22(8):888--905, 2000. Google ScholarDigital Library
- Alexander Strehl and Joydeep Ghosh. Cluster ensembles--a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research, 3:583--617, 2003. Google ScholarDigital Library
- Stijn Van Dongen. A cluster algorithm for graphs. Report-Information systems, (10):1--40, 2000.Google Scholar
- Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE TPAMI, 15(11):1101--1113, 1993. Google ScholarDigital Library
- Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. In IEEE ICDM, pages 745--754, 2012. Google ScholarDigital Library
Index Terms
- Community Detection based on Distance Dynamics
Recommendations
Overlapping community detection in networks: The state-of-the-art and comparative study
This article reviews the state-of-the-art in overlapping community detection algorithms, quality measures, and benchmarks. A thorough comparison of different algorithms (a total of fourteen) is provided. In addition to community-level evaluation, we ...
Empirical comparison of algorithms for network community detection
WWW '10: Proceedings of the 19th international conference on World wide webDetecting clusters or communities in large real-world graphs such as large social or information networks is a problem of considerable interest. In practice, one typically chooses an objective function that captures the intuition of a network cluster as ...
Community Discovery in Dynamic Networks: A Survey
Several research studies have shown that complex networks modeling real-world phenomena are characterized by striking properties: (i) they are organized according to community structure, and (ii) their structure evolves with time. Many researchers have ...
Comments