Standard

Evolution of a Modified Binomial Random Graph by Agglomeration. / Kang, Mihyun; Pachon, Angelica; Rodríguez, Pablo M.

In: Journal of Statistical Physics, Vol. 170, No. 3, 15.12.2017, p. 509-535.

Research output: Contribution to journalArticle

Harvard

Kang, M, Pachon, A & Rodríguez, PM 2017, 'Evolution of a Modified Binomial Random Graph by Agglomeration', Journal of Statistical Physics, vol. 170, no. 3, pp. 509-535. https://doi.org/10.1007/s10955-017-1940-6

APA

Kang, M., Pachon, A., & Rodríguez, P. M. (2017). Evolution of a Modified Binomial Random Graph by Agglomeration. Journal of Statistical Physics, 170(3), 509-535. https://doi.org/10.1007/s10955-017-1940-6

Vancouver

Kang M, Pachon A, Rodríguez PM. Evolution of a Modified Binomial Random Graph by Agglomeration. Journal of Statistical Physics. 2017 Dec 15;170(3):509-535. https://doi.org/10.1007/s10955-017-1940-6

Author

Kang, Mihyun ; Pachon, Angelica ; Rodríguez, Pablo M. / Evolution of a Modified Binomial Random Graph by Agglomeration. In: Journal of Statistical Physics. 2017 ; Vol. 170, No. 3. pp. 509-535.

BibTeX

@article{0d1bd91888624245a997551a178df033,
title = "Evolution of a Modified Binomial Random Graph by Agglomeration",
abstract = "In the classical Erdős–R{\'e}nyi random graph G(n, p) there are n vertices and each of the possible edges is independently present with probability p. The random graph G(n, p) is homogeneous in the sense that all vertices have the same characteristics. On the other hand, numerous real-world networks are inhomogeneous in this respect. Such an inhomogeneity of vertices may influence the connection probability between pairs of vertices. The purpose of this paper is to propose a new inhomogeneous random graph model which is obtained in a constructive way from the Erdős-R{\'e}nyi random graph G(n, p). Given a configuration of n vertices arranged in N subsets of vertices (we call each subset a super-vertex), we define a random graph with N super-vertices by letting two super-vertices be connected if and only if there is at least one edge between them in G(n, p). Our main result concerns the threshold for connectedness. We also analyze the phase transition for the emergence of the giant component and the degree distribution. Even though our model begins with G(n, p), it assumes the existence of some community structure encoded in the configuration. Furthermore, under certain conditions it exhibits a power law degree distribution. Both properties are important for real-world applications.",
keywords = "Connectedness, Erdős–R{\'e}nyi model, Inhomogeneous random graph, Phase transition, Random graph",
author = "Mihyun Kang and Angelica Pachon and Rodr{\'i}guez, {Pablo M.}",
year = "2017",
month = "12",
day = "15",
doi = "10.1007/s10955-017-1940-6",
language = "English",
volume = "170",
pages = "509--535",
journal = "Journal of Statistical Physics",
issn = "0022-4715",
publisher = "Springer Verlag",
number = "3",

}

RIS

TY - JOUR

T1 - Evolution of a Modified Binomial Random Graph by Agglomeration

AU - Kang, Mihyun

AU - Pachon, Angelica

AU - Rodríguez, Pablo M.

PY - 2017/12/15

Y1 - 2017/12/15

N2 - In the classical Erdős–Rényi random graph G(n, p) there are n vertices and each of the possible edges is independently present with probability p. The random graph G(n, p) is homogeneous in the sense that all vertices have the same characteristics. On the other hand, numerous real-world networks are inhomogeneous in this respect. Such an inhomogeneity of vertices may influence the connection probability between pairs of vertices. The purpose of this paper is to propose a new inhomogeneous random graph model which is obtained in a constructive way from the Erdős-Rényi random graph G(n, p). Given a configuration of n vertices arranged in N subsets of vertices (we call each subset a super-vertex), we define a random graph with N super-vertices by letting two super-vertices be connected if and only if there is at least one edge between them in G(n, p). Our main result concerns the threshold for connectedness. We also analyze the phase transition for the emergence of the giant component and the degree distribution. Even though our model begins with G(n, p), it assumes the existence of some community structure encoded in the configuration. Furthermore, under certain conditions it exhibits a power law degree distribution. Both properties are important for real-world applications.

AB - In the classical Erdős–Rényi random graph G(n, p) there are n vertices and each of the possible edges is independently present with probability p. The random graph G(n, p) is homogeneous in the sense that all vertices have the same characteristics. On the other hand, numerous real-world networks are inhomogeneous in this respect. Such an inhomogeneity of vertices may influence the connection probability between pairs of vertices. The purpose of this paper is to propose a new inhomogeneous random graph model which is obtained in a constructive way from the Erdős-Rényi random graph G(n, p). Given a configuration of n vertices arranged in N subsets of vertices (we call each subset a super-vertex), we define a random graph with N super-vertices by letting two super-vertices be connected if and only if there is at least one edge between them in G(n, p). Our main result concerns the threshold for connectedness. We also analyze the phase transition for the emergence of the giant component and the degree distribution. Even though our model begins with G(n, p), it assumes the existence of some community structure encoded in the configuration. Furthermore, under certain conditions it exhibits a power law degree distribution. Both properties are important for real-world applications.

KW - Connectedness

KW - Erdős–Rényi model

KW - Inhomogeneous random graph

KW - Phase transition

KW - Random graph

U2 - 10.1007/s10955-017-1940-6

DO - 10.1007/s10955-017-1940-6

M3 - Article

AN - SCOPUS:85038084110

VL - 170

SP - 509

EP - 535

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 3

ER -

ID: 2840744