Component evolution in general random intersection graphs

DOI10.1007/978-3-642-18009-5_5MaRDI QIDQ3067505zbMATH OpenOpenAlexWikidataFDO

Authors Milan Bradonjić, Aric Hagberg, Allon G. Percus, Nicolas W. Hengartner

Publication date 21 January 2011

Published in Algorithms and Models for the Web-Graph (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.5475

zbMATH Keywords

branching processesgeneral random intersection graphsgiant componentrandom discrete structuresrandom graphsstochastic processes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of branching processes (60J85) Internet topics (68M11) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Random intersection graphs (RIGs) are an important random structure with applications in social networks, epidemic networks, blog readership, and wireless sensor networks. RIGs can be interpreted as a model for large randomly formed non-metric data sets. We analyze the component evolution in general RIGs, and give conditions on existence and uniqueness of the giant component. Our techniques generalize existing methods for analysis of component evolution: we analyze survival and extinction properties of a dependent, inhomogeneous Galton-Watson branching process on general RIGs. Our analysis relies on bounding the branching processes and inherits the fundamental concepts of the study of component evolution in ErdH{o}s-R'enyi graphs. The major challenge comes from the underlying structure of RIGs, which involves its both the set of nodes and the set of attributes, as well as the set of different probabilities among the nodes and attributes.

Recommendations

• Component evolution in random intersection graphs
• Component evolution in general random intersection graphs
• Phase transition in random intersection graphs with communities
• On Some Combinatorial Properties of Random Intersection Graphs

Cited in

(9)

• Selected Combinatorial Properties of Random Intersection Graphs
• Evolution of high-order connected components in random hypergraphs
• Degree distribution of an inhomogeneous random intersection graph
• The coupling method for inhomogeneous random intersection graphs.
• Component evolution in general random intersection graphs
• Phase transition in random intersection graphs with communities
• Clustering and percolation on superpositions of Bernoulli random graphs
• A survey on the Intersection graphs of ideals of rings
• Component evolution in random intersection graphs

This page was built for publication: Component evolution in general random intersection graphs

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