- 微博 QQ QQ空间 贴吧
1 .Peer-to-Peer and Social Networks Power law graphs
2 .Random vs. Power-law Graphs The degree distribution in of the webpages in the World Wide Web follows a power-law Binomial distribution
3 .Random vs. Power-Law networks
4 .Example: Airline Routes Think of how new routes are added to an existing network
5 .Examples of Power law distribution Also known as scale-free graph . Other examples are -- Airport network -- Income and number of people with that income -- Magnitude and number of earthquakes of that magnitude -- Population and number of cities with that population
6 .Preferential attachment New node Existing network A new node connects with an existing node with a probability proportional to its degree . The sum of the node degrees = 8 This leads to a power-law distribution ( Barabási & Albert) Also known as “ Rich gets richer ” policy
7 .Preferential attachment Barabási and Albert showed that when large networks are formed by the rules of preferential attachment , the resulting graph shows a power-law distribution of the node degrees. We will derive it in the class, so follow the lecture.
8 .Preferential attachment The probability that the new node connects with an existing node = Since and so Degree of node = At t = 0, there are no nodes. At t = 1, one node appears. Thereafter, each time unit, a new node is added
9 .Preferential attachment = number of nodes with degree k after time step t
10 .Preferential attachment is then fraction of nodes with degree k at time t
11 .Preferential attachment As Call it
12 .Preferential attachment is of the order of * Before time step (t+1), the new node is the only node with degree 0, and its degree will change to 1 *
13 .Other properties of power law graphs Graphs following a power-law distribution have a small diameter ( n = number of nodes). The clustering coefficient decreases as the node degree increases (power law again) Graphs following a power-law distribution tend to be highly resilient to random edge removal , but quite vulnerable to targeted attacks on the hubs.