Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci Chin    2011, Vol. 5 Issue (1) : 87-99    https://doi.org/10.1007/s11704-010-0071-x
RESEARCH ARTICLE
Identifying different community members in complex networks based on topology potential
Yanni HAN1(), Deyi LI1,2, Teng WANG1
1. State Key Laboratory of Software Development Environment, Beijing University of Aeronautics and Astronautics, Beijing 100191, China; 2. Institute of Electronic System Engineering, Beijing 100039, China
 Download: PDF(1140 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): HAN Yanni,Email:hyn@nlsde.buaa.edu.cn   
Issue Date: 05 March 2011
 Cite this article:   
Yanni HAN,Deyi LI,Teng WANG. Identifying different community members in complex networks based on topology potential[J]. Front Comput Sci Chin, 2011, 5(1): 87-99.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-010-0071-x
https://academic.hep.com.cn/fcs/EN/Y2011/V5/I1/87
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
doi: 10.3724/SP.J.1016.2008.00677
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
doi: 10.1073/pnas.032093399
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
doi: 10.1103/PhysRevE.69.026113
5 Girvan M, Newman M E J. Community structure in social and biological networks. Natl. Acad. Sci. , 2002, 99(12): 7821–7826
doi: 10.1073/pnas.122653799
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
doi: 10.1137/0611030
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
doi: 10.1103/PhysRevE.70.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
doi: 10.1073/pnas.0400054101
11 Wu F, Huberman B. Finding communities in linear time: a physics approach. The European Physical Journal B , 2004, 38(2):331–338
doi: 10.1140/epjb/e2004-00125-x
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
doi: 10.1007/978-3-540-30216-2_15
15 Reichardt J, Bornholdt S. Detecting fuzzy community structures in complex networks with a potts model. Physical Review Letters , 2004, 93(21): 218–224
doi: 10.1103/PhysRevLett.93.218701
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)
doi: 10.1103/PhysRevE.70.025101
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
doi: 10.1103/PhysRevE.69.066133
18 Duch J, Arenas A. Community detection in complex networks using extreme optimization. Physical Review E , 2005, 72: 027104
doi: 10.1103/PhysRevE.72.027104
19 Donetti L, Munoz M A. Detecting Network Communities: a new systematic and efficient algorithm. Journal of Statistical Mechanics , 2004: P10012
doi: 10.1088/1742-5468/2004/10/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
doi: 10.1038/nature03607
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
doi: 10.1080/01972240590925348
23 Son S W. Random field ising model and community structure in complex networks. The European Physical Journal B , 2006, 50: 431
doi: 10.1140/epjb/e2006-00155-4
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
doi: 10.1103/PhysRevE.75.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
doi: 10.1140/epjb/e2004-00110-5
28 Newman M E J. Assortative mixing in networks. Physical Review Letters , 2002, 89(20): 208701
doi: 10.1103/PhysRevLett.89.208701
29 V Colizza, A Flammini, M A Serrano, A Vespignani. Detecting rich-club ordering in complex networks. Nature Physics 2 , 2006: 110–115
doi: 10.1038/nphys209
30 Barabási A L, Albert R. Emergence of scaling in random networks. Science , 1999, 286(5439): 509–512
doi: 10.1126/science.286.5439.509
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
doi: 10.1073/pnas.200327197
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
doi: 10.1103/PhysRevE.70.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
doi: 10.1073/pnas.122653799
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
[1] Wei DUAN, Zongchen FAN, Peng ZHANG, Gang GUO, Xiaogang QIU. Mathematical and computational approaches to epidemic modeling: a comprehensive review[J]. Front. Comput. Sci., 2015, 9(5): 806-826.
[2] Zihou WANG, Yanni HAN, Tao LIN, Yuemei XU, Song CI, Hui TANG. Topology-aware virtual network embedding based on closeness centrality[J]. Front Comput Sci, 2013, 7(3): 446-457.
[3] Zonghua LIU , Xiaoyan WU , Pak-Ming HUI , . An alternative approach to characterize the topology of complex networks and its application in epidemic spreading[J]. Front. Comput. Sci., 2009, 3(3): 324-334.
[4] Weifeng PAN , Yutao MA , Jing LIU , Yeyi QIN , Bing LI , . Class structure refactoring of object-oriented softwares using community detection in dependency networks[J]. Front. Comput. Sci., 2009, 3(3): 396-404.
[5] Lili RONG , Tianzhu GUO , Jiyong ZHANG , . A new centrality measure based on sub-tree[J]. Front. Comput. Sci., 2009, 3(3): 356-360.
[6] Huan LI , . Scale-free network modles with accelerating growth[J]. Front. Comput. Sci., 2009, 3(3): 373-380.
[7] Chengyi XIA , Shiwen SUN , Feng RAO , Junqing SUN , Jinsong WANG , Zengqiang CHEN , . SIS model of epidemic spreading on dynamical networks with community[J]. Front. Comput. Sci., 2009, 3(3): 361-365.
[8] Shiwen SUN , Chengyi XIA , Junqing SUN , Zhenhai CHEN , Zengqiang CHEN , . Genealized collaboration networks in software systems: a case study of Linux kernels[J]. Front. Comput. Sci., 2009, 3(3): 421-426.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed