Distribution-Free Models of Social Networks

Tim Roughgarden, C. Seshadhri

TL;DR

This paper explores new ways to model social networks that go beyond traditional probabilistic approaches. Instead of assuming specific distributions, it focuses on deterministic structural properties like triadic closure and power-law degree distributions. This shift allows for more robust theoretical guarantees and better explanations for why simple algorithms perform surprisingly well on real-world network data.

What Problem Does This Paper Address?

Social networks, like those formed by friendships on Facebook or followers on Twitter, exhibit predictable structures that are not well-captured by standard random graph models (e.g., Erdős-Rényi). These structures include heavy-tailed degree distributions, triadic closure (friends of friends tend to be friends), community-like clusters, and the small-world property. Traditional approaches often rely on generative models, which are hard to validate and can lead to results that are artifacts of the chosen model. This paper addresses the challenge of developing more robust models that capture these essential network properties deterministically, enabling stronger theoretical guarantees for algorithms and a better understanding of their practical effectiveness.

Methods

The paper introduces and analyzes several classes of graphs defined by deterministic combinatorial properties:

  • c-Closed Graphs: These graphs model strong triadic closure, where if two nodes share at least c common neighbors, they are directly connected. This is a more stringent condition than observed in real networks but serves as a foundation.
  • Weakly c-Closed Graphs: A relaxation where every induced subgraph must contain at least one "c-good" vertex (a vertex that satisfies the c-closure property with respect to its neighbors in that subgraph). This class is more amenable to algorithmic analysis.
  • d-Triangle-Dense Graphs: These graphs are characterized by a constant fraction of "wedges" (two-hop paths) forming triangles. This property is related to triadic closure and is measured by triangle density.
  • Power-Law Bounded (PLB) Graphs: These graphs generalize the power-law degree distribution assumption. Instead of requiring a strict power-law fit for all degrees, they ensure that the average degree distribution over intervals follows a power law. This is considered a more realistic and robust assumption for real-world networks.
  • BCT Model: A set of deterministic metric properties inspired by random graphs, designed to capture properties related to shortest paths and graph diameter.

The paper then explores algorithmic implications for these graph classes, particularly focusing on problems like maximum clique enumeration and triangle counting. It shows how these structural properties lead to improved algorithmic performance compared to general graphs.

Datasets

The paper references several real-world social network datasets for empirical validation and illustration:

  • Enron email network: Used to illustrate triadic closure properties.
  • SNAP (Stanford Large Network Dataset) collection: Specifically mentions "p2p-Gnutella04," "wiki-Vote," and "ca-GrQc" for analyzing c-closure properties.
  • Facebook graph: Mentioned in the context of triangle density.

No new datasets are introduced in this paper.

Key Insights and Ideas

  • Deterministic Models for Robustness: Moving from probabilistic generative models to deterministic combinatorial properties (like c-closure or triangle density) provides stronger theoretical guarantees. Algorithms designed for these classes are less susceptible to the specific choices of generative models.
  • Triadic Closure and Cliques: Strong triadic closure (modeled by c-closed graphs) has implications for efficiently finding maximal cliques, a fundamental problem in social network analysis.
  • Triangle Density as a Proxy: Triangle density offers a coarse but useful measure of triadic closure, distinguishing real networks from random graphs.
  • Power-Law Bounded Graphs Offer Algorithmic Advantages: PLB graphs, a more robust version of power-law degree distributions, allow for faster algorithms for problems like triangle counting and clique enumeration. This is because they control the number of high-degree vertices and the overall number of wedges.
  • Simple Heuristics Work Well for a Reason: The BCT model provides a theoretical framework to explain why simple heuristics (like the TwoSweep algorithm for diameter computation) perform well on real-world networks, by showing that distances can often be approximated by sums of vertex-specific quantities.

Key Results

  • Maximum Clique in Weakly c-Closed Graphs: The maximum clique problem is polynomial-time solvable in weakly c-closed graphs when c is a constant, with the number of maximal cliques bounded by $O(n^2 \cdot 3^{(c-1)/3})$. This implies polynomial solvability for $c = O(\log n)$.
  • Triangle Density and Inverse Theorems: For d-triangle-dense graphs, an "inverse theorem" guarantees the existence of a "tightly-knit family" that captures a constant fraction of the graph's triangles.
  • Triangle Counting in PLB Graphs: Triangle counting can be performed efficiently in PLB graphs. For exponent $\gamma=3$, it takes $O(n \log n)$ time, and for $\gamma > 3$, it takes $O(n)$ time. For $\gamma \in (2,3)$, a more refined analysis yields $O(n^{3/\gamma})$ time.
  • Diameter Approximation: The BCT model provides theoretical justification for heuristics like the TwoSweep algorithm, showing they can approximate the graph diameter well by bounding vertex eccentricities.

Limitations and Future Work

  • Open Problems in c-Closed Graphs: The paper poses open questions about the tightness of bounds on maximal cliques in c-closed graphs and the possibility of linear-time algorithms for enumeration.
  • Improving Triangle Density Bounds: Further research is suggested to improve the constant in the exponent of the inverse theorem for triangle-dense graphs and to explore additional assumptions beyond average triangle density.
  • Algorithmic Applications of Tightly-Knit Families: The paper asks if there are compelling algorithmic applications for graphs that can be approximated by tightly-knit families.
  • Triangle Conductance and Communities: The paper highlights the observation that low triangle conductance cuts yield more meaningful communities and poses the question of finding a theoretical explanation.
  • Developing New Practical Algorithms: A general goal is to leverage the theoretical insights from these models to develop new, practical algorithms for fundamental graph problems.
  • BCT Model Nuances: The paper acknowledges that the BCT model has a more nuanced version of its properties than presented, involving vertex degrees and approximate power-law distributions, which were simplified for exposition.

Summary updated

Abstract

The structure of large-scale social networks has predominantly been articulated using generative models, a form of average-case analysis. This chapter surveys recent proposals of more robust models of such networks. These models posit deterministic and empirically supported combinatorial structure rather than a specific probability distribution. We discuss the formal definitions of these models and how they relate to empirical observations in social networks, as well as the known structural and algorithmic results for the corresponding graph classes.
BibTeX
@inproceedings{roughgarden2020distribution,
  author = {Tim Roughgarden and C. Seshadhri},
  title = {{Distribution-Free Models of Social Networks}},
  booktitle = {Beyond the Worst-Case Analysis of Algorithms},
  year = {2020},
  url = {https://openreview.net/forum?id=JGKJXiK2b1},
}
Figure