When is a Scale-Free graph ultra-small?

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Citaties (Scopus)

Uittreksel

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.

TaalEngels
Pagina's223-264
Aantal pagina's42
TijdschriftJournal of Statistical Physics
Volume169
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 4 sep 2017

Vingerafdruk

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

Trefwoorden

    Citeer dit

    @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, Nr. 2, 04.09.2017, blz. 223-264.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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

    VL - 169

    SP - 223

    EP - 264

    JO - Journal of Statistical Physics

    T2 - Journal of Statistical Physics

    JF - Journal of Statistical Physics

    SN - 0022-4715

    IS - 2

    ER -