IBM HRL template

Size: px

Start display at page:

Download "IBM HRL template"

制于
4 years ago
Views:

1 2007 年暑期数模培训复杂网络模型石柯华中科技大学计算机学院

2 What is a network? Network: a collection of entities that are interconnected with links. people that are friends computers that are interconnected web pages that point to each other proteins that interact 2 keshi@mail.hust.edu.cn

century, with Leonhard Euler The problem of Königsberg bridges

3 Graphs In mathematics, networks are called graphs, the entities are nodes, and the links are edges Graph theory starts in the 18th century, with Leonhard Euler The problem of Königsberg bridges Since then graphs have been studied extensively. 3 keshi@mail.hust.edu.cn

4 Networks in the past Graphs have been used in the past to model existing networks (e.g., networks of highways, social networks) usually these networks were small network can be studied visual inspection can reveal a lot of information 4 keshi@mail.hust.edu.cn

5 Networks now More and larger networks appear Products of technological advancement e.g., Internet, Web Result of our ability to collect more, better, and more complex data e.g., gene regulatory networks Networks of thousands, millions, or billions of nodes impossible to visualize 5 keshi@mail.hust.edu.cn

6 Example 1: Internet 6 keshi@mail.hust.edu.cn

7 Example 2: World Wide Web 7 keshi@mail.hust.edu.cn

8 Example 3: http 8 keshi@mail.hust.edu.cn

9 Example 4: Tele network 9 keshi@mail.hust.edu.cn

10 Example 5: American Aviation network 10

11 Example 6: News Net 11

12 Example 7: Biological network 12

13 Example 8: Social Network 13

14 Complex Network Goal: What are the statistics of real life networks? Can we explain how the networks were generated? 14

15 Example 1: Gossip protocol 15

16 Example 1: Gossip protocol 16

17 Example 1: Gossip protocol 17

18 Example 1: Gossip protocol 18

19 Example 1: Gossip protocol 19

20 Example 1: Gossip protocol Anti-entropy 20

21 Example 1: Gossip protocol Network Overhead Load balance 21

22 Example 2: The fragileness of Internet 22

23 Complex Network Network Topology Models: Random Network Small World Network Scale-Free Network 23

24 Network Topology Graph G=(V,E) V = set of vertices E = set of edges undirected graph E={(1,2),(1,3),(2,3),(3,4),(4,5)} keshi@mail.hust.edu.cn

25 Network Topology Graph G=(V,E) V = set of vertices E = set of edges directed graph E={ 1,2, 2,1 1,3, 3,2, 3,4, 4,5 } keshi@mail.hust.edu.cn

26 Undirected graph degree d(i) of node i number of edges incident on node i 2 degree sequence [d(i),d(2),d(3),d(4),d(5)] [2,2,2,1,1] 1 3 degree distribution [(1,2),(2,3)] keshi@mail.hust.edu.cn

27 Directed Graph in-degree d in (i) of node i number of edges pointing to node i 2 out-degree d out (i) of node i number of edges leaving node i 1 3 in-degree sequence [1,2,1,1,1] out-degree sequence [2,1,2,1,0] keshi@mail.hust.edu.cn

28 Paths Path from node i to node j: a sequence of edges (directed or undirected from node i to node j) path length: number of edges on the path nodes i and j are connected cycle: a path that starts and ends at the same node keshi@mail.hust.edu.cn 5 4

29 Shortest Paths Shortest Path from node i to node j also known as BFS path, or geodesic path keshi@mail.hust.edu.cn 5 4

30 Diameter The longest shortest path in the graph keshi@mail.hust.edu.cn 5 4

31 Model Random Network - Erdös and Rényi (1960) Dominant in the past 40 Recent Discoveries: Small World Phenomena (Watts and Strogatz, Nature, 1998) Scale-Free (Barabási and Albert, Science, 1999) 31 keshi@mail.hust.edu.cn

32 Random network Characteristics: Degree Distribution Poisson The degree of a node is close to the average value. 32 keshi@mail.hust.edu.cn

33 Small World Network Characteristics: (Similar to ER Random Graphs) Degree Distribution Poisson 33

34 Scale-free Network An initial network with M 0 nodes (i) Add new nodes p, With probability a new node is added into the network (ii) Add new links The new node has m ( ) new links to the already existing nodes in the network with probability ( k i ) = ki + 1 ( kl + 1) l m m 0 34 keshi@mail.hust.edu.cn

Scale-free Network Characteristics: Degree Distribution Power law The relative commonness of vertices with a degree that greatly exceeds the average The

35 Scale-free Network Characteristics: Degree Distribution Power law The relative commonness of vertices with a degree that greatly exceeds the average The highest-degree nodes are often called "hubs", and are thought to serve specific purposes in their networks, although this depends greatly on the domain. 35 keshi@mail.hust.edu.cn

36 Basic Concepts Average Distance Clustering Coefficient Degree and Degree Distribution 36

37 Average Distance Distance between node n and m d(n,m) = the length of Shortest Path from node n to node m Diameter D = max{d(n,m)} Average Distance L = Average{d(n,m)} In most complex networks, L is small L small world phenomena 37 keshi@mail.hust.edu.cn

38 Example:. L = d 1 ij i> j d 12 = 1 1 N( N 1) 2 d d = 1 = = 2 = 1 = 2 Total = 16 Average: L = 16 / 10 = 1.6 d d d d d 15 d 25 d 35 = 1 = 2 45 = 2 = 3 38 keshi@mail.hust.edu.cn

39 Clustering coefficient Measures the density of triangles (local clusters) in the graph triangles centered at node i C i = triples centered at node i 0 < C < 1 (2) C = 1 n C i In most complex network, C is large small world phenomena 39 keshi@mail.hust.edu.cn

