Research on the Community Detection Methods in Complex Networks

Abstract:

In recent 15 years, the study of complex networks has been gradually becoming an important issue. Community structure is an interesting property of complex networks. Researchers have made much exciting and important progress in community detection methods. The paper introduced the definition and significance of community structure; elaborates on the overview of community discovery algorithms and a proposed taxonomy according to the basic principle that they used. Modularity function was recommended briefly. Finally, described several popular test methods and benchmarks.

• Periodical: Applied Mechanics and Materials (Volumes 513-517)
• Pages: 2433-2438
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.513-517.2433
• Online since: February 2014
• Authors: Lu Wang*, Yong Quan Liang, Jie Yang, Chao Song, Shu Han Cheng
• Keywords: Community Detection, Community Structure, Complex Network, Modularity Function, Real-World Networks

References

[1] S.N. Dorogovtsev, J. F. F. Mendes, Evolution of networks, Advances in Physics, 6th March (2001).

[2] M. Girvan, M.E.J. Newman, Community structure in social and biological networks, PNAS, 2002, Vol. 99, no. 12, pp.7821-7826.

[3] Capocci, A., V.D.P. Servedio, et al. Detecting communities in large networks [J]. Physica A: Statistical Mechanics and its Applications, 2005. 352(2-4): pp.669-676.

DOI: 10.1016/j.physa.2004.12.050

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

[5] Newman MEJ Fast algorithm for detecting community structure in networks. Physical Review E, 2010, Vol 69, 066133.

[6] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy: Automated discovery of community structure within organizations[C] Proceedings of First International Conference on Communities and Technologies. Dordrecht: Kluwer, 2003, pp.81-96.

DOI: 10.1007/978-94-017-0115-0_5

[7] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks [J]. Proceedings of National Academy of Science, 2004, 101(9), pp.2658-2663.

DOI: 10.1073/pnas.0400054101

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

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

DOI: 10.1038/nature03288

[10] Kernighan BW, Lin S An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970, Vol 49, p.291–307.

DOI: 10.1002/j.1538-7305.1970.tb01770.x

[11] Donetti L, Muñoz MA, Detecting network communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics: Theory and Experiment, 2004, P10012.

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

[12] Capocci A, Servedio VDP, Caldarelli G, Colaiori F Detecting communities in large networks. Physica A, 2004, Vol 352, No 2-4, pp.669-676.

DOI: 10.1016/j.physa.2004.12.050

[13] Wu F, Huberman BA Finding communities in linear time: a physics approach. European Physical Journal B, 2004, Vol 38, pp.331-338.

[14] Wu FY (1982) The Potts model. Reviews of Modern Physics, Vol 54, p.235–268.

[15] Reichardt J, Bornholdt S (2004) Detecting fuzzy community structure in complex networks. Physical Review Letters, Vol 93, No 21, 218701.

DOI: 10.1103/physrevlett.93.218701

[16] Zhou H (2003) Network landscape from a Brownian particle's perspective. Physical Review E, Vol 67, 041908.

[17] S. Fortunato and M. Barthelemy (2007). Resolution limit in community detection. Proceedings of the National Academy of Science of the USA 104 (1), p.36–41.

[18] L. Danon, A. Daz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics, P09008, (2005).

DOI: 10.1088/1742-5468/2005/09/p09008

[19] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. New benchmark in community detection. arXiv: 0805. 4770v2 [physics. soc-ph], (2008).