922 4 R = B in B in + B out (1) B in, B out. R,,., R,,., : 1),. ; 2),, ; 3),. 1 (a), A, B C D, A i j., A x, y, i A, R R i = y + 3 x y + 3 = y

Size: px

Start display at page:

Download "922 4 R = B in B in + B out (1) B in, B out. R,,., R,,., : 1),. ; 2),, ; 3),. 1 (a), A, B C D, A i j., A x, y, i A, R R i = y + 3 x y + 3 = y"

记德怀
7 years ago
Views:

1 4 5 Vol. 4, No ACTA AUTOMATICA SINICA May, , 2.,,,.., (Shell interception and core expansion, SICE). : 1) ( ), ; 2). SICE,,., SICE,. DOI,,,,.., 214, 4(5): /SP.J Method for Local Community Mining in the Complex Networks YUAN Chao 1 CHAI Yi 1, 2 Abstract Community structure detection bears both theoretical and practical significance for the study of complex systems. Generally speaking, the local community detection is relatively a more difficult problem than the global community detection. So up to now, the related researches are still slow progress. And there are many defects existing in the previous local community detection algorithms, such as low precision and poor stability. In this paper, a local community detection algorithm, which is called shell interception and core expansion (SICE), has been proposed. There are two innovations in this algorithm: 1) A node similarity model is introduced into this algorithm, and a community expansion mode one subgraph at a time is proposed; 2) An effective method which is named shell interception and core expansion is proposed. By these two innovations, the SICE algorithm has solved the problem of missing global network information, and avoided a fatal weakness of the previous algorithms. Theoretical analysis and experiments all illustrate that the SICE algorithm has high precision and stability, and it outperforms the previous algorithms. Key words Complex network, local community structure, data mining, clustering Citation Yuan Chao, Chai Yi. Method for local community mining in the complex networks. Acta Automatica Sinica, 214, 4(5): [1].,.,, [2 3] [4]., Manuscript received March 26, 213; accepted August 13, 213 ( ) Supported by National Natural Science Foundation of China ( ) Recommended by Associate Editor LV Jin-Hu School of Automation, Chongqing University, Chongqing State Key Laboratory of Power Transmission Equipment and System Security and New Technology, Chongqing University, Chongqing 444 ( [5 9] [1 11] ) [12 13] [14 18].,,,.,.,,.,.,,.,., Clauset R [14]. R,,, R,., R :

2 922 4 R = B in B in + B out (1) B in, B out. R,,., R,,., : 1),. ; 2),, ; 3),. 1 (a), A, B C D, A i j., A x, y, i A, R R i = y + 3 x y + 3 = y + 3 x + y + 5 j A, R R j = y + 3 x y + 3 = y + 3 x + y + 6 (2) (3) R i > R j. R, A i., A j, i B.,,. [15], Bagrow Kj l.,, α, Kj l α,., ;, α. Kj l. Kl j : K l j = Kl j K l 1 j (4), Kj l j l.. 1 (b), 5 l, Kj l = 1, K l 1 j = 5 (, ), Kj l = 2, α,.,,,.,, K l j R. B out /B in, R = B in B in + B out = B out B in (5),, K l j R. [16], Luo M,., M., M : M = E in E out (6), E in, E out. : 1) ; 2),. 1 (a), E in = y, E out = x, i A, M M i = y + 3 x = y + 3 (7) x + 2 j A, M M j = y + 3 x = y + 3 x + 3 (8) M i > M j. M, A i., A j, i B. (a) R M L (a) R value, M value, L value 1 Fig. 1 (b) K l j (b) K l j value Examples of the defects of the previous local community detection algorithms Chen L, [17]. L : L = L in L ex (9), L in, L ex.

