Evolution of a Modified Binomial Random Graph by Agglomeration

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 n...

Full description

Saved in:
Bibliographic Details
Published in:Journal of statistical physics 2018-02, Vol.170 (3), p.509-535
Main Authors: Kang, Mihyun, Pachon, Angelica, Rodríguez, Pablo M.
Format: Article
Language:English
Subjects:
AGGLOMERATION
Coding
CONFIGURATION
Configurations
DISTRIBUTION
EVOLUTION
GRAPH THEORY
Inhomogeneity
Mathematical and Computational Physics
MATHEMATICAL METHODS AND COMPUTING
PHASE TRANSFORMATIONS
Phase transitions
Physical Chemistry
Physics
Physics and Astronomy
PROBABILITY
Quantum Physics
RANDOMNESS
Statistical Physics and Dynamical Systems
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-4715
1572-9613
DOI:10.1007/s10955-017-1940-6