Hyperbolicity, degeneracy, and expansion of random intersection graphs
arXiv:1409.8196
Abstract
We establish the conditions under which several algorithmically exploitable structural features hold for random intersection graphs, a natural model for many real-world networks where edges correspond to shared attributes. Specifically, we fully characterize the degeneracy of random intersection graphs, and prove that the model asymptotically almost surely produces graphs with hyperbolicity at least . Further, we prove that in the parametric regime where random intersection graphs are degenerate an even stronger notion of sparseness, so called bounded expansion, holds with high probability. We supplement our theoretical findings with experimental evaluations of the relevant statistics.
arXiv commentUpdating license to CC-BY
References in corpus (8)
- Random graphs with arbitrary degree distributions and their applications
- Hyperbolic Geometry of Complex Networks
- The Large Scale Curvature of Networks
- Characterisations and Examples of Graph Classes with Bounded Expansion
- Epidemics on random intersection graphs
- Assortativity and clustering of sparse random intersection graphs
- Connectivity in Secure Wireless Sensor Networks under Transmission Constraints
- On the Hyperbolicity of Small-World and Tree-Like Random Graphs