TY - JOUR

T1 - An algorithm generating random graphs with power law degree distributions

AU - Volchenkov, D.

AU - Blanchard, Ph

N1 - Funding Information:
One of the authors (D.V.) benefits from a scholarship of the Alexander von Humboldt Foundation (Germany) that he gratefully acknowledges.

PY - 2002/12/10

Y1 - 2002/12/10

N2 - We propose a simple random process generating various types of random graphs and the scale-free random graphs among others. The model is of a threshold nature and differs from the preferential attachment approach discussed in the literature before. The degree statistics of a random graph in our model is governed by the control parameter η stirring the pure exponential statistics for the degree distribution (at η=0, when the threshold value is changed each time a new edge is added to the graph) to a power law (at η=1, when the threshold is frozen). The exponent γ characterizing the power law can vary in the wide range γ(1,∞) and can be tuned in different values γin and γout for in-degrees and out-degrees probability distributions independently. For η(0,1), the decay rate is mixed. Taking different statistics for the threshold changes, one obtains dissimilar asymptotic profiles for the degree distribution having, in general, nothing to do with power laws at η=1, but still uniformly exponential at η=0.

AB - We propose a simple random process generating various types of random graphs and the scale-free random graphs among others. The model is of a threshold nature and differs from the preferential attachment approach discussed in the literature before. The degree statistics of a random graph in our model is governed by the control parameter η stirring the pure exponential statistics for the degree distribution (at η=0, when the threshold value is changed each time a new edge is added to the graph) to a power law (at η=1, when the threshold is frozen). The exponent γ characterizing the power law can vary in the wide range γ(1,∞) and can be tuned in different values γin and γout for in-degrees and out-degrees probability distributions independently. For η(0,1), the decay rate is mixed. Taking different statistics for the threshold changes, one obtains dissimilar asymptotic profiles for the degree distribution having, in general, nothing to do with power laws at η=1, but still uniformly exponential at η=0.

KW - Power laws

KW - Real-world networks

KW - Scale-free random graphs

UR - http://www.scopus.com/inward/record.url?scp=0037058795&partnerID=8YFLogxK

U2 - 10.1016/S0378-4371(02)01004-X

DO - 10.1016/S0378-4371(02)01004-X

M3 - Article

AN - SCOPUS:0037058795

VL - 315

SP - 677

EP - 690

JO - Physica A: Statistical Mechanics and its Applications

JF - Physica A: Statistical Mechanics and its Applications

SN - 0378-4371

IS - 3-4

ER -