3 5 : 923, ( 1 (a)),. Chen [18],.,. 1 (a)., : 1),.,., ; 2).,, ( 1 (a)), ; 3),.,.,.,, (Shell interception and core expansion, SICE).. 1),. : a).,,,,,,,.,,. b), ( 3.2 ). 2),,,.,,.,,,.,, SICE,. : 1 k ; 2 G ; 3,, ; 4 ; 5. 1 k,., SICE.,. [19] ( Salton [2] Dice [21] ) ( Katz [22] RWR [23] ) ( [24] [25] ).,. [25] SRW (Superposed random walk), k.,..,.,,., P. W, D = diag{w 1,, W n }, P ij P ij = W ij W i (1) P ij i j, W ij i j, W i i., P P = D 1 W. [25] (SRW). : x, t 1, π x (t 1), t π x (t) π x (t) = P T π x (t 1) (11), π x () N 1, x 1,, T. (Local random walk, LRW) s LRW xy (t) = q x π xy (t) + q y π yx (t) (12), s LRW xy (t) x y t (LRW), π xy (t) x t y, q x = k x /(2 E ), E. t,

4 924 4 (SRW) : s SRW xy (t) = t l=1 s LRW xy (l) (13) (12) (LRW),,. 2, x t y h (,., ), k ij ( i j, k x k y x y ), : π xy (t) = 1 k x 1 k 11 1 k 12 1 k 1(t 1) k x k 21 k 22 k 2(t 1) (14) k x k h1 k h2 k h(t 1) π yx (t) = 1 k y 1 k 1(t 1) 1 k 12 1 k k y k 2(t 1) k 22 k (15) k y k h(t 1) k h2 k h1, (14) (15), : k x π xy (t) = k y π yx (t) (16) (12), q x = k x /(2 E ), E, E, (16) 2 E, : 2 Fig. 2 q x π xy (t) = q y π yx (t) (17) x t y Illustration of the paths from x to y by t steps, (13) (SRW) s SRW xy (t) = 2q x t l=1 s LRW xy (l) = t π xy (l) = 2q y l=1 t π yx (l) (18) l=1 (18), x y y x..,, E,,,., k (Superposed unidirectional random walk, SURW) : s SURW xy (k) = k x k π xy (l) (19) l=1 x y x. s SURW xy (k) (14),, x y, x y,., k 3,. ( ),,,.,, k = 3, SURW. 2 G, R K j l M L.. R, 3, A B, 6., A 5 2, 1, 1, 17, R 2/3; B 6 1, 2,, R 2/3., B,. A,,,., R. G (Gap ). n E out (l) l=1 E in (l) G = (2) n

5 5 : 925, n, E out (l) l, E in (l) l. Fig. 3 3 A B Illustration of the boundaries of subgraph A and subgraph B G R,, R. G,,. 3, A B G , B,., G 1 (a)... 3,,. 1 (a), j A,, B C D,, j A.,.,.,.,,, ( ).,. (SICE),. SICE,,,. 3.1 SICE. LC = SICE(v, NET) /* v, NET, LC v. */ 1. ( (19), k = 3),. 1) v ; 2), j, j, 4);, j, j ; 3) 2); 4) 2; 2.. 1) v neighbor,, 3; 2) 1 v neighbor C new, C new ; 3) C new C k, C new C k (C k, ); 4) 1); 3.. 1) G G core ; G, G min. G core > G min,,, 2, ;, 3); 2) 1). 3) ; 4.,,. 1),, 2 3, ; 2) C i C j, [18] : f(c i, C j ) = C i C j min( C i, C j ) (21) 3) f(c i, C j ) ξ (ξ.5, 3.2 ),, C i ;, 6); 4) C i, 2 3; 5) 1); 6) LC,., 3 4,., G,,.,,.,

