The largest component in an inhomogeneous random intersection graph with clustering

MaRDI QIDQ986718zbMATH OpenFDO

Authors Mindaugas Bloznelis

Publication date 12 August 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.4649, https://eudml.org/doc/223948, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r110.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of branching processes (60J85)

Abstract: Given b>0, integers n, m=bn and a probability measure Q on {0, 1,..., m}, consider the random intersection graph on the vertex set [n]={1, ..., n}, where i and j are declared adjacent whenever S(i) and S(j) intersect. Here S(1), ..., S(n) denote iid random subsets of [m] such that P(|S(i)|=k)=Q(k). For sparse random intersection graphs we establish a first order asymptotic for the order of the largest connected component N=n(1-Q(0))g+o(n) in probability. Here g is an average of nonextinction probabilities of a related multi-type Poisson branching process.

Review text

Summary: Given integers \(n\) and \(m=\lfloor\beta n\rfloor\) and a probability measure \(Q\) on \(\{0,1,\dots,m\}\), consider the random intersection graph on the vertex set \([n]= \{0,1,\dots,m\}\) where \(i,j\in [n]\) are declared adjacent whenever \(S(i)\cap S(j)\neq\emptyset\). Here \(S(1),\dots,S(n)\) denote the i.i.d. random subsets of \([m]\) with the distribution \({\mathbf P}(S(i)=A)= \binom{m}{|A|}^{-1} Q(|A|)\), \(A\subset [m]\). For sparse random intersection graphs, we establish a first-order asymptotic as \(n\to\infty\) for the order of the largest connected component \(N_1= n(1-Q(0))\rho+ o_P(n)\). Here \(\rho\) is the average of nonextinction probabilities of a related multitype Poisson branching process.

Recommendations

• Component evolution in general random intersection graphs
• Central limit theorem for the largest component of random intersection graph
• A note on the component structure in random intersection graphs with tunable clustering
• The largest component in critical random intersection graphs
• Component evolution in random intersection graphs

Cited in

(11)

• A note on the component structure in random intersection graphs with tunable clustering
• Degree and clustering coefficient in sparse random intersection graphs
• Central limit theorem for the largest component of random intersection graph
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• Clustering Coefficients of Random Intersection Graphs
• Degree distribution of an inhomogeneous random intersection graph
• Component evolution in general random intersection graphs
• On local weak limit and subgraph counts for sparse random graphs
• Phase transition in random intersection graphs with communities
• Clustering and percolation on superpositions of Bernoulli random graphs
• Near-critical bipartite configuration models and their associated intersection graphs

This page was built for publication: The largest component in an inhomogeneous random intersection graph with clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986718)