Exploring biological network structure with clustered random networks

Abstract

Background: Complex biological systems are often modeled as networks of interacting units. Networks of biochemical interactions among proteins, epidemiological contacts among hosts, and trophic interactions in ecosystems, to name a few, have provided useful insights into the dynamical processes that shape and traverse these systems. The degrees of nodes (numbers of interactions) and the extent of clustering (the tendency for a set of three nodes to be interconnected) are two of many well-studied network properties that can fundamentally shape a system. Disentangling the interdependent effects of the various network properties, however, can be difficult. Simple network models can help us quantify the structure of empirical networked systems and understand the impact of various topological properties on dynamics.

Results: Here we develop and implement a new Markov chain simulation algorithm to generate simple, connected random graphs that have a specified degree sequence and level of clustering, but are random in all other respects. The implementation of the algorithm (ClustRNet: Clustered Random Networks) provides the generation of random graphs optimized according to a local or global, and relative or absolute measure of clustering. We compare our algorithm to other similar methods and show that ours more successfully produces desired network characteristics.Finding appropriate null models is crucial in bioinformatics research, and is often difficult, particularly for biological networks. As we demonstrate, the networks generated by ClustRNet can serve as random controls when investigating the impacts of complex network features beyond the byproduct of degree and clustering in empirical networks.

Conclusion: ClustRNet generates ensembles of graphs of specified edge structure and clustering. These graphs allow for systematic study of the impacts of connectivity and redundancies on network function and dynamics. This process is a key step in unraveling the functional consequences of the structural properties of empirical biological systems and uncovering the mechanisms that drive these systems.

Figure 1

(a) a triple among the nodes i, j, k (b) a triangle among the nodes i, j, k (c) A rewiring of edges (i, j) and (k, l) can result in (i, k) and (j, l), or (i, l) and j, k) (d) Four (among many) scenarios for the result of one rewiring step of our algorithm. The configuration of edges before (left) and after (right) a rewiring step are shown for each scenario. The two bottom scenarios would be rejected by our algorithm as they do not strictly increase the number of triangles.

Figure 2

Possible triangle additions (green) and removals (red) in one step of the rewiring procedure. Black lines represent existing edges and edges added after a rewiring event, gray lines represent edges lost during a rewiring event.

Figure 3

The evolution with our algorithm of a Poisson-distributed random graph with 50 nodes from (a) ≈ 0,(b) = 0.1,(c) = 0.5 and (d) = 0.8, with the connectivity constraint.

Figure 4

Discrepancies between input and average output degree distributions (left panels) and average transitivity values (right panels) for an ensemble of 15 Poisson (top panels), exponential (middle panels) and scale-free graphs (bottom panels) as generated by our algorithm and the algorithms presented in [30]and [20]. Each graph has N = 500 and mean degree, ⟨d⟩ = 5. In the left graphs, the input degree distribution is shown as a black circles; and output degree distributions are shown for the Newman (green dashed line) and the Volz (gray dashed line) algorithms. Output degree distributions are not shown for ClustRNet as the degree sequence always perfectly match the input. In the right graphs, the input is shown as black circles, and output transitivity values are shown for two runs: (1) using SV-transitivity (()) as the clustering measure in ClustRNet (blue line), and (2) ClustRNet [without a connectivity constraint] (orange line), the Newman algorithm (green dashed line) and the Volz algorithm (gray dashed line), all with transitivity (()) as the clustering measure.

Figure 5

Degree correlations (A and B) and average path lengths (C and D) in random graphs with specified degree distributions (Poisson and exponential with mean degree = 5) compared to clustered random graphs with the same degree distributions and T = 0.5 generated by our algorithm (with the connectivity constraint), as well as the Volz [30]and Newman [20]algorithms (in A and B). The graphs present averages over 15 graphs generated by each algorithm. Our algorithm introduces fewer degree correlations than the alternatives, and the clustered graphs have only slightly higher average path lengths than their random counterparts: 4.05 for the Poisson random graphs versus 4.39 for the clustered graphs; and 3.95 for the exponential random graphs versus 4.14 for the clustered graphs.