6 926 4 ( G, )., b,, G 2b k (k )., 4 (21)., (, ).,, (21),. : A B,, A B, SICE SICE.,.. 1). : a) SURW. SURW k. SURW,,.,, SURW ; b), (, ).,.,,.,. 2)., 1.,. SICE,,,. 4, i j, B C D S, S G ( R M L ) i ( j), A i ( j)., i ( j) A i ( j)., A j G, j B C D A,.,. 4 (A, i j ) Fig. 4 Illustration of core subgraph expansion phase (A represents the core subgraph, i and j represent two subgraphs which will be merged by A.) 3).,.,. SICE,,.. 5 (a), A B C, A i, B j, C k., i, A, j, B, k, C,.,.,. i, A,, j B, f (A, B) >.5, A B., k C, f ({A, B}, C) >.5,, C,., j k,.,.,,, 5 (b), A, B C D E., B, f(a, B) >.5, B A, B ; C, 5 %,, C A, A, ; D E, A,, A A

7 5 : 927.,, SICE. (a) (a) Example of how to ensure the stability of the algorithm Fig. 5 5 (b) (b) All the possible position relations between the core sub-graph and the neighbor sub-graphs Illustration of shell interception phase, (21).,,, 5 % (, 5 %,, ).,,, 5 %.,,,.,, 5 %.,,. 1,, f(c i, C j ),,. 1, { },. 1, f(c i, C j ) f(c i, C j )., f(c i, C j ).,, f(c i, C j ).5 ( );, f(c i, C j ) ( 1, )., ξ,.,, ξ [.3,.7],. ξ,., ξ =.5, f(c i, C j ).5,,,. SICE. 3.3 SICE 4, 1 2, 3, 4., ,, 1 2., n 1, n 2, 1 2 n 1 + n 2., k 3 (k, ),, 1 2 k 3 (n 1 + n 2 ). : 1) 3 G ; 2) 4 (21). 1), m 1 2, m ( m,, (n 1 + n 2 )),, l, G m l., G 3.1, 2b k (k, b )., 1) 2b k m l. 2), 3.1 n 1 + n 2 (n 1, n 2 )., SICE k 3 (n 1 + n 2 ) + 2bkml + n 1 + n 2 = (k 3 + 1)(n 1 + n 2 ) + 2bkml (22), k ; n 1, n 2 ; m 1 2 ; b 1 2 ; l 3., n 1 + n 2, k m b l,, 2bkml n 1 + n 2., SICE,. 4 SICE, Clauset-R [14] LWP [16]

