Hyperbolicity, degeneracy, and expansion of random intersection graphs.

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 $$\\log {n}$$logn. Further, we prove that when degenerate, the graphs generated by this model belong to a bounded-expansion graph class with high probability, a property particularly suitable for the design of linear time algorithms.