Identifying different community members in complex networks based on topology potential

Abstract

There has been considerable interest in designing algorithms for detecting community structure in real-world complex networks. A majority of these algorithms assume that communities are disjoint, placing each vertex in only one cluster. However, in nature, it is a matter of common experience that communities often overlap and members often play multiple roles in a network topology. To further investigate these properties of overlapping communities and heterogeneity within the network topology, a new method is proposed to divide networks into separate communities by spreading outward from each local important element and extracting its neighbors within the same group in each spreading operation. When compared with the state of the art, our new algorithm can not only classify different types of nodes at a more fine-grained scale successfully but also detect community structure more effectively. We also evaluate our algorithm using the standard data sets. Our results show that it performed well not only in the efficiency of algorithm, but also with a higher accuracy of partition results.

Keywords

complex network / community structure / topology potential / overlapping nodes

References

[1] Shen H W, Cheng X Q, Chen H Q, Liu Y. Information bottleneck based community detection in network. Chinese Journal of Computers, 2008, 31(4): 677–686

[2] Kernigan B. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970

[3] Eckmann J P, Moses E. Curvature of co-links uncovers hidden thematic layers in the World Wide Web. In: Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(9): 5825–5829

[4] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(2): 026113

[5] Girvan M, Newman M E J. Community structure in social and biological networks. Natl. Acad. Sci., 2002, 99(12): 7821–7826

[6] Macqueen J B. Some methods of classification and analysis of multivariate observations. In Proceeding of 5th Berkeley Symp on Mathematical Statistics and Probability. 1967: 281–297

[7] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl., 1990, 11(3): 430–452

[8] Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001, 25: 163–177

[9] Fortunato S, Latora V, Marchiori M. Method to find community structures based on information centrality. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2004, 70(5): 056104

[10] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. In: Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658–2663

[11] Wu F, Huberman B. Finding communities in linear time: a physics approach. The European Physical Journal B, 2004, 38(2):331–338

[12] Zhou H J, Lipowsky R. Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities. Lecture Notes in Computer Science, 2004, 3038: 1062–1069

[13] Bagrow J P, Rozenfeld H D, Bollt E M, et al. How famous is a scientist? ---famous to those who know us. cond-mat/0404515, Euro phys. Lett, 2004, 67(4): 511–516

[14] Capocci A, Servedio V D P, Caldarelli G, Colaiori F. Communities detection in large networks. Lecture Notes in Computer Science, 2004, 3243: 181–187

[15] Reichardt J, Bornholdt S. Detecting fuzzy community structures in complex networks with a potts model. Physical Review Letters, 2004, 93(21): 218–224

[16] Guimera R, Sales-Pardo M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks. Physical Review E, 2004, 70(2): 025101(R)

[17] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(6): 66–133

[18] Duch J, Arenas A. Community detection in complex networks using extreme optimization. Physical Review E, 2005, 72: 027104

[19] Donetti L, Munoz M A. Detecting Network Communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics, 2004: P10012

[20] Donetti L, Munoz M A. Improved spectral algorithm for the detection of network communities. In: Proceedings of the 8th International Conference on Modeling Cooperative Behavior in the Social Sciences. New York: American Institute of Physics, 2005, 779: 104–107

[21] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814–818

[22] Tyler J R, Wilkinson D, Huberman B. E-Mail as spectroscopy: automated discovery of community structure within organizations. Information Society, 2005, 21(2): 143–153

[23] Son S W. Random field ising model and community structure in complex networks. The European Physical Journal B, 2006, 50: 431

[24] Boccaletti S. Detection of complex networks modularity by dynamical clustering. Phys Rev E Stat Nonlin Soft Matter Phys, 2007, 75(4 Pt 2): 045102

[25] Han Y N, Li D Y. A novel measurement of structure properties in complex networks. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 2009, (5): 1292–1297

[26] He N, Li D Y. Evaluate nodes importance in the network based on data field theory. In: Proceedings of the 2007 International Conference on Convergence Information Technology, 2007: 1225–1234

[27] Amaral L A N, Ottino J. Complex networks. European Physical Journal B, 2004, 38(2): 147–162

[28] Newman M E J. Assortative mixing in networks. Physical Review Letters, 2002, 89(20): 208701

[29] V Colizza, A Flammini, M A Serrano, A Vespignani. Detecting rich-club ordering in complex networks. Nature Physics 2, 2006: 110–115

[30] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509–512

[31] Amaral L A N, Scala A, Barthelemy M, Stanley H E. Classes of small-world networks. In: Proceedings of the National Academy of Sciences of the United States of America, 2000, 97(21): 11149–11152

[32] Gregory S. An algorithm to find overlapping community structure in networks. In: Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases. 2007, (4702): 91–102

[33] Du N, Wang B, Wu B. Overlapping community structure detection in networks. In: Proceedings of the 17th ACM Conference on information and Knowledge Management. 2008: 1371–1372

[34] Zhang S H, Wang R S, Zhang X S. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications. 2006, 374(1): 483–490

[35] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2004, 70(6): 066111

[36] Girvan M, Newman M E J. Community structure in social and biological networks. In: Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821–7826

[37] Leskovec J, Lang K J, Dasgupta A. Statistical properties of community structure in large social and information networks. In: Proceedings of the 17th international conference on World Wide Web. 2008, 695–704

[38] Ulrik B, Daniel D, Marco G, Robert G. On finding graph clustering with maximum modularity. In: Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science. 2007, (4769): 121–132

[39] Rumi G, Kristina L. Community detection using a measure of global influence. In: Proceedings of the 2nd SNA-KDD Workshop '08. Las Vegas, Nevada, USA. 2008, 0805.4606

[40] http://www.orgnet.com/divided.html

[41] Niu Y Q, Hu B Q, Zhang W, Wang M. Detecting the community structure in complex networks based on quantum mechanics. Physical A: Statistical mechanics and its applications, 2008, 387(24): 6215–6224

Acknowledgements

This work was supported by the National Grand Fundamental Research 973 Program of China entitled “Requirement Engineering: Fundamental Research on Software Engineering within Complex Systems” (2007CB310804).

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg