|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|