8 928 4 Table 1 1 f(c i, C j) The f(c i, C j) values between the core-subgraph and the neighbor-subgraphs during the merging process 1 {1,2,3,4,5,6,7,8,11,12,13,14,17,18,2,22} {9,1,15,16,19,21,23,24,25,26,27,28,29,3,31, 32,33,34} f(c i, C j) Zachary 1 {1,3,11,29,31,43,48} {2,6,7,8,1,14,18,2,23,26,27,28,32,33,4,42, 49,55,57,58,61} {6,7,8,1,14,2,33,4,42,49,55,57,58,61} {4,5,9,12,16,19,22,24,25,3,36,46,52,56,6} {1,3,4,5,9,11,12,13, 15,16,17,19,21,22,24,25, 29,31,34,35,37,38,39,41,43,44,45,46,47,48, 1 5,51,52,53,54,56, 59,6,62} {54,62} {1,3,4,5,9,11,12,13,15,16,17,19,21,22,24, 25,29,31,34,35,37,38,39,41,43,44,45,46, 47,48,5,51,52, 53,54,56,59,6,62} {1,3,4,5,9,11,12,13,15,16,17,19,21,22,24, 25,29,31,34,35,37,38,39,41,43,44,45,46, 47,48,5,51,52,53,54,56,59,6,62} {2,6,7,8,1,14,18,2,23,26,27,28,32,33,4, 42,49,55,57,58,61} {6,7,8,1,14,2,33,4,42,49,55,57,58,61} {4,5,9,12,16,19,22,24,25,3,36,46,52,56,6}.87 {54,62} 1 {2,6,7,8,1,14,18,2,23,26,27,28,32,33,4, 42,49,55,57,58,61} {6,7,8,1,14,2,33,4,42,49,55,57,58,61} {4,5,9,12,16,19,22,24,25,3,36,46,52,56,6} {1,3,4,5,9,11,12,13,15,16,17,19,21,22,24, 25,29,3,31,34,35,36,37,38,39,41,43,44, 45,46,47,48,5,51,52,53,54, 56,59,6,62} f(c i, C j).87, f(c i, C j),. 38 {1,3,4,5,9,11,12,13,15,16,17,19,21,22, 24,25,29,31,34,35,37,38,39,41,43,44, 45,46,47,48,5,51,52,53,54,56,59,6,62 } {2,6,7,8,1,14,18,2,23,26,27,28,32,33,4,42, 49,55,57,58,61} {6,7,8,1,14,2,33,4,42,49,55,57,58,61} {4,5,9,12,16,19,22,24,25,3,36,46,52,56,6} {1,3,4,5,9,11,12,13,15,16,17,19,21,22,24, 25,29,3,31,34,35,36,37,38,39,41,43,44, 45,46,47,48,5,51,52,53,54, 56,59,6,62} f(c i, C j).87, f(c i, C j),. 22 {22,23,8,9,52,69,78,79,19,112} 52 {52,53,59,65,66,69,7,86} 52 1 {52,53,59,65,66,68,69,7,86,14,15} {3,7,14,16,33,4,48,61,65,11,17} {4,6,11,41,53,73,75,82,85,99,13,18} {1,5,1,17,24,42,94,15} {12,25,29,51,7,91} {18,21,28,57,63,66,71,77,88,96,97,114} {2,3,31,36,56,8,81,83,95,12} {47,5,54,68,74,84,89,111,115} {4,9,1,11,12,13,14,15,16,17,18,19,2,21,22, 23,24,25,26,27,28,33,34,35,36,37,38,39,4,41, 42,43,44,45,46,47, 48,49,5,51,54,55,56,57,58} {29,31,32,6,61,62,63,64,67,71,72,73,74,75,76, 77,78,79,8,81, 82,83,84,85,87,88,89,9,91,92, 93,94,95,96,97,98,99,1,11,12,13} {1,2,3,5,6,7,8,3} {52,53,59,65,66,68,69,7,86,14,15} 1 f(c i, C j) 1, f(c i, C j),. LMD (Local maximum degree) [18] CNM [26] GSB (Group similarity based algorithm) [8].,, GN [5] Zachary [27] [28] [29] [5]., [3]..

9 5 : , 4. (Precision) (Recall) (F1) (Normalized mutual information, NMI) [31]. 1) (Precision) (Precision). : P = L result L true L result (23), L result, L true. 2) (Recall) (Recall). : R = L result L true L true (24), L result, L true. 3) (F1) Precision Recall. Precision,,, Precision (Precision 1); Recall,,, Recall (Recall 1)., Precision Recall., F1 : F 1 = 2P R (25) P + R, P, R. 4) (NMI) (NMI). : I(A, B) = C A i=1 2 C A X i log C B i=1 j=1 ( Xi N ( Xij N X ij log X i X j ) + C B j=1 X j log ) ( X j N ) (26), A ; B ; C A ; C B ; X, X ij = i j (i A, j B, i j i j 1 ); X i X i ; X j X j. I(A, B) [, 1],,. 4.2 GN GN. 128, 4, 32. z in, z out, z in + z out = 16. z out, z out, ;,., z out.,,.,, GN. GN, ; GN,., GN, 2, 1.5., SICE Clauset-R. 6., SICE Clauset-R., Clauset-R,. SICE,,., SICE Clauset-R. 6, SICE F 1, SICE, Clauset-R. 4.3 Zachary Zachary, ,.,. (a) GN (a) GN benchmark I (b) GN (b) GN benchmark II

