Connectivity threshold for superpositions of Bernoulli random graphs
The authors consider a random graph model generated by taking the union of several random graphs, with possibly different vertex sets, but all of them living inside a common ground set. The basic parameters of interest in their model are \(n\) (the total number of vertices in the ground set \(V\)) and \(m = m(n)\), which is the number of ``communities, i.e., random graphs. Then one considers a sequence of random variables \((X_{n,i}, Q_{n,i})\) for \(i \in \{1, \dotsc, m\}\), where \(X_{n,i} \in \{0, ..., n\}\) and \(Q_{n,i} \in [0,1]\). Then the \(i\)-th community \(G_i\) is generated by sampling a subset of \(V\) of size \(X_{n,i}\) and then adding every possible edge inside it independently with probability \(Q_{n,i}\). Finally, one considers \(G\) as the union of all the communities \(G_i\). This model is called ``community affiliation graph and was considered previously by \textit{J. Yang} and \textit{J. Leskovec} [ACM Trans. Intell. Syst. Technol. 5, No. 2, 1--35 (2014; \url{doi:10.1145/2594454})] motivated by algorithmic applications.\N\NThe authors consider the case where both \(n\) and \(m\) tend to infinity, and determine some technical, but natural, conditions on the random variables \((X_{n,i}, Q_{n,i})\) ensuring the final graph \(G\) is connected with high probability. The conditions recover some previously known cases in the literature.
- Approximating sparse graphs: The random overlapping communities model
- Bipartite structure of all complex networks
- Clustering and percolation on superpositions of Bernoulli random graphs
- Clustering coefficient of random intersection graphs with infinite degree variance
- Connectivity of inhomogeneous random graphs
- Connectivity of random hypergraphs with a given hyperedge size distribution
- Connectivity of the uniform random intersection graph
- Diameter, connectivity, and phase transition of the uniform random intersection graph
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- On local weak limit and subgraph counts for sparse random graphs
- Random graphs and complex networks. Volume 1
- Random intersection graphs with communities
- Two Models of Random Intersection Graphs and their Applications
- Zero-One Laws for Connectivity in Inhomogeneous Random Key Graphs
- Zero–One Laws for Connectivity in Random Key Graphs
This page was built for publication: Connectivity threshold for superpositions of Bernoulli random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6933582)
