SDSC,skitter(July1998)

《SDSC,skitter(July1998)》由会员分享，可在线阅读，更多相关《SDSC,skitter(July1998)（30页珍藏版）》请在装配图网上搜索。

1、SDSC,skitter(July 1998)A random graph model for massive graphsWilliam AielloFan Chung GrahamLincoln Lu1What are the properties of the?Is the World Wide Web connected?If not,how large is the largest component,the second largest component,etc.?Can these questions be answered exactly?Probably not!The c

2、hanging constantly.Even a“snapshot”of the Web is too large to handle.2An important observation has a power law degree distribution Broder,Kleinberg,Kumar,Raghavan,Rajagopalan aaand Tomkins,1999.Barabsi,Albert and Jeung,1999.Discovered by several groups independently3Power Law GraphsPower law decay o

3、f the degree distribution:The number of vertices of degree d is proportional to 1/db where b is some constant 0.Let y(d)be the number of nodes of degree d y 1/dblog y=a blog d45Power Law Graphs Robust and UbiquitousInternet Router GraphPower Grid GraphPhone Call GraphScientific Citation GraphCo-Star

4、s Graph(e.g.the six degrees of Kevin Bacon)The power in the power law stays constant even as the graphs grow and change.6What does a massive graph look like?sparseclustered small diameterHard to describe!Harder to analyze!prohibitively large dynamically changing incomplete information7Dont worry abo

5、ut exact answersUse Models InsteadData sets too large and dynamic for exact analysis occur in many other areas:the physical,biological,and social sciences and engineering.Progress in understanding often made by iterative interplay between modeling and experimental data,where both often have a random

6、 or statistical nature.8Modeling Power Law GraphsDevelop model of Power Law GraphsAnalyze properties of model,e.g.,connected component structureCompare results to experimental dataOur model will be of variant of an important model in graph theory called Random Graphs9Random GraphsG(n,e)n nodes all g

7、raphs with e edges have uniform probabilityH(3,1)prob 1/3H(3,2)prob 1/310Random GraphsG(n,p)n nodes each edge is included with probability p expected degree=p(n-1)(1-p)3p3p(1-p)2 p2(1-p)11Paul Erdos and A.Renyi,On the evolution of random graphsMagyar Tud.Akad.Mat.Kut.Int.Kozl.5(1960)17-61./12The evo

8、lution of random graphs G(n,p)0cycles of any size one giant component,i.e.,size(n),other components are o(n)-sized treeslog n/nconnected and almost regular,expected degree w log n1/n pdisjoint union of treesthe double jumpsc/n,c1 G(n,p)is connectedw log n/n,wc/n,0c113Random Graphs and Degree Distrib

9、utionsH(n,s)n nodess=(y(1),y(2),y(n-1),where y(i)is the number of nodes with degree i.all graphs with degree distribution s have uniform probability14Random Graphs and Degree DistributionsH(4,s),s=(1,2,1).All have prob.1/1215Random Power Law GraphsA power law degree distribution can be described by

10、two parameters:,y=e/x log y=log xwhere y is the number of nodes of degree xA new random graph model:P(,).P(a,b)assigns uniform probability to all graphs with degree distribution y=e/x16A few facts about P(,):The maximum degree is e/.The number of vertices n is n=e/x z()e,1 x e/,where z()=S1/x the Re

11、imann Zeta function.The number of edges E is E=1/2 e/x-1 z(-1)e/2 The density E/n=z(-1)/z()is controlled by.17Facts on P(,):a root of (-2)=2(-1)The second largest components are of size O(log n).For any x,2xO(log n),there is a component of size x.smaller components are of size O(log n/log log n).For

12、 any x,2x add a new vertex with a self-loop.“heads”-add a new edge between the existing set of nodes:Select a vertex u with probability proportional to the the degree of u,i.e.,Pr u chosen =deg(u)/2|E|.Independently select vertex v with probability proportional to deg v.Add the edge u,v.23A Graph Ev

13、olution Process p 1-puvGt The number of nodes grows with time Edges are not added uniformly Nodes which are added early have an“advantage”over nodes added late Gives a power law degree distribution y 1/d1+1/p24ComparisonsFrom simulation using Model BFrom real data25Evolution Process for Directed Gra

14、phsSelect a vertex u with probability proportional to the the out degree of u,i.e.,Pr u chosen =out-deg(u)/|E|.Select a vertex v with probability proportional to the the in degree of v.Flip two coins;heads with prob p1 and p2.Heads,heads-add an edge from u to v.Heads,tails -add an edge from u to a n

15、ew node.Tails,heads -add an edge from a new node to v.Tails,Tails -add a directed self-loop to a new node.#nodes w/outdegree d 1/d1+1/p1#nodes w/indegree of d 1/d1+1/p226Massive GraphsRandom graphsSimilarities:Adding one(random)edge at a time.Differences:Random graphs-almost regular.Massive graphs-u

16、neven degrees.Correlations.27The advantages of power law models Approximating real data graphs.Possible to analyze rigorouslydiscover implicit structure of massive graphs Models for generating network topologies28 Erds and Rynis seminal papers.Methods:Martingales.Concentration bounds.Molloy+Reeds re

17、sults on random graphs with.given degree squences.29 Can be found at A JAVA generation/simulation of power graphsFuture directionsThe evolution of power graphs concerning -diameters of connected components luuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuLus thesis -frequency of occurrences of certain subgraphs -power law of eigenvalues -scaling behavior of power law graphs -“signatures”in graphs to distinguish models 30