Clustering in a hyperbolic model of complex networks

Research output: Contribution to journalArticlepeer-review

Standard

Clustering in a hyperbolic model of complex networks. / Fountoulakis, Nikolaos; Muller, Tobias; Schepers, Markus; van der Hoorn, Pim.

In: Electronic Journal of Probability, Vol. 26, 25.01.2021, p. 1-132.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Fountoulakis, Nikolaos ; Muller, Tobias ; Schepers, Markus ; van der Hoorn, Pim. / Clustering in a hyperbolic model of complex networks. In: Electronic Journal of Probability. 2021 ; Vol. 26. pp. 1-132.

Bibtex

@article{2c1c73dfeff74041abba144b7fd9b187,
title = "Clustering in a hyperbolic model of complex networks",
abstract = "In this paper we consider the clustering coefficient, and clustering function in a random graph model proposed by Krioukov et al. in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most at a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution, “short distances” and a nonvanishing clustering coefficient. The model is specified using three parameters: The number of nodes n, which we think of as going to infinity, and α; v > 0, which we think of as constant. Roughly speaking, the parameter γ controls the power law exponent of the degree sequence and v the average degree. Here we show that the clustering coefficient tends in probability to a constant that we give explicitly as a closed form expression in terms of α; v and certain special functions. This improves earlier work by Gugelmann et al., who proved that the clustering coefficient remains bounded away from zero with high probability, but left open the issue of convergence to a limiting constant. Similarly, we are able to show that c(k), the average clustering coefficient over all vertices of degree exactly k, tends in probability to a limit γ(k) which we give explicitly as a closed form expression in terms of α; v and certain special functions. We are able to extend this last result also to sequences (k n) n where k n grows as a function of n. Our results show that (k) scales differently, as k grows, for different ranges of α. More precisely, there exists constants c α;I depending on α and v, such that as k →∞,γ(k) ~ c α;v k 2-4α if ½ < α < ¾,γ (k) ~ c α;v log(k) k -1 if α =¾ and γ (k) ~ c α;v k -1 when α > ¾. These results contradict a claim of Krioukov et al., which stated that γ (k) should always scale with k -1 as we let k grow. ",
keywords = "clustering coefficient, random graphs, hyperbolic plane, Random graphs, Hyperbolic random graph, Clustering",
author = "Nikolaos Fountoulakis and Tobias Muller and Markus Schepers and {van der Hoorn}, Pim",
note = "Funding Information: We are grateful to Dmitri Krioukov for pointing us to the problem of local clustering in this model and his helpful insights during discussions of the topic. We thank Remco van der Hofstad for pointing out a mistake in an earlier version of the proof of Theorem 1.3. We also thank an anonymous referee for his/her suggestions and comments on improving the manuscript. Nikolaos Fountoulakis was partially supported by the Alan Turing Institute, grant no. EP/N510129/1. Pim van der Hoorn was partially supported by ARO Grant W911NF-16-1-0391 and W911NF-17-1-0491. Tobias M?ller and Markus Schepers were partially supported by NWO grant 639.032.529. Tobias M?ller was additionally supported by NWO grant 612.001.409. Publisher Copyright: {\textcopyright} 2021, Institute of Mathematical Statistics. All rights reserved. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",
year = "2021",
month = jan,
day = "25",
doi = "10.1214/21-EJP583",
language = "English",
volume = "26",
pages = "1--132",
journal = "Electronic Journal of Probability",
issn = "1083-6489",
publisher = "Institute of Mathematical Statistics",

}

RIS

TY - JOUR

T1 - Clustering in a hyperbolic model of complex networks

AU - Fountoulakis, Nikolaos

AU - Muller, Tobias

AU - Schepers, Markus

AU - van der Hoorn, Pim

N1 - Funding Information: We are grateful to Dmitri Krioukov for pointing us to the problem of local clustering in this model and his helpful insights during discussions of the topic. We thank Remco van der Hofstad for pointing out a mistake in an earlier version of the proof of Theorem 1.3. We also thank an anonymous referee for his/her suggestions and comments on improving the manuscript. Nikolaos Fountoulakis was partially supported by the Alan Turing Institute, grant no. EP/N510129/1. Pim van der Hoorn was partially supported by ARO Grant W911NF-16-1-0391 and W911NF-17-1-0491. Tobias M?ller and Markus Schepers were partially supported by NWO grant 639.032.529. Tobias M?ller was additionally supported by NWO grant 612.001.409. Publisher Copyright: © 2021, Institute of Mathematical Statistics. All rights reserved. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/1/25

Y1 - 2021/1/25

N2 - In this paper we consider the clustering coefficient, and clustering function in a random graph model proposed by Krioukov et al. in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most at a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution, “short distances” and a nonvanishing clustering coefficient. The model is specified using three parameters: The number of nodes n, which we think of as going to infinity, and α; v > 0, which we think of as constant. Roughly speaking, the parameter γ controls the power law exponent of the degree sequence and v the average degree. Here we show that the clustering coefficient tends in probability to a constant that we give explicitly as a closed form expression in terms of α; v and certain special functions. This improves earlier work by Gugelmann et al., who proved that the clustering coefficient remains bounded away from zero with high probability, but left open the issue of convergence to a limiting constant. Similarly, we are able to show that c(k), the average clustering coefficient over all vertices of degree exactly k, tends in probability to a limit γ(k) which we give explicitly as a closed form expression in terms of α; v and certain special functions. We are able to extend this last result also to sequences (k n) n where k n grows as a function of n. Our results show that (k) scales differently, as k grows, for different ranges of α. More precisely, there exists constants c α;I depending on α and v, such that as k →∞,γ(k) ~ c α;v k 2-4α if ½ < α < ¾,γ (k) ~ c α;v log(k) k -1 if α =¾ and γ (k) ~ c α;v k -1 when α > ¾. These results contradict a claim of Krioukov et al., which stated that γ (k) should always scale with k -1 as we let k grow.

AB - In this paper we consider the clustering coefficient, and clustering function in a random graph model proposed by Krioukov et al. in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most at a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution, “short distances” and a nonvanishing clustering coefficient. The model is specified using three parameters: The number of nodes n, which we think of as going to infinity, and α; v > 0, which we think of as constant. Roughly speaking, the parameter γ controls the power law exponent of the degree sequence and v the average degree. Here we show that the clustering coefficient tends in probability to a constant that we give explicitly as a closed form expression in terms of α; v and certain special functions. This improves earlier work by Gugelmann et al., who proved that the clustering coefficient remains bounded away from zero with high probability, but left open the issue of convergence to a limiting constant. Similarly, we are able to show that c(k), the average clustering coefficient over all vertices of degree exactly k, tends in probability to a limit γ(k) which we give explicitly as a closed form expression in terms of α; v and certain special functions. We are able to extend this last result also to sequences (k n) n where k n grows as a function of n. Our results show that (k) scales differently, as k grows, for different ranges of α. More precisely, there exists constants c α;I depending on α and v, such that as k →∞,γ(k) ~ c α;v k 2-4α if ½ < α < ¾,γ (k) ~ c α;v log(k) k -1 if α =¾ and γ (k) ~ c α;v k -1 when α > ¾. These results contradict a claim of Krioukov et al., which stated that γ (k) should always scale with k -1 as we let k grow.

KW - clustering coefficient

KW - random graphs

KW - hyperbolic plane

KW - Random graphs

KW - Hyperbolic random graph

KW - Clustering

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

U2 - 10.1214/21-EJP583

DO - 10.1214/21-EJP583

M3 - Article

VL - 26

SP - 1

EP - 132

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

SN - 1083-6489

ER -