Rich-club connectivity dominates assortativity and transitivity of complex networks

Xiaoke Xu, Jie Zhang, Michael SmallarXiv 2010 · arXiv

Abstract

In network science, global statistical measures are often used to characterize the architecture of complex systems. However, research reveals a "tail wagging the dog" phenomenon: the global properties of an entire network can be dictated by a tiny elite of nodes. This "rich-club"—the most highly connected nodes—can dominate measures like assortativity and clustering, even when they represent less than 1% of the total population. This paper explores how manipulating this minority can radically alter the perceived topology of massive networks.

The Problem with Global Averages

Standard metrics such as the clustering coefficient (transitivity) and the assortativity coefficient (degree-degree correlation) provide a high-level view of network topology. In networks with skewed degree distributions, where a few "rich" nodes have vastly more connections than the "poor" majority, these global averages can be misleading. The researchers sought to determine if these metrics truly represent the network's overall structure or if they are merely artifacts of how the most influential nodes are interconnected.

Methodology: Manipulating the Elite

The study analyzed nine networks, including four synthetic models (Small-world, Erdős-Rényi, Barabási-Albert, and PFP) and five real-world datasets (US Power Grid, co-authorship networks, web links, Internet topology, and word adjacency).

The researchers employed a simple yet powerful experimental design:

  1. Identify the "Rich-Club": They isolated the top 0.5% of nodes with the highest degrees.
  2. Connectivity Manipulation: They compared the network's properties under two extreme scenarios for these nodes: making them "fully connected" (forming a clique) versus completely removing all edges between them.
  3. Global Impact Assessment: They recalculated global assortativity ($r$), clustering ($c$), and average path length ($l$) to observe how the wiring of this 0.5% minority affected the entire system.
Schematic of a rich-club core where high-degree nodes ($c_1-c_4$) are densely interconnected, influencing the global topology.

Key Results and Structural Regimes

The results demonstrated that the rich-club's influence is both profound and predictable. As shown in the data table below, the presence or absence of a rich-club can flip the perceived nature of a network.

Table of network parameters and the resulting global metrics ($r, c, l$) for various models and real-world networks.

Assortativity and Clustering

In the Small-World (SW) model, adding a rich-club shifted the assortativity coefficient ($r$) from a neutral 0.00 to a highly assortative 0.69, despite 99.5% of the nodes remaining unchanged. Similarly, in the PFP Internet model, the rich-club nearly doubled the clustering coefficient ($c$), increasing it from 0.15 to 0.28. This proves that the Internet’s observed transitivity is almost entirely a product of its highly interconnected core routers.

The $k_{max}/k_s$ Ratio

The authors identified two distinct structural regimes based on the ratio of the maximum degree ($k_{max}$) to the structural cutoff ($k_s$):

  • Low $k_{max}/k_s$ (e.g., Power Grid, Small-World): The rich-club primarily controls assortativity.
  • High $k_{max}/k_s$ (e.g., Internet, Word Networks): The rich-club primarily controls clustering (transitivity).

The "Shortcut" Effect

Beyond social cohesion, the rich-club acts as a critical infrastructure for navigation. Even though they are a tiny fraction of the nodes, their interconnection significantly reduces the average shortest path ($l$) across the entire network. By providing high-speed "shortcuts," the rich-club ensures efficient communication across disparate parts of the system.

Conclusion

This study highlights that the "social cohesion" of many complex systems is essentially the cohesion of its most influential members. While the current research focused on undirected and unweighted networks, it opens the door for investigating how rich-club dynamics affect processes like epidemic spreading or information flow. Understanding that global metrics can be "hijacked" by a small core is crucial for accurately modeling and protecting critical infrastructure.

Summary updated

BibTeX
@misc{xu2010rich,
  author = {Xiaoke Xu and Jie Zhang and Michael Small},
  title = {{Rich-club connectivity dominates assortativity and transitivity of complex networks}},
  year = {2010},
  eprint = {1010.1705},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1010.1705},
}
Figure