Degree Distribution, And Scale-free Networks

Degree Distribution,andScale-free networksProf. Ralucca Gera,Applied Mathematics Dept.Naval Postgraduate SchoolMonterey, Californiargera@nps.eduExcellence Through Knowledge

Learning Outcomes Understand the degree distributions ofobserved networks Understand Scale Free networks Power law degree distribution Versus exponential, log-normal, 2

Degree DistributionExcellence Through Knowledge

Degree distributions The degree distribution is a frequencydistribution of the degree sequence We define pk to be the fraction of vertices in anetwork that have degree k That is the same as saying: pk is the probabilitythat a randomly selected node of the network willhave degree kp0 12421, p1 , p2 , p3 , p4 , pk 0 k 51010101010 A well connected vertex is called a hub4

Plot of the degree distributionThe InternetCommonly seen plots of real networksRight-skewed Many nodes with small degrees, few withextremely high5– Largest degree is 2407 (not shown). Sincethis node is adjacent to 12% of the network19956

Degree distribution in directed networks For directed networks we have both in- andout-degree distributions.The Web6

Observed networks are SF (power law) Power laws appear frequently in sciences: Pareto : income distribution, 1897Zipf-Auerbach: city sizes, 1913/1940’sZipf-Estouf: word frequency, 1916/1940’sLotka: bibliometrics, 1926Yule: species and genera, 1924.Mandelbrot: economics/information theory, 1950’s Research claims that observed real networks are scalefree, not consistent defn., [ref. 1–7], i.e.– The fraction of nodes of degree 𝑘 follows a power law distribution𝑘 , where 𝛼 1,– Generally being observed 𝛼 2, 3 , see [ref. 8, 9]– Or at least the upper tail of the distribution is power law) [ref. 10]– Or it is more plausible than other thin-tailed distributions [ref. 11]Broido and Clauset “Scale-free networks are rare”, Jan 2018, https://arxiv.org/abs/1801.03400 [ref. 13]https://www.eecs.harvard.edu/ michaelm/TALKS/Radcliffe.ppt

Power law distributions Power law distribution:(Infinite mean and variance possible) Identifying power-law from non power-lawdistributions is not trivial– Simplest (but not very accurate) strategy visualinspection plots– In 2006 - fit a distribution over the observed data,and test the goodness of the fit. This analysisrevealed that none of them fits the theoreticaldistribution There are alternatives as we will see8

Egypt IP-layer data

And its degree distributionNotice the long tail.It looks like apower lawdistribution𝑝𝑐 𝑘 ,𝛼 0A bit hard to differentiate the count values can this visualizationbe improved to be useful? How? We’ll see in a few slides10

Statistics for real networksα power in the power law distribution11

The powerlaw exponent Claim:𝑝𝑐𝑘,𝛼0 Analysis of 1000networks:observednetworks havethe power lowexponentsplotted on theright Code at:https://github.com/adbroido/SFAnalysisBroido and Clauset “Scale-free networks are rare”, Jan 2018, https://arxiv.org/abs/1801.03400 [ref. 13]12

Exponent by network typeThe values of power law exponents for several types of networksEikmeier and Gleich, “Revisiting Power-law Distributions in Spectra of Real World Networks”, Aug 2017https://dl.acm.org/citation.cfm?id 309812813

BinningExcellence Through Knowledge

BA Example (n 1000)15

BinningA binned degree histogram may give poorstatistics at the tail of the distribution As k gets large, in every bin there will be onlya few samples large statistical fluctuationsin the number of samples from bin to bin which makesthe tail endnoisy anddifficult todecide if itfollows apower-law16

Detecting and visualizing power lawsAlternatives: We could use larger bins to reduce the noise atthe tail since more samples fall in the same bin– this reduces the detail captured from the histogramsince we end up with fewer bins17

Logarithmic BinningExcellence Through Knowledge

Visualizing power lawsAlternatives: Try to get the best of both worlds differentbin sizes in different parts of the histogram– Careful at normalizing the bins correctly: a bin ofwidth 10 will get 10 times more samples comparedto the previous bin of width 1 divide the countnumber by 10 logarithmic view (log-log plots)19

Logarithmic binning𝑙𝑜𝑔Ck Plot the degree distribution for the Internet inlog-log scale:here thewidth ofthe bins isfixed, thedisplay ischanged0𝑙𝑜𝑔 1M.E.J. Newman, “Power laws, Pareto distributions and Zipf’s law”2𝑙𝑜𝑔degree k1𝑙𝑜𝑔 10𝑙𝑜𝑔 100

Logarithmic binningIn this scheme each bin is made wider than itspredecessor by a constant factor a 10– The 1-st bin will cover the range:– The 2-nd bin will cover the range:– The 3-rd bin will cover the range: k k k The most common choices for a are 2 and 10,since larger values of a give ranges that are toobig, and smaller a values give non-integerranges limits21– The n-th bin will cover the range: an-1 k an

Power Law and Scale FreeExcellence Through Knowledge

Power laws and scale free networks Networks that follow power law degree distribution arereferred to as scale-free networks Scale-free network: means that the ration of veryconnected nodes to the number of nodes in the rest of thenetwork remains constant as the network changes in size(supports research based on some sampling methods) Real networks do not follow power law degreedistribution over the whole range of degree k– That is the degree distribution is not monotonicallydecreasing over the whole range of degrees– Many times we refer to its tail only (high degrees) Deviations from power law can appear for high values of k as wellhttp://networksciencebook.com/chapter/4

