Two-point-uncorrelated scale-free network induced by Koch curve

Zhongzhi Zhang, Shuigeng Zhou, Lichao Chen, Yichao Zhang, Jihong Guan

Abstract

A vast variety of real-life networks display the ubiquitous presence of scale-free phenomenon and small-world effect, both of which play a significant role in the dynamical processes running on networks. Although various dynamical processes have been investigated in scale-free small-world networks, analytical research about random walks on such networks is much less. In this paper, we will study analytically the scaling of the mean first-passage time (MFPT) for random walks on scale-free small-world networks. To this end, we first map the classical Koch fractal to a network, called Koch network. According to this proposed mapping, we present an iterative algorithm for generating the Koch network, based on which we derive closed-form expressions for the relevant topological features, such as degree distribution, clustering coefficient, average path length, and degree correlations. The obtained solutions show that the Koch network exhibits scale-free behavior and small-world effect. Then, we investigate the standard random walks and trapping issue on the Koch network. Through the recurrence relations derived from the structure of the Koch network, we obtain the exact scaling for the MFPT. We show that in the infinite network order limit, the MFPT grows linearly with the number of all nodes in the network. The obtained analytical results are corroborated by direct extensive numerical calculations. In addition, we also determine the scaling efficiency exponents characterizing random walks on the Koch network.

Introduction

In network science, researchers often categorize complex systems as "scale-free" (where a few hubs possess a disproportionately high number of connections) and "small-world" (where any two nodes are separated by only a few hops). While these traits are common in real-world systems like the internet or social circles, they are often accompanied by degree correlations. In many models, high-degree hubs tend to link preferentially to other hubs (assortative) or avoid them (disassortative).

These correlations significantly complicate the mathematical analysis of dynamical processes, such as how a virus spreads or how a random walker navigates a system. To find exact analytical solutions, physicists require a "null model" that maintains scale-free and small-world structures but remains completely two-point uncorrelated. This paper introduces the Koch network, a deterministic model derived from the famous Koch fractal, designed specifically to fill this gap.

Methods: The Koch Network Construction

The authors propose a deterministic, iterative algorithm based on the geometry of the Koch curve fractal. The construction begins at Step 0 with three nodes forming a triangle. In each subsequent step, every existing node "gives birth" to two new nodes. These two new nodes and their "mother" node are linked to form a new triangle.

Iterative construction of the Koch network showing the growth from a base triangle (Step 0) to the first iteration (Step 1).

Because the network is built recursively, the authors utilize discrete mathematics and recurrence relations to derive exact closed-form expressions for the network's topological properties. This approach allows for rigorous proof of the network's characteristics rather than relying solely on numerical simulations.

Key Results and Topological Features

The analytical results, corroborated by direct extensive numerical calculations, prove that the Koch network possesses several "ideal" characteristics for a theoretical substrate:

  • Scale-Free Behavior: The degree distribution follows a power law with an exponent of $\gamma = 3$, identical to the well-known Barabási-Albert model.
  • Small-World Effect: The average path length $d_t$ grows logarithmically with the number of nodes $N_t$. Even as the network expands to millions of nodes, the "distance" between them remains remarkably small.
  • High Clustering: Despite being a sparse network (with an average degree converging to approximately 3), the Koch network maintains a high clustering coefficient of $\approx 0.82$, mimicking the "cliquishness" observed in real social networks.
  • Zero Correlation: The Pearson correlation coefficient is exactly zero. This confirms the network is a perfect substrate for testing dynamical theories without the mathematical "noise" introduced by degree correlations.
Average path length $d_t$ as a function of network size $N_t$, confirming the logarithmic scaling characteristic of small-world networks.

Discussion and Conclusion

The primary breakthrough of this research is the creation of a network that is simultaneously scale-free, small-world, and uncorrelated. By using fractal symmetry as a tool, the authors were able to calculate complex properties using simple recurrence relations.

While the Koch network is deterministic—whereas real-world networks are typically stochastic—its mathematical tractability makes it an invaluable "testbed" for studying more complex physics problems. Future work will utilize this uncorrelated scale-free structure to investigate synchronization and epidemic spreading, providing a clearer view of how network topology influences global dynamics.

Summary updated

Abstract

A vast variety of real-life networks display the ubiquitous presence of scale-free phenomenon and small-world effect, both of which play a significant role in the dynamical processes running on networks. Although various dynamical processes have been investigated in scale-free small-world networks, analytical research about random walks on such networks is much less. In this paper, we will study analytically the scaling of the mean first-passage time (MFPT) for random walks on scale-free small-world networks. To this end, we first map the classical Koch fractal to a network, called Koch network. According to this proposed mapping, we present an iterative algorithm for generating the Koch network, based on which we derive closed-form expressions for the relevant topological features, such as degree distribution, clustering coefficient, average path length, and degree correlations. The obtained solutions show that the Koch network exhibits scale-free behavior and small-world effect. Then, we investigate the standard random walks and trapping issue on the Koch network. Through the recurrence relations derived from the structure of the Koch network, we obtain the exact scaling for the MFPT. We show that in the infinite network order limit, the MFPT grows linearly with the number of all nodes in the network. The obtained analytical results are corroborated by direct extensive numerical calculations. In addition, we also determine the scaling efficiency exponents characterizing random walks on the Koch network.
BibTeX
@inproceedings{zhang2009two,
  author = {Zhongzhi Zhang and Shuigeng Zhou and Lichao Chen and Yichao Zhang and Jihong Guan},
  title = {{Two-point-uncorrelated scale-free network induced by Koch curve}},
  booktitle = {Physical},
  year = {2009},
  doi = {10.1103/physreve.79.061113},
}
Figure