\documentclass[12pt]{article} \usepackage{amssymb} \usepackage{graphicx} \usepackage{latexsym} \usepackage{caption2} \usepackage{flafter} \oddsidemargin 0.7cm \textwidth 15cm \textheight 20cm \title{\bf Complex networks: two ways to be robust?} \author{{\bf Carlos J. Meli\'an} and {\bf Jordi Bascompte} \\ \\Integrative Ecology Group \\Estaci\'on Biol\'ogica de Do\~nana, CSIC \\Apdo. 1056, E-41013 Sevilla, Spain.} \\ \begin{document} \date{} \maketitle \baselineskip=6.1 mm \vspace{0.2 in} \vspace{0.2 in} \centerline{\large \em Ecol. Lett., in press} \vspace{0.2 in} Correspondence should be sent to: Carlos J. Meli\'an, Estaci\'on Biol\'ogica de Do\~nana, CSIC, Apdo. 1056, E-41080 Sevilla, Spain. Telephone:(+) 34 954 232340. Fax:(+) 34 954 621125. e-mail: cmelian@ebd.csic.es. \vspace{0.2 in} Biosketch: Carlos J. Meli\'an uses both theory and the statistical analysis of data sets to understand the structure and dynamics of ecological webs and their responses to perturbations. \newpage \begin{abstract} Recent studies in biological networks have focused on the distribution of the number of links per node. However, connectivity distribution does not uncover all the complexity of their topology. Here, we analyze the relation between the connectivity of a species and the average connectivity of its nearest neighbors in three of the most resolved community food webs. We compare the arising pattern with the one recently reported for protein networks and by a simple null model of a random network. While two highly connected nodes are unlikely to be connected in protein networks, the reverse happens in food webs. We discuss this difference in organization in relation to the robustness of biological networks in front of different types of perturbations. \vspace{0.2 in} \centerline{Key words: Topology. Randomly assembled networks. } \centerline{Complex networks. Food webs. Protein networks.} \end{abstract} \vspace{0.3 in} \newpage \section{Introduction} With the recent growth of empirical information, biological networks are becoming better resolved. This empirical work is providing insight on how these complex networks are assembled and how they remain stable against deleterious perturbations (Williams \& Martinez 2000; Albert et al. 2000; Sol\'e \& Montoya 2001). Previous studies in biological networks have focused on the connectivity distribution, that is, the probability density distribution of the number of links per node. This connectivity distribution has been shown to have longer tails than would be expected for an exponential distribution, meaning that some species may be extremely connected and that the network is very heterogeneous (Ulanowicz \& Wolff 1991; Amaral et al. 2000; Jeong et al. 2000; Montoya \& Sol\'e 2002; Jordano, Bascompte \& Olesen, unpublished ms; see however Camacho et al. 2002 and Dunne et al. 2002a). However, connectivity distribution does not necessarily capture all the topological complexity of biological networks (Dorogovtsev \& Mendez 2002). A first step towards a more detailed characterization of biological networks concerns the study of connectivity correlation, that is, the relation between the number of interactions of a node and the average connectivity of its nearest neighbors (Krapivsky \& Redner 2001). Recently, Internet and protein networks have been analyzed by plotting their connectivity correlation (Pastor-Satorras et al. 2001; Maslov \& Sneppen 2002), a method never used before in ecology. Two types of protein networks have been analyzed: physical interaction, and transcription regulatory networks. Protein connectivity represents the fraction of pairs of proteins that interact, forming a network with functional and structural relationships (Maslov \& Sneppen 2002). Here, we analyze the connectivity correlation in three of the most resolved community food webs to date and compare the arising pattern with that recently reported for protein networks. Protein networks show an inverse relationship between the connectivity of a node and the average connectivity of its nearest neighbors. That is, neighbors of highly connected proteins have low connectivity and, similarly, low connected proteins are connected with highly connected proteins. This means that links between highly connected proteins are systematically suppressed. That is, the network is compartmentalized in subnetworks organized around a highly connected node with few links among such subnetworks (Maslov \& Sneppen 2002). In this paper we first study the connectivity correlation in food webs, and compare the observed pattern with characteristic values for protein networks. We discuss differences between both types of networks in relation to their robustness in front of perturbations. \section{Methods} Connectivity correlation (Fig. 1a) is best represented by the conditional probability $P_c(k'|k)$, which defines the probability that a link belonging to species with connectivity $k$ points to a species with connectivity $k'$. If $P_c(k'|k)$ is independent of $k$, there is no correlation among species' connectivity. The average connectivity ($$) of the species directly connected (nearest neighbors) to a species with connectivity $k$ can be expressed as: \vspace{0.2 in} $$ = ${\sum_{k'}{k'P_c(k'|k)}$. \hspace{3.5 in} (1) \vspace{0.2 in} To detect shifts on the relationship between the connectivity of a node ($k$) and the average connectivity of its nearest neighbors ($$) we used split-line regression (Schmid et. al 1994; Bersier \& Sugihara 1997). Provided that a shift was detected in the slope of the regression, the threshold value ($k_c$) was calculated, and the data were divided into two groups: one including the data with values below the threshold, and the other including the rest of the data. Different subsets are thus determined in base to significantly differences in the slope of the regression. As a benchmark to compare the connectivity correlation pattern we generated 1000 randomly assembled networks with the same number of species and connectivity in a similar way than Newman et al (2001). For species with connectivity $k$ we calculated the average connectivity and standard deviation of the nearest neighbors across all generated networks. The basic rules operating in the assemblage process were: \begin{enumerate} \item At time $t=0$, $n_o$ nodes with $n_o-1$ links each were created. \item At each time step, a new node was added to the network, and ingoing and outgoing links with nodes already present were established with the same probability. That is, a link between two nodes was treated as a random event, independent of the presence of other links. \end{enumerate} Although some patterns may depend on the choice of the nature of the links considered (ingoing links, outgoing links, or both; Camacho et al. 2002; Montoya \& Sol\'e 2002), in this paper we consider both ingoing and outgoing links following the analysis by Maslov \& Sneppen (2002). We can thus directly compare our results with the ones observed for protein networks. Also, the results presented here are based on binary interactions. Future work will determine to what extent results based on binary interactions stand when quantitative information (i.e., interaction strength) is incorporated (Ulanowicz \& Wolff 1991; Ulanowicz 2002). \section{Results} The three types of networks compared here differed in their internal topology (see Fig. 1). For both interaction and regulatory protein networks (Fig. 1b), correlation existed across all domains of connectivity ($k$), with connectivity correlation ($$) decaying as a power law $ \varpropto k^ {-0.6}$ (Maslov \& Sneppen 2002; Fig. 1b'). On the other hand, randomly assembled networks (Fig. 1c) showed uncorrelated connectivity across all the domain of connectivity, that is, an absence of correlation between a species connectivity and the average connectivity of its nearest neighbors (Fig. 1c'). In contrast to protein and random networks, food webs (Fig. 1d) showed a connectivity threshold $k_c$ in the response of $$ with increasing $k$ ($k_c$=19 interactions for Ythan Estuary; $k_c$=39 for Little Rock Lake; and $k_c$=28 for El Verde, Fig. 1d'). That is, food webs had two different domains with significantly different slopes across the range of values of species' connectivity. Specifically, Ythan Estuary's both subsets best fit to a power law ($p<0.05$), with slopes of $-0.27$ and $-0.49$ above and below the threshold, respectively; Little Rock Lake's first subset best fits to a linear regression ($p<0.05$) with a slope of $-0.48$; the relationship is non-significative below the threshold; El Verde best fits to a power law ($p<0.05$) in both subsets with slopes of $0.12$ and $-0.26$ above and below the threshold, respectively. The above pattern suggests the existence of two assembly patterns at different scales of connectivity. In the first domain, connectivity of the nearest neighbors either decays very slowly or does not decay at all with $k$. In the second domain, $$ decays with $k$ in a similar way than for protein networks. Globally, the average connectivity of the nearest neighbors does not decay as fast with the connectivity of a focal node as it happens in protein networks. \section{Summary and Discussion} The internal topology of the two types of biological networks compared here depart from randomly assembled networks. Interaction and regulatory protein networks are structured so that two highly connected nodes are not connected to each other. The distribution of connections is highly heterogeneous, the network being organized as a series of highly connected nodes isolated from each other. In other words, the network is compartmentalized. Recent papers on complex networks have studied the robustness of a network in front of two different types of perturbation: robustness to the spread of a deleterious mutation (Maslov \& Sneppen 2002), and robustness to the fragmentation of the network as an increasing number of nodes is deleted (Albert et al. 2000; Sol\' e \& Montoya 2001; Dunne et al. 2002b). How is the connectivity correlation pattern observed for food webs related to these two types of robustness? As suggested by Maslov \& Sneppen (2002) the compartmentalized pattern observed in protein networks increases the overall robustness of the network by isolating the cascading effects of deleterious mutations. In contrast, the food webs studied here have a pattern which is neither similar to the structure of randomly assembled webs, nor similar to protein networks. Food webs show two well-defined domains in the connectivity correlation distribution. As opposed to protein networks, two highly connected species within a food web are likely to interact among each other. This is likely to decrease the level of compartmentalization, a traditional concept in food web studies (Pimm \& Lawton 1980). In this regard, food webs are likely to be more susceptible to the spread of a contaminant. However, the connectivity correlation pattern here described for food webs, with their low level of compartmentalization (densely connected species connected to each other), may confer them a higher resistance to fragmentation if a fraction of the species were removed. Thus, there are different ways of being robust related to different types of perturbations. Previous authors have explored the effect of the connectivity distribution on the resistance of complex networks to fragmentation (Albert et al. 2000; Sol\'e \& Montoya 2001; Dunne et al. 2002b). However, a given connectivity distribution may be organized in different patterns of connectivity correlation. Our results build on previous work focusing on connectivity distribution patterns by pointing out that the pattern of connectivity correlation may also be important for understanding how food webs respond to perturbations. We suggest that the connectivity correlation provides an additional characterization of both the structure of food webs and their susceptibility to perturbations. Further work based on assembly models of biological networks incorporating both qualitative and quantitative information (Ulanowicz 2002) will give more insight into the relationship between connectivity distribution, connectivity correlation, and their importance to network responses to disturbances. Through this and related papers we have looked at structural properties of food webs. This work complements traditional theoretical approaches based on the stability of linearized dynamical systems (May 1972; Rozdilsky \& Stone 2001). Further work is needed to integrate these two perspectives. In summary, the pattern of connectivity correlation of complex networks reveals intrinsic features of their topology. The suppression of links between highly connected proteins, but their presence in food webs, reflects both differences on their structure and on their response to different perturbations. \section{Acknowledgments} We thank Pedro Jordano, Sandy Liebhold, and Miguel Angel Rodr\'{\i}guez for useful comments on a previous draft. Funding was provided by the Spanish Ministry of Science and Technology (Grant BOS2000-1366-C02-02 to J. B. and Ph.D. Fellowship FP2000-6137 to C. J. M.). \newpage \section{References} Albert, R., Jeong, H., \& Barabasi, A-L. (2000). Error and attack tolerance of complex networks. {\em Nature}, 406, 378-382. \vspace{0.2 in} Amaral, L. A., Scala, A., Barth\'el\'emy, M., \& Stanley, H. E. (2000). Classes of small-world networks. {\em Proc. Nat. Acad. Sci.}, 97, 11149-11152. \vspace{0.2 in} Bersier, L-F., Sugihara, G. (1997). Scaling regions for food web properties. {\em Proc. Nat. Acad. Sci.}, 94,1247-1251. \vspace{0.2 in} Camacho, J., Guimer\'a, R., Amaral, L. A. (2002). Robust patterns in food web structure. {\em Phys. Rev. Lett.} 88, 228102. \vspace{0.2 in} Dorogovtsev, S.N. \& Mendes, J.F.F. (2002). Evolution of networks. {\em Adv. Phys.}, 51, 1079. \vspace{0.2 in} Dunne, J. A., Williams, R. J. \& Martinez, N. D. (2002a). Small networks but not small worlds: unique aspects of food web structure. {\em Proc. Nat. Acad. Sci.}, in press. \vspace{0.2 in} Dunne, J. A., Williams, R. J. \& Martinez, N. D. (2002b). Network structure and biodiversity loss in food webs: robustness increases with connectance. {\em Ecol. Lett.}, 5, 558-567. \vspace{0.2 in} Huxham, M., Beaney, S., \& Raffaelli, D. (1996). Do parasites reduce the changes triangulation in a real food web? {\em Oikos} 76, 284-300. \vspace{0.2 in} Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. \& Barab\'asi, A-L. (2000). The large-scale organization of metabolic networks. {\em Nature}, 407, 651-654. \vspace{0.2 in} Krapivsky, P. L., \& Redner, S. (2001). Organization of growing random networks. {\em Phys. Rev. E}, 63, 066123. \vspace{0.2 in} Martinez, N. D. (1991). Artifacts or Attributes? Effects of resolution on the Little Rock Lake food web. {\em Ecol. Monogr.}, 61, 367-392. \vspace{0.2 in} Maslov, S., \& Sneppen, K. (2002). Specificity and stability in topology of protein networks. {\em Science}, 296, 910-913. \vspace{0.2 in} May, R. M. (1972). Will a large complex system be stable? {\em Nature}, 238, 413-414. \vspace{0.2 in} Montoya, J. M. \& Sol\' e, R. V. (2002). Small World Pattern in Food Webs. {\em J. Theor. Biol.}, 214, 405-412. \vspace{0.2 in} Newman, M.E.J., Strogatz, S.H. \& Watts, D.J. (2001). Random graphs with arbitrary degree distributions and their applications. {\em Phys. Rev. E}, 64, U153-U168. \vspace{0.2 in} Pastor-Satorras, R., V\'azquez, A., \& Vespignani, A. (2001). Dynamical and correlation properties of the Internet. {\em Phys. Rev. Lett.}, 87, 258701. \vspace{0.2 in} Pimm, S. L., \& Lawton, J. H. (1980). Are food webs divided into compartments? {\em J. Anim. Ecol.}, 49, 879-898. \vspace{0.2 in} Reagan, D. P. \& Waide, R. B. (1996). The food web of a tropical rain forest. University of Chicago Press. \vspace{0.2 in} Rozdilsky, I. D. \& Stone, L. (2001). Complexity can enhance stability in competitive systems. {\em Ecol. Lett.}, 4, 397-400. \vspace{0.2 in} Schmid, B., Polasek, W., Weiner, J., Krause, A., \& Stoll, P. (1994). Modeling of discontinuous relationships in biology with censored regression. {\em Am. Nat.}, 143, 494-507. \vspace{0.2 in} Sol\'e, R. V. \& Montoya, J. M. (2001). Complexity and fragility in ecological networks. {\em Proc. Roy. Soc. B}, 268, 2039-2045. \vspace{0.2 in} Ulanowicz, R. E. \& Wolff, W. F. (1991). Ecosystem flow networks: loaded dice? {\em Math. Biosci.}, 103, 45-68. \vspace{0.2 in} Ulanowicz, R. E. (2002). The balance between adaptability and adaptation. {\em BioSystems}, 64, 13-22. \vspace{0.2 in} Williams, R. J., \& Martinez, N. D. (2000). Simple rules yield complex food webs. {\em Nature}, 404, 180-183. \vspace{0.2 in} \newpage \section{Figure Legend} \vspace{0.2 in} $\bullet$ [Fig. 1] A hypothetical food web graph (a). The average connectivity of the neighbors of the black node with $k=3$ links is $$=4. A subset of the network of physical interactions between nuclear proteins (b; modified from Maslov \& Sneppen 2002); a single random replicate of the Ythan Estuary food web (c), and the graph of the Ythan Estuary food web (d). The average connectivity $$ of the neighbors of a link with connectivity $k$ as a function of $k$ in interaction ($\circ$) and regulatory ($\Box$) protein networks (b'), the average and standard deviation of 1000 randomly assembled networks (c'), and the average connectivity of food webs (d', Little Rock Lake ($\triangle$), (Martinez 1991); El Verde ($\bullet$), (Reagan \& Waide 1996); and Ythan Estuary ($\Box$) (Huxham et al. 1996)). Arrows point the threshold in connectivity ($k_c$) where a significant shift in the relationship appears. Note that links between highly connected proteins are systematically suppressed, generating a compartmentalized network (b and b'), while links between highly connected species are common in food webs, generating a cohesive network (d and d'). Randomly assembled networks show uncorrelated connectivity (c and c'). The network visualization was done using the Pajek program for large network analysis:$$. \newpage \section{Figures} \vspace{1 in} \begin{center} \includegraphics[width=6in]{Fig1.eps} \centerline{\caption{Fig. 1}} \end{center} \end{document}