Methods for Generating Complex Networks with Selected Structural Properties for Simulations: A Review and Tutorial for Neuroscientists

Brenton J. Prettejohn, Matthew J. Berryman, Mark D. McDonnellFrontiers Comput. Neurosci 2011 · DOI · OpenReview

Introduction: Moving Beyond Randomness

In computational neuroscience, the structural "wiring diagram" of a simulation is a primary determinant of its functional behavior. For decades, researchers often defaulted to Erdös–Rényi (ER) random networks or regular lattices due to their mathematical tractability and ease of implementation. However, empirical studies of anatomical brain networks have revealed that they are far from homogeneous. Instead, they exhibit sophisticated features such as "hubs" (nodes with exceptionally high connectivity) and "small-world" properties—the combination of high local clustering and short global path lengths.

This review addresses two critical gaps in the field. First, while the theory of complex networks is well-established in physics and mathematics, clear, implementation-ready tutorials tailored for neuroscientists are scarce. Second, most classic graph algorithms produce undirected edges, whereas neural synapses are inherently directed. This paper provides a practical roadmap for generating biologically realistic directed networks.

Foundational Network Models

The authors review four foundational models that serve as the building blocks for neural simulations:

  1. Erdös–Rényi (ER): This serves as the baseline random graph. In an ER network, any two nodes have a fixed, independent probability of being connected. While useful as a null model, it fails to capture the clustering or hub structures seen in real brains.
  2. Watts–Strogatz (WS): This model generates "small-world" networks. It begins with a regular lattice where each node is connected to its nearest neighbors. By "rewiring" a small fraction of these edges to random distant nodes, the model creates shortcuts that drastically reduce the average path length while maintaining high local clustering.
A regular lattice network, which serves as the starting point for generating small-world topologies.
  1. Barabási–Albert (BA): This "scale-free" model is based on the principle of preferential attachment—the "rich-get-richer" effect. New nodes are more likely to connect to existing nodes that already have many connections. This process results in a power-law degree distribution characterized by a few highly connected hubs.
  2. Klemm–Eguílez (KE): A more sophisticated architecture that combines the strengths of the WS and BA models. It produces networks that are both scale-free (having hubs) and highly clustered (small-world), making it a strong candidate for modeling cortical structures.

Bridging the "Directedness Gap"

A significant contribution of this work is the introduction of a "directedness" parameter ($d$). In traditional graph theory, an edge between A and B is often undirected. In the brain, signal flow is one-way. The authors propose a method to control the probability that an edge is reciprocal (bidirectional) versus unidirectional. This allows researchers to transform undirected models into directed graphs while ensuring the resulting topology preserves the intended statistical properties, such as the specific degree distribution.

Verification and Metrics

The tutorial emphasizes the importance of "unit testing" network generation code by comparing simulated results against known mathematical approximations. Key metrics include:

  • Degree Distribution: Ensuring the simulated network follows the predicted Binomial, Poisson, or Power-law distributions.
  • Proximity-Ratio ($S$): A quantitative measure of "small-world-ness." It compares the clustering coefficient ($C$) and average path length ($L$) of the generated network to those of an equivalent random graph. A value of $S \gg 1$ confirms a small-world architecture.
  • Scaling Laws: Demonstrating how $L$ scales with network size ($N$). In complex networks, $L$ typically increases logarithmically with $N$, whereas in regular lattices, it increases linearly.

Results and Insights

The authors demonstrate that their implementations perfectly match theoretical predictions across various network sizes (typically $N=1000$ to $N=5000$). Notably, they show that in WS and KE models, clustering remains high and relatively independent of network size, whereas in ER or BA models, clustering tends to vanish as the network grows. The KE model is highlighted as particularly relevant for neuroscience because it captures both the hub-heavy nature of global brain connectivity and the high local "cliquishness" observed within cortical columns.

Limitations and Future Directions

While providing a robust toolkit, the authors acknowledge several limitations:

  • Weights: The current models focus on binary connectivity (presence or absence of an edge), whereas synaptic weights are crucial for neural dynamics.
  • Modularity: The paper discusses modular or community structures but notes the lack of a single "canonical" algorithm for generating them.
  • Spatial Constraints: Real neural networks are constrained by physical space and metabolic costs, factors not fully captured by these purely topological models.

Future developments in network generation for neuroscience will likely integrate these topological models with spatial constraints and dynamic evolution rules to better reflect the developmental and functional realities of the brain.

Summary updated

Abstract

Many simulations of networks in computational neuroscience assume completely homogenous random networks of the Erdös–Rényi type, or regular networks, despite it being recognized for some time that anatomical brain networks are more complex in their connectivity and can, for example, exhibit the “scale-free” and “small-world” properties. We review the most well known algorithms for constructing networks with given non-homogeneous statistical properties and provide simple pseudo-code for reproducing such networks in software simulations. We also review some useful mathematical results and approximations associated with the statistics that describe these network models, including degree distribution, average path length, and clustering coefficient. We demonstrate how such results can be used as partial verification and validation of implementations. Finally, we discuss a sometimes overlooked modeling choice that can be crucially important for the properties of simulated networks: that of network directedness. The most well known network algorithms produce undirected networks, and we emphasize this point by highlighting how simple adaptations can instead produce directed networks.
BibTeX
@article{prettejohn2011methods,
  author = {Brenton J. Prettejohn and Matthew J. Berryman and Mark D. McDonnell},
  title = {{Methods for Generating Complex Networks with Selected Structural Properties for Simulations: A Review and Tutorial for Neuroscientists}},
  journal = {Frontiers Comput. Neurosci.},
  year = {2011},
  doi = {10.3389/fncom.2011.00011},
}
Figure