When is a Scale-Free graph ultra-small?

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
46 Downloads (Pure)

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 (Formula presented.), up to value (Formula presented.) for some (Formula presented.) and (Formula presented.). This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law empirical degree distributions where the (possibly exponential) truncation happens at (Formula presented.). These examples are commonly observed in many real-life networks. We show that the graph distance between two uniformly chosen vertices centers around (Formula presented.), with tight fluctuations. Thus, the graph is an ultrasmall world whenever (Formula presented.). We determine the distribution of the fluctuations around this value, in particular we prove these form a sequence of tight random variables with distributions that show (Formula presented.)-periodicity, and as a result it is non-converging. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order (Formula presented.), where (Formula presented.) is a random variable that oscillates with n. We decompose shortest paths into three segments, two ‘end-segments’ starting at each of the two uniformly chosen vertices, and a middle segment. The two end-segments of any shortest path have length (Formula presented.)+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length (Formula presented.)+tight, and it contains only vertices with degree at least of order (Formula presented.), 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 (Formula presented.), and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.

Original languageEnglish
Pages (from-to)223-264
Number of pages42
JournalJournal of Statistical Physics
Volume169
Issue number2
DOIs
Publication statusPublished - 4 Sep 2017

Fingerprint

Graph in graph theory
apexes
Shortest path
Infinite Variance
Power Law
Empirical Distribution
random variables
Degree Distribution
Configuration
configurations
Random variable
Fluctuations
Graph Distance
vulnerability
Path Length
Vulnerability
Truncation
Periodicity
attack
periodic variations

Keywords

  • Configuration model
  • Random networks
  • Scale free
  • Small world property
  • Truncated power law degrees
  • Typical distances

Cite this

@article{729efc0801e4452dae12758640aec138,
title = "When is a Scale-Free graph ultra-small?",
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 (Formula presented.), up to value (Formula presented.) for some (Formula presented.) and (Formula presented.). This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law empirical degree distributions where the (possibly exponential) truncation happens at (Formula presented.). These examples are commonly observed in many real-life networks. We show that the graph distance between two uniformly chosen vertices centers around (Formula presented.), with tight fluctuations. Thus, the graph is an ultrasmall world whenever (Formula presented.). We determine the distribution of the fluctuations around this value, in particular we prove these form a sequence of tight random variables with distributions that show (Formula presented.)-periodicity, and as a result it is non-converging. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order (Formula presented.), where (Formula presented.) is a random variable that oscillates with n. We decompose shortest paths into three segments, two ‘end-segments’ starting at each of the two uniformly chosen vertices, and a middle segment. The two end-segments of any shortest path have length (Formula presented.)+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length (Formula presented.)+tight, and it contains only vertices with degree at least of order (Formula presented.), 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 (Formula presented.), and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.",
keywords = "Configuration model, Random networks, Scale free, Small world property, Truncated power law degrees, Typical distances",
author = "{van der Hofstad}, R. and J. Komj{\'a}thy",
year = "2017",
month = "9",
day = "4",
doi = "10.1007/s10955-017-1864-1",
language = "English",
volume = "169",
pages = "223--264",
journal = "Journal of Statistical Physics",
issn = "0022-4715",
publisher = "Springer",
number = "2",

}

When is a Scale-Free graph ultra-small? / van der Hofstad, R.; Komjáthy, J.

In: Journal of Statistical Physics, Vol. 169, No. 2, 04.09.2017, p. 223-264.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - When is a Scale-Free graph ultra-small?

AU - van der Hofstad, R.

AU - Komjáthy, J.

PY - 2017/9/4

Y1 - 2017/9/4

N2 - 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 (Formula presented.), up to value (Formula presented.) for some (Formula presented.) and (Formula presented.). This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law empirical degree distributions where the (possibly exponential) truncation happens at (Formula presented.). These examples are commonly observed in many real-life networks. We show that the graph distance between two uniformly chosen vertices centers around (Formula presented.), with tight fluctuations. Thus, the graph is an ultrasmall world whenever (Formula presented.). We determine the distribution of the fluctuations around this value, in particular we prove these form a sequence of tight random variables with distributions that show (Formula presented.)-periodicity, and as a result it is non-converging. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order (Formula presented.), where (Formula presented.) is a random variable that oscillates with n. We decompose shortest paths into three segments, two ‘end-segments’ starting at each of the two uniformly chosen vertices, and a middle segment. The two end-segments of any shortest path have length (Formula presented.)+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length (Formula presented.)+tight, and it contains only vertices with degree at least of order (Formula presented.), 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 (Formula presented.), and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.

AB - 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 (Formula presented.), up to value (Formula presented.) for some (Formula presented.) and (Formula presented.). This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law empirical degree distributions where the (possibly exponential) truncation happens at (Formula presented.). These examples are commonly observed in many real-life networks. We show that the graph distance between two uniformly chosen vertices centers around (Formula presented.), with tight fluctuations. Thus, the graph is an ultrasmall world whenever (Formula presented.). We determine the distribution of the fluctuations around this value, in particular we prove these form a sequence of tight random variables with distributions that show (Formula presented.)-periodicity, and as a result it is non-converging. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order (Formula presented.), where (Formula presented.) is a random variable that oscillates with n. We decompose shortest paths into three segments, two ‘end-segments’ starting at each of the two uniformly chosen vertices, and a middle segment. The two end-segments of any shortest path have length (Formula presented.)+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length (Formula presented.)+tight, and it contains only vertices with degree at least of order (Formula presented.), 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 (Formula presented.), and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.

KW - Configuration model

KW - Random networks

KW - Scale free

KW - Small world property

KW - Truncated power law degrees

KW - Typical distances

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

U2 - 10.1007/s10955-017-1864-1

DO - 10.1007/s10955-017-1864-1

M3 - Article

AN - SCOPUS:85028890747

VL - 169

SP - 223

EP - 264

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 2

ER -