When is a scale-free graph ultra-small?

DOI10.1007/S10955-017-1864-1zbMATH Open1386.60041arXiv1611.03639OpenAlexW3100954726WikidataQ59512957 ScholiaQ59512957MaRDI QIDQ1685487FDOQ1685487

Júlia Komjáthy, Remco van der Hofstad

Publication date: 14 December 2017

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: In this paper we study typical distances in the configuration model, when the degrees have asymptotically infinite variance. We assume that the empirical degree distribution follows a power law with exponent $auin(2,3)$, up to value $$ for some $$ and $gammain(0,1)$. This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law distributions where the (possibly exponential) truncation happens at $$. We show that the graph distance between two uniformly chosen vertices centers around $$, with tight fluctuations. Thus, the graph is an emph{ultrasmall world} whenever $$. We determine the distribution of the fluctuations around this value, in particular we prove that these are non-converging tight random variables that show $loglog$-periodicity. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order $$, where $f_{n}in(0,1)$ is a random variable that oscillates with $n$. The two end-segments of any shortest path have length $$+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length $$+tight, and it contains only vertices with degree at least of order $$, thus all the degrees on this segment are comparable to the maximal degree. Our theorems also apply when instead of truncating the degrees, we start with a configuration model and we remove every vertex with degree at least $$, and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.

Full work available at URL: https://arxiv.org/abs/1611.03639

Recommendations

• Diameter in ultra-small scale-free random graphs
• When are small subgraphs of a random graph normally distributed?
• The Small Giant Component in Scale-Free Random Graphs
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications
• Could any graph be turned into a small-world?
• Ultra-small scale-free geometric networks
• Sizes of critical graphs with small maximum degrees
• Component sizes of the random graph outside the scaling window
• Scale-free graphs of increasing degree

zbMATH Keywords

random networksconfiguration modelscale freetypical distancessmall world propertytruncated power law degrees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Cites Work

• Power-Law Distributions in Empirical Data
• Statistical mechanics of complex networks
• Title not available (Why is that?)
• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• The Structure and Function of Complex Networks
• Metric structure of random networks
• A critical point for random graphs with a given degree sequence
• Collective dynamics of ‘small-world’ networks
• Exploring complex networks
• Title not available (Why is that?)
• The Average Distance in a Random Graph with Given Expected Degrees
• On a conditionally Poissonian graph process
• First passage percolation on random graphs with finite mean degrees
• Universality for first passage percolation on sparse random graphs
• Distances in random graphs with finite mean and infinite variance degrees
• Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• The structure of scientific collaboration networks
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Diameters in preferential attachment models
• Distances in random graphs with finite variance degrees
• The simple branching process with infinite mean. I
• The diameter of sparse random graphs
• A new approach to the giant component problem
• The simple branching process: a note on convergence when the mean is infinite
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Phase transitions in social networks
• The diameter of sparse random graphs
• Regularly varying functions in the theory of simple branching processes
• Vulnerability of robust preferential attachment networks
• Enumeration of graphs with a heavy-tailed degree sequence
• Critical Window for Connectivity in the Configuration Model
• Attack Resistance of Power-Law Random Graphs in the Finite-Mean, Infinite-Variance Region
• FERROMAGNETIC FLUID AS A MODEL OF SOCIAL IMPACT

Cited In (11)

• Tight fluctuations of weight-distances in random graphs with infinite-variance degrees
• Weighted distances in scale-free configuration models
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• Limit laws for self-loops and multiple edges in the configuration model
• Sampling Geometric Inhomogeneous Random Graphs in Linear Time
• Could any graph be turned into a small-world?
• Diameter in ultra‐small scale‐free random graphs
• Long-range first-passage percolation on the torus
• How unproportional must a graph be?
• Penalising transmission to hubs in scale-free spatial random graphs
• Linking the mixing times of random walks on static and dynamic random graphs

Uses Software

• plfit

This page was built for publication: When is a scale-free graph ultra-small?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1685487)