10 93 4 (c) GN (c) GN benchmark I (e) GN (e) GN benchmark I (d) GN (d) GN benchmark II (f) GN (f) GN benchmark II.,.,,.,. SICE ( 8)., 4. 3, SICE, Precision Recall F 1. Clauset-R LWP LMD Precision, Recall F 1,,,.,. 2 Table 2 SICE Zachary Comparison between SICE algorithm and other algorithms on the Zachary karate club network Fig. 6 6 SICE GN The experimental results of SICE algorithm on the GN benchmark,,. 7,,. 2 SICE Clauset-R LWP LMD., SICE. SICE. F 1 SICE Clauset-R LWP LMD : Clauset-R LWP LMD [18]. Table 3 3 SICE Comparison between SICE algorithm and other algorithms on the dolphins social network F 1 SICE Clauset-R LWP (a) I (, ) (a) Local community I mined by the algorithm (For any node, the results are stable.) 7 Fig. 7 (b) II (, ) (b) Local community II mined by the algorithm (For any node, the results are stable.) SICE Zachary The experimental results of SICE algorithm on 4.4 the Zachary karate club network 62, LMD : Clauset-R LWP LMD [18]. 4.5 Girvan Newman, ,,,. 12, 12., SICE, 12 ( 9).

11 5 : 931, 8, , {12, 25, 51, 6, 64, 7, 98}, {12, 25, 51, 7} {6, 64, 98}.,. 4 SICE Clauset-R LWP LMD. SICE. 4 Table 4 SICE Comparison between SICE algorithm and other algorithms on the American college football network F 1 SICE Clauset-R LWP LMD : Clauset-R LWP LMD [18]. (a) I (, ) (b) II (, ) (a) Local community I mined by the algorithm (For (b) Local community II mined by the algorithm (For any node, the results are stable.) any node, the results are stable.) 8 SICE Fig. 8 The experimental results of SICE algorithm on the dolphins social network Fig. 9 9 SICE 12 (, SICE ) Twelve local communities detected from the American college football network by SICE algorithm (Starting from any node in the local communities, the SICE algorithm can give a stable solution.)

12 (Amazon.com), ,.,,., SICE. 1, 4.,..,, 1 (a) 1 (d),, 1 (b) 1 (c).,, 1 (b) 1 (c)., SICE. 5, SICE Precision Recall F 1. 5 Table 5 SICE Comparison between SICE algorithm and other algorithms on the Krebs network of books on American politics F 1 SICE Clauset-R LWP LMD : Clauset-R LWP LMD [18]. 4.7,, , SICE, CNM GSB. NMI,. SICE : 1) ; 2), SICE, ; 3) 2),,., SICE. 6,, NMI.9878, 128, 276, 98, 2.,. SICE CNM NMI.9578, GSB NMI.9595, , 42, 2., SICE,.,,,,,. (a) I (, ) (a) Local community I mined by the algorithm (For any node, the results are stable.) (b) II (, ) (b) Local community II mined by the algorithm (For any node, the results are stable.)

13 5 : 933 Fig. 1 (c) III (, ) (c) Local community III mined by the algorithm (For any node, the results are stable.) 1 (c) IV (, ) (c) Local community IV mined by the algorithm (For any node, the results are stable.) SICE The experimental results of SICE algorithm on the Krebs network of books on American politics 6 Table 6 SICE Comparison between SICE algorithm and the global community detection algorithms on collaboration network in science of networks NMI / SICE CNM.9578 SICE GSB.9595 CNM GSB.9878 SICE / 2 CNM / 2 GSB / 2 5,. ( ),,.,,., k.,,,, SICE., : 1), SICE,. SICE. 2) SICE,,.,. SICE,,.,,.. G, SICE. References 1 Jin Di, Liu Jie, Yang Bo, He Dong-Xiao, Liu Da-You. Genetic algorithm with local search for community detection in large-scale complex networks. Acta Automatica Sinica, 211, 37(7): (,,,,.., 211, 37(7): ) 2 Panagiotakis C, Papadakis H, Grinias E, Komodakis N, Fragopoulou P, Tziritas G. Interactive image segmentation based on synthetic graph coordinates. Pattern Recognition, 213, 46(11): Hu D D, Ronhovde P, Nussinov Z. Replica inference approach to unsupervised multiscale image segmentation. Physical Review E, 212, 85(1): Zhang Z F, Li Q D, Zeng D, Gao H. User community discovery from multi-relational networks. Decision Support Systems, 213, 54(2): Girvan M, Newman M E J. Community structure in social and biological networks. Proceedings of National Academy of Sciences of the United States of America, 22, 99(12): Zhang Z Y. Community structure detection in complex networks with partial background information. Europhysics Letters, 213, 11(4): Yang Bo, Liu Jie, Liu Da-You. A random network ensemble model based generalized network community mining algorithm. Acta Automatica Sinica, 212, 38(5):

