- - 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 http://arxiv.org GRIPS 3
Network Science 1736 1960 Random Graph 1998 Watts 1999 Barabasi 1967 Small World GRIPS 4
GRIPS 5
GRIPS 6
What is Complex Networks? Complex Networks GRIPS 7
L. Euler (1707-1783) Konigsburg Problem (1736) ( ) GRIPS 8
V E 2 V(G),E(G), (G) -> G(V,E) GRIPS 9
Random Networks P. Erdos (1913-1996) Erdos Number Random Graph Erdos-Renyi Model GRIPS 10
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
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
Network Random Network Regular Network 20 GRIPS 13
実際のネットワーク World Wide Web Erdos number Protein network Telephone network Coauthor network Model? ER Random Network Model は妥当性にかける 知的財産マネジメント研究会 GRIPS 14
Small World acquaintance acquaintance It s a Small World! GRIPS 15
Stanley Milgram S. Milgram (1933-1984) Yale University social psychology Milgram Small World J. Kleinfeld, The Small world problem, Society, 39(2), pp.61-66, 2002 GRIPS 16
Small World S. Milgram: The Small-World Problem, PsychologyToday, Vol. 1, pp. 61 67 (1967) acquaintance acquaintance Q1. X Z Y It s a Small World! Q2. X Z a,b,,y GRIPS 17
Small World Source Nebraska Target Name : Bob Business: Trader Address : Boston 5.5 steps => Q1. X Z Y GRIPS 18
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
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. 440 442 (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
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. 286, pp. 509 512 (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
Scale Free Networks degree distribution:p(k) k- Hub Node =>Low Diameter GRIPS 23
Preferential Attachment Growing Process Preferential Attachment k t i = ki k j j GRIPS 24
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
Scale Free Networks Networks Complex Networks Regular Networks Random Networks Small World Networks GRIPS 26
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, pp167-256 (2003) GRIPS 27
(characteristic path length) (centrality) (degree distribution) (clustering coefficient) (degree correlation) (spectrum) (modularity),etc GRIPS 28
E. Ravasz and A. L. Barabasi, Physical Review E, 67, 026112, 2003, Hierarchical organization in complex networks GRIPS 29
GRIPS 30
GRIPS 31
Navigation GRIPS 32
GRIPS 33
( 7 ) ( ) 25 21 5 GRIPS 34
GRIPS 35
GRIPS 36
GRIPS 37
1. 2. 3. 5. 6. 7. 8. 9. 10. ID, ID GRIPS 38
2001 2005 ID ID GRIPS 39
Size Rank - betweenness centrality clustering GRIPS 40
Rank-Size 2nd Zipf GRIPS 41
a. b. GRIPS 42
degree-clustering coefficient a. 2001 b. 2002 c. 2003 d. 2004 e. 2005 GRIPS 43
a. 2001 b. 2002 c. 2002 d. 2004 e. 2005 GRIPS 44
Betweenness Centrality Clustering Boost Graph Library Brandes beetweenness centrality Ulrik Brande, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology 25 (2):163-177, 2001. bc_clustering.hpp edge 1 remove edge remove Newman Modularity: GRIPS 45
Newman Modularity Betweenness Shortest Path Betweenness 2004 Newman Modularity GRIPS 46
(2004) GRIPS 47
GRIPS 48
(2003) GRIPS 49
GRIPS 50
Scale Free + 10% GRIPS 51
( ), 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 http://www.nd.edu/~alb/ http://www-personal.umich.edu/~mejn/, http://www.santafe.edu/~mark/ GRIPS 52
Pajek, http://vlado.fmf.uni-lj.si/pub/networks/pajek/ Otter, http://www.caida.org/tools/visualization/otter/ GraphViz, http://www.graphviz.org/ Large Graph Layout, http://apropos.icmb.utexas.edu/lgl/ Boost Graph Library, http://www.boost.org/libs/graph/doc/ GRIPS 53
Thank you GRIPS 54