18 October 2019 in Physical Review Research
We bring rigor to the vibrant activity of detecting power laws in empirical degree distributions in real-world networks. We first provide a rigorous definition of power-law distributions, equivalent to the definition of regularly varying distributions that are widely used in statistics and other fields. This definition allows the distribution to deviate from a pure power law arbitrarily but without affecting the power-law tail exponent. We then identify three estimators of these exponents that are proven to be statistically consistent—that is, converging to the true value of the exponent for any regularly varying distribution—and that satisfy some additional niceness requirements. In contrast to estimators that are currently popular in network science, the estimators considered here are based on fundamental results in extreme value theory, and so are the proofs of their consistency. Finally, we apply these estimators to a representative collection of synthetic and real-world data. According to their estimates, real-world scale-free networks are definitely not as rare as one would conclude based on the popular but unrealistic assumption that real-world data come from power laws of pristine purity, void of noise, and deviations.
13 January 2005 in Random Structures & Algorithms
10 March 2005 in Random Structures & Algorithms
4 February 2013 in Physical Review E
Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, and social and biological networks, are often characterized by degree-degree dependencies between neighboring nodes. In this paper, we propose a new way of measuring degree-degree dependencies. One of the problems with the commonly used assortativity coefficient is that in disassortative networks its magnitude decreases with the network size. We mathematically explain this phenomenon and validate the results on synthetic graphs and real-world network data. As an alternative, we suggest to use rank correlation measures such as Spearman's $$\rho${}$. Our experiments convincingly show that Spearman's $$\rho${}$ produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In particular, we discover much stronger negative degree-degree dependencies in Web graphs than was previously thought. Rank correlations allow us to compare the assortativity of networks of different sizes, which is impossible with the assortativity coefficient due to its genuine dependence on the network size. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.
1 August 2006 in Combinatorica
16 July 2008 in Journal of Statistical Physics
We consider self-avoiding walk, percolation and the Ising model with long and finite range. By means of the lace expansion we prove mean-field behavior for these models if d>2(α∧2) for self-avoiding walk and the Ising model, and d>3(α∧2) for percolation, where d denotes the dimension and α the power-law decay exponent of the coupling function. We provide a simplified analysis of the lace expansion based on the trigonometric approach in Borgs et al. (Ann. Probab. 33(5):1886–1944, 2005).