14 934 4 (,,.., 212, 38(5): ) 8 Yuan Chao, Chai Yi. Group similarity based algorithm for network community structure detection. Acta Physica Sinica, 212, 61(21): (,.., 212, 61(21): ) 9 Liu Xu, Yi Dong-Yun. Complex network community detection by local similarity. Acta Automatica Sinica, 211, 37(12): (,.., 211, 37(12): ) 1 Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 25, 435(743): Huang Fa-Liang, Xiao Nan-Feng. Discovering overlapping communities based on line graph and PSO. Acta Automatica Sinica, 211, 37(9): (,. PSO., 211, 37(9): ) 12 Bassett D S, Porter M A, Wymbs N F, Grafton S T, Carlson J M, Mucha P J. Robust detection of dynamic community structure in networks. Chaos, 213, 23(1): Chen Z Z, Hendrix W, Samatova N F. Community-based anomaly detection in evolutionary networks. Journal of Intelligent Information Systems, 212, 39(1): Clauset A. Finding local community structure in networks. Physical Review E, 25, 72(2): Bagrow J P, Bollt E M. Local method for detecting communities. Physical Review E, 25, 72(4): Luo F, Wang J Z, Promislow E. Exploring local community structures in large networks. Web Intelligence and Agent Systems, 28, 6(4): Chen J Y, Zaiane O R, Goebel R. Local community identification in social networks. In: Proceedings of the 29 International Conference on Advances in Social Network Analysis and Mining. Athens, Greek: IEEE, Chen Q, Wu T T, Fang M. Detecting local community structures in complex networks based on local degree central nodes. Physica A: Statistical Mechanics and Its Applications, 213, 392(3): Lü L Y, Zhou T. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and Its Applications, 211, 39(6): Salton G, McGill M J. Introduction to Modern Information Retrieval. New York: McGraw-Hill, Yuan C, Chai Y, Wei S B. Feature analysis and modeling of the network community structure. Communications in Theoretical Physics, 212, 58(4): Katz L. A new status index derived from sociometric analysis. Psychometrika, 1953, 18(1): Brin S, Page L. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 1998, 3(1 7): Lü L Y, Jin C H, Zhou T. Similarity index based on local paths for link prediction of complex networks. Physical Review E, 29, 8(4): Liu W P, Lü L Y. Link prediction based on local random walk. Europhysics Letters, 21, 89(5): Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E, 24, 7(6): Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 1977, 33(4): Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 23, 54(4): Newman M E J. Modularity and community structure in networks. Proceedings of National Academy of Sciences of the United States of America, 26, 13(23): Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 26, 74(3): Strehl A, Ghosh J. Cluster ensembles a knowledge reuse framework for combining multiple partitions. Journal on Machine Learning Research, 22, 3: ,. yuan home@163.com (YUAN Chao Ph. D. candidate at the School of Automation, Chongqing University. His research interest covers complex network theory and data mining.).,.. chaiyi@cqu.edu.cn (CHAI Yi Professor at the School of Automation, Chongqing University. His research interest covers system optimization and intelligent control, and fault diagnosis. Corresponding author of this paper.)

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier 36 7 Vol. 36, No. 7 2010 7 ACTA AUTOMATICA SINICA July, 2010 1, 2 1, 2, 3 1, 2,,,,,,, DOI,,, 10.3724/SP.J.1004.2010.00923 Distributed Simulation System Hierarchical Design Model Based on Quotient Space