Food-web structure and network theory: The role of connectance and size

Small-world properties emerge in highly compartmentalized networks with intermediate group sizes and numbers

Many recent studies have focused on two statistical properties observed in diverse real-world networks: the small-world property and compartmentalization [D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998); M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. 99, 7821 (2002)]. Models that include group affiliations have been shown to produce networks with high clustering coefficients, a necessary condition for small-world properties [M. E. J. Newman, Phys. Rev. E, 68, 026121 (2003); M. E. J. Newman and J. Park, Phys. Rev. E 68, 036122 (2003)]. However, the consequences of varying the number and size of groups in a network are not well understood. In order to investigate the consequences of group organization, we examined sets of networks that varied simultaneously in the size and number of groups, while maintaining the same overall size and average degree. Here we show that the small-world property arises in maximally compartmentalized and clustered networks that occur in the intermediate region between few, very large groups and many, very small groups.

Extremal dynamics on complex networks: analytic solutions

The Bak-Sneppen model displaying punctuated equilibria in biological evolution is studied on random complex networks. By using the rate equation and the random walk approaches, we obtain the analytic solution of the fitness threshold xc to be 1/((k)f+1), where (k)f=(k2)/(k) (=(k)) in the quenched (annealed) updating case, where kn is the nth moment of the degree distribution. Thus, the threshold is zero (finite) for the degree exponent gamma<3 (gamma>3) for the quenched case in the thermodynamic limit. The theoretical value xc fits well to the numerical simulation data in the annealed case only. Avalanche size, defined as the duration of successive mutations below the threshold, exhibits a critical behavior as its distribution follows a power law, Pa(s) approximately s(-3/2).

The smallest of all worlds: pollination networks

A pollination network may be either 2-mode, describing trophic and reproductive interactions between communities of flowering plants and pollinator species within a well-defined habitat, or 1-mode, describing interactions between either plants or pollinators. In a 1-mode pollinator network, two pollinator species are linked to each other if they both visit the same plant species, and vice versa for plants. Properties of 2-mode networks and their derived 1-mode networks are highly correlated and so are properties of 1-mode pollinator and 1-mode plant networks. Most network properties are scale-dependent, i.e. they are dependent upon network size. Pollination networks have the strongest small-world properties of any networks yet studied, i.e. all species are close to each other (short average path length) and species are highly clustered. Species in pollination networks are much more densely linked than species in traditional food webs, i.e. they have a higher density of links, a shorter distance between species, and species are more clustered.

Using community viability analysis to identify fragile systems and keystone species

Owing to interdependences among species in ecological communities, the loss of one species can trigger a cascade of secondary extinctions with potentially dramatic effects on the functioning and stability of the community. It is, therefore, important to assess the risk and likely extent of secondary extinctions. Community viability analysis is a new technique that can be used to accomplish this goal. The analysis can also be used to identify fragile community structures and keystone species and, hence, to provide guidelines for conservation priorities. Here, we describe the principles underlying community viability analysis and review its contributions to our understanding of the response of ecological communities to species loss.

Local method for detecting communities

We propose a method of community detection that is computationally inexpensive and possesses physical significance to a member of a social network. This method is unlike many divisive and agglomerative techniques and is local in the sense that a community can be detected within a network without requiring knowledge of the entire network. A global application of this method is also introduced. Several artificial and real-world networks, including the famous Zachary karate club, are analyzed.

Evolutionary ecology in silico: Does mathematical modelling help in understanding 'generic' trends?

Motivated by the results of recent laboratory experiments, as well as many earlier field observations, that evolutionary changes can take place in ecosystems over relatively short ecological time scales, several 'unified' mathematical models of evolutionary ecology have been developed over the last few years with the aim of describing the statistical properties of data related to the evolution of ecosystems. Moreover, because of the availability of sufficiently fast computers, it has become possible to carry out detailed computer simulations of these models. For the sake of completeness and to put these recent developments in perspective, we begin with a brief summary of some older models of ecological phenomena and evolutionary processes. However, the main aim of this article is to review critically these 'unified' models, particularly those published in the physics literature, in simple language that makes the new theories accessible to a wider audience.

