Detecting Overlapping Communities with MDS and Local Expansion FCM

Abstract:

Community structure is an important feature to understand structural and functional properties in various complex networks. In this paper, we use Multidimensional Scaling (MDS) to map nodes of network into Euclidean space to keep the distance information of nodes, and then we use topology feature of communities to propose the local expansion strategy to detect initial seeds for FCM. Finally, the FCM are used to uncover overlapping communities in the complex networks. The test results in real-world and artificial networks show that the proposed algorithm is efficient and robust in uncovering overlapping community structure.

• Periodical: Applied Mechanics and Materials (Volumes 644-650)
• Pages: 3295-3299
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.644-650.3295
• Online since: September 2014
• Authors: Lin Li*, Zheng Min Xia, Sheng Hong Li, Li Pan, Zhi Hua Huang
• Keywords: Community Structure, Local Expansion Strategy, MDS

References

[1] S.H. Strogatz. Exploring complex networks[J], Nature, 410, 268-276, (2001).

[2] Watts D J, Strogatz S H. Collective dynamics of small-world, networks [J]. Nature , 1998, 393(6684): 440-442.

DOI: 10.1038/30918

[3] 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

[4] Hand D J, Mannila H, Smyth P. Principles of data mining[M]. MIT press, (2001).

[5] Huang J, Sun H, Han J, et al. Density-based shrinkage for revealing hierarchical and overlapping community structure in networks[J]. Physica A: Statistical Mechanics and its Applications, 2011, 390(11): 2160-2171.

DOI: 10.1016/j.physa.2010.10.040

[6] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11(3): 033015.

DOI: 10.1088/1367-2630/11/3/033015

[7] Z. Feng, X. Xu, Yuruk N. and Schweiger. A Novel Similarity-Based Modularity Function for Graph Partitioning[C]. In Proceedings of DaWaK'2007, 385-396.

DOI: 10.1007/978-3-540-74553-2_36

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

[9] Chen D, Shang M, Lv Z, et al. Detecting overlapping communities of weighted networks via a local algorithm[J]. Physica A: Statistical Mechanics and its Applications, 2010, 389(19): 4177-4187.

DOI: 10.1016/j.physa.2010.05.046

[10] Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(09): P09008.

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

[11] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 036106.

DOI: 10.1103/physreve.76.036106

[12] 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. MLA.

[13] Jiang Y, Jia C, Yu J. An efficient community detection method based on rank centrality[J]. Physica A: Statistical Mechanics and its Applications, 2013, 392(9): 2182-2194.

DOI: 10.1016/j.physa.2012.12.013