The shortest distance in random multi-type intersection graphs

2010/01/29 by A. D. Barbour, Barbour, A. D., Gesine Reinert +2
Computer Science · Mathematics · Physics and Astronomy · #05C80 #60E05 #60E17 #60F05 #60J85 #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST) #Stochastic processes and statistical mechanics #math.PR #math.ST #msc:05C80 #msc:60E05 #msc:60E17 #msc:60F05 #msc:60J85 #stat.TH

paper · pdf · doi:10.48550/arxiv.1001.5357

32 pages

arxiv created 2010/01/29 · openalex publication_date 2010/01/29 · arxiv updated 2010/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Using an associated branching process as the basis of our approximation, we show that typical inter-point distances in a multitype random intersection graph have a defective distribution, which is well described by a mixture of translated and scaled Gumbel distributions, the missing mass corresponding to the event that the vertices are not in the same component of the graph.

Related

• A note on loglog distances in a power law random intersection graph
• On the total variation distance between the binomial random graph and the random intersection graph
• The largest component in an inhomogeneous random intersection graph with clustering
• Random bipartite graphs with i.i.d. weights and applications to inhomogeneous random intersection graphs
• Traveling in randomly embedded random graphs