复旦大学：《网络科学导论 Introduction to Network Science》教学课件_5- NW+Searching+Pagerank

Network science An English introductory course for undergraduate students Lecturer: Dr. Cong LI ee@ Fudan University Adaptive Networks and Control Lab

Network Science Lecturer: Dr. Cong LI EE @ Fudan University —— An English introductory course for undergraduate students Adaptive Networks and Control Lab

The Newman -Watts small-world model a) WS model re wiring of links b)NW model b addition of links

The Newman-Watts small-world model a) WS model b) NW model

The algorithm description of the UModel Starting from a regular lattice Randomly add one edge between a pair of two nodes with probability p On average(Kp)edges are added to a node Stop when the sufficient edges are newly added rewiring of links addition of links

The algorithm description of the NW model • Starting from a regular lattice • Randomly add one edge between a pair of two nodes with probability p • On average (Kp) edges are added to a node • Stop when the sufficient edges are newly added

Mark e. newman OXTORD aul Dirac Collegiate Professor of Networks An Introduction Physics M. E J. Newman Univ of michigan

Mark E.J. Newman • Paul Dirac Collegiate Professor of Physics • Univ. of Michigan

Question any difference between the ws model and the nw model? rewiring of links addition of links

Question • Any difference between the WS model and the NW model?

Why the nw model?年 Recall: the ws model's drawbacks 1)Isolation possibility (why?) 2)Difficult for mathematical analysis Advantage of the nw model 1)No isolation clusters (why?) 2) Easy for mathematical analysis 3) Equivalent to the ws model with O<p<<l

Why the NW model? • Recall: the WS model’s drawbacks: 1) Isolation possibility (why?) 2) Difficult for mathematical analysis • Advantage of the NW model 1) No isolation clusters (why?) 2) Easy for mathematical analysis 3) Equivalent to the WS model with 0<p<<1

Recall: Watts-Strogatz Model Regul Small-world Random p=1 Increasing randomness 0.8 C(p)/C(p) D L(p)/L(O) ⊥⊥⊥⊥L 0.0001 0.001 C(p): clustering coeff. L(p): average path length (Watts and Strogatz, Nature 393, 440(1998))

Recall: Watts-Strogatz Model C(p) : clustering coeff. L(p) : average path length (Watts and Strogatz, Nature 393, 440 (1998))

C nw.L nw. degree dist Example: Degree distribution N-1[ Kp R-K kp N-1-R+K P(k)= k-K/N-1 N How about the C nw? rewiring of links additron of tinks

C_nw, L_nw, Degree Dist. Example: Degree distribution How about the C_nw?

Recall: Criticisms and doubts ·J. Kleinfeld: Six Degrees of separation an urban myth? T Berman Six Degrees of separation fact or Friction M. Blastland other? How well are you connected ach Could we really all be connected to ea How to solve the doubts?

Recall: Criticisms and Doubts • J. Kleinfeld: Six Degrees of Separation: an urban myth? • T. Berman: Six Degrees of Separation: Fact or Friction? • M. Blastland: Could we really all be connected to each other? How well are you connected? …… How to solve the doubts?

A 500th person to the riaht of A Your Friends Friends Friends Only have local information to reach ur Friends Friend the(global)target Your Friends Given the network is You reachable in a definite (not many) steps The shortest path

Only have local information to reach the (global) target! Given the network is reachable in a definite (not many) steps. The shortest path