A note on the component structure in random intersection graphs with tunable clustering

MaRDI QIDQ1010663zbMATH OpenFDO

Authors M. Lindholm, Andreas Nordvall Lagerås

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0709.1416, https://eudml.org/doc/129823, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1n10.html

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

zbMATH Keywords

component structurelargest componentlogarithmic orderphase transitionrandom intersection graphstunable clustering

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the component structure in random intersection graphs with tunable clustering, and show that the average degree works as a threshold for a phase transition for the size of the largest component. That is, if the expected degree is less than one, the size of the largest component is a.a.s. of logarithmic order, but if the average degree is greater than one, a.a.s. a single large component of linear order emerges, and the size of the second largest component is at most of logarithmic order.

Review text

Summary: We study the component structure in random intersection graphs with tunable clustering, and show that the average degree works as a threshold for a phase transition for the size of the largest component. That is, if the expected degree is less than one, the size of the largest component is a.a.s.\ of logarithmic order, but if the average degree is greater than one, a.a.s.\ a single large component of linear order emerges, and the size of the second largest component is at most of logarithmic order.

Recommendations

• Component evolution in random intersection graphs
• The largest component in an inhomogeneous random intersection graph with clustering
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• The largest component in critical random intersection graphs
• Central limit theorem for the largest component of random intersection graph

Cited in

(12)

• The largest component in critical 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
• Size of the largest component in a critical graph
• Constructions of independent sets in random intersection graphs
• Clustering Coefficients of Random Intersection Graphs
• An elementary approach to component sizes in critical random graphs
• Phase transition in random intersection graphs with communities
• Clustering and percolation on superpositions of Bernoulli random graphs
• The number of triangles in random intersection graphs
• Component evolution in random intersection graphs
• The largest component in an inhomogeneous random intersection graph with clustering

This page was built for publication: A note on the component structure in random intersection graphs with tunable clustering

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