Community Detection in Social Networks

Abstract:

Community detection as a branch of social network analysis has been a hot topic in the past decade. This paper reviews the research about the community detection these years and focuses on the community detection relevant classical algorithms as well as the classic real network datasets.

• Periodical: Applied Mechanics and Materials (Volumes 496-500)
• Pages: 2174-2177
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.496-500.2174
• Online since: January 2014
• Authors: Chang Su*, Yu Kun Wang, Yue Yu
• Keywords: Community Detection, Dataset, Modularity, Social Network

References

[1] Milgram S. The small world problem[J]. Psychology today, 1967, 2(1): 60-67.

[2] Albert R, Barabási A L. Statistical mechanics of complex networks[J]. Reviews of modern physics, 2002, 74(1): 47.

[3] Adamic L A, Adar E. Friends and neighbors on the web[J]. Social networks, 2003, 25(3): 211-230.

DOI: 10.1016/s0378-8733(03)00009-1

[4] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

DOI: 10.1073/pnas.122653799

[5] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.

[6] Hastie T, Tibshirani R, Friedman J, et al. The elements of statistical learning: data mining, inference and prediction[J]. The Mathematical Intelligencer, 2005, 27(2): 83-85.

DOI: 10.1007/bf02985802

[7] Garey M R, Johnson D S. Computers and intractability[M]. San Francisco: freeman Publishers (1979).

[8] Fortunato S, Latora V, Marchiori M. Method to find community structures based on information centrality[J]. Physical review E, 2004, 70(5): 056104.

DOI: 10.1103/physreve.70.056104

[9] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133.

[10] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical review E, 2004, 70(6): 066111.

DOI: 10.1103/physreve.70.066111

[11] Donetti L, Munoz M A. Detecting network communities: a new systematic and efficient algorithm[J]. Journal of Statistical Mechanics: Theory and Experiment, 2004, 2004(10): P10012.

DOI: 10.1088/1742-5468/2004/10/p10012

[12] Donath W E, Hoffman A J. Lower bounds for the partitioning of graphs[J]. IBM Journal of Research and Development, 1973, 17(5): 420-425.

DOI: 10.1147/rd.175.0420

[13] M. Meila and J. Shi. A random walks view of spectral segmentation. In Proceedings of the 8th International Workshop on Artificial Intelligence and Statistics, pages 92–97, Kaufmann, San Francisco, 2001. Citeseer.

[14] Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174.

[15] MacQueen J. Some methods for classification and analysis of multivariate observations [C]/Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. 1967, 1(281-297): 14.

[16] J.C. Bezdek. Pattern recognition with fuzzy objective function algorithms. Kluwer Academic Publishers, (1981).

[17] Schuetz P, Caflisch A. Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement[J]. Physical Review E, 2008, 77(4): 046112.

DOI: 10.1103/physreve.77.046112

[18] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028): 895-900.

DOI: 10.1038/nature03288

[19] Boettcher S, Percus A G. Optimization with extremal dynamics[J]. Complexity, 2002, 8(2): 57-62. S.

[20] Duch J, Arenas A. Community detection in complex networks using extremal optimization[J]. Physical review E, 2005, 72(2): 027104.

DOI: 10.1103/physreve.72.027104

[21] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical review E, 2006, 74(3): 036104.

[22] Wang G, Shen Y, Ouyang M. A vector partitioning approach to detecting community structure in complex networks[J]. Computers & Mathematics with Applications, 2008, 55(12): 2746-2752.

DOI: 10.1016/j.camwa.2007.10.028

[23] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.

[24] Van Dongen S. Graph clustering by flow simulation[D]. Utrecht, Netherlands: University of Utrecht, (2000).

[25] Arenas A, Díaz-Guilera A, Pérez-Vicente C J. Synchronization reveals topological scales in complex networks[J]. Physical review letters, 2006, 96(11): 114102.

DOI: 10.1103/physrevlett.96.114102

[26] Lambiotte R, Delvenne J C, Barahona M. Laplacian dynamics and multiscale modular structure in networks[J]. arXiv preprint arXiv: 0812. 1770, (2008).

[27] Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118-1123.

DOI: 10.1073/pnas.0706851105

[28] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977: 452-473.

DOI: 10.1086/jar.33.4.3629752

[29] Lusseau D. The emergent properties of a dolphin social network[J]. Proceedings of the Royal Society of London. Series B: Biological Sciences, 2003, 270(Suppl 2): S186-S188.

DOI: 10.1098/rsbl.2003.0057