untitled

Size: px

Start display at page:

Download "untitled"

ただきよかやぬま
5 years ago
Views:

1 - - GRIPS 1

2 traceroute IP Autonomous System Level GRIPS 2

3 Network Science GRIPS 3

4 Network Science Random Graph 1998 Watts 1999 Barabasi 1967 Small World GRIPS 4

5 GRIPS 5

6 GRIPS 6

7 What is Complex Networks? Complex Networks GRIPS 7

8 L. Euler ( ) Konigsburg Problem (1736) ( ) GRIPS 8

9 V E 2 V(G),E(G), (G) -> G(V,E) GRIPS 9

10 Random Networks P. Erdos ( ) Erdos Number Random Graph Erdos-Renyi Model GRIPS 10

11 ER Random Graph Model N 1 N nodes, M edges : G(N,M) N(N-1)/2 edges Probability p : G(N, p) M =pn GRIPS 11

12 ER Random Graph Model G(N, p) p=n -1 p=log(n)/n Degree Distribution : P(k) P(k)= N-1 C k p k (1-p) N-1-k -> exp(- ) k /k! (N->, p->0, pn-> ) Diameter : d d=log(n)/log(pn) log(n)/log(<k>) N 1 GRIPS 12

13 Network Random Network Regular Network 20 GRIPS 13

14 実際のネットワーク World Wide Web Erdos number Protein network Telephone network Coauthor network Model? ER Random Network Model は妥当性にかける知的財産マネジメント研究会 GRIPS 14

15 Small World acquaintance acquaintance It s a Small World! GRIPS 15

16 Stanley Milgram S. Milgram ( ) Yale University social psychology Milgram Small World J. Kleinfeld, The Small world problem, Society, 39(2), pp.61-66, 2002 GRIPS 16

17 Small World S. Milgram: The Small-World Problem, PsychologyToday, Vol. 1, pp (1967) acquaintance acquaintance Q1. X Z Y It s a Small World! Q2. X Z a,b,,y GRIPS 17

18 Small World Source Nebraska Target Name : Bob Business: Trader Address : Boston 5.5 steps => Q1. X Z Y GRIPS 18

19 ER Random Graph Model G(N, p) N 1 Diameter : d d=log(n)/log(pn) log(n)/log(<k>) Small World X Z Y ER X Z Y p(<<1) X Z GRIPS 19

20 Small World Networks Duncan J. Watts Columbia University D. J. Watts and S. H. Strogatz: Collective dynamics of small-world networks, Nature, Vol. 393, No. 4, pp (1998) Clustering coefficient: C i = E( Γ C k i i ), C Small World: 1. Low Diameter 2. High Clustering 2 = 1 N N C i= 1 i X GRIPS 20

21 Random Rewiring Small World Small World: Low Diameter High Clustered Low Diameter <=Shortcut Path, Long Range Contact GRIPS 21

Scale Free Networks Albert-László Barabási University of Notre Dame A. L. Barabasi and R. Albert: Emergence of Scaling in Random Networks, Science, Vol.

22 Scale Free Networks Albert-László Barabási University of Notre Dame A. L. Barabasi and R. Albert: Emergence of Scaling in Random Networks, Science, Vol. 286, pp (1999) WWW Hyperlink (Pages 325,729 Links 1,469,680) degree distribution:p(k) k - Power Low = Scale Free diameter :d 11.2 => New class! GRIPS 22

23 Scale Free Networks degree distribution:p(k) k- Hub Node =>Low Diameter GRIPS 23

24 Preferential Attachment Growing Process Preferential Attachment k t i = ki k j j GRIPS 24

25 Small World Networks or Scale Free Networks ER Random Network Low Diameter Small World Network Low Diameter High Clustered (Clustering Coefficient) Scale Free Network Low Diameter Hub Node (Power Low Degree Distribution) def1. Small World = Low Diameter ER Random Network, Small World Network, Scale Free Network def2. Small World = Low Diameter and High Clustered Small World Network GRIPS 25

26 Scale Free Networks Networks Complex Networks Regular Networks Random Networks Small World Networks GRIPS 26

27 Complex Networks Mark E. J. Newman Santa Fe Institute Complex Systems Self-Organizing Systems M. E. J. Newman: The Structure and Function of Complex Networks, SIAM Review, vol45, pp (2003) GRIPS 27

28 (characteristic path length) (centrality) (degree distribution) (clustering coefficient) (degree correlation) (spectrum) (modularity),etc GRIPS 28

29 E. Ravasz and A. L. Barabasi, Physical Review E, 67, , 2003, Hierarchical organization in complex networks GRIPS 29

30 GRIPS 30

31 GRIPS 31

32 Navigation GRIPS 32

33 GRIPS 33

34 ( 7 ) ( ) GRIPS 34

35 GRIPS 35

36 GRIPS 36

37 GRIPS 37

38 ID, ID GRIPS 38

39 ID ID GRIPS 39

40 Size Rank - betweenness centrality clustering GRIPS 40

41 Rank-Size 2nd Zipf GRIPS 41

42 a. b. GRIPS 42

43 degree-clustering coefficient a b c d e GRIPS 43

44 a b c d e GRIPS 44

45 Betweenness Centrality Clustering Boost Graph Library Brandes beetweenness centrality Ulrik Brande, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology 25 (2): , bc_clustering.hpp edge 1 remove edge remove Newman Modularity: GRIPS 45

46 Newman Modularity Betweenness Shortest Path Betweenness 2004 Newman Modularity GRIPS 46

47 (2004) GRIPS 47

48 GRIPS 48

49 (2003) GRIPS 49

50 GRIPS 50

51 Scale Free + 10% GRIPS 51

52 ( ), Duncan J. Watts ( ), ( ), ( ) ( ), ( ) Six Degrees: The Science of a Connected Age Duncan J. Watts ( ) Linked: The New Science of Networks Albert-Laszlo Barabasi ( ) ( ), Duncan J. Watts ( ), ( ), ( ), ( ) Small Worlds: The Dynamics of Networks Between Order and Randomness Duncan J. Watts ( ) ( ), ( ) The Structure And Dynamics of Networks Duncan J. Watts ( ), Mark Newman ( ) Web Site GRIPS 52

53 Pajek, Otter, GraphViz, Large Graph Layout, Boost Graph Library, GRIPS 53

54 Thank you GRIPS 54

1 2 : etc = x(t + 1) = 1 ax(t) 2 + y(t) y(t + 1) = bx(t) x y 2006 p.2/58

2006 338 8570 255 Tel : 048 858 3577, Fax : 048 858 3716 Email : tohru@ics.saitama-u.ac.jp URL : http://www.nls.ics.saitama-u.ac.jp/ tohru 2006 p.1/58 1 2 : etc = x(t + 1) = 1 ax(t) 2 + y(t) y(t + 1) =