DOE OSTI · 993122
Component evolution in general random intersection graphs
Abstract
We analyze component evolution in general random intersection graphs (RIGs) and give conditions on existence and uniqueness of the giant component. Our techniques generalize the existing methods for analysis on component evolution in RIGs. That is, 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 from the study on component evolution in Erdos-Renyi graphs. The main challenge becomes from the underlying structure of RIGs, when the number of offsprings follows a binomial distribution with a different number of nodes and different rate at each step during the evolution. RIGs can be interpreted as a model for large randomly formed non-metric data sets. Besides the mathematical analysis on component evolution, which we provide in this work, we perceive RIGs as an important random structure which has already found applications in social networks, epidemic networks, blog readership, or wireless sensor networks.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Bradonjic, Milan, Hagberg, Aric, Hengartner, Nick, Percus, Allon G. 2010-01-01. Component evolution in general random intersection graphs. https://doi.org/10.1007/978-3-642-18009-5_5
Cite the original work for its findings. Save a collection to share your selection of sources.