Connectivity of a family of bilateral preference random graphs

Hossein Dabirian, Vijay SubramanianJournal of Applied Probability 2025 · DOI

TL;DR

This paper analyzes a specific type of random graph called "bilateral preference graphs" (LK(n,k)). The authors prove a conjecture that the connectivity of these graphs hinges on the parameter k being around log(n), providing a precise threshold. They also characterize the average degree of vertices in these graphs, offering a deeper understanding of their structure.

What Problem Does This Paper Address?

Random graph models are crucial for understanding complex networks, from social interactions to biological systems. While Erdős-Rényi (ER) graphs are a foundational model, they assume independent edge formation, which doesn't capture the nuanced preferences often seen in real-world networks. The La and Kabkab (LK) model introduces "bilateral preference," where an edge exists only if both endpoints mutually prefer it based on their k most preferred neighbors. This paper tackles two main questions about LK graphs:

  1. Connectivity Threshold: What is the critical value of k that determines whether the graph is connected or not? La and Kabkab conjectured that this threshold is k = log(n), and this paper aims to prove and refine this conjecture.
  2. Average Degree Behavior: How does the average number of connections per vertex behave as the graph grows large (n → ∞)? Understanding this helps characterize the graph's overall density and structure.

Methods

The authors employ a combination of probabilistic and combinatorial techniques:

  • Second Moment Method: Used to prove disconnectedness by showing that the expected number of isolated vertices grows to infinity.
  • Erdős-Rényi Sub- and Super-graphs: The approach of La and Kabkab is extended to find ER graphs that are contained within or contain the LK graph. This allows leveraging known results about ER graph connectivity.
  • Asymptotic Analysis: Techniques like Stirling's approximation and detailed analysis of combinatorial sums are used to derive precise asymptotic behaviors for probabilities and expected values.
  • Infinite Urn Model: This abstraction is used to connect probabilities in finite permutation spaces to binomial and negative multinomial distributions, simplifying complex calculations.
  • Bernstein Inequality: Applied to bound probabilities related to vertex isolation.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of a random graph model, not empirical evaluation on datasets.

Key Insights and Ideas

  • The log(n) Connectivity Threshold: The paper confirms and refines the conjecture that k = log(n) is the critical point for connectivity in LK graphs. This is a significant result, as it mirrors the connectivity threshold of ER graphs, despite the fundamentally different edge formation mechanism (bilateral preference vs. independent edges).
  • Finer Window Analysis: Beyond just the threshold, the paper provides a more detailed understanding of the "window" around log(n) where connectivity transitions from unlikely to likely.
  • Average Degree Correction: The authors provide a more precise asymptotic characterization of the average degree than previously conjectured, correcting an earlier approximation.
  • Dependencies Don't Break Connectivity Intuition: Despite the inherent dependencies in LK graph construction (unlike ER graphs), the intuition that a mean degree greater than log(n) implies connectivity and a mean degree less than log(n) implies isolated vertices still holds.

Key Results

  • Theorem 1.1: Establishes the connectivity threshold for LK(n,k) graphs. For k ≤ log(n) + t' log log(n)√log(n) with t' < -1/2, the graph is disconnected with high probability. For k > log(n) + t' log log(n)√log(n) with t' > 1/2, the graph is connected with high probability.
  • Theorem 1.2: Provides asymptotic behavior for the mean degree E[D]. For k = o(√n), E[D] = k - [(2k-1)(2k-2)/(k-1)] * O(k²/n). For k = o(n¹/3) and k → ∞, E[D] = k - √(π/k) + O(1/√k).
  • Theorem 4.1: Proves that for k ≤ log(n) + t' log log(n)√log(n) with t' < -1/2, the graph is disconnected with high probability.
  • Theorem 5.3: Proves that for k ≥ log(n) + t' log log(n)√log(n) with t' > 1/2, the graph is connected with high probability.

Limitations and Future Work

  • Open Problem on the Exact Threshold Window: The paper notes that there's still a gap in precisely identifying the connectivity threshold for a specific range of k values (log(n) – 0.5 log log(n)√log(n) ≤ k ≤ log(n) + 0.5 log log(n)√log(n)). This is attributed to the complexity of the dependencies in the LK model.
  • Diameter Characterization: While La and Kabkab determined the diameter for some k, characterizing it for the additional range of k where connectivity holds remains an open problem.
  • Limiting Distribution of Degree: Finding the limiting distribution of (D - E[D])/√Var[D] is identified as a challenging open problem due to the complicated dependence structure.
  • Concentration of Node Degrees: Generalizing concentration of node degrees around the mean degree (as seen in ER graphs) to LK graphs under certain conditions is suggested for future work.
  • Simpler Conditions: The authors mention that developing analytically simpler sufficient conditions for connectivity could be a direction for future research.

Summary updated

Abstract

Abstract We study the bilateral preference graphs $\mathit{LK}(n, k)$ of La and Kabkab, obtained as follows. Put independent and uniform [0, 1] weights on the edges of the complete graph $K_n$ . Then, each edge ( i , j ) is included in $\mathit{LK}(n,k)$ if it is bilaterally preferred, in the sense that it is among the k edges of lowest weight incident to vertex i , and among the k edges of lowest weight incident to vertex j . We show that $k = \log(n)$ is the connectivity threshold, solving a conjecture of La and Kabkab, and obtaining finer results about the window. We also investigate the asymptotic behavior of the average degree of vertices in $\mathit{LK}(n, k)$ as $n\rightarrow\infty$ .
BibTeX
@article{dabirian2025connectivity,
  author = {Hossein Dabirian and Vijay Subramanian},
  title = {{Connectivity of a family of bilateral preference random graphs}},
  journal = {Journal of Applied Probability},
  year = {2025},
  doi = {10.1017/jpr.2025.10051},
}
Figure