IPSJ SIG Technical Report Vol.2012-MPS-88 No /5/17 1,a) 1 Network Immunization via Community Structure based Node Representation Tetsuya Yoshida

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2012-MPS-88 No /5/17 1,a) 1 Network Immunization via Community Structure based Node Representation Tetsuya Yoshida"

たかよしこうだ
5 years ago
Views:

1 1,a) 1 Network Immunization via Community tructure based Node Reresentation Tetsuya Yoshida 1,a) Yuu Yamada 1 Abstract: We roose an aroach for immunization of networks via modularity based node reresentation. ince eidemics (e.g, virus) are roagated among grous of nodes (communities) in a network, network immunization has often been conducted by removing nodes with large score (e.g., centrality) so that the major art of the network can be rotected from the contamination. ince communities are often interwoven through intermediating nodes, we roose to identify such nodes based on the community structure of a network and remove them for immunization. By regarding the community structure in terms of nodes, we construct a vector reresentation of each node based on a quality measure of communities for node artitioning. Preliminary exeriments are conducted over synthetic and real-world networks, and comared with other centrality based immunization strategies. Keywords: modularity, node rofile, eigenma 1. 1 Graduate chool of Information cience and Technology, Hokkaido University, aoro, Hokkaido , Jaan a) yoshida@meme.hokudai.ac.j 1

2.1 A ij A ij tr A A T 1 n 1 n a diag(a) *1 G n m [7] G A {0, 1} n n i

2 [6], [9], [5] A ij A ij tr A A T 1 n 1 n a diag(a) *1 G n m [7] G A {0, 1} n n i j A ij = 1 A ij = 0 G A k = A1 n k i i 2.2 LCC 1) *1 diag(a) i a i 1 node removal LCC = 7 Fig. 1 Network immunization 2.3 [3], [7] G G G Google [8] [8] [4] [2] [5] [6] B = A P (1) 2

3 P ij = k i k j /2m k B (1) B q border B UΛU T (2) U = [u 1, u 2,..., u q ] u j Λ 2 [6] X = UΛ 1/2 (3) X i i x i R q 3 i [6] *2 2 Fig. 2 Community nodes :center :midde :fringe Node tyes in a synthetic network. cc(x i ) = x T i x i (4) x i = 0 q (5) i=1 1 R q a) b) a) q b) 2 5 *2 [6] x i x T i x i L 2 x i 3 c=2 c=3 Fig. 3 Distribution of node vectors (uer: c=2, lower: c=3) c 2, 3 q θ 3 ( ) a) θ 3

4 b) (i, j) θ ij θ ij θ ij D = diag( x 1,..., x n ) (6) X 1 = D 1 X (7) Θ = cos 1 (X 1 X T 1 ) (8) { 1 (Θij < θ) f(θ ij, θ) = (9) 0 (otherwise) ivd(x i ) = 1 n j f(θ ij, θ) (10) 6 D ( x 1,..., x n ) T θ 10 ivd( ) 3 X D 1 7 X 1 L 2 X f θ θ ij 3.2) θ 10 ivd( ) IVD IVD 3 IVD 1 Table 1 ynthetic networks ( ) CL CL CL Table 2 Real-world networks karate dolhins olbooks [6] IVD ccivd(x i ) = cc(x i ) ivd(x i ) (11) 11 CCIVD ( 1) ( 2) Barabási-Albert BA [1] * CL CL 2 CL 3 *4 1) 10 2 GML (grah marku language) LCC [4] n G LCC #remaining nodes =, = LCC n n (12) *3 BA 4 *4 CL 2 CL 3 2, 3 4

5 LCC LCC D B EVC CC ModC [4] q θ : : ModC ModC fastgeedy [5] , LCC x D + B EVC CC ModC IVD CCIVD R 4 IVD CL IVD LCC CCIVD IVD ModC > , IVD CCIVD B CCIVD B CCIVD IVD ModC LCC 5. q θ (No ) [1] Barabási, A.-L. and Albert, R.: Emergence of scaling in random networks, cience, Vol. 286, (1999). [2] Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z. and Wagner, D.: On Modularity Clustering, IEEE Transactions on Knowledge and Data Engineering, Vol. 20, No. 2, (2008). [3] Freeman, L. C.: Centrality in ocial Networks Concetual Clarification, ocial Networks, (1979). [4] Masuda, N.: Immunization of networks with community structure, New Journal of Physics, Vol. 11, (2011). [5] Clauset, A., Newman, M. E. J. and Moore, C.: Finding community structure in very large networks, Physical Review E, Vol. 70, No. 6, (2004). [6] Newman, M.: Finding community structure using the eigenvectors of matrices, Physical Review E, Vol. 76, No. 3, (2006). [7] Newman, M.: Networks: An Introduction, Oxford University Press (2010). [8] Restreo, J. G., Ott, E. and Hunt, B. R.: Characterizing the Dynamical Imortance of Network Nodes and Links, Physical Review Letters, Vol. 97, (2006). [9] : Vol. 5, No. 1, (2012). 5

6 D B EVC CC IVD CCIVD CL_2_5_1 CL_2 CL_3 RD RB REVC RCC ModC RIVD RCCIVD CL_2_5_1 4 Fig. 4 CL_2 CL_3, Results of synthetic networks (uer: single, lower: recalc) D B EVC CC IVD CCIVD karate dolhins olbooks RD RB REVC RCC ModC RIVD RCCIVD karate 5 Fig. 5 dolhins olbooks, Results of real-world networks (uer: single, lower: recalc) 6

untitled

untitled - - GRIPS 1 traceroute IP Autonomous System Level http://opte.org/ GRIPS 2 Network Science http://opte.org http://research.lumeta.com/ches/map http://www.caida.org/home http://www.imdb.com http://citeseer.ist.psu.edu