A note on loglog distances in a power law random intersection graph

2009/11/26 by Mindaugas P. Bloznelis, Bloznelis, Mindaugas P.
Mathematics · #05C80 #05C82 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:05C82

paper · pdf · doi:10.48550/arxiv.0911.5127

LaTex, 14 pages

arxiv created 2009/11/26 · arxiv updated 2009/12/08

Abstract

We consider the typical distance between vertices of the giant component of a random intersection graph having a power law (asymptotic) vertex degree distribution with infinite second moment. Given two vertices from the giant component we construct O(log log n) upper bound (in probability) for the length of the shortest path connecting them.

Related

• The shortest distance in random multi-type intersection graphs
• Typical distances in ultrasmall random networks
• Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
• On the robustness of power-law random graphs in the finite mean, infinite variance region
• Typical distances in a geometric model for complex networks