Power laws and scale free networks It is important to mention what property of thenetwork is scale-free.– Generally it is the degree distribution, and we say thatthe “network is scale-free” which in reality says “thedegree distribution is scale-free”– Sometimes the exponent of the degree distributioncaptures this. Why? The exponent is the slope of theline that fits the data on log-log scale.– This has been tested with random subnetworks ofscale free models that indeed show scale free degreedistribution (but not always the same exponent)24

Power law for WWW data from 1999The Degree Distribution of the WWWThe incoming (a) and outgoing (b) degree distribution of the WWW (1999). The degree distribution isshown on log-log plot, in which a power law follows a straight line. The symbols correspond to theempirical data and the line corresponds to the power-law fit, with degree exponents γin 2.1 and γout 2.45. We also show as a green line the degree distribution predicted by a Poisson function with the25average degree 〈kin〉 〈kout〉 4.60 of the WWW er-laws

Hubs are Large in Scale-free NetworksThe estimated degree of the largest node (natural cutoff) in scale-free and random networkswith the same average degree 〈k〉 3. For the scale-free network we chose 𝛼 2.5. Forcomparison, we also show the linear behavior, kmax N 1, expected for a completenetwork. Overall, hubs in a scale-free network are several orders of magnitude larger thanthe biggest node in a random network with the same N and ubs

A video - scale free introduction4

Scale freeConclusion: in a random network hubs areeffectively forbidden, while in scale-free networksthey are naturally present.General belief: Scale free networks grow becauseof preferential attachment Moreover:preferential attachment scale freeButpreferential attachment scale freecounterexamples: the configuration model, random geometric model28

New researchExcellence Through Knowledge

New research (Jan 2018) bits a thintail andrelatively lowvariance, isfavored overthe power law(36%) nearlyas often as thepower law isfavored overtheexponential(37%).”Power law(Power law is a specific instance of this power law with cuttoff)Broido and Clauset “Scale-free networks are rare”, Jan 2018, https://arxiv.org/abs/1801.03400 [ref. 13]“over half of the data sets favor the cutoffmodel over the pure power-law model, whichsuggests that, to the degree that scale-freenetworks are universal, finite-size effects inthe extreme upper tail are quite common”

Takeaways Networks have heavy-tailed degree distributions:– scale-free networks are rare: 4% strong SF, and– 33% weak (as likely as other models) SF evidence Weak correlation of SF across different types:– Stronger correlation shows that SF structures occur inbiological and technological networks “ there is likely no single universal mechanism,or even a handful of mechanisms, that can explainthe wide diversity of degree structures found inreal-world networks.”Broido and Clauset “Scale-free networks are rare”, Jan 2018, https://arxiv.org/abs/1801.03400 [ref. 13]31

References[1] R. Albert, H. Jeong, and A. L. Barab asi, Nature 401, 130 (1999).[2] N. Prˇzulj, Bioinformatics 23, 177 (2007).[3] G. Lima-Mendez and J. van Helden, Molecular BioSystems 5, 1482 (2009).[4] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, in Proc. 7thACM SIGCOMM Conference on Internet Measurement (IMC) (2007) pp. 29–42.[5] M. T. Agler, J. Ruhe, S. Kroll, C. Morhenn, S. T. Kim, D. Weigel, and E. M. Kemen,PLoS Biology 14, 1 (2016).[6] G. Ichinose and H. Sayama, Artificial Life 23, 25 (2017).[7] L. Zhang, M. Small, and K. Judd, Physica A 433, 182 (2015).[8] S. N. Dorogovtsev and J. F. F. Mendes, Advances in Physics 51, 1079 (2002).[9] A. L. Barab asi and R. Albert, Science 286, 509 (1999).[10] W. Willinger, D. Alderson, and J. C. Doyle, Notices of the AMS 56, 586 (2009).[11] R. Albert, H. Jeong, and A.-L. Barab asi, Nature 406, 378 (2000).[12] N. Eikmeier, and D. Gleich. "Revisiting Power-law Distributions in Spectra of RealWorld Networks." Proceedings of the 23rd ACM SIGKDD International Conference onKnowledge Discovery and Data Mining. ACM, 2017.[13] A. Broido and A. Clauset, “Scale-free networks are rare”, 201832

New research (Jan 2018) data: Applying state-of-the-art statistical methods toa diverse corpus of 927 real-world networks:– estimate thebest-fittingpower-law model,– test its statisticalplausibility, and– compare it via alikelihood ratiotest to alternative non-scale-freedistributions.Broido and Clauset “Scale-free networks are rare”, Jan 2018, https://arxiv.org/abs/1801.03400 [ref. 13]33

Best fitting model1. For each degree sequence, estimate the bestfitting power-law distribution model: the power-law holds above some minimum value 𝑘 , chosenbefore fitting the distribution Test use is Kolmogrov-Smirnov (KS) minimization approach(which actually chooses the optimal value of 𝑘 )2. Used goodness-of-fit to obtain a standard p-value: if p 0.1, then the degree sequence is scale free, while if p 0.1, reject the scale-free hypothesis. failing to reject does not imply that the model is correct, onlythat it is a plausible data generating process.34Broido and Clauset “Scale-free networks are rare”, Jan 2018, https://arxiv.org/abs/1801.03400 [ref. 13]

Testing the goodness-of-fitAlternative heavy tailed distrib. (starting at): Exponential (a thin tail and relatively low variance), stretched exponential or Weibull distribution (can produceboth thin or heavy tails, and is a generalization of theexponential distribution), log-normal (a broad distribution that can exhibit very heavytails, finite mean and variance), power-law with exponential cutoff in the upper tail (powerlaw is a special case of this).35Broido and Clauset “Scale-free networks are rare”, Jan 2018, https://arxiv.org/abs/1801.03400 [ref. 13]