Planar unclustered graphs to model technological and biological networks

Alícia Miralles, Lichao Chen, Zhongzhi Zhang, Francesc ComellasarXiv 2009 · DOI · arXiv

Abstract

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases—usually associated with topological restrictions—their clustering is low and they are almost planar. In this paper, we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular technological and biological networks.

Introduction

Network science has traditionally relied on stochastic models, such as the Barabási-Albert preferential attachment model, to explain the "small-world" and "scale-free" properties of complex systems. However, these random models often struggle to capture specific topological constraints found in physical networks. Technological systems like electronic circuits and biological systems like protein-protein interaction (PPI) networks are often planar (or nearly so) and exhibit very low clustering.

This paper addresses this gap by introducing a deterministic family of graphs, denoted as $M_d(t)$. These graphs are modular, self-similar, and planar, with a clustering coefficient of exactly zero, while still maintaining the essential scale-free and small-world characteristics of real-world networks.

The $M_d(t)$ Model Construction

The graph family $M_d(t)$ is defined by a branching parameter $d$ and an iteration step $t$. The construction is iterative:

  1. Initial Step ($t=0$): The graph $M_d(0)$ consists of a single "generating edge" connecting two vertices.
  2. Iterative Step: In each subsequent step $t+1$, every generating edge from step $t$ is replaced by $d$ parallel paths of length three.

Alternatively, the graph can be viewed recursively: $M_d(t)$ is composed of $2d$ copies of $M_d(t-1)$, joined at specific connecting vertices. This deterministic growth allows for the derivation of exact recurrence relations for the network's properties.

Key Analytical Results

Because the construction is fixed, the authors provide closed-form solutions for several critical network metrics.

Scale-Free Degree Distribution

The model successfully replicates the power-law degree distribution $P(k) \sim k^{-\gamma}$ observed in nature. The exponent is given by $\gamma = 1 + \ln(2d)/\ln(d)$. By tuning the parameter $d$, the model can be adapted to match the specific exponents of different real-world systems.

Small-World Behavior and Planarity

Despite the lack of random "shortcuts," the network remains "small-world." Both the diameter and the average path length scale logarithmically with the number of nodes ($D \sim \ln|V|$). Furthermore, the graphs are proven to be planar, meaning they can be embedded in a 2D plane without any edges crossing—a vital feature for modeling physical layouts like circuit boards.

Disassortativity and Zero Clustering

A distinguishing feature of this model is its clustering coefficient of exactly zero, meaning no triangles exist in the graph. Additionally, the model naturally exhibits disassortativity, where high-degree hubs tend to connect to low-degree nodes. This negative correlation is a common trait in biological and technological networks, setting them apart from social networks which are typically assortative and highly clustered.

Applications and Conclusion

The $M_d(t)$ model provides an excellent fit for benchmark datasets, including electronic circuit networks and the S. cerevisiae protein-protein interaction network. The predicted exponents and path lengths align closely with empirical data from these systems.

By providing a deterministic "skeleton" for complex networks, this framework allows researchers to bypass probabilistic estimations and use exact formulas to study network dynamics. While real-world networks contain stochastic noise, the $M_d(t)$ family serves as a precise baseline for understanding how planarity and modularity shape the evolution of technological and biological systems.

Summary updated

Abstract

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases - usually associated with topological restrictions- their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular technological and biological networks.
BibTeX
@misc{miralles2009planar,
  author = {Alícia Miralles and Lichao Chen and Zhongzhi Zhang and Francesc Comellas},
  title = {{Planar unclustered graphs to model technological and biological networks}},
  year = {2009},
  eprint = {0902.4273},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0902.4273},
  howpublished = {arXiv},
}

Loading related content...

Figure