Remarks on Category-Based Routing in Social Networks

Karl Bringmann, Kurt Mehlhorn, Adrian NeumannarXiv 2012 · arXiv

Introduction: The Mystery of the Small World

The "six degrees of separation" phenomenon suggests that any two people on Earth are connected by a short chain of acquaintances. However, the true scientific puzzle is not just the existence of these short paths, but how individuals can efficiently find them using only local information. Sociological theories propose that humans use a "greedy" strategy, passing messages to the acquaintance most similar to the target based on social categories like geography or occupation.

In 2011, Eppstein et al. formalized this as category-based routing. This research investigates the "membership dimension"—the number of categories a person must belong to for this greedy strategy to always succeed. If this number is too high, the model becomes cognitively implausible. This paper establishes tighter mathematical bounds for this dimension, supporting the feasibility of human-driven social routing.

Category-based routing on a simple path graph.

Methodology: Combinatorial Analysis and Tree Decomposition

The authors employ graph theory to define a "good" category system: one where every node can always identify a neighbor "closer" to any target. Distance is measured by the discrepancy in category memberships between the current node and the target.

To derive these bounds, the paper utilizes several key techniques:

  • Recursive Tree Decomposition: To establish upper bounds, the authors use "balanced routing cuts" on spanning trees. By splitting a tree into smaller components and building categories that route toward the split point, they can recursively define a global routing system.
  • Rectangle Covering & Anti-chains: For lower bounds in specific topologies like "star" graphs, the problem is reduced to the rectangle covering problem, utilizing the properties of anti-chains in binary vectors.
  • Hypercube Measures: A universal lower bound is derived by defining measures on high-dimensional hypercubes, demonstrating that insufficient categories lead to overlapping similarity patterns that break greedy routing.
The recursive process of building category systems on trees.

Key Insights and Theoretical Results

The research provides a significant tightening of the mathematical envelope for category-based routing:

  1. Diameter as a Fundamental Limit: The membership dimension must be at least as large as the graph's diameter. Granularity is required to distinguish nodes across long paths.
  2. Logarithmic Cognitive Load: For many common network structures, the required number of categories is logarithmic relative to the network size. This suggests that humans only need to track a manageable amount of information to be efficient routers.
  3. The Connectivity Paradox: While higher connectivity (average degree $\delta$) usually shortens paths, it actually increases the categorical requirements. More neighbors create more potential "wrong turns," requiring more information to disambiguate the correct path.

Improved Bounds

The paper proves that for any graph $G$, a membership dimension of $O(\text{diam}(G) \cdot \log(2|V|/\text{diam}(G)))$ is sufficient. This is a major improvement over previous bounds. Furthermore, they establish a universal lower bound of $\Omega(\text{diam}(G) + \frac{\log |V|}{\log \delta})$. For bounded-degree graphs, these bounds nearly meet, effectively characterizing the complexity of the model.

Conclusion and Future Directions

While this work refines the theoretical foundation of social routing, limitations remain. Real-world social networks often follow power-law distributions and high clustering, which differ from the idealized graphs used here. Additionally, the model assumes 100% success for greedy routing; relaxing this to allow for occasional backtracking or random steps might further reduce the informational requirements. Future research may also explore how the "expansion" properties of a graph influence the necessary membership dimension.

Summary updated

Abstract

It is well known that individuals can route messages on short paths through social networks, given only simple information about the target and using only local knowledge about the topology. Sociologists conjecture that people find routes greedily by passing the message to an acquaintance that has more in common with the target than themselves, e.g. if a dentist in Saarbr\"ucken wants to send a message to a specific lawyer in Munich, he may forward it to someone who is a lawyer and/or lives in Munich. Modelling this setting, Eppstein et al. introduced the notion of category-based routing. The goal is to assign a set of categories to each node of a graph such that greedy routing is possible. By proving bounds on the number of categories a node has to be in we can argue about the plausibility of the underlying sociological model. In this paper we substantially improve the upper bounds introduced by Eppstein et al. and prove new lower bounds.
BibTeX
@misc{bringmann2012remarks,
  author = {Karl Bringmann and Kurt Mehlhorn and Adrian Neumann},
  title = {{Remarks on Category-Based Routing in Social Networks}},
  year = {2012},
  eprint = {1202.2293},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1202.2293},
}
Figure