An alternative approach to determining average distance in a class of scale-free modular networks

Zhongzhi Zhang, Lin YuanJournal of Statistical Mechanics Theory and Experiment 2010 · DOI · arXiv

Abstract: Various real-life networks of current interest are simultaneously scale-free and modular. Here we study analytically the average distance in a class of deterministically growing scale-free modular networks. By virtue of the recursive relations derived from the self-similar structure of the networks, we compute rigorously this important quantity, obtaining an explicit closed-form solution, which recovers the previous result and is corroborated by extensive numerical calculations. The obtained exact expression shows that the average distance scales logarithmically with the number of nodes in the networks, indicating an existence of small-world behavior. We present that this small-world phenomenon comes from the peculiar architecture of the network family.

Introduction

In the study of complex systems—ranging from metabolic pathways to social media—two properties often appear simultaneously: scale-free distributions (where a few "hubs" have many connections while most nodes have few) and modular structure (where nodes form dense local clusters).

Calculating the "average distance" (the mean number of steps to get from any node to another) is a fundamental way to understand how efficiently information or diseases spread through these networks. However, calculating this for complex, growing networks is mathematically taxing. Previous attempts relied on complex mappings to physics models, such as the Potts model. This paper seeks a more direct, analytical approach to find an exact formula for average distance in a specific, popular model of these networks known as the Ravasz-Barabási (RB) model.

Methodology: Deterministic Growth and Recursion

The authors utilize the deterministic nature of the RB model. Unlike random networks, the RB model grows through a specific iterative process. It begins with a small complete graph of $m$ nodes. To create the next generation, $m-1$ replicas of the previous generation are made, and their peripheral nodes are connected to the central hub of the original unit.

The hierarchical structure of a modular scale-free network, illustrating the recursive arrangement of nodes and hubs.

Because the network is self-similar (the whole looks like a collection of its parts), the authors established recursion relations. They broke the total distance down into three manageable parts: the distance within existing modules, the distance from nodes to the central "hub," and the distance from nodes to the "peripheral" nodes. By solving these simultaneous equations inductively, they moved from simple base cases to a general formula that describes the network at any stage of its growth ($g$).

Key Results and Verification

The primary achievement of this work is the derivation of an exact closed-form expression for total distance ($D_g$) and average distance ($d_g$). For a network with $N_g$ nodes, the average distance is shown to be approximately:

$$d_g \approx \frac{4(m-1)}{m^2 \ln m} \ln N_g$$

This result rigorously confirms that as the network grows to an infinite size, the average distance remains manageable, scaling logarithmically with the number of nodes. This indicates "small-world" behavior, which is distinct from the "ultra-small-world" behavior (double-logarithmic growth) seen in non-modular scale-free networks. Essentially, modularity makes the network slightly "longer" but more organized.

Average distance $d_g$ as a function of network size $N_g$ for different branching factors $m$, showing the perfect overlap between theoretical lines and numerical data.

As shown in the figure above, there is a perfect overlap between the theoretical lines and the numerical data points across different network sizes and branching factors ($m=3, 4, 5$), proving the formula's accuracy.

Discussion and Future Work

The study highlights the "bridge" role of hubs. In this modular model, large hubs are not directly linked; instead, they are connected via layers of smaller nodes. Despite this indirect connection, the hubs act as essential bridges that maintain low average distances.

The primary limitation of this approach is its reliance on the strictly deterministic nature of the RB model. Real-world networks often contain stochastic (random) elements that this specific recursive method might not easily capture. Furthermore, while the paper identifies that modularity increases average distance compared to random counterparts, the deeper mechanical reasons for this dissimilarity require further investigation. Future research could explore how this specific architecture affects dynamic processes like synchronization, random walks, or epidemic spreading.

Summary updated

Abstract

Various real-life networks of current interest are simultaneously scale-free and modular. Here we study analytically the average distance in a class of deterministically growing scale-free modular networks. By virtue of the recursive relations derived from the self-similar structure of the networks, we compute rigorously this important quantity, obtaining an explicit closed-form solution, which recovers the previous result and is corroborated by extensive numerical calculations. The obtained exact expression shows that the average distance scales logarithmically with the number of nodes in the networks, indicating an existence of small-world behavior. We present that this small-world phenomenon comes from the peculiar architecture of the network family.
BibTeX
@article{zhang2010alternative,
  author = {Zhongzhi Zhang and Lin Yuan},
  title = {{An alternative approach to determining average distance in a class of scale-free modular networks}},
  journal = {Journal of Statistical Mechanics Theory and Experiment},
  year = {2010},
  doi = {10.1088/1742-5468/2010/12/p12017},
}
Figure