40 Example: C ( i) = number of complete triangles with corner i number of all triangular graphs with corner i Node-1 has 1 complete triangle and 3 triangular graphs, so C(1) = 1/3 Node-2 has 1 complete triangle and 3 triangular graphs, so C(2) = 1/3 Node-3 has 1 complete triangle and 1 triangular graph, so C(3) = 1 Node-4 has 0 complete triangles, so C(4) = 0 Node-5 has 0 complete triangles, so C(5) = 0 Average C = (1/3+1/ ) / 5 = 1/3 40 keshi@mail.hust.edu.cn

41 Degree and Degree Distribution Degree of node n k(n) = number of edges incident on node n Average Degree <k> Degree Distribution frequency f k = fraction of nodes with degree k = probability of a randomly selected node to have degree k f k k degree 41 keshi@mail.hust.edu.cn

42 Full Connected Network L = 1 C = 1 Degree Distribution: delta 函数 For example: K=0 K=100 K= keshi@mail.hust.edu.cn

43 Nearest neighbor Network L ring C = N ( N ) keshi@mail.hust.edu.cn

44 Star Network Lstar 2 ( N ) C star = 0 44 keshi@mail.hust.edu.cn

45 Random Network k ER = p( N 1) pn P( k) k μ μ = e k! Poisson C = p = k / N <<1 45 keshi@mail.hust.edu.cn

46 46 Random Network μ μ = e k k P k! ) ( k N k p p k N N k P = ) (1 ) ( k N k N N k N k N N k P = μ μ μ 1 )!!(! ) ( 1! 1 1 1! 1) ( 1) ( lim ) ( lim ) ( = + = = μ μ μ μ μ μ e k N N k N k N N N N k P k P k k N k k N N L Np = μ

47 Degree Distribution Deterministic Network: P(k) ~Delta 分布 Most real life network: P(k) ~ k^{-γ} (Power law) scale-free Random network: P(k) ~ Poisson (Deterministic) delta k^{-γ} Poisson (random) 47 keshi@mail.hust.edu.cn

48 Real example World Wide Web Internet 48

49 1. World Wide Web Average Distance L = 14 Diameter = 19 You can reach any webpage via at most 19 clicks Degree Dsitribution Out-degree degree: P(k) ~ k^{-γ}, γ = 2.38~2.72 in-degree degree: P(k) ~ k^{ -γ}, γ = keshi@mail.hust.edu.cn

50 2. Internet Average Distance L = 4.0 ER Random Network: L = 10 (too large) Internet is a small world network Degree Distribution Power law: P(k) ~ k^{-γ}, γ = 2.2 scale-free Clustering coefficient C = 0.3 ER Random Network : C = (too small) 50 keshi@mail.hust.edu.cn

Small world experiment Milgram s small world experiment Letters were handed out to people in Nebraska to be sent to a target in Boston People were instructed to pass on the

51 Small world experiment Milgram s small world experiment Letters were handed out to people in Nebraska to be sent to a target in Boston People were instructed to pass on the letters to someone they knew on first-name basis The letters that reached the destination followed paths of length around 6 Six degrees of separation 51 keshi@mail.hust.edu.cn

52 Small world experiment The game "Six Degrees of Kevin Bacon Kevin Bacon famous American actor The goal is to link any actor to Kevin Bacon through no more than six connections, where two actors are connected if they have appeared in a movie together Average value is 周星驰 s value id keshi@mail.hust.edu.cn

53 Application Understand better how some complex systems work if we can understand the patterns in their networks e.g. proteins in biological systems Spread of viruses better studied on more realistic networks, better preventative methods? Search Algorithms how did Milgram s letters reach their destination? Why did 80% fail to arrive? 53 keshi@mail.hust.edu.cn

54 Applications: Network Resilience Resilience of Networks, if remove vertices (hardware failure, virus attack) when does a network split into small disconnected pieces? For random vertex removal: Random Network fails when 2E/N =<k>=1 A Scale Free γ <3 never fails Remove biggest hubs first: Scale Free Networks fail very quickly Build a scale free network but make sure the hubs have the best protection! 54 keshi@mail.hust.edu.cn

55 Application: Search in P2P network Standard systems: Client/Server structured P2P systems: Clients help one-another out 55

56 Application: Search in P2P network Napster Having obtained a top-level page listing peers with copies of music or other content desired, a client can download the files directly from the peer Got Sting? Can I have a copy? no problem, dude Where can I find a copy of Sting:Fields try of Barley? or Data center builds the pages users see when they access Napster 56 keshi@mail.hust.edu.cn

57 Gnutella I m looking for Sting:Fields 57 keshi@mail.hust.edu.cn

58 Gnutella TTL determines how far the search will flood in the network. Here, TTL of 2 reached 10 nodes 58 keshi@mail.hust.edu.cn

59 Gnutella Nodes with a copy send Download back a file from the first message offering it. node This that offers a copy. basically is a URL for the Hopefully file this is a nearby source with good connectivity 59 keshi@mail.hust.edu.cn

60 Improvement: Random walk: a well-known technique, which forwards a query message to a randomly chosen neighbor at each step until the object is found. We call this message a walker. With more walkers, we can find objects faster, but also generate more loads. Since multiple-walker random walks require a mechanism to terminate the walks, two methods are used: TTL: means that, similar to flooding, each random walk terminates after a certain number of hops. Checking : means that a walker periodically checks with the original requester before walking to the next node. 60 keshi@mail.hust.edu.cn

61 61

096STUT DOC

096STUT DOC i YouTube was established in 2005 until now only more than 3 years. Although it was established just more than 3 years, it has already become the one of multitudinous video shares website that most people