Complex networks emerging from fluctuating random graphs: analytic formula for the hidden variable distribution

In analogy to superstatistics, which connects Boltzmann-Gibbs statistical mechanics to its generalizations through temperature fluctuations, complex networks are constructed from fluctuating Erdös-Rényi random graphs. Using a quantum-mechanical method, the exact analytic formula for the hidden variable distribution is presented which describes the nature of the fluctuations and generates a generic degree distribution through the Poisson transformation. As an example, a static scale-free network is discussed and the corresponding hidden variable distribution is found to decay as a power law and to diverge at the origin.

Keystone species and vulnerable species in ecological communities: strong or weak interactors?

The loss of a species from an ecological community can trigger a cascade of secondary extinctions. The probability of secondary extinction to take place and the number of secondary extinctions are likely to depend on the characteristics of the species that is lost--the strength of its interactions with other species--as well as on the distribution of interaction strengths in the whole community. Analysing the effects of species loss in model communities we found that removal of the following species categories triggered, on average, the largest number of secondary extinctions: (a) rare species interacting strongly with many consumers, (b) abundant basal species interacting weakly with their consumers and (c) abundant intermediate species interacting strongly with many resources. We also found that the keystone status of a species with given characteristics was context dependent, that is, dependent on the structure of the community where it was embedded. Species vulnerable to secondary extinctions were mainly species interacting weakly with their resources and species interacting strongly with their consumers.

Maximal planar networks with large clustering coefficient and power-law degree distribution

In this article, we propose a simple rule that generates scale-free networks with very large clustering coefficient and very small average distance. These networks are called random Apollonian networks (RANs) as they can be considered as a variation of Apollonian networks. We obtain the analytic results of power-law exponent gamma=3 and clustering coefficient C= (46/3)-36 ln 3/2 approximately 0.74, which agree with the simulation results very well. We prove that the increasing tendency of average distance of RANs is a little slower than the logarithm of the number of nodes in RANs. Since most real-life networks are both scale-free and small-world networks, RANs may perform well in mimicking the reality. The RANs possess hierarchical structure as C(k) approximately k(-1) that are in accord with the observations of many real-life networks. In addition, we prove that RANs are maximal planar networks, which are of particular practicability for layout of printed circuits and so on. The percolation and epidemic spreading process are also studied and the comparisons between RANs and Barabási-Albert (BA) as well as Newman-Watts (NW) networks are shown. We find that, when the network order N (the total number of nodes) is relatively small (as N approximately 10(4)), the performance of RANs under intentional attack is not sensitive to N , while that of BA networks is much affected by N. And the diseases spread slower in RANs than BA networks in the early stage of the susceptible-infected process, indicating that the large clustering coefficient may slow the spreading velocity, especially in the outbreaks.

Random initial condition in small Barabasi-Albert networks and deviations from the scale-free behavior

Barabasi-Albert networks are constructed by adding nodes via preferential attachment to an initial core of nodes. We study the topology of small scale-free networks as a function of the size and average connectivity of their initial random core. We show that these two parameters may strongly affect the tail of the degree distribution, by consistently leading to broad-scale or single-scale networks. In particular, we argue that the size of the initial network core and its density of connections may be the main responsible for the exponential truncation of the power-law behavior observed in some small scale-free networks.

Characterizing the network topology of the energy landscapes of atomic clusters

By dividing potential energy landscapes into basins of attractions surrounding minima and linking those basins that are connected by transition state valleys, a network description of energy landscapes naturally arises. These networks are characterized in detail for a series of small Lennard-Jones clusters and show behavior characteristic of small-world and scale-free networks. However, unlike many such networks, this topology cannot reflect the rules governing the dynamics of network growth, because they are static spatial networks. Instead, the heterogeneity in the networks stems from differences in the potential energy of the minima, and hence the hyperareas of their associated basins of attraction. The low-energy minima with large basins of attraction act as hubs in the network. Comparisons to randomized networks with the same degree distribution reveals structuring in the networks that reflects their spatial embedding.

Self-similar disk packings as model spatial scale-free networks

The network of contacts in space-filling disk packings, such as the Apollonian packing, is examined. These networks provide an interesting example of spatial scale-free networks, where the topology reflects the broad distribution of disk areas. A wide variety of topological and spatial properties of these systems is characterized. Their potential as models for networks of connected minima on energy landscapes is discussed.

Finding community structure in very large networks

The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m approximately n and d approximately log n, in which case our algorithm runs in essentially linear time, O (n log(2) n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web site of a large on-line retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400 000 vertices and 2 x 10(6) edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.

Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions

In this paper, we investigate the problem of secondary extinction in food webs through the use of dominator trees, network topological structures that reduce food webs to linear pathways that are essential for energy delivery. Each species along these chains is responsible for passing energy to the taxa that follow it, and, as such, it is indispensable for their survival; because of this it is said to dominate them. The higher the number of species a node dominates, the greater the impact resulting from its removal. By computing dominator trees for 13 well-studied food webs we obtained for each of them the number of nodes dominated by a single species and the number of nodes that dominate each species. We illustrate the procedure for the Grassland Ecosystem showing the potential of this method for identifying species that play a major role in energy delivery and are likely to cause the greatest damage if removed. Finally, by means of two indices that measure error and attack sensitivity, we confirm a previous hypothesis that food webs are very robust to random loss of species but very fragile to the selective loss of the hubs.

Reinforcing the resilience of complex networks

Given a connected network, it can be augmented by applying a growing strategy (e.g., random- or preferential-attachment rules) over the previously existing structure. Another approach for augmentation, recently introduced, involves incorporating a direct edge between any two nodes which are found to be connected through at least one self-avoiding path of length L. This work investigates the resilience of random- and preferential-attachment models augmented by using the three schemes identified above. Considering random- and preferential-attachment networks, their giant cluster are identified and reinforced, then the resilience of the resulting networks with respect to highest-degree node attack is quantified through simulations. Statistical characterization of the effects of augmentations over some of the network properties is also provided. The results, which indicate that substantial reinforcement of the resilience of complex networks can be achieved by the expansions, also confirm the superior robustness of the random expansion. An important obtained result is that the initial growth scheme was found to have little effect over the possibilities of further enhancement of the network by subsequent reinforcement schemes.

Scaling of directed dynamical small-world networks with random responses

A dynamical model of small-world networks, with directed links which describe various correlations in social and natural phenomena, is presented. Random responses of sites to the input message are introduced to simulate real systems. The interplay of these ingredients results in the collective dynamical evolution of a spinlike variable S(t) of the whole network. The global average spreading length <L>(s) and average spreading time <T>(s) are found to scale as p(-alpha)ln(N with different exponents. Meanwhile, S(t) behaves in a duple scaling form for N>>N(*): S approximately f(p(-beta)q(gamma)t), where p and q are rewiring and external parameters, alpha, beta, and gamma are scaling exponents, and f(t) is a universal function. Possible applications of the model are discussed.

Emergence of non-random structure in local food webs generated from randomly structured regional webs

Previous studies have shown that high-resolution, empirical food webs possess a non-random network structure, typically characterized by uniform or exponential degree distributions. However, the empirical food webs that have been investigated for their structural properties represent local communities that are only a subset of a larger pool of regionally coexisting species. Here, we use a simple model to investigate the effects of regional food web structure on local food webs that are assembled by two simple processes: random immigration of species from a source web (regional food web), and random extinction of species within the local web. The model shows that local webs with non-random degree distributions can arise from randomly structured source webs. A comparison of local webs assembled from randomly structured source webs with local webs assembled from source webs generated by the niche model shows that the former have higher species richness at equilibrium, but have a nonlinear response to changing extinction rates. These results imply that the network structure of regional food webs can play a significant role in the assembly and dynamics of local webs in natural ecosystems. With natural landscapes becoming increasingly fragmented, understanding such structure may be a necessary key to understanding the maintenance and stability of local species diversity.

Defining and identifying communities in networks

The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems.

Finding and evaluating community structure in networks

We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.

Uncovering Network Systems Within Protein Structures

Traditionally, proteins have been viewed as a construct based on elements of secondary structure and their arrangement in three-dimensional space. In a departure from this perspective we show that protein structures can be modelled as network systems that exhibit small-world, single-scale, and to some degree, scale-free properties. The phenomenological network concept of degrees of separation is applied to three-dimensional protein structure networks and reveals how amino acid residues can be connected to each other within six degrees of separation. This work also illuminates the unique features of protein networks in comparison to other networks currently studied. Recognising that proteins are networks provides a means of rationalising the robustness in the overall three-dimensional fold of a protein against random mutations and suggests an alternative avenue to investigate the determinants of protein structure, function and folding.

Scale-free networks from a Hamiltonian dynamics

Contrary to many recent models of growing networks, we present a model with fixed number of nodes and links, where a dynamics favoring the formation of links between nodes with degree of connectivity as different as possible is introduced. By applying a local rewiring move, the network reaches equilibrium states assuming broad degree distributions, which have a power-law form in an intermediate range of the parameters used. Interestingly, in the same range we find nontrivial hierarchical clustering.

The nested assembly of plant-animal mutualistic networks

Most studies of plant-animal mutualisms involve a small number of species. There is almost no information on the structural organization of species-rich mutualistic networks despite its potential importance for the maintenance of diversity. Here we analyze 52 mutualistic networks and show that they are highly nested; that is, the more specialist species interact only with proper subsets of those species interacting with the more generalists. This assembly pattern generates highly asymmetrical interactions and organizes the community cohesively around a central core of interactions. Thus, mutualistic networks are neither randomly assembled nor organized in compartments arising from tight, parallel specialization. Furthermore, nestedness increases with the complexity (number of interactions) of the network: for a given number of species, communities with more interactions are significantly more nested. Our results indicate a nonrandom pattern of community organization that may be relevant for our understanding of the organization and persistence of biodiversity.

Simple model for directed networks

We study a model for directed networks based on the Watts-Stogatz model for small-world phenomena. We focus on some topological aspects of directed networks inspired in food web theory, namely, the fraction of basal and top nodes in the network and node level distributions. We argue that in directed networks basal nodes play an important role, collecting information or resources from the environment. We give analytical expressions for the fraction of basal and top nodes for the model, and study the node level distributions with numerical simulations.

Universal scaling relations in food webs

The structure of ecological communities is usually represented by food webs. In these webs, we describe species by means of vertices connected by links representing the predations. We can therefore study different webs by considering the shape (topology) of these networks. Comparing food webs by searching for regularities is of fundamental importance, because universal patterns would reveal common principles underlying the organization of different ecosystems. However, features observed in small food webs are different from those found in large ones. Furthermore, food webs (except in isolated cases) do not share general features with other types of network (including the Internet, the World Wide Web and biological webs). These features are a small-world character and a scale-free (power-law) distribution of the degree (the number of links per vertex). Here we propose to describe food webs as transportation networks by extending to them the concept of allometric scaling (how branching properties change with network size). We then decompose food webs in spanning trees and loop-forming links. We show that, whereas the number of loops varies significantly across real webs, spanning trees are characterized by universal scaling relations.

Two degrees of separation in complex food webs

Feeding relationships can cause invasions, extirpations, and population fluctuations of a species to dramatically affect other species within a variety of natural habitats. Empirical evidence suggests that such strong effects rarely propagate through food webs more than three links away from the initial perturbation. However, the size of these spheres of potential influence within complex communities is generally unknown. Here, we show for that species within large communities from a variety of aquatic and terrestrial ecosystems are on average two links apart, with >95% of species typically within three links of each other. Species are drawn even closer as network complexity and, more unexpectedly, species richness increase. Our findings are based on seven of the largest and most complex food webs available as well as a food-web model that extends the generality of the empirical results. These results indicate that the dynamics of species within ecosystems may be more highly interconnected and that biodiversity loss and species invasions may affect more species than previously thought.