A Random Graph Model For Massive Graphs - Tufts University
A Random Graph Model for Massive GraphsVq' .lia m A i e 11oAT&T LabsF l o r h a m Park, New J e r s e yFan ChungUnive rs ity of California,S a n DiegoLinyuan LuUnive rs ity of California,S a n Diegoaie 11o@ re s e arch.att, c o mfan@ u c s d . e d ullu@ m a t h . u c s d.e duABSTRACTreal world graphs. Indeed, Abello et al. [1] have shown thatthe degree sequence of so called call graphs is nicely approximated by a power law distribution. Call graphs are graphsof calls handled by some subset of telephony carriers for aspecific time period. In addition, Faloutsos, et al. [9] haveshown that the degree sequence of the Internet router graphalso follows a power law.Just as many other real world processes have been effectively modeled by appropriate random models, in thispaper we propose a parsimonious random graph model forgraphs with a power law degree sequence. We then deriveconnectivity results which hold with high probability in various regimes of our parameters. And finally, we compare theresults from the model with the exact connectivity structurefor some call graphs computed by Abello et al. [1].We propose a random graph model which is a specialcase of sparse random graphs with given degree sequences.This model involves only a small number of parameters,called logsize and log-log growth rate. These parameterscapture some universal characteristics of massive graphs.Furthermore, from these parameters, various properties ofthe graph can be derived. For example, for certain rangesof the parameters, we will compute the expected distribution of the sizes of the connected components which almostsurely occur with high probability. We will illustrate theconsistency of our model with the behavior of some massivegraphs derived from data in telecommunications. We willalso discuss the threshold function, the giant component,and the evolution of random graphs in this model.1.11. INTRODUCTIONPower-Law Random GraphsThe study of random graphs dates back to the work ofErd6s and R nyi whose seminal papers [7; 8] laid the foundation for the theory of random graphs. There are threestandard models for what we will call in this paper uniformrandom graphs [4]. Each has two parameters. One parameters controls the number of nodes in the graph and onecontrols the density, or number of edges. For example, therandom graph model G(n, m) assigns uniform probability toall graphs with n nodes and m edges while in the randomgraph model ( n , p ) each edge in an n node graph is chosenwith probability p.Our power law random graph model also has two parameters. The two parameters only roughly delineate thesize and density but they are natural and convenient fordescribing a power law degree sequence. The power lawrandom graph model P ( a , fl) is described as follows. Let ybe the number of nodes with degree x. P(a, fl) assigns uniform probability to all graphs with y e /x (where selfloops are allowed). Note that a is the intercept and fl is the(negative) slope when the degree sequence is plotted on alog-log scale.We remark that there is also an alternative power lawrandom graph model analogous to the uniform graph model (n,p). Instead of having a fixed degree sequence, the random graph has an expected degree sequence distribution.The two models are basically asymptotically equivalent, subject to bounding error estimates of the variances (which willbe further described in a subsequent paper).Is the World Wide Web completely connected? If not,how big is the largest component, the second largest component, etc.? Anyone who has "surfed" the Web for anylength of time will undoubtedly come away feeling that ifthere are disconnected components at all, then they mustbe small and few in number. Is the Web too large, dynamicand structureless to answer these questions?Probably yes, if the answers for the sizes of the largestcomponents are required to be exact. Recently, however,some structure of the Web has come to light which mayenable us to describe graph properties of the Web qualitatively. Kumar et al. [11; 12] and Kleinberg et al. [10] havemeasured the degree sequences of the Web and shown thatit is well approximated by a power law distribution. That is,the number of nodes, y, of a given degree x is proportionalto x - for some constant/ 0. This was reported independently by Albert, Barab si and Jeong in [3; 5; 6]. The powerlaw distribution of the degree sequence appears to be a veryrobust property of the Web despite its dynamic nature. Infact, the power law distribution of the degree sequence maybe a ubiquitous characteristic, applying to many massivePermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copiesare not made or distributedfor profit or commercialadvantageand thatcopies bear this noticeand the full citation on the first page. To copyotherwise, to republish,to post on servers or to redistributeto lists,requires prior specific permissionand/or a fee.STOC 2000 Portland Oregon USACopyright ACM 2000 1-58113-184-.4/00/5. 5.001.2Our ResultsJust as for the uniform random graph model wheregraph properties are studied for certain regimes of the den-171
c/x 3. Moreover, all the graphs can be decomposed into mdisjoint trees, where m is a parameter of the model. The(a, fl) model in [12] is able to generate graphs for which thepower law for the indegree is different than the power lawfor the outdegree as is the case for the Web. However, todo so, the model requires that there be a constant fractionof nodes that have only indegree and no outdegree and visaversa. While this may be appropriate for call graphs (e.g.,customer service numbers) it remains to be seen whether itmodels the Web. Thus, while the random graph generationapproach holds the promise of accurately predicting a widevariety a structural properties of many real world massivegraphs much work remains to be done.In this paper we take a different approach. We do notattempt to answer how a graph comes to have a power lawdegree sequence. Rather, we take that as a given. In ourmodel, all graphs with a given power law degree sequenceare equi-probable. The goal is to derive structural properties which hold with probability asymptotically approaching1. Such an approach, while potentially less accurate thanthe detailed modeling approach above, has the advantage ofbeing robust: the structural properties derived in this modelwill be true for the vast majority of graphs with the givendegree sequence. Thus, we believe that this model will be animportant complement to random graph generation models.The power law random graph model will be describedin detail in the next section. In Sections 3 and 4, our resultson connectivity will be derived. In section 5, we discussthe sizes of the second largest components. In section 6, wecompare the results of our model to exact connectivity datafor call graphs.sity parameter and shown to hold with high probabilityasymptotically in the size parameter, in this paper we studythe connectivity properties of P(a, t3) as a function of thepower/3 which hold almost surely for sufficiently large graphs.Briefly, we show that when 1, the graph is almost surelyconnected. For 1 13 2 there is a giant component, i.e.,a component of size O(n). Moreover, all smaller components are of size O(1). For 2 fl fi0 3.4785 there isa giant component and all smaller components are of sizeO(log n). For fl 2 the smaller components are of sizeO(log n loglog n). For fl 130 the graph almost surely hasno giant component. In addition we derive several resultson the sizes of the second largest component. For example,we show that for fl 4 the numbers of components of givensizes can be approximated by a power law as well.1.3Previous WorkStrictly speaking our model is a special case of random graphs with a given degree sequence for which thereis a large literature. For example, Wormald [17] studiedthe connectivity of graphs whose degrees are in an interval[r, R], where r 3. Luczak [13] considered the asymptoticbehavior of the largest component of a random graph withgiven degree sequence as a function of the number of vertices of degree 2. His result was further improved by Molloyand Reed [14; 15]. They consider a random graph on n vertices with the following degree distribution. The fractionof vertices of degree 0, 1, 2 , . . . is asymptotically A0, A1, . . . ,respectively, where the A's sum to 1. It is shown in [14]that if Q i i(i - 2)Ai 0 (and the maximum degree isnot too large), then such random graphs have a giant component with probability tending to 1 as n goes to infinity,while if Q 0 (and the maximum degree is not too large),then all components are small with probability tending to 1as n --* c . They also examined the threshold behavior ofsuch graphs. In this paper, we will apply these techniquesto deal with the special case that applies to our model.Several other papers have taken a different approach tomodeling power law graphs than the one taken here [2; 5; 6;10; 12]. The essential idea of these papers is to define a random process for growing a graph by adding nodes and edges.The intent is to show that the defined processes asymptotically yield graphs with a power law degree sequence withvery high probability. While this approach is interestingand important it has several difficulties. First, the modelsare difficult to analyze rigorously since the transition probabilities are themselves dependent on the current state. Forexample, [5; 6] implicitly assume that the probability thata node has a given degree is a continuous function. The authors of [10; 12] will offer an improved analysis in an upcoming paper [16]. In [2] we derive a power law degree sequencefor several graph evolution models for asymptotically largegraphs by explicitly solving the recurrence relations givenby the random evolution process for the expected degree sequence and showing tight concentration around the meanusing Azuma's inequality for martingales. We also deriveresults for the distribution of connected component sizes,but not for the entire range of powers given in this paper.Second, while the models may generate graphs with powerlaw degree sequences, it remains to be seen if they generategraphs which duplicate other structural properties of theWeb, the Internet, and call graphs. For example, the modelin [5; 6] cannot generate graphs with a power law other than2.A RANDOMGRAPH MODELWe consider a random graph with the following degreedistribution depending on two given values and ft. Suppose there are y vertices of degree x 0 1 where x and ysatisfylog y a - fllog x.In other words, we haveI{vldeg(v) x} I Y -Z"Basically, is the logarithm of the number of nodes of degree1 and f is the log-log rate of decrease of the number of nodesa given degree.We note that the number of edges should be an integer.To be precise, the above expression for y should be roundede t down to [-- J. If we use real numbers instead of roundingdown to integers, it may cause some error terms in furthercomputation. However, we will see that the error terms canbe easily bounded. For simplicity and convenience, we willuse real numbers with the understanding the actual numbers are their integer parts. Another constraint is that thesum of the degrees should be even. This can be assuredby adding a vertex of degree 1 if the sum is old if needed.Furthermore, for simplicity, we here assume that there is noisolated vertices.We can deduce the following facts for our graph:1There are several ways to deal with nodes with zero degree.For simplicity, here we simply exclude such isolated nodesfrom the graph.172
(1) The m a x i m u m degree of the graph is e . Note that0 log y c --/3 log x.(2) The vertices n u m b e r n can be computed as follows: Bys u m m i n g y(x) for x from 1 to e , we have e n Ez-5f (fl)e ' Ix 1 e e if/3 1iffl lifO fl 13.THECONNECTEDCOMPONENTSMolloy and Reed [14] showed t h a t for a r a n d o m graphwith (Ai o(1))n vertices of degree i, where Ai are nonnegative values which sum to 1, the giant component emergesa. s. when Q i 1 i(i-2)Ai 0, provided that the maxi-m u m degree is less t h a n nl/4-C T h e y also show that almostsurely there is no giant c o m p o n e n t when Q 1 i ( i 2)Ai 0 and m a x i m u m degree less t h a n n 1/8- .Here we compute Q for our ( ,/3)-graphs.where (t) - ' n 1 -r1 is the R i e m a n n Zeta function.(3) The n u m b e r of edges E can be computed as follows:x -- x lif/3 2if/3 2 e 271 e fl22- ;r lif0 /3 2eaEx l. (4) The differences of the real n u m b e r s in (1)-(3) and theirinteger parts can be estimated as follows: For the n u m b e rn of vertices, the error term is at most e . For/3 1, it iso(n), which is a lower order term. For 0 / 3 1, the errorterm for n is relatively large. In this case, we havec n e -1-/3xZ-22 Eeax -ix l(if(/3- 2) - 2 ( / 3 - 1))e if/3 3Hence, we consider the value /3o 3.47875 . , which is asolution to (/3 - 2) - 2 (/3 - 1) 0c e aQ - z(x- 2)Lxe- j ( - 1)e {E et If/3 /30, we have/3e- 1-/3eftolY ( -2)L J oTherefore, n has the same m a g n i t u d e as le -- . The n u m b e rE of edges can be treated in a similarly way. For/3 2, theerror term of E is o(E), a lower order term. For 0 / 3 2,E has the same m a g n i t u d e as in formula of item (3). In thispaper, we mainly deal wi h the case/3 2. The only placethat we deal with the case 0 / 3 2 is in the next sectionwhere we refer to 2 - / 3 as a constant. By using real numbersinstead of rounding down to their integer parts, we simplifythe arguments without affecting the conclusions.In order to consider the r a n d o m graph model, we willneed to consider large n. We say that some property almostsurely (a. s.) happens if the probability that the propertyholds tends to 1 as the n u m b e r n of the vertices goes toinfinity. Thus we consider a to be large b u t where /3 isfixed.We use the following r a n d o m graph model for a givendegree sequence:The model:1. Form a set L containing deg(v) distinct copies of eachvertex v.2. Choose a r a n d o m matching of the elements of L.3. For two vertices u and v, the n u m b e r of edges joining uand v is equal to the n u m b e r of edges in the matching of Ljoining copies of u to copies of v.We remark that the graphs that we are considering arein fact multi-graphs, possibly with loops. This model is anatural extension of the model for k-regular graphs, whichis formed by combining k r a n d o m matching. For referencesand undefined terminology, the reader is referred to [4; 18].We note that this r a n d o m graph model is slightly different from the uniform selection model P ( a , / 3 ) as describedin section 1.1. However, by using techniques in Lemma 1 of[15], it can be shown that if a r a n d o m graph with a givendegree sequence a. s. has property P under one of these twomodels, then it a. s. has property P under the other model,provided some general conditions are satisfied.X IWe first summarize the results here:1. W h e n /3 fl0 3 . 4 7 8 7 5 . . . , the r a n d o m graph a. s.has no giant component. W h e n / 3 /30 3 . 4 7 8 7 5 . . . ,there is a. s. a unique giant component.2. W h e n 2 /3 /30 3 . 4 7 8 7 5 . . . , the second largestcomponents are a. s. of size (log n). For any 2 x (log n), there is almost surely a component of size x.3. W h e n /3 2, a. s. the second largest components areofsize (.lo. 322 ]. For any 2 x O( , 1 -29-a2- there loglog n -loglog n ]'is almost surely a component of size x.4. W h e n 1 /3 2, the second largest components area. s. of size (1). The graph is a. s. not connected.5. W h e n 0 / 3 1, the graph is a. s. connected.6. For fl /30 3 . 4 7 8 7 5 . . . , this is a very complicatedcase. It corresponds to the double j u m p of randomgraph (J(n,p) with p L.For/3 1, there is a nonr trivial probability for either cases that the graph isconnected or disconnected.Before proceeding to state the main theorems, here are somegeneral discussions:For fl 8, Molloy and Reed's result immediately implies that almost surely there is no giant component. When/3 8, additional analysis is needed to deal with the degreeconstraints. We will prove in T h e o r e m 2 that almost surelythere is no giant c o m p o n e n t when /3 rio. Also, almostsurely there is a unique giant c o m p o n e n t when fl /3o (Theproof will be given in the full paper) For 2 / 3 rio, we will consider the sizes of the secondlargest component in section 5. It can be shown that thesecond largest c o m p o n e n t almost surely has size O(log n).173
for some c o n s t a n t M. Hence, a. s. all vertices with degree atleast M a log a are in the giant component. Hence, the giantcomponent is so large t h a t only a small portion of vertices(as b o u n d e d below) are not in it.In the other direction, we will show that the second largestcomponent has size at least @(log n).For 0 / 3 2, the graph has O ( e - ) edges. We expectthat the giant exponent is very large. For some constants Tand C, a. s. every vertex of degree greater that T l o g n C abelongs to the giant component. T h a t is, the n u m b e r ofedges which do not belong to the giant component is quitesmall. It is at mostea L -zJ2Mcc log c eC xL J (loga)e z lFor any pair of vertices (u, v), the probability that u is inthe giant c o m p o n e n t while v is in other component of sizeat least 2.1tog a is at most O((Ca) 2- e' ) O ( E log2- E)x-- al o g a 21" ( . . )Now we consider the second largest component. For any pair(u, v), the probability that u belongs to the giant componentwhile v belongs to the other c o m p o n e n t of size greater t h a nM O(1) is at most:e 2 . o o1 -2'la o ( n - 2 )Again, this almost surely is not likely to happen. Hence, weprove that the size of the second largest components is atmost 2.11o a.gNow we find a vertex v of degree x 0.9loan.Thegprobability that all its neighbors are of degree 1 is a zThe probability that no such vertex exists is at most( E - 1 log2-#E) M -- o(n -2)for some large constant M, which only depends on/3. Thisimplies that all components except for the giant componenta. s. have size at most M. Therefore, a. s. the second largestcomponent has size O(1).For 1 / 3 2, fix a vertex v of degree 1. T h e probability that the other vertex t h a t connects to v is also of degree1 is about 1 e ( ) x r e - - -,o.1,,7 o(1)(1 -- ( - - ) z ) * aHence, a. s. there is a vertex of degree 0 ' 9 lOg,which formsa connected c o m p o n e n t of size 0.91o- 1. Again, when xis smaller, almost surely there is a c o m p o n e n t of size x.eaCt 4.Therefore the probability that no component has size of 2 isat most(1 - -E) ( - e-a , , e , aCOMPOFOR/3For /3 /3o 3 . 4 7 8 7 5 . . . , almost surely there is nogiant component. This range is of special interest since itis quite useful later for describing the distribution of smallcomponents. We will prove the following: e - ( 2 a - ) o0)e/3In other words, the graph a. s. has at least one componentof size 2.For 0 /3 1, the r a n d o m graph is a. s. connected.Here we sketch the ideas. Since the size of the possiblesecond largest component is b o u n d e d by a constant M, allvertices of degree M are almost surely in the giant component. We only need to show the probability t h a t there isan edge connecting two small degree vertices is small. Thereare onlyMTHE SIZES OF CONNECTEDNENTS IN CERTAIN RANGESTHEOREM 1. For (a,/3)-graphs with/3 4, the distribution of the number of connected components is as follows:1. For each vertex v of degree d ft(1), let -r be the sizeof connected component containing v. Thencle c WI -where cl 2 and c2 ( -1) are two constants. In other words, for d a (slowly)increasing function and ) d e, for some arbitrarilysmall postive constant e, the vertex v a. s. belongs to aconnected component of size d O(d½ e).vertices w i t h degree less than M . For any random pair ofvertices .(u,v), the probability that there is an edges connecting them is about1EHence the probability that there is edge connecting twosmall degree vertices is at most- O(e- )2. The number of connected components of size x is a. s.at leaste (1 o(Xllcf x1 (Ce )2 (eZ ) o(1)u 'vand at mostHence, every vertex is a. s. connected to a vertex with degree M, which a. s. belongs to the giant exponent. Hence, ther a n d o m graph is a. s. connected.The case of B 2 is quite interesting. In this case, thegraph has y1 a e a edges. Since a. s. all other components except for the giant one has size at most O(log n) M a log ae log -1 nC3where c3 /3.174X .{. 1is a constant only depending on
3. A connected component of the (c ,/3)-graph a. s. hasthe size at moste We haveE(Z,)o(n logn)In our proof we use the second m o m e n t whose convergencedepends on /3 4. In fact for /3 4 the second m o m e n tdiverges as the size of the graph goes to infinity so t h a t ourm e t h o d no longer applies.T h e o r e m 1 strengthens the following result (which canbe derived from L e m m a 3 in [14]) for the range of fl 4. v ' e # x x E -ffe -, 1e # x2-t ?--. a ( -2) o(n - ) ( -1) o(n s) p-2;g-1 )Now we will bound Wi. Suppose t h a t there are m edgesexposed at stage i - 1. T h e n the probability that a newneighbor is in L i - a is at most . We haveooTHEOREM 2. For fl /30 3 . 4 7 8 7 5 . . . , a connected component of the ( , 3)-graph a. s. has the size at mostmCe a O ( n log n)where C 16 is a constant only depending on/3. The proof for T h e o r e m 2 is by using branching processmethod. We here briefly describe the proof since it is neededfor the proof of T h e o r e m 1. We start by "exposing" anyvertex v0 in our graph, then we expose its neighbors, andthen the neighbors of its neighbors, repeating until the entirecomponent is exposed. At any stage of the process the entirecomponent will have some nodes which are marked "live,"some which are marked "dead," and some which are notmarked at all. At stage i, we choose an arbitrary live vertexv to expose. T h e n we m a r k v dead and, for each neighbor uof v, we m a r k u live if u is unmarked so far. Let L be the setof marked vertices at stage i and Xi be the random variablethat denotes the number of vertices in Li. We note t h a t allvertices in Li are markea by either "live" or "dead". LetOi be the set of live vertices and be the random variablethat is the number of vertices of Oi. At each step we m a r kexact one dead vertex, so the total number of dead verticesat i-th step is i. We have Xi i. Initially we assignL0 O0 {v0}. T h e n at stage i 1, we do the following:E(1- . )2-- O(*)((E) )" Eprovided - o(1).2 t. ,ac,W h e n i Ce ( , m is at most zea Ce . Hence,mEO ( n -1 log n) ----o(1)We haveiE(Id) Y E( -] I)j 2i d E(Z,-2-Wj)j 2 d (i-1)( (/3 d-c (i-1) io(1)--\ - 2) - 2 , ) - i O ( n t ' -a 1)1logn)P r o o f o f T h e o r e m 2: Since ]Yj - Yj-a] e , by A z u m a ' smartingale inequality, we have1. If Y -I 0, then we stop and o u t p u t X i - 1 .Pr(l - E(I )I t) 2exp2. Otherwise, randomly choose a live vertex u from 0 i - 1and expose its neighbors in Nu. T h e n m a r k u dead andm a r k each vertex live if it is in N but not in L i - 1 .We have Li Li-1 tO U , and Oi (Oi-a \ {u}) tOBy taking i 1D-18e log n , and t i . Since(u, \ L ,).E(Y ) t d-cl(i-1) io(1) Suppose that v has degree d. T h e n X1 d 1, and]I1 -- d. Eventually will hit 0 if i is large enough. Let rdenote the stopping time of Y, namely, Y -- 0. T h e n X Y r -- r measures the size of the connected component.We first compute the expected value of and then useA z u m a ' s Inequality [14] to prove T h e o r e m 2.Suppose t h a t the vertex u is exposed at stage i. T h e nN Li- contains at least one vertex, which was exposed toreach u. However, N L i may contain more than one vertex. We call t h e m "backedges". We note t h a t "backedges"causes the exploration to stop more quickly, especially whenthe component is large. However in our case /3 /3o -3 . 4 7 8 7 5 . . . , the contribution of "backedges" is quite small.We denote Zi # { N } and Wi --/ {N,, O L i - a } -- 1. Zlmeasures the degree of the vertex exposed at stage i, whileWi measures the number of "backedges". By definition, we - - c i d c l i o ( 1 ) 0We havePr(r e tlogn) Pr(r i) Pr(Y E(Yd t) Pr(Y O) 2 exp Hence, the probabifity t h a t there exists a vertex v such thatlies in a c o m p o n e n t of size greater t h a n e most22nn2. . . .no(1).[]Vlog n is at&verticesT h e proof of T h e o r e m 1 uses the methodology aboveas a starting point while introducing the calculation of thevariance of the above r a n d o m variables.Proof of Theorem 1h aveYi - Yi-1 Zi - 2 -2iWi.175
. W h e n i O ( e ) , m ze O(eWe follow the notation and previous results of Section 4. Under the assumption /3 4, we consider the following:E(!d) d (i-1) ( ( / 3 - 2 )1)\ -- 4e - (i - 1) 1 o ( . - d-(i-1)cle , we have 1)-I-,-- .m2 ) iO(nt -1) o(1)ie Var(Zi) )Var(Yi) Var(e E ( Y j - Yj-1))- E(Z,) j 2iE ( - 3) o ( -1)( ( -- 1) O ( n -,-1t )3-- 1 O(n j 2i( (3- 2)):\ (-- - V) E(v. (z,) Va (Wj))3 2 )( (fl -- 2 ) ) 2 (fl--3) ( - 1)- w,)) Va (F,(zjx - - E(Zi) k -7-fiV).4 1(CoVe,(z,, z )-CoVar( Zj, Wk ) CoVar(Wj, Wk ) ) O(n - )c2 o(1) io(1) O(e( -l) )) ic2 io(1) i(O(e ( - ) ) O ( e ( - l ) ) ) ic2 io(1)since /3 4.Chebyshev's inequality givesWe need to compute the covariants. There are modelsfor r a n d o m graphs in which the edges are in dependentlychosen. Then, Zi and Zj are independent. However, in themodel based on r a n d o m matchings, there is a small correlation. For example, Zi x slightly effects the probabilityof Zj y. Namely, Zj x has slightly less chance, whileZj y # x has slightly more chance. Both differences canbe bounded by1E-11p (l i - E( )l a ) a--7where a is the s t a n d a r d deviation of 1 , a o(v )Let11 -- k - V /-z- ,w,, and is [ -/S' V2X l ," We haveE ( ] , ) - Aa 12E - E -- d - (il - 1)cl o(1) - (Ac / / o(x/ -l)) 2j,,d/q -- , - o ( )V- -Hence CoVar(Z,, Zj) E(Z,)E - O ( ) if i # j .ci -Now we will b o u n d Wi. Suppose that there are medges exposed at stage i - 1. T h e n the probability that am We havenew neighbor is in Li-1 is at most -.o(vq) 0Hence,1Pr(r ia) Pr(Yq O) Pr(Yq E ( Y q ) - Aa) - Similarly,E(14 ) Aa d - (i2 - 1)cl 0(1) () c /' 2/2 o(V/' -2))Var(Wi) -2 ,d/Zg ), c o(,/J)--9 ( 1) O ( ( E ) )m O((E) )Va--EVcad[2- o ( )ci 0Hence,1Pr(r i2) Pr(Yi2 O) Pr(Y, 2 E(Y 2) An) - mCoV (w,, w ) /v (m)v (w,) o ( ( ) : )ThereforePrCoVar(Zi, Wj) /Var(Zi)Var(Wi) O( f- E )176I - c l 1 - - ClV -c- l ] - -
For a fixed v and A a slowly increasing function to infinity,above inequality implies t h a t almost surely we have r O(AC-d).We note that almost all components generated by vertices of degree x is about the size of g d. One such compo-when vertices of large degrees are involved. We will modifythe branching process m e t h o d as follows:For 2 /3 /30, we consider Q ½E I * ( - 2 ) 1 ] .(Note t h a t Q is a positive constant.) T h e r e is a constantinteger x0 satisfying 1 Y'] I ' 9. We choose o x ( x - 2)[ ,J/i satisfying:nent can have at most about 1c vertices of degree d. Hence,a the number of component of size dq is at least aa . Letd clx. T h e n the number of components of size x is atleast/icf axO(1 o(1))The above proof actually gives the following result. T h esize of every component, whose vertices have degree at mostdo, is almost surely Cdglog n where C - 16 is the sameconstant as in T h e o r e m 2. Let x Cd 2 log n and considerthe number of components of size x. A c o m p o n e n t of size xalmost surely contains at least one vertex of degree greaterthan do.For each vertex v with degree d do, by part 1, we haveI " - d le , e-7-V GdJ - --) , Let Aa C l O d 4l g n c c 2 dPr(r Cd logn)-havewe -Prr d e--;e V-2;d]d " C3 d41og ny0* [ C l o g n ] , where C depending on/3.where Cz c C 2 ½ is constant depending only on /3.e o Since there are only - vertices of degree d, the number ofcomponents of size at least x is at moste ead c e0'log d d 0C3 e '- *C3e 12-I Yi* -1 x0E(Y *-Y * )2C3e '(fl - 2)d0 2 log ne cr log ---I ne (r: - y x ( x - 2)[-dyJ - E ( W 0 QQ Q-244 P (W- E(r,') e- , o(n - )provided i C l o g n.T h e above inequality implies t h a t with probability atleast 1 - o ( n - 1 ) , Y/* 98! 0 when i r c l o g 1. Since Y *decreases at most by 1 at each step, Yi* can not be zero ifi [ C l o g hi. So Yi* 0 for all i. In other words, a. s. thebranching process will not stop. However, it is impossibleto have Y* 0, t h a t is a contradiction. Thus we concludethat the c o m p o n e n t must have at least /in edges. So it isa giant component. We note t h a t if a component has morethan [ C l o g n] edges exposed, then almost surely it is a giantcomponent. In particular, any vertex with degree more thanno component has size greater than e 2 . This completesthe proof of T h e o r e m 1.ON THE SIZE OF THE SECOND-EST COMPONENTe By A z u m a ' s martingale inequality, we haveX Iwhere c3 C2) c 1 4 a For x ea-- a, the( ) I above inequality implies t h a t the number of components ofsize at least x is at most o(1). In other words, a l m o s t surely5.xo.G1do4log 2 n / 3 - 2 d 0 -2C3Y *Iis a constant only Let Wi be the n u m b e r of "backedges" as defined insection 4. By inequality (*) and t
1.1 Power-Law Random Graphs The study of random graphs dates back to the work of Erd6s and R nyi whose seminal papers [7; 8] laid the foun- dation for the theory of random graphs. There are three standard models for what we will call in this paper uniform random graphs [4]. Each has two parameters. One param-
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
The totality of these behaviors is the graph schema. Drawing a graph schema . The best way to represent a graph schema is, of course, a graph. This is how the graph schema looks for the classic Tinkerpop graph. Figure 2: Example graph schema shown as a property graph . The graph schema is pretty much a property-graph.
Oracle Database Spatial and Graph In-memory parallel graph analytics server (PGX) Load graph into memory for analysis . Command-line submission of graph queries Graph visualization tool APIs to update graph store : Graph Store In-Memory Graph Graph Analytics : Oracle Database Application : Shell, Zeppelin : Viz .
10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan
service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största
Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid
LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .
Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is th
