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 in this distribution corresponds to the event that the vertices are not in the same component of the graph.
Introduction
Many real-world networks are fundamentally bipartite in nature, representing relationships between two distinct sets of entities—such as directors and the boards they serve on, or genes and the biological properties they regulate. In these contexts, researchers are often interested in the "induced" graph, known as an intersection graph. For example, in a network of directors, a link exists between two individuals if they share a seat on at least one common board.
While simple random graph models like the Erdős–Rényi model are well-understood, they often fail to capture the "multi-type" complexity of real-world systems where different categories of actors interact with varying probabilities. This paper addresses a fundamental question in network theory: In a large, multi-type random intersection graph, what is the probability distribution of the shortest path length between two randomly chosen points, and how accurate are our mathematical approximations for finite networks?
Methodology
The authors employ a sophisticated probabilistic framework to approximate distances, relying on three primary pillars:
1. Multitype Branching Processes
The local neighborhood of a vertex is modeled as a branching process that grows in generations. The growth rate of this process is determined by the largest eigenvalue ($\tau$) of the mean offspring matrix. By analyzing this spectral property, the authors can estimate the number of reachable nodes at each step of the path-finding process.
2. Poisson Approximation and Coupling
To transition from an infinite branching process to a finite graph, the authors use a Poisson approximation to account for "coincidences"—instances where different branches of the process intersect at the same vertex. A significant challenge involves managing "ghosts"—nodes that appear in the theoretical branching process but cannot exist in the actual graph because their index has already been claimed. The paper provides rigorous coupling bounds to prove that these ghosts do not significantly distort distance calculations.
3. Extreme Value Theory
The limiting distribution of the distance is derived using Extreme Value Theory. The authors demonstrate that the shortest path length is related to the Gumbel distribution, which typically arises when analyzing the minimum or maximum of a large set of random variables.
Key Insights
The Spectral Connection
The "speed" at which a network is traversed is dictated by the principal eigenvalue ($\tau$) of the mean matrix of the associated branching process. If the matrix of connection probabilities between types is known, the average distance can be predicted with high precision.
Defective Distributions
In these graphs, there is a non-trivial probability that two nodes are not connected at all (distance = $\infty$). The authors handle this by utilizing a "defective" distribution, where the total probability of all finite distances sums to less than 1. The "missing" mass represents the probability that the two nodes belong to different components.
Rank-1 Minimality
The research explores exponential random graph models where connection probability is a simple product of vertex and object weights. The authors show that these models provide a lower bound for the eigenvalue $\tau$, establishing a baseline for network connectivity.
Key Results
- Distance Scaling: The shortest distance $D$ between two nodes of types $k_1$ and $k_2$ scales according to the relationship $\log n / \log \tau$, where $n$ is the number of vertices.
- Explicit Error Bounds: The authors provide a rate of convergence for their approximations, showing that the error behaves like $n^{-1/4}$ (the inverse fourth root of the number of vertices).
- Distributional Form: The probability $P(D > d)$ is shown to be approximately $E[\exp(-W^A W^B \kappa \tau^u \phi(n))]$, where $W^A$ and $W^B$ are random variables representing the long-term survival of the branching processes starting from the two nodes.
Limitations and Future Work
The current analysis is specifically tuned to the 2-periodic structure of bipartite graphs. While the authors provide remarks on unipartite (general) graphs, the bipartite case requires more complex eigenvalue handling. Additionally, the "standard asymptotics" assume that the number of objects ($m$) and vertices ($n$) grow at comparable rates. If the ratio $m/n$ becomes very small, the graph likely becomes disconnected, rendering the distance infinite with high probability. Future research may further relax the assumption that link probabilities depend solely on vertex and object types to better model highly irregular networks.
Summary updated