Modeling and Simulation in Science, Engineering and Technology Series Editor Nicola Bellomo Politecnico di Torino Italy Advisory Editorial Board M. Avellaneda (Modeling in Economics) Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York, NY 10012, USA
[email protected]
H.G. Othmer (Mathematical Biology) Department of Mathematics University of Minnesota 270A Vincent Hall Minneapolis, MN 55455, USA
[email protected]
K.J. Bathe (Solid Mechanics) Department of Mechanical Engineering Massachusetts Institute of Technology Cambridge, MA 02139, USA
[email protected]
L. Preziosi (Industrial Mathematics) Dipartimento di Matematica Politecnico di Torino Corso Duca degli Abruzzi 24 10129 Torino, Italy
[email protected]
P. Degond (Semiconductor and Transport Modeling) Mathématiques pour l’Industrie et la Physique Université P. Sabatier Toulouse 3 118 Route de Narbonne 31062 Toulouse Cedex, France
[email protected] A. Deutsch (Complex Systems in the Life Sciences) Center for Information Services and High Performance Computing Technische Universität Dresden 01062 Dresden, Germany
[email protected] M.A. Herrero Garcia (Mathematical Methods) Departamento de Matematica Aplicada Universidad Complutense de Madrid Avenida Complutense s/n 28040 Madrid, Spain
[email protected] W. Kliemann (Stochastic Modeling) Department of Mathematics Iowa State University 400 Carver Hall Ames, IA 50011, USA
[email protected]
V. Protopopescu (Competitive Systems, Epidemiology) CSMD Oak Ridge National Laboratory Oak Ridge, TN 37831-6363, USA
[email protected] K.R. Rajagopal (Multiphase Flows) Department of Mechanical Engineering Texas A&M University College Station, TX 77843, USA
[email protected] Y. Sone (Fluid Dynamics in Engineering Sciences) Professor Emeritus Kyoto University 230-133 Iwakura-Nagatani-cho Sakyo-ku Kyoto 606-0026, Japan
[email protected]
Dynamics On and Of Complex Networks Applications to Biology, Computer Science, and the Social Sciences
Niloy Ganguly Andreas Deutsch Animesh Mukherjee Editors
Birkhäuser Boston • Basel • Berlin
Editors Niloy Ganguly Indian Institute of Technology Department of Computer Science and Engineering Kharagpur 721302 India
[email protected]
Andreas Deutsch Center for Information Services and High Performance Computing Technische Universität Dresden 01062 Dresden Germany
[email protected]
Animesh Mukherjee Indian Institute of Technology Department of Computer Science and Engineering Kharagpur 721302 India
[email protected]
ISBN: 978-0-8176-4750-6 DOI: 10.1007/978-0-8176-4751-3
e-ISBN: 978-0-8176-4751-3
Library of Congress Control Number: 2009921285 Mathematics Subject Classification (2000): 05C85, 68M10, 82B43, 90B15, 90B18, 90B40, 90C35, 91D30, 92D30, 94C15 © Birkhäuser Boston, a part of Springer Science+Business Media, LLC 2009
All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Birkhäuser Boston, c/o Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Birkhäuser Boston is part of Springer Science+Business Media (www.birkhauser.com)
Preface
In the context of network theory, Complex networks can be defined as a collection of nodes connected by edges representing various complex interactions among the nodes. Almost any large-scale system, be it natural or man-made, can be viewed as a complex network of interacting entities, which is dynamically evolving over time. Naturally occurring networks include biological, ecological and social networks (e.g., metabolic networks, gene regulatory networks, protein interaction networks, signaling networks, epidemic networks, food webs, scientific collaboration networks and acquaintance networks), whereas man-made networks include communication networks and transportation infrastructures (e.g., the Internet, the World Wide Web, peerto-peer networks, power grids and airline networks). This edited volume is a sequel to the workshop Dynamics on and of Complex Networks (http://www.cel.iitkgp.ernet.in/∼eccs07/ ) held as a satellite event of the fourth European Conference on Complex Systems in Dresden, Germany from October 1–5, 2007. The primary aim of this workshop was to systematically explore the statistical dynamics “on” and “of” complex networks that prevail across a large number of scientific disciplines. Dynamics on networks refers to the different types of processes, for instance, proliferation and diffusion, that take place on networks. The functionality/efficiency of these processes is strongly tied to the underlying topology as well as the dynamic behavior of the network. On the other hand, dynamics of networks mainly refers to the phenomena of self-organization, which in turn lead to the emergence of the complex structure of the network. Another important motivation of the workshop was to create a forum for researchers applying the theories of complex networks to various domains as well as across several disciplines such as computer science, statistical physics, nonlinear dynamics, econometrics, biology, sociology and linguistics. The workshop received a large number of quality submissions from authors pursuing research in multiple disciplines, thus making the forum truly interdisciplinary. The total number of participants who attended the workshop
VI
Preface
was approximately 40. There were around 20 speakers, including both senior researchers and young scientists, who spoke about the dynamics on and of different systems exhibiting a complex network structure. The theme of this edited volume is identical to that of the workshop. Its primary aim is to show how the theories of complex networks are being successfully used by researchers to tackle numerous difficult problems in various domains. Towards this aim, it presents an extended version of some of the very high quality submissions received at the workshop together with new invited contributions, which can play an extremely important role in the understanding as well as advancement of the field. Since the target audience of this book is expected to be largely cross-disciplinary, the chapters have been made as readable as possible, explaining all the intricate technicalities wherever necessary in sufficient detail. The uniqueness of this volume lies in the fact that it presents an equal mix of (a) very relevant reviews (eight chapters) of important works in the field, which gives the reader an up-to-date picture of the state of the art, and (b) independent research reports (eight chapters) providing a clear conception about how complex networks can be extremely useful in harnessing even the hardest problems of a particular discipline. The editors feel that research in this area has reached a stage where there is an urgent need to have a comprehensive knowledge of the past and the present before the future can be planned. The blend of reviews and the contributory chapters presented in this volume strive to achieve this objective and, thereby, set the platform for a “Phase II” research in complex networks. The volume consists of three parts. The contributions in Part I center around the application of complex networks in the understanding of biological problems. This part consists of five chapters. The first chapter is From Network Structure to Dynamics and Back Again: Relating Dynamical Stability and Connection Topology in Biological Complex Systems, in which Sitabhra Sinha presents a study of how the topology of a biological network influences the nature of its dynamics, and conversely, how dynamical considerations put constraints on the network structure. The next chapter deals with Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis, in which Madalena Chaves et al. model and analyze, in the framework of complex networks, the interaction of the nuclear factor κB with the apoptosis signaling pathway. In the third chapter, Network-Based Models in Molecular Biology, Andreas Beyer presents a survey on the extensive literature that employs complex networks to understand numerous intricate phenomena in biology. The fourth chapter, Ecological Networks: Structure, Interaction Strength, and Stability, by Samit Bhattacharyya and Somdatta Sinha, presents a detailed survey of the various studies conducted on ecological networks and especially on food webs. In the last chapter, Signaling and Feedback in Biological Networks, Sandeep Krishna et al. review some important studies on the signaling and feedback mechanisms that are observed in different biological networks.
Preface
VII
Part II is also spread over five chapters and focuses on social networks. This part begins with a chapter on Topographic Spreading Analysis of an Empirical Sex Workers’ Network, by Johannes Bjelland et al., where the authors present a “topographic” analysis of spreading (of HIV) on an empirical network of female sex workers. The authors find that the HIV graph breaks into small components, thereby reducing the spreading if perfect condom protection is made possible. The next chapter, Spectral Characterization of Network Structures and Dynamics, by Anirban Banerjee and J¨ urgen Jost, centers around the investigation of the spectral properties of complex networks with a special thrust on social networks. The third chapter, Dynamics of Social Complex Networks: Some Insights into Recent Research, is authored by Sergi Lozano and presents a comprehensive review of how complex network theory has been instrumental in explaining the structure and the dynamics of a society. The last two chapters show how complex networks can be applied to explain the dynamics of human languages. The first one, titled The Structure and Dynamics of Linguistic Networks, by Monojit Choudhury and Animesh Mukherjee, is a review of the current literature on linguistic networks. The second one, Networks Generated from Natural Language Text, by Chris Biemann and Uwe Quasthoff, presents a survey focusing on how corpus linguistics (i.e., the study of language as expressed in corpora) can be studied within the framework of complex networks. Part III presents a comprehensive overview of the networks that are prevalent in information sciences. This part is laid out in six chapters. The first chapter in this part, Efficiency of Navigation in Indexed Networks, by Petter Holme, explores the efficiency of navigation of data packets on “indexed” graphs. The second chapter, Evolution of Apache Open Source Software, by Haoran Wen et al., attempts to explain the evolution of the Apache open source software through the analysis of its call graphs. The next chapter, Some New Applications of Network Growth Models, by Gourab Ghoshal, presents new models of growth for peer-to-peer file-sharing networks. The fourth chapter, The Big Friendly Giant: The Giant Component in Clustered Random Graphs, by Yakir Berchenko et al., is a theoretical study of the properties of the giant component in a special kind of random graph, which is relevant for various information networks. The fifth chapter, Technological Networks, by Bivas Mitra, presents a detailed review of the large number of studies that have been conducted on information networks, especially the World Wide Web and peer-to-peer networks. The last chapter, Advances in the Theory of Complex Networks, by Fernando Peruani, presents a survey of some of the theoretical advancements that have taken place and helps in providing a better understanding of the structure and dynamics of information networks. These contributions collectively demonstrate that complex networks indeed provide an elegant research framework relevant to a variety of scientific disciplines. The chapters are designed to serve as the state of the art not only for students and new comers who intend to pursue research in this field but
VIII
Preface
also for the experts. All the chapters have been carefully peer reviewed for their scientific content as well as readability and self-consistency. We would like to thank the authors for their contributions, constructive co-operation and gracious acceptance of the editorial comments. We are also indebted to Ranjita Bhagwan, Chris Biemann, Lutz Brusch, Geoffrey Canright, Michael Gamon, Gourab Ghoshal, Petter Holme, A. Kumaran, Abyayananda Maiti, Pabitra Mitra, Luis Morelli, Gautam Mukherjee, Romit Roy Choudhury, Gustavo Sibona and Biplab K. Sikdar for their constructive criticisms, comments and suggestions, which have significantly improved the quality of the chapters. In addition, we would also like to extend our gratitude to Rishabh Singh for his painstaking effort in helping to prepare the Glossary of Essential Terms. Finally, we are also grateful to Tom Grasso and the Birkh¨ auser team for all their help and support towards the publication of this volume. Kharagpur, India Dresden, Germany Kharagpur, India
Niloy Ganguly Andreas Deutsch Animesh Mukherjee
Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V List of Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XI Part I Biological Sciences From Network Structure to Dynamics and Back Again: Relating Dynamical Stability and Connection Topology in Biological Complex Systems Sitabhra Sinha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis Madalena Chaves, Thomas Eissing, and Frank Allg¨ ower . . . . . . . . . . . . . . 19 Network-Based Models in Molecular Biology Andreas Beyer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Ecological Networks: Structure, Interaction Strength, and Stability Samit Bhattacharyya and Somdatta Sinha . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Signaling and Feedback in Biological Networks Sandeep Krishna, Mogens H. Jensen, and Kim Sneppen . . . . . . . . . . . . . . . 73
Part II Social Sciences Topographic Spreading Analysis of an Empirical Sex Workers’ Network Johannes Bjelland, Geoffrey Canright, Kenth Engø-Monsen, and Valencia P. Remple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
X
Contents
Spectral Characterization of Network Structures and Dynamics Anirban Banerjee and J¨ urgen Jost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Dynamics of Social Complex Networks: Some Insights into Recent Research Sergi Lozano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 The Structure and Dynamics of Linguistic Networks Monojit Choudhury and Animesh Mukherjee . . . . . . . . . . . . . . . . . . . . . . . . . 145 Networks Generated from Natural Language Text Chris Biemann and Uwe Quasthoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
Part III Information Sciences Efficiency of Navigation in Indexed Networks Petter Holme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 Evolution of Apache Open Source Software Haoran Wen, Raissa M. D’Souza, Zachary M. Saul, and Vladimir Filkov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Some New Applications of Network Growth Models Gourab Ghoshal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 The Big Friendly Giant: The Giant Component in Clustered Random Graphs Yakir Berchenko, Yael Artzy-Randrup, Mina Teicher, and Lewi Stone . . . 237 Technological Networks Bivas Mitra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Advances in the Theory of Complex Networks Fernando Peruani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 Glossary of Essential Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
List of Contributors
Frank Allg¨ ower Institute for Systems Theory and Automatic Control University of Stuttgart Pfaffenwaldring 9 70550 Stuttgart Germany
[email protected] Yael Artzy-Randrup Biomathematics Unit Faculty of Life Sciences Tel Aviv University Ramat Aviv 69978 Israel
[email protected] Anirban Banerjee Max Planck Institute for Molecular Genetics Ihnestr. 63–73 14195 Berlin Germany
[email protected] Yakir Berchenko Interdisciplinary Brain Research Center Bar Ilan University Ramat Gan 52900 Israel
[email protected]
Andreas Beyer Biotechnology Center Technische Universit¨at Dresden 01062 Dresden Germany andreas.beyer@biotec. tu-dresden.de Samit Bhattacharyya Mathematical Modelling and Computational Biology Group Centre for Cellular and Molecular Biology, CSIR Hyderabad 500007 India
[email protected] Chris Biemann Institute for Computer Science NLP Department University of Leipzig Johannisgasse 26 04103 Leipzig Germany
[email protected] Johannes Bjelland Telenor R&I 1331 Fornebu Norway
[email protected]
XII
List of Contributors
Geoffrey Canright Telenor R&I 1331 Fornebu Norway
[email protected] Madalena Chaves COMORE, INRIA 2004 Route des Lucioles, BP 93 06902 Sophia-Antipolis France
[email protected] Monojit Choudhury Microsoft Research India Sadashivnagar Bangalore 560080 India
[email protected] Raissa M. D’Souza Department of Mechanical and Aeronautical Engineering Center for Computational Science and Engineering University of California Davis, CA 95616 USA
[email protected] Thomas Eissing Bayer Technologies Services GmbH PT-AS Systems Biology 51368 Leverkusen Germany thomas.eissing@ bayertechnology.com Kenth Engø-Monsen Telenor R&I 1331 Fornebu Norway
[email protected]
Vladimir Filkov Department of Computer Science University of California Davis, CA 95616 USA
[email protected]
Gourab Ghoshal Department of Physics, and Michigan Center for Theoretical Physics University of Michigan Ann Arbor MI, 48109 USA
[email protected]
Petter Holme Department of Physics Ume˚ a University 90187 Ume˚ a Sweden
[email protected]
Mogens H. Jensen Center for Models of Life Niels Bohr Institute Blegdamsvej 17 2100 Copenhagen Denmark
[email protected]
J¨ urgen Jost Max Planck Institute for Mathematics in the Sciences Inselstr. 22 04103 Leipzig Germany Santa Fe Institute Santa Fe, NM 87501 USA
[email protected]
List of Contributors
Sandeep Krishna Center for Models of Life Niels Bohr Institute Blegdamsvej 17 2100 Copenhagen Denmark
[email protected] Sergi Lozano ETH Z¨ urich Swiss Federal Institute of Technology UNO D11 Universit¨atstr. 41 8092 Z¨ urich Switzerland
[email protected] Bivas Mitra Department of Computer Science and Engineering Indian Institute of Technology Kharagpur 721302 India
[email protected]
XIII
Uwe Quasthoff Institute for Computer Science NLP Department University of Leipzig Johannisgasse 26 04103 Leipzig Germany quasthoff@informatik. uni-leipzig.de Valencia P. Remple BC Centre for Disease Control Epidemiology University of British Columbia Vancouver, BC V5Z 4R4 Canada
[email protected] Zachary M. Saul Department of Computer Science University of California Davis, CA 95616 USA
[email protected]
Animesh Mukherjee Department of Computer Science and Engineering Indian Institute of Technology Kharagpur 721302 India
[email protected]
Sitabhra Sinha The Institute of Mathematical Sciences CIT Campus Taramani Chennai 600113 India
[email protected]
Fernando Peruani Service de Physique de l’Etat Condens´e (SPEC/CEA) and Complex System Institute Paris Ile-de-France (ISC-PIF) F-75005, Paris France
[email protected]
Somdatta Sinha Mathematical Modelling and Computational Biology Group Centre for Cellular and Molecular Biology, CSIR Hyderabad 500007 India
[email protected]
XIV
List of Contributors
Kim Sneppen Center for Models of Life Niels Bohr Institute Blegdamsvej 17 2100 Copenhagen Denmark
[email protected]
Mina Teicher Interdisciplinary Brain Research Center Bar Ilan University Ramat Gan 52900 Israel
[email protected]
Lewi Stone Biomathematics Unit Faculty of Life Sciences Tel Aviv University Ramat Aviv 69978 Israel
[email protected]
Haoran Wen Department of Mechanical and Aeronautical Engineering Center for Computational Science and Engineering University of California Davis, CA 95616, USA
[email protected]
From Network Structure to Dynamics and Back Again: Relating Dynamical Stability and Connection Topology in Biological Complex Systems Sitabhra Sinha The Institute of Mathematical Sciences, CIT Campus, Taramani, Chennai 600113, India;
[email protected]
1 Introduction To see a world in a grain of sand, And a heaven in a wild flower, Hold infinity in the palm of your hand, And eternity in an hour. – William Blake, Auguries of Innocence Like Blake, physicists look for universal principles that are valid across many different systems, often spanning several length or time scales. While the domain of physical systems has often offered examples of such widely applicable “laws,” biological phenomena tended to be, until quite recently, less fertile in terms of generating similar universalities, with the notable exception of allometric scaling relations [20]. However, this situation has changed with the study of complex networks emerging into prominence. Such systems comprise a large number of nodes (or elements) linked with each other according to specific connection topologies, and are seen to occur widely across the biological, social and technological worlds [4, 9, 16]. Examples range from the intra-cellular signaling system which consists of different kinds of molecules affecting each other via enzymatic reactions, to the internet composed of servers around the world which exchange enormous quantities of information packets regularly, and food webs which link, via trophic relations, large numbers of inter-dependent species. While the existence of complex networks in various domains had been known for some time, the recent excitement among physicists working on such systems has to do with the discovery of certain universal principles among systems which had hitherto been considered very different from each other. N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 1, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
4
S. Sinha
Reflecting the development of the modern theory of critical phenomena, the rise of physics of complex networks has been driven by the simultaneous occurrence of detailed empirical studies of extremely large networks that were made possible by the advent of affordable high-power computing and the development of statistical mechanics tools to analyze the new network models. Prior to these developments, the networks that were studied by physicists belonged to either the class of (i) regular networks, defined on geometrical lattices, where each node interacted with all the neighboring nodes belonging to a specified neighborhood, or (ii) random networks, where any pair of nodes had a fixed probability of being linked, i.e., interacting with each other. The first work that focused public attention on the new network approach presented a class of network models that were neither regular nor random, but exhibited properties of both [28]. Such small world networks, as they were referred to, exhibited high clustering (with nodes sharing a common neighbor having a higher probability of being connected to each other than to other nodes) and a very low average path length (where the path length between any two nodes is defined as the shortest number of connected nodes one has to go through in order to reach one node starting from the other). As the former property characterized a regular network, while the latter was typical for a random network, this new class of networks was somehow intermediate between the extremes of the two well-known network models, which was manifest in their construction procedure (Fig. 1). Several networks occurring in reality, in particular, the power grid, the actor collaboration network and the neural connection patterns of the C. elegans worm, were shown to have the small-world property. Later, other examples were added to this list, including the network of co-active functional brain areas [1] and the Indian railway system [21]. Very soon afterwards, it was discovered that the frequency distribution of a node degree (i.e., the number of links a node has) exhibits a power-law scaling form for a large variety of systems including the world wide web [3].
Fig. 1. Constructing a small-world network on a 2-dimensional square lattice substrate. Starting from a regular network (left) where each node is connected to its nearest and next-nearest neighbors, a fraction p of the links are rewired among randomly chosen pairs of nodes. When all the links are rewired, i.e., p = 1, the system is identical to a random network (right). For small p, the resulting network (center) still retains the local properties of the regular network (e.g., high clustering), while exhibiting global properties of a random network (e.g., short average path length).
From Network Structure to Dynamics and Back Again
5
This further underlined the fact that most networks occurring in reality are neither regular (in which case the degree distribution would be close to a delta function) nor random (which has a Poisson degree distribution), as for both cases the probability of having a node with large degree (i.e., a hub) would be significantly smaller than that indicated by the power-law tail of empirically obtained degree distributions. In addition, it was observed that there exist non-trivial degree correlations among linked pairs of nodes. For example, a network where nodes with high degree tend to preferentially connect with other high degree nodes is said to show assortative mixing [15]. On the other hand, in a disassortative network, nodes with a large number of links prefer to connect with nodes having low degree. Empirical studies indicate that most biological and technological networks are disassortative, while social networks tend to be assortative [16]. As assortative mixing promotes percolation and makes a network more robust to vertex removal, it may be hard to understand why natural evolution in the biological world has favored disassortativity. However, in a recent study, we have shown that when one considers the stability of dynamical states of a network, disassortative networks would tend to be more robust, and this may be one of the reasons why they are preferred [6]. This brings us to the thrust of recent work in the area of complex networks which has shifted from the initial focus on purely structural aspects of the connection topology to the role such features play in determining the dynamical processes defined on a network [27]. Over the past few years, much effort has been made to understand not only how structure affects dynamics, and hence function, in a network, but also the reverse problem of how functional criteria, such as the need for dynamical stability, can constrain the topological properties of a network. In this chapter, some of the principal results obtained by our group will be briefly described. The goal of our research program is to understand the evolution of robust yet complex biological structures, viz., networks occurring in reality that are stable against perturbations and, yet, which can adapt to a changing environment.
2 Biological Networks: Some Examples Across Length Scales Before describing our results, which are applicable to a wide range of networks, we provide motivation for our general approach by briefly discussing in this section a few examples of biological networks. Although they span an enormous range of length scales, from ∼10−8 m in the case of protein contact networks to ∼105 m in the case of ecological interaction networks, they are often subject to similar constraints and may share common structural and dynamical properties. Questions about networks in one domain may often have answers and ramifications in another domain.
6
S. Sinha
Molecular scale: protein contact network. Protein structure, viewed as a network of non-covalent connections between the constituent amino acids, is one of the smallest length scale networks in the natural world. Its nodes are the Cα atoms of each amino acid, and their interaction strength is determined by their proximity to each other. Two nodes are considered to be linked if the Euclidean distance between them (in 3-dimensional space) is less than a A, which is the relevant distance for noncutoff value dc , usually between 8–14 ˚ covalent interactions. Figure 2 shows the KirBac1.1 protein, which belongs to the family of potassium ion channels involved in transmission of inward rectifying current across a cellular membrane [13]. The protein consists of four identical subunits spanning the membrane and intra-cellular regions. The corresponding protein contact network (PCN) manifests the existence of the identical subunits in the approximately block diagonal structure of the adjacency matrix. In addition, each of these four blocks can be divided into two modules, corresponding approximately to the membrane and intra-cellular regions. It is easy to see that the PCN shares the features of a small-world network, with the majority of connections between spatially neighboring nodes, although there are a few long-range connections. This small-world property of PCNs for different protein molecules has indeed been noted several times in the literature (see, e.g., Ref. [2]). This is probably not very surprising, given that it is also true for a randomly folded polymer. However, in addition, the PCN adjacency network shows a modular structure, with a majority of connections occurring between nodes belonging to the same module. This is a feature not seen in conventional models of small-world networks (e.g., the Watts–Strogatz model [28]). It is all the more intriguing, as we have recently subunit I
intra−cellular domain
subunit II subunit III subunit IV
200 400 600
membrane domain
800 1000 200
400
600
800
1000
Fig. 2. Structure of the KirBac1.1 protein (left) which comprises four identical subunits spanning the membrane and intra-cellular regions [13]. The PCN is constructed A, whose adjacency matrix is shown for by considering a cutoff distance of dc = 12 ˚ the entire network (right). Each of the four blocks corresponding to a subunit shows a clear partition into membrane and intra-cellular compartments, indicating a modular structure.
From Network Structure to Dynamics and Back Again
7
shown that modular networks (whatever the connection topology of individual modules) exhibit the small-world properties of high clustering and low average path length [18]. To identify whether the existence of modules indeed has a significant effect on protein dynamics (e.g., during folding), we look at the spectral properties of the Laplacian matrix1 L, defined as Lii = ki , where the degree of node i, Lij = −1 if nodes i and j are connected, 0 otherwise. The eigenvector for the smallest eigenvalue (=0), c(1) , corresponds to the time-invariant properties of the system and has uniform contribution from all components. The next few smallest eigenvalues dominate the time-dependent behavior of the protein and show a relatively large spectral gap with the bulk of the eigenvalue spectra. This indicates the existence of very distinct time scales in the protein dynamics which approximately correspond to the interand intra-modular modes of motion. As we shall see, the occurrence of modular structures in complex networks and their effect on dynamics is not just confined to PCNs but appears in many other biological networks. Intra-cellular scale: signaling network. Signal transduction pathways, through which a cell responds appropriately to a signal or stimulus, involve ordered sequences of biochemical reactions carried out by enzymes inside the cell. One of the most commonly observed class of enzymes in intra-cellular signaling is that of kinases, which activate target molecules (usually proteins) by transferring phosphate groups from energy donor molecules such as ATP to the targets. This process of phosphorylation is mirrored by the reverse process of deactivation by phosphatases through dephosphorylation. Such reaction cascades are activated by second messengers (e.g., cyclic AMP or calcium ions) and may last for a few minutes, with the number of kinase proteins and other molecules involved in the process increasing with every reaction step away from the initial stimulation. Thus, such a signaling cascade can result in a large response for a relatively low-amplitude signal. Research over the past decade has, however, shown that the classical picture of almost isolated cascades linking a unique signal to a specific response does not explain many experimental results. The adaptability of intra-cellular signaling is now thought to be a result of multiple signaling pathways interacting with one another to form complex networks. In this picture, complexity arises from the large number of components, many of which have partially overlapping functions, from the large number of links (through enzymatic reactions) among components and from the spatial relationship between the components [29]. Figure 3 shows a small fraction of the signaling network downstream of the B-cell antigen receptor (BCR) involved in immune response. As the breakdown of communication in this network can lead to disease (a fact that may be utilized by infectious agents for proliferation), it is of obvious importance to understand the mechanisms by which the network allows the cell response to be sensitive to different stimuli and yet to be robust in the presence of intra-cellular noise. With this in mind, the time evolution 1
The Laplacian matrix is also referred to as the Kirchhoff matrix (e.g., see Ref. [10]).
8
S. Sinha IgG receptor Igα, Igβ Syk
Pyk2
PI3K
Lyn
PIP2
PIP3
Shc Btk
BLNK Grb2 SOS
Rac DAG MEKK
Raf−1 MEK 1/2 K
Erk 1/2
PDK1
PLCg2
Vav
MKK 4/7
MKK 3/4/6
Jnk 1/2
p38
IP3
PKC IKK IkB
Akt Ca2+
CaMK2 NFAT
Bad
Bcl2
Fig. 3. A subset of the signal transduction network of the BCR [12]. The kinases are represented by squares, while other molecules (such as second messengers and adapters) are depicted as circles.
of the activity (i.e., phosphorylation) of about 20 signaling molecules in this network was recorded in a recent experiment by Kumar et al. [12]. Apart from observing the activation profiles under normal conditions, the network was also subjected to a series of perturbations by serially blocking each of these molecules from activating any of the other molecules in the network. The resulting experimental data, capturing the behavior of these molecules under 21 different conditions, enabled the detection of correlations between the activity of these molecules. This showed that the existing picture of interactions (Fig. 3) is grossly inadequate in explaining these correlations, e.g., the fact that p38 kinase seems to influence the activation of a majority of the other molecules, although it occurs at the end of a particular pathway. The results suggest that the signaling network is, in fact, a far more densely connected system than had been previously suspected. It also raises the question of how certain signals can elicit very specific responses, without significant risk of cross-talk between interacting pathways. This brings us to the issue of whether functional modules can exist in networks, such that by using positive and negative interactions one can channel information from the stimulus to the response along specific subnetworks only. Inter-cellular scale: neuronal network. The previous question is of importance not only for information processing within a cell, but also between cells. The most important example of the latter process is, of course, the networks of neurons occurring in the brain. As the nervous system of the nematode C. elegans comprising 302 neurons has been completely mapped out (in terms of the positions of the neurons, as well as all their interconnections), it provides a model system for studying these issues. We have recently analyzed the connection topology of the non-pharyngeal portion of the nervous system to which the majority of the neurons (280) belong [7]. One of the striking
From Network Structure to Dynamics and Back Again
9
observations is that many of the sensory neurons belonging to different modalities, viz., chemosensation, mechanosensation, etc., send signals to the same set of densely connected interneurons which forms the innermost core of the nervous system. Subsequently, signals are sent from these interneurons to specific motor neurons which generate appropriate muscle response, e.g., moving along a chemical gradient, egg laying, etc. It is vital that the signals coming from different sensory neurons to the same interneurons should not interfere with each other, as it may result in activation of the incorrect motor response. A preliminary investigation of a dynamical model for the neuronal network shows that a complex set of excitatory and inhibitory links between the interneurons manages to achieve segregation of the different functional circuits. This means that, e.g., a mechanical tap signal will not elicit egg laying, even if the tap withdrawal circuit shares many common interneurons with the egglaying circuit. Even more interesting is the fact that such functional modules do not need the existence of structural modules in the underlying networks. It underscores the importance of looking at the nature of the interactions, which can create complicated control mechanisms to prevent cross-talk and enable robust response in the presence of environmental noise. Inter-organism scale: epidemic propagation network. At the scale of individual organisms, such as human beings, one of the most widely studied networks is that which leads to propagation of epidemics. The ubiquity of small-world networks in nature implies that some of the classic theories of epidemiological transmission, based on assumptions of random connections, may need to be reviewed. In particular, the global spread of diseases like SARS shows that even a few long-range links can drastically enhance the propagation of epidemics [8]. This has led to a series of studies of different disease propagation models on Watts–Strogatz or related network models (e.g., see Ref. [19]). However, as mentioned above, all the structural features of such networks are also shared by modular networks, although modular network have very different dynamical properties. We have recently shown that while Watts– Strogatz networks have a continuous range of time scales, modular networks exhibit very distinct time scales that are related to intra- and inter-modular events [18]. Thus, an effective strategy to counter the spread of epidemics must take into account a detailed knowledge of such structures in the social network of contagious and susceptible individuals. Inter-species scale: food webs. Possibly the largest (in terms of length scale) biological networks on earth are those of interactions between different species in an ecosystem. While general ecological networks consist of all possible links, such as cooperation and competition, food webs describe the trophic relations, i.e., between predator and prey. A food web is a directed network where the nodes are the various species, with prey connected by arrows to predators, the direction of the arrow indicating the flow of biomass. The links are usually weighted to represent the amount of energy that is transferred.
10
S. Sinha
It is in the context of these networks that questions first arose on the connection between the structural properties of a network and the stability of its dynamical behavior (see Section 4). Indeed, one not only asks what kind of structures allow complex networks to be stable against ever-present perturbations, but also how the requirement to be robust constrains the kind of structures such networks can evolve. To stress the universality of the questions asked by physicists about networks, we note that, like many other networks, food webs also have been shown to have a modular structure, with species in each module interacting between themselves strongly and only weakly with other species [11]. As in the other systems discussed earlier, the role that modularity plays in stabilizing the dynamics of ecosystems can be seen as a specific instance of a much more general question. Having discussed a few instances of how universal principles about networks can appear by investigating very different systems in the biological world, we now describe certain results of our studies on general network models. However, we stress that each of these results has relevance to problems appearing in the context of specific biological systems.
3 From Structure to Dynamics The role that the connection topology of a network plays in the nature of its dynamics has been extensively investigated for spin models occurring in physics. In fact, such systems had been explored for a long time prior to the recent interest in complex networks, and many results are known regarding ordering transition in both regular as well as random structures. More recently, it has been shown that, for partial random rewiring in a system of sufficiently large size, any finite value of p (the rewiring probability) causes a transition to the small-world regime, with the Ising model defined on such a network exhibiting a finite temperature ferromagnetic phase transition [5]. However, spin models are extremely restricted in their dynamical repertoire; therefore, researchers have looked at the effect of introducing other kinds of node dynamics in such network structures, e.g., oscillators. Motivated by recent observations that the brain may have a connection structure with small-world properties (see e.g., Ref. [1]), we have examined the effect of long-range connections (i.e., non-local diffusion) over an otherwise regular network of nodes with links between nearest neighbors on a square lattice [25]. The dynamics considered is that of the excitable type, with the variable having a single stable state and a threshold. If a perturbation causes the system variable to exceed the threshold, we see a rapid transition to a metastable excited state followed by a slow recovery phase when the system gradually converges to the stable state. As a result of coupling the dynamics of individual nodes through diffusive coupling, various spatial patterns (which may be temporally varying) are observed. Such a dynamics is commonly observed in a large variety of biological
From Network Structure to Dynamics and Back Again Temporal Patterns Burn−out
Spatial Patterns time
0
0
0
500
0.2
1000
time
0.5
Activity
0.5
1500
11
2000
0.4
p
0
1600
plc 0.6
1800
0.5
time
0 2000 0 100 200
0.8 pu c
1
Fig. 4. Schematic diagram indicating the different dynamical regimes in a 2-dimensional small-world excitable medium as a function of the rewiring probability, p. For low p, the system exhibits spatial patterns characterized by single or multiple spirals. At p = plc , there is a transition to a state dominated by temporally periodic patterns that are spatially relatively homogeneous. Above p = puc , all activity ceases after a brief transient.
cells such as neurons and cardiac myocytes, as well as in non-linear chemical systems such the Belousov–Zhabotinsky reaction. In our simulations, by varying the probability of long-range connections, p, we have observed three categories of patterns. For 0 < p < plc , after an initial transient period where multiple coexisting circular waves are observed, the system is eventually spanned by a single or multiple rotating spiral waves whose temporal behavior is characterized by a flat power spectral density. At p = plc , the system undergoes a transition from a regime with temporally irregular, spatial patterns to one with spatially homogeneous, temporally periodic patterns (Fig. 4). The latter behavior occurs over the range plc < p < puc as a result of the increased number of long-range connections, whereby a large fraction of the system is synchronously active and subsequently goes into the recovery phase. Beyond the upper critical value puc , there is no longer any self-sustained activity in the system, as all nodes converge to the stable state. The patterns in each regime were found to be extremely robust against even large perturbations or disorder in the system. Our model explains several hitherto unexplained observations in experimental systems where non-local diffusion had been implemented [26]. In addition, by identifying the long-range connections with those made by neurons and the regular network with that formed by the glial cells in the brain, our results provide a possible explanation of why evolution may have preferred to increase the number of glial cells over neurons (with a ratio of more than 10:1 for certain parts of the human brain) in order to maintain robust dynamical patterns as brain size increased. It also points towards a possible functional role of the small-world brain topology in the occurrence of dynamical diseases such as epileptic seizures and bursts. More generally, our work shows
12
S. Sinha
how non-standard network topologies can influence system dynamics by generating different kinds of spatio-temporal patterns depending on the extent of non-local diffusion.
4 From Dynamics to Structure An important functional criterion for most networks occurring in nature and society is the stability of their dynamical states. While earlier studies have concentrated on the robustness of the network when subjected to structural perturbations (e.g., removal of nodes or links), we have looked at the effect of perturbations on the steady states of network dynamics. In particular, the question we ask is whether networks become more susceptible to small perturbations as their size (i.e., number of nodes N ) increases, the connections between the nodes become denser (i.e., increased connection probability C) and the average strength of interaction (s) increases. This is related to a decades-old controversy, often referred to as the stability-complexity debate. In the early 1970s, May [14] had shown that for a model ecological network, where species are assumed to interact with a randomly chosen subset of all other species, an arbitrarily chosen equilibrium state of the system becomes unstable if any of the parameters determining the network’s complexity (e.g., N , C or s) is increased. In fact, by using certain results of random matrix theory, the critical condition for the stability of the network was shown to be N Cs2 < 1 (May–Wigner theorem) [14]. This flew against common wisdom, gleaned from a large number of empirical studies as well as naive reasoning, which dictated that increased diversity and/or stronger interactions between species results in more robust ecosystems. Thus, ever since the publication of these results, there have been attempts to understand the reason behind the apparent paradox, especially as this result relates not only to ecological systems but extends to all dynamical networks for which the stability of equilibria has functional significance, e.g., in intra-cellular biochemical networks where the concentrations of different molecules need to be maintained within physiological levels. Two of the common charges leveled against the theoretical model of May is that (i) it assumes the interaction network to be random, whereas naturally occurring networks may have certain kinds of structures, and (ii) the linear stability analysis assumes the existence of simple steady states (viz., fixed point attractors), which may not be the case for real systems that may either be oscillating or in a chaotic state. In our work on dynamical systems defined on networks, we have tried to address both of these lines of criticism (see Ref. [31] for a recent discussion of our results from the perspective of ecosystem robustness). For example, focusing on the question of the inadequacy of linear stability analysis, we have considered networks with non-trivial dynamics at the nodes, spanning the range from simple steady states to periodic oscillation and fully developed chaos, and measured the robustness of the dynamics with respect to variations in N , C and s [23, 24].
From Network Structure to Dynamics and Back Again
13
Each node in our model network has a dynamical variable associated with it, which evolves according to a well-known class of difference equations commonly used for modeling population dynamics. By varying a non-linear parameter, the nature of the dynamics (i.e., whether it converges to a steady state or undergoes chaotic fluctuations) at each node can be controlled. However, in the absence of coupling, each node will always have a finite, positive value for its dynamical variable. When coupled in a network (initially in a random fashion) with links that can have either positive or negative weights, it is possible that as a result of dynamical fluctuations, the variable for some nodes can become negative or zero. As this implies the absence of any activity, the corresponding node is considered to be “extinct” and thus isolated from the network. This procedure may create further fluctuations and cause more nodes to becomes “extinct,” resulting in gradual reduction of the size of the network (Fig. 5). The final asymptotic size of the network, relative to its initial size, is a measure of its robustness—the more robust network is one with a higher fraction of nodes having persistent activity. Analysis showed that the network robustness (as measured by the above global criterion) not only decreased with N , C and s, as expected from local stability analysis, but actually matched the May–Wigner theorem quantitatively [23]. In addition, the asymptotic network exhibited robust macroscopic features: (a) the number of persistently active nodes was independent of the initial network size, and (b) the asymptotic number of links between these persistently active nodes was independent of both the initial size and connectivity [24]. This is all the more surprising, as the removal of nodes (and hence, links) is not guided by any explicit fitness criterion, but rather emerges naturally from the nodal dynamics through fluctuations of individual node properties. Our results imply that asymptotically
Pa
Fig. 5. Evolution of a network with non-trivial dynamics at the nodes. The initial (left) and final asymptotic (right) networks are shown. Only nodes having persistent activity are connected to the network. The figures were drawn using Pajek software.
14
S. Sinha
active networks are non-extensive: when two networks of size N are coupled to each other (with the same connectance as the individual networks), although the resulting network initially has a size 2N , the ensuing dynamical fluctuations will reduce its size to N . This implies that simply increasing the number of redundant elements is not a good strategy for designing robust systems. We have also looked at the effect of empirically reported structures, such as small-world connection topology and scale-free degree distribution, on the dynamical stability of networks. Our results indicate that, in general, introducing such structural features does not alter the outcome expected from the May–Wigner theorem [6, 22]. However, these details can indeed affect the nature of the stability-instability transition; for example, the transition exhibiting a cross-over from being very sharp (resembling first-order phase transition) for a random network to a more gradual change as the network becomes more regular in the small-world regime [22].
5 Evolution of Robust Networks This brings us to the issue of how complex networks can be stable at all, given that the May–Wigner theorem seems to hold even for networks that have structures similar to those seen in reality and where non-trivial dynamical situations have also been considered. The solution to this apparent paradox lies in the observation that most networks that we see around us did not occur fully formed but emerged through a process of gradual evolution, where stability with respect to dynamical fluctuations is likely to be one of the key criteria for survival. In earlier work, we have shown that a simple model, where nodes are gradually added to or removed from a network according to whether this results in a dynamically stable network or not, leads to a non-equilibrium steady state in which the network is extremely robust [30]. The robustness is manifested by increased resistance and resilience, as well as decreased probability of large extinction cascades, when the network size (i.e., the system diversity) is increased. Thus, our results reconcile the apparently contradictory conclusions of the May–Wigner theorem and a large number of empirical studies. More recently, we have shown that model networks can evolve many of the observed structural features seen among networks in the natural world, by taking into account the fact that the majority of such systems must optimize between several (often conflicting) constraints, which may be structural as well as dynamical in nature. In particular, most networks need to have high communication efficiency (i.e., low average path length) and low connectivity (to reduce the resource cost involved in maintaining many links) while being stable with respect to dynamical perturbations. If a network satisfied only the first two constraints, the optimal structure would have been that of a star (Fig. 6). Even if the resource cost constraint is somewhat relaxed, so that the network can have more links than the minimum necessary to make it
From Network Structure to Dynamics and Back Again
15
(A)
(I)
(II)
(B)
(C)
Fig. 6. Networks with (I) star and (II) clustered star connection topologies can form the fundamental building blocks of different types of modular networks. Network configurations with clustered star modules can be constructed by (A) connecting different modules by single undirected links among the hub nodes, or (B) connecting nodes of a module to another module only through the hub node of the latter, or (C) connecting nodes of a module randomly to any node of another module.
connected, the resulting optimal configuration is slightly modified to that of a “clustered” star. However, we note that the dynamical equilibria in such systems would be extremely unstable with respect to small perturbations. This happens because the rate of growth of small perturbations is related to the maximum degree of the network, which, in the case of a star or a clustered star, is almost identical to the system size. It is easy to see that dividing the network into multiple stars, connected to each other, will reduce the maximum degree and hence increase the stability. Indeed, our results show that simultaneous optimization of all three constraints results in networks with modular structure, i.e., subnetworks with a high density of connections within themselves compared to between distinct subnetworks, where each module possesses a prominent hub [17] (see Fig. 6 for possible configurations of such modular networks). As these evolved systems also exhibit heterogeneous degree distribution, our findings have implications for a wide range of systems in the biological and technological worlds where such features have been observed.
16
S. Sinha
Acknowledgments I would like to thank my collaborators with whom the work described here has been carried out, in particular, R. K. Pan, S. Sinha, N. Chatterjee, M. Brede, C. C. Wilmers, J. Saram¨ aki and K. Kaski, as well as S. Vemparala, D. Kumar, K. V. S. Rao and B. Saha for helpful discussions.
References 1. Achard, S., Salvador, R., Whitcher, B., Suckling, J., Bullmore, E.: A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs. J. Neurosci., 26, 63–72 (2006) 2. Aftabuddin, M., Kundu, S.: Hydrophobic, hydrophilic and charged amino acid networks within protein. Biophys. J., 93, 225–231 (2007) 3. Albert, R., Barab´ asi, A.L.: Emergence of scaling in random networks. Science, 286, 509–512 (1999) 4. Albert, R., Barab´ asi, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys., 74, 47–97 (2002) 5. Barrat, A., Weigt, M.: On the properties of small-world network models. Eur. Phys. J.B, 13, 547–560 (2000) 6. Brede, M., Sinha, S.: Assortative mixing by degree makes a network more unstable. Arxiv preprint, cond-mat/0507710 (2005) 7. Chatterjee, N., Sinha, S.: Understanding the mind of a worm: Hierarchical network structure underlying nervous system function in C. elegans. Prog. Brain Res., 168, 145–153 (2007) 8. Deem, M.W.: Mathematical adventures in biology. Physics Today, 60(1), 42–47 (2007) 9. Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford Univ. Press, Oxford (2003) 10. Haliloglu, T., Bahar, I., Erman, B.: Gaussian dynamics of folded proteins. Phys. Rev. Lett., 79, 3090–3093 (1997) 11. Krause, A.E., Frank, K.A., Mason, D.M., Ulanowicz, R.U., Taylor, W.W.: Compartments revealed in food-web structure. Nature, 426, 282–284 (2003) 12. Kumar, D., Srikanth, R., Ahlfors, H., Lahesmaa, R., Rao, K.V.S.: Capturing cellfate decisions from the molecular signatures of a receptor-dependent signaling response. Molecular Systems Biology, 3, 150 (2007) 13. Kuo, A., Gulbis, J.M., Antcliff, J.F., Rahman, T., Lowe, E.D., Zimmer, J., Cuthbertson, J., Ashcroft, F.M., Ezaki, T., Doyle, D.A.: Crystal structure of the potassium channel KirBac1.1 in the closed state. Science, 300, 1922–1926 (2003) 14. May, R.M.: Stability and Complexity in Model Ecosystems. Princeton Univ. Press, Princeton (1973) 15. Newman, M.E.J.: Assortative mixing in networks. Phys. Rev. Lett., 89, 208701 (2002) 16. Newman, M.E.J.: The structure and function of complex networks. SIAM Review, 45, 167–256 (2003) 17. Pan, R.K., Sinha, S.: Modular networks emerge from multiconstraint optimization. Phys. Rev. E, 76, 045103(R) (2007)
From Network Structure to Dynamics and Back Again
17
18. Pan, R.K., Sinha, S.: The small world of modular networks. Arxiv preprint, arXiv:0802.3671 (2008) 19. Saram¨ aki, J., Kaski, K.: Modelling development of epidemics with dynamic smallworld networks. J. Theor. Biol., 234, 413–421 (2005) 20. Schmidt-Nielsen K: Scaling: Why is Animal Size So Important? Cambridge Univ. Press, Cambridge (1984) 21. Sen, P., Dasgupta, S., Chatterjee, A., Sreeram, P.A., Mukherjee, G., Manna, S.S.: Small-world properties of the Indian railway network. Phys. Rev. E, 67, 036106 (2003) 22. Sinha, S.: Complexity vs. stability in small-world networks. Physica A, 346, 147– 153 (2005) 23. Sinha, S., Sinha, S.: Evidence of universality for the May-Wigner stability theorem for random networks with local dynamics. Phys. Rev. E, 71, 020902(R) (2005) 24. Sinha, S., Sinha, S.: Robust emergent activity in dynamical networks. Phys. Rev. E, 74, 066117 (2006) 25. Sinha, S., Saram¨ aki, J., Kaski, K.: Emergence of self-sustained patterns in smallworld excitable media. Phys. Rev. E, 76, 015101(R) (2007) 26. Steele, A.J., Tinsley, M., Showalter, K.: Spatiotemporal dynamics of networks of excitable nodes. Chaos, 16, 015110 (2006) 27. Strogatz, S.H.: Exploring complex networks. Nature, 410, 268–276 (2001) 28. Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442 (1998) 29. Weng, G., Bhalla, U.S., Iyengar, R.: Complexity in biological signaling systems. Science, 284, 92–96 (1999) 30. Wilmers, C.C., Sinha, S., Brede, M.: Examining the effects of species richness on community stability: An assembly model approach. Oikos, 99, 363–367 (2002) 31. Wilmers, C.C.: Understanding ecosystem robustness. Trends Ecol. Evoln., 22, 504–506 (2007)
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis Madalena Chaves,1 Thomas Eissing,2 and Frank Allg¨ ower3 1
2
3
COMORE, INRIA, 2004 Route des Lucioles, BP 93, 06902 Sophia-Antipolis, France;
[email protected] Bayer Technologies Services GmbH, PT-AS Systems Biology, Germany
[email protected] Institute for Systems Theory and Automatic Control, University of Stuttgart, Pfaffenwaldring 9, 70550 Stuttgart, Germany;
[email protected]
1 Introduction Programmed cell death (or apoptosis) has an essential biological function, enabling successful embryonic development, as well as maintenance of a healthy living organism [6]. Apoptosis is a physiological process which enables an organism to remove unwanted or damaged cells. Malfunctioning apoptotic pathways can lead to many diseases, including cancer and inflammatory or immune system related problems. A family of proteins called caspases are primarily responsible for execution of the apoptotic process: basically, in response to appropriate stimuli, initiator caspases (for instance, caspases 8, 9) activate effector caspases (for instance, caspases 3, 7), which will then cleave various cellular substrates to accomplish the cell death process [22]. Nuclear factor κB (NFκB) is a transcription factor for a large group of genes which are involved in several different pathways. For instance, NFκB activates its own inhibitor (IκB) [14] as well as groups of pro-apoptotic and anti-apoptotic genes [21]. Among the latter, NFκB activates transcription of a gene encoding for inhibitor of apoptosis protein (IAP). This protein in turn contributes to downregulate the activity of the caspase cascade which forms the core of the apoptotic pathway [6, 8]. The canonical NFκB pathway is induced, among other stimuli, by the cytokine tumor necrosis factor α (TNFα) [21]. Binding of TNFα to death receptor TNFR1 forms a first complex which eventually activates NFκB. A second complex is later formed, which will activate the initiator caspase 8 [6], and hence activate the apoptotic process. The same signal (TNFα stimulation) thus triggers two parallel but contrary pathways: the pro-apoptotic caspase cascade and the anti-apoptotic NFκB-IκB-IAP pathway. These two pathways, together with the interactions among their components, form a N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 2, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
20
M. Chaves et al.
complex network which shapes the decision on cell survival or initiation of programmed cell death. To contribute to a better understanding of the role of NFκB in the regulation of apoptosis, we propose a qualitative study of this system and its dynamics, based on a discrete (Boolean) model of the complex network. This discrete model closely follows a continuous one, recently developed and studied in [23, 24]. The model integrates the well-known model for the NFκB pathway [17] and the caspase cascade [8]. Boolean models provide a convenient formalism to describe protein and gene networks [25]. The states of the network components (e.g., proteins or messenger RNAs) are characterized as “expressed” or “not expressed” and are represented by logical variables (with values 0 or 1). The interactions among the various components are classified as “inhibition” or “activation” links (these can generally be deduced from gene/protein expression data). Boolean models thus describe the network structure of a system without involving any kinetic details. The qualitative behaviour of a system can be seen as an emergent property of this structure. Boolean models are especially useful in the case of large networks [1, 9], for which kinetic parameters are often unknown, but qualitative properties such as generation of specific gene expression patterns, stability or multistability, and oscillatory modes can be studied. Several methods have been developed for analysis of discrete and qualitative models [2, 5, 7, 13, 26]. Using an approach which combines discrete rules with continuous degradation rates, our model reproduces many of the known properties of the system, notably the oscillatory dynamics that can be induced by the NFκB-IκB negative feedback loop [14, 15, 19]. We explore different configurations for the network structure and predict its effects on the decision between cell survival or apoptosis.
2 The Model The network of interactions among the NFκB pathway and the apoptosis signaling cascade to be studied here is shown in Fig. 1. The various components of the network (here messenger RNAs, proteins, or protein complexes) form the set of variables or nodes (Xi , i = 1, . . . , n) of the Boolean model. The system will evolve according to a set of logical rules which are deduced from the interactions or links depicted in the schematic diagram of Fig. 1. The interactions among nodes can be classified as “activation” or “inhibition” links: a directed arrow Xi → Xj means that a high concentration of component Xi activates component Xj , while the symbol Xi Xj means that a high concentration of component Xi inhibits Xj . The components in our model and the activation or inhibition links among them are based on existing literature data. For general aspects, the reviews [6, 21] were used. However, some pathways of regulation among the NFκB pathway and the caspase cascade are not yet clear, and more work is needed to understand how these two signaling pathways are interconnected. In this chapter, we aim to investigate and test several possible hypotheses for
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis
21
Fig. 1. Schematic diagram of the NFκB pathway and the caspase cascade (light shaded regions). The oval dark grey shaded region represents the cellular nucleus. Both pathways are activated by binding of TNFα to death receptor TNFR1 (the resulting complex is represented simply by the rectangle TNF). Messenger RNAs are represented by ellipses, while transcription factors, caspases, and other proteins are represented by squares. To study the interconnections between the two pathways, four network variants, based on different combinations of the links A, L, and C, will be analysed and compared (see Table 2).
the combined network structure. We will consider four model variants and try to discriminate between them by comparing our numerical analysis with experimental data from the literature. The four network variants (see Table 2) are based on different combinations of three links (A, L, C in Fig. 1) which have been suggested but are not fully established in the apoptosis literature. The NFκB pathway follows very closely the model presented in [17]. Stimulation of death receptors with TNFα leads (see for instance [6]), first, to the formation of a complex I (T1 in Fig. 1) which will recruit and activate inhibitor of IκB kinases (IKK). Inhibitor of NFκB, or IκB, acts by binding to NFκB molecules and preventing their transcriptional function. Active IKK (IKKa) phosphorylates IκB which releases NFκB, thus enabling its translocation to the nucleus and transcription of NFκB-dependent genes, including genes for inhibitor of apoptosis protein (iap), inhibitor of NFkB (iκB), a protein associated with inhibition of complex T2 (flip), and a protein regulating IKK activity (a20) [21]. Transcription of IκB mRNA generates a negative feedback
22
M. Chaves et al.
loop in the NFκB pathway [14, 20], which may lead to oscillatory behaviour in NFκB and IκB concentrations [19]. In a second step, after dissociation of components of complex I from the death receptor, a second complex is formed (T2 in Fig. 1) which will recruit and activate initiator caspase 8 (C8a). As a result of the signaling cascade [8, 22], effector caspase 3 is also activated (C3a). Thus, complex T1 activates the anti-apoptotic pathway and, after a certain delay, complex T2 activates the pro-apoptotic pathway. Two well-documented points of regulation of the apoptotic pathway by NFκB are inhibition of C3a by IAP and regulation of complex T2 by FLIP [6]. Active caspase 8 was found to be negatively regulated by caspase-8 and caspase-10-associated RING proteins (CARPs) [18], which seem to play an analogous role to IAP’s, but are less well studied. It was found that CARPs are overexpressed in tumors, and that their suppression leads to restoration of the apoptotic pathway, with the CARP being rapidly cleaved. In addition, it was observed that inhibitors of caspase 3 block CARP cleavage. In our model, we introduced CARP and a pre-complex CARP0 , which is inhibited by C3a. Inhibition by C3a is, however, not sufficient to control CARP, and there are probably other regulators. Since CARP plays a similar role to caspases 8 and 10, as IAP plays to caspases 3 and 9 (and in the absence of further details), we assume that the pre-complex CARP0 is also regulated by a product of the NFκB pathway. The points where the caspase cascade influences the NFκB pathway are less well documented. We will use our model to test different hypotheses by studying and comparing the network dynamics for the following cases (see also Table 2): inhibition of IKKa (link L) and/or NFκB (link A) by C3a, or neither of these links present. To obtain the logical rules shown in Table 1, some simplifications of the biological processes were inevitably introduced. For instance, the bound complex NFκB−IκB (either in the cytoplasm or in the nucleus) was not explicitly considered in the system, but was simply treated as an inhibition effect: the rule for NFκB says that it vanishes whenever IκB is expressed. Thus, any state with NFκB = 0 and IκB = 1 represents in fact a high concentration of bound complex NFκB − IκB, while any state with NFκB = 1 and IκB = 0 represents a high concentration of free NFκB and low concentration of free IκB. To translate our diagram into a set of logical rules, the convergence of two or more arrows (either activation or inhibition) at the same node was always treated as a logical AND, except in three cases: IκB, IAP, and CARP0 . For these proteins, the overall effect was treated as an AND in the presence of TNF stimulation, but treated as an OR in the absence of TNF. These three proteins represent inhibitors whose levels should be stable in the absence of any stimulus [8]: IAP and CARP0 (or CARP) should be effective inhibitors of the caspases, and IκB should be at approximately constant levels to control NFκB transcriptional activity. In contrast, with TNF stimulation, the degradation rates of these proteins can vary and lead to rapid changes in their concentrations (different degradation rates in the presence or absence of TNF
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis
23
have been observed, notably for bound IκB [20]). For instance, under TNF treatment, the rule for inhibition of NFκB is simplified to IκB+ = [iκB and not IKKa]. Suppose that IKK becomes activated at time t1 , that is IKKa(t1 ) = 1. Then, in the next iteration of the model, the IκB rule implies that IκB will degrade very fast, with IκB(t1 +Δ) = 0. In contrast, in the absence of the TNF stimulus, the rule is IκB+ = [iκB or not IKKa]. If IKK becomes active at time t1 , one has IκB(t1 + Δ) = iκB(t1 ), meaning that IκB is only rapidly degraded if no more of its messenger RNA is available. A similar reasoning justifies the rules for IAP and CARP0 . The rules for these three proteins with inhibiting roles reflect the fact that their degradation rates, and hence turnover, can be much faster in response to TNF stimulation.
3 Analysis of Boolean Models Boolean networks are a representation of a system, consisting of a set of n variables or nodes X = (X1 , . . . , Xn ), together with a set of logical rules (Fi (X), i = 1, . . . , n) describing the evolution of the system from the current state (Xi at time t) to the next state (Xi at time t + Δ). The variables or nodes take values in the discrete set {0, 1}, where 1 (resp., 0) denotes the “expressed” (resp., “not expressed”) state of the node. The associated rules are typically a composition of logical OR and AND functions, which can be determined from gene/protein expression patterns (from Western blots or microarray data, for instance). The set of rules Fi given in Table 1 for the NFκB pathway and the caspase cascade is a translation of the diagram shown in Fig. 1. The temporal evolution of the system, X(t), t ∈ (0, ∞), is determined by successively iterating the logical rules Fi , for which several algorithms are available. Synchronous algorithms assume that all nodes are simultaneously updated: Xi+ = Fi (X1 , . . . , Xn ),
i = 1, . . . , n,
(1)
where Xi ∈ {0, 1}, X = (X1 , . . . , Xn ) denotes the state of the system at time t, and X + = (X1+ , . . . , Xn+ ) denotes the next state (at t + Δ). Alternatively, with asynchronous algorithms, at each iteration the nodes are sequentially updated, according to a given order (which can be prespecified or randomly chosen). Discrete models focus on the structure of the network (links), thus offering a more qualitative description of the system’s dynamics. Continuous models may offer more detailed descriptions of a system, but they also have the disadvantage of involving a large set of kinetic parameters, many of which are unknown. A method for analysis of Boolean models was introduced in [12, 13], which provides a bridge between discrete and continuous approaches. In this method, each node Xi of the network is represented by one continuous variable (xi ) and one discrete variable (Xi , as before). The continous variables are
24
M. Chaves et al.
Table 1. Boolean rules for the model of regulation of apoptosis via the NFκB pathway. TNF is a constant input. Identification of the nodes is given in the text. The letter “a” juxtaposed to a variable name denotes the active form of a molecule. The subscript “nuc” denotes the given component in the cellular nucleus. Alternative rules are given for the presence/absence of links A, C, L. Node +
T1 T2 + IKKa+ NFκB+ NFκB+ nuc iκB+ IκB+ IκB+ nuc a20+ A20+ A20a+ iap+ IAP+ flip+ FLIP+ C3a+ C8a+ CARP+ 0 CARP+
Boolean rule TNF T1 and not FLIP {L} T1 and not A20a and not C3a {no L} T1 and not A20a {A} not IκB and not C3a {no A} not IκB NFκB and not IκBnuc NFκBnuc [T1 and (iκB and not IKKa)] or [not T1 and (iκB or not IKKa)] IκB NFκBnuc a20 T1 and A20 NFκBnuc [T1 and (iap and not C3a)] or [not T1 and (iap or not C3a)] NFκBnuc flip not IAP and C8a {C} not CARP and (C3a or T2 ) {no C} C3a or T2 [T1 and (NFκBnuc and not C3a)] or [not T1 and (NFκBnuc or not C3a)] CARP0
governed by ordinary differential equations, which combine a synthesis rate (based on its Boolean rule) and a linear degradation rate: d xi = −ai xi + bi Fi (X1 , X2 , . . . , Xn ), dt
i = 1, . . . , n.
(2)
At each instant t, the discrete variable Xi is defined as a function of the continuous variable according to a threshold value of its maximal concentration: 0, xi (t) ≤ θi abii Xi (t) = (3) 1, xi (t) > θi abii , where θi ∈ (0, 1) represents the fraction of maximal concentration which is necessary for component Xi to become “active” and perform its biological functions. Initial conditions are equal for discrete and continuous variables: Xi (0) = xi (0). It is easy to see that the hypercube [0, b1 /a1 ] × · · · × [0, bn /an ] is an invariant set for system (2). The continuous variables denote concentrations of molecules; they are translated into a Boolean 0/1 response according to θi . The discrete variables Xi represent expression (1) or not expression (0)
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis
25
of species i, according to whether its continuous concentration xi is above or below the threshold θi bi /ai . Letting the parameters ai , bi , and θi be specific for each node i allows us to study different time scales for different biological processes (for instance, transcription, translation, or post-translational processes, as in [5]), or investigate the relative turnover rates of two molecules. Similar piecewise linear systems have also been studied in [7, 26]. 3.1 Steady States The steady states of a Boolean model are given by all the possible solutions X ∗ of the equations: Xi∗ = Fi (X1∗ , . . . , Xn∗ ),
i = 1, . . . , n.
It is easy to see that any steady state of the Boolean model yields a steady state of the piecewise linear equations (2), since d xi bi = 0 ⇔ xi = Fi (X1 , X2 , . . . , Xn ), i = 1, . . . , n, dt ai independently of θi . Because the right-hand side of this equation is discontinuous, it is difficult to provide general results on the existence and uniqueness of solutions for system (2) (see for instance [3] and [11]). In view of this difficulty, in the present study we will assume that trajectories are well defined and analyze their dynamical behavior. For the model of Table 1, the steady states depend on the value of TNF (see Table 2). It is not difficult to check that (both with and without link A) there are exactly two distinct steady states when TNF = 0, characterized by the presence or absence of caspases 3 and 8, and hence corresponding to the survival or apoptotic responses (nodes not indicated below are zero): (4) (Ap0 ) T1 = T2 = 0, C3a = C8a = 1, IκB = IκBnuc = 1, (Lf0 ) T1 = T2 = 0, IκB = IκBnuc = 1, CARP0 = CARP = IAP = 1. This is in agreement with the idea that, under typical conditions, the cell should be capable of stably maintaining either an apoptotic or a survival Table 2. Steady states of the Boolean model, for each model variant, in the presence and absence of TNF. Model I II III IV
Links A, C, no L L, C, no A C, no A, no L L, no A, no C
TNF = 0 Ap0 , Ap0 , Ap0 , Ap0 ,
Lf0 Lf0 Lf0 Lf0
TNF = 1
Oscillations?
Ap1 — — —
Yes Yes Yes Yes
26
M. Chaves et al.
state [8, 4]. If TNF = 1, there is only one possible steady state for models with link A: (Ap1 )
T1 = T2 = 1, C3a = C8a = 1.
(5)
For models with no link A, there is no possible steady state when TNF = 1, and there are only periodic orbits of period higher than 1. Therefore, during TNF treatment, models with link A may at any time make a decision towards the apoptotic pathway, while models with no link A will exhibit oscillatory behaviour and can only make a decision when TNF treatment ceases. Upon removal of TNF stimulation, trajectories of system (2) may be expected to converge to either the apoptotic or survival state. The choice of one or the other state will depend on the initial condition and the set of parameters ai , bi , and θi . Since these parameters are very likely to vary from cell to cell, it is reasonable to consider several (randomly chosen) sets of parameters and then compute the probability of convergence to each steady state. To examine the dynamics of system (2), and its dependence on parameters and the structure of the network of interactions, several numerical studies were performed, as described next. 3.2 Numerical Experiments To test the model and analyse the effects of links A and L (Fig. 1), system (2) was simulated several times, with randomly chosen sets of parameters. For simplicity, the synthesis rates and threshold constants were fixed (bi = 1 and θi = 0.5 for all i), and only parameters ai were allowed to vary, chosen from a uniform distribution in the interval [1/3, 3] (h−1 ). This seems reasonable, as the degradation rates used in [17] are roughly between 0.5 and 4 h−1 . Observe that ai plays a double role: it represents a degradation rate, but also defines the 0/1 threshold concentration (0.5/ai ). Hence, high degradation rates also imply that a lower concentration is needed to achieve the 0/1 transition. Different durations of TNF stimulation were considered, namely: 2, 6, 11, 16, and 21 hours. For these simulations, one initial condition was chosen: IκB(0) = 1 and all other nodes set to zero. This is based on a natural physiological starting point of the system: previous to stimulation, IKK is in its inactive form, while IκB is bound to NFκB, preventing transcriptional activity. Caspases reside in the cytosol in dormant forms [22]. To understand the importance of the links A, C, and L (the least well documented), four variants of the model depicted in Fig. 1 are compared: (I) links A and C present, (II) links L and C present, (III) only link C present, and (IV) only link L present (as listed in Table 2). The first three variants aim at comparing the effects of links A and L, and the last aims at evaluating the effect of link C. Other alternatives gave similar results (for example, a model with all three links gave results very similar to I) and thus are not detailed here. For each variant, the response of the system to each of the five TNF
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis
27
durations was simulated 500 times. Since different sets of parameters {ai } introduce different time scales, variations in the dynamics from one simulation to another are expected. These variations may also be interpreted as a result of natural variability in biological systems. The average response over the 500 simulations will then yield the probability of the system converging towards each of the steady states. Other open questions that may be studied with our model include competition between the pro- and anti-apoptotic pathways and the point of irreversibility of the apoptotic decision. For instance, how long after caspase activation is recovery from the apoptotic pathway still possible [22]? To address these questions, numerical experiments were conducted by letting NFκB(0) = 1, setting all others to zero, and maintaining C3a(t) = 1 for durations of 10, 30, 60, and 360 minutes. For analysis of the numerical results, a “peak” in the trajectory of node Xj will be defined as a time interval [T0 , T1 ], during which Xj (t) = 1, and such that Xj (T0 − Δ) = Xj (T1 + Δ) = 0. The period of oscillations is calculated as the average time interval between the onset of two consecutive peaks, i.e., Np 1 T0,i − T0,i−1 , Period = Np − 1 i=2
where Np is the number of peaks observed during the simulation time.
4 Results and Discussion In the numerical simulations, it is observed that, once TNF stimulation ceases, a steady state pattern is always achieved, corresponding to either the apoptosis or survival states (4), (5). In the former case IκB is bound to NFκB, so that mRNAs and proteins downstream of NFκB are not expressed, and the cell has chosen the apoptotic pathway. The latter case represents survival of the cell, with IAP stably expressed preventing C3a activation, and CARP preventing C8a activation (see Fig. 2). In the presence of TNF stimulation, IκB, NFκB, and its dependent mRNAs/proteins may exhibit oscillatory dynamics, as observed experimentally in [14, 19]. In fact, computation of steady states shows that the models with no link A have no alternative but to exhibit oscillatory behaviour in the presence of TNF, since no possible steady states exist (except possible special solutions of the associated differential inclusion). The oscillatory behaviour (see analysis below) is in very good agreement with the experimental data reported in [19]. Qualitatively, all model variants respond in a similar fashion to TNF stimulation. As the stimulus duration increases, more cells choose the apoptotic pathway. Testing the four model variants shows that link A is very strong: not surprisingly, models with link A favour the apoptotic pathway, with 80% of cells reaching the apoptotic state, as opposed to around 50% or 40% in
M. Chaves et al.
TNF
28
1
1
0.5
0.5
C3a
C8a
IAP
NFkBn
IkBn
IKK
0 0 1
5
10
15
0 0 1
20
10
15
20 1.1631
0.5
0.5 0 0 1
5
10
15
0 0 1
20
5
10
15
20 2.9469
5
10
15
20 2.5784
5
10
15
20 1.8348
5
10
15
20 2.5642
5
10
15
1.898 0.5
0.5 0 0 1
5
10
15
0 0 1
20 2.3488
0.5
0.5
0 0 1
5
10
15
0 0 1
20 0.90041
0.5
0.5
0 0 1
5
10
15
0 0 1
20 0.79962
0.5
0.5
0 0 1
5
10
15
0 0 1
20 0.4439
0.5 0
5
2.6733
20 0.69736
0.5 0
5
10
15
0
20
0
5
Time (hours)
10
15
20
Time (hours)
Fig. 2. Example of network dynamics with the hybrid model (variant II), corresponding to cell survival (left) or apoptosis (right) solution. Numbers indicate the degradation rates for these numerical experiments. Solid lines represent normalized continuous variables (xi ) and dashed lines represent discrete variables (Xi ). 90 80
Survival rate (%)
70 60
III
50
II
40
IV
30
I
20 10
2
4
6
8
10
12
14
16
18
20
22
TNF duration (hours)
Fig. 3. Percentage of surviving cells for the four model variants.
models II and IV, or 30% in the model with only link C (which favours the anti-apoptotic pathway) (Fig. 3). These values appear to be in agreement with experimental data: Rehm et al. [22] report that, for 8 hour treatments with
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis Average period (hours)
6
6
I
5
II
5 survival
4
3
apoptosis
3
2
2
2
1
1
apoptosis
1 10
0 0
20
0
20
7
I
6
survival apoptosis
0
TNF duration (hours)
TNF duration (hours) 7
10
III
5
4
survival
0 0
TPeak i −TPeak i−1 (hours)
6
3
4
6
4
4
4
3
3
3
2
2
2
1
1
1
4
6
0 0
2
4
Peak i
III
6
II
5
Peak i
20
7
5
2
10
TNF duration (hours)
5
0 0
29
6
0 0
2
4
6
Peak i
Fig. 4. Top row: Average period of nuclear IκB oscillations for apoptotic or surviving cells, as a function of TNF stimulus duration. Vertical lines represent standard deviation over the 500 numerical experiments. Bottom row: Relative timing of sucessive peaks in IκB oscillations, for apoptotic (grey) or surviving (black) cells. The “+” signs mark the experimental peak timing in [19].
high and low concentrations of TNFα, the percentage of cells undergoing activation of effector caspases was, respectively, 86% and 24%. The numerical experiments with our model capture the response to high (or significant) concentrations of TNFα, so variants I (followed by II and IV) are closer to the real system. Quantitative analysis of the oscillatory behaviour reveals some interesting facts (Fig. 4). To characterize the oscillatory dynamics, the following quantities were computed for nuclear IκB: period of oscillations (approximated), number of peaks, and relative timing between peaks. First, in all cells oscillations cease when TNF stimulation ceases, in agreement with observations. Second, the timing of successive peaks is also in remarkable quantitative agreement with experimental data [19], see Fig. 4 (bottom row). The first peak in nuclear IκB concentration was observed about 72 minutes from the start of TNF stimulation, and the second peak appears about 4 hours later, very close to the 75 minutes and 4.5 hours reported in [19]. It is striking that the time span of the first peak is typically longer than that of the following peaks, and that the time lapse between consecutive peaks decreases (see Figs. 2, 4). Third, the average period of oscillations is fairly constant, but “depends” on the apoptosis/survival decision. Statistical analysis of the period of oscillations
30
M. Chaves et al.
(calculated as indicated in Section 3.2) in nuclear IκB indicates that there is a natural period (for TNF treatment longer than 3 hours) for cells that eventually survived. This period is about 3.5 ± 1 hours for models I, II, and IV, and slightly higher at 4 ± 1 hours for model III. In contrast, for cells that chose the apoptotic pathway, the period of oscillations can be much smaller. For models with link A, essentially no oscillations are observed in apoptotic cells (Fig. 4, top, left): this is because cell death is decided very early on, with link A immediately preventing any further NFκB activity. For model II (links C and L only), oscillations are observed in apoptotic cells with a natural period which is lower (about 3 ± 1 hours) than that for surviving cells (Fig. 4, top, middle). Results for model IV (not shown) are quite similar to those of model II. For model variant III, there is no difference between observed periods (Fig. 4, top, right). These results provide indications for discriminating between the four model variants and also suggest that the period of oscillations may play a role in the survival/apoptosis decision: lower periods/higher frequencies would lead towards the apoptotic pathway. A similar result has been reported, for instance, in the p53-Mdm2 system [16], where more peaks (higher frequency) were detected in response to higher (and more damaging) γ-irradiation doses. The p53-Mdm2 system also contains a negative feedback loop similar to the NFκB-IκB loop. To address the question of irreversibility of the apoptotic decision, we checked the capacity of the network to recover from overexpression of active caspase 3. Fixing node C3a at its maximal value for intervals of 10, 30, 60, and 360 minutes (that is setting discrete C3a(t) = 1, for t <10, 30, 60, or 360), we calculated the percentage of surviving cells. With model I there are no surviving cells after 1 hour of C3a overexpression but, with model II or IV, this percentage drops very fast from 45% to 30% survival at 1 hour overexpression and remains at this value for continued C3a overexpression (see Fig. 5). This suggests that a significant percentage of cells can still invert the apoptotic
60 III
Survival rate (%)
50 40
II 30 IV 20 10 I 0
0
50
100
150
200
250
300
350
400
C3a overexpression interval (mins.)
Fig. 5. Percentage of surviving cells under increasing intervals of C3a overexpression for the four model variants and TNF treatment for 16 hours.
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis
31
decision, while for the largest part (70% of all cells) the apoptotic pathway is chosen early on, within an hour of TNF stimulation. Not surprisingly, examination of the relative values of the parameters ai shows that two thirds of cells that were able to recover from the apoptotic pathway had degradation rates for C3a higher than those for NFκB or IκB. Based on our study of regulation of apoptosis and the NFκB pathway, it seems clear that the links A and L play quite important roles, and at least one of these should definitely be included for faithful modeling of apoptosis via TNF receptors. This eliminates model III. Both links contribute to the same physiological function: downregulation of NFκB transcriptional activity. However, link A (direct inhibition of NFκB by C3a) achieves this objective in a much faster way than link L (“indirect” inhibition of NFκB by C3a, through complex IKK). The essential difference between models I and II is thus the length of the pathway representing inhibition of NFκB by C3a. The shorter path (model I, with link A) leads to much higher apoptosis rates than the longer path (models II or IV, with link L). The shorter path also renders recovery from the apoptosis pathway practically impossible, with apoptosis rates higher than 95% after only half an hour with C3a overexpression (Fig. 5). The longer path allows a higher recovery rate from the apoptotic pathway, although the probability of apoptosis does not increase above 70%, even after 6 hours of C3a overexpression. Recent experimental evidence [10] points to the existence of a link L, that is, caspases are responsible for cleavage or degradation of (parts of) complex IKK. To further discriminate between a short or long pathway for the influence of caspases on the NFκB pathway, the results shown in Fig. 4 suggest the following experiment. First, measure the period of oscillations during TNF stimulation and then monitor cells for some time after TNF removal. Next, compare the frequency of oscillations in cells that survive and in cells that eventually go through the apoptotic program. If the frequency of oscillations is similar for both groups of cells, or slightly higher in apoptotic cells, then model II (longer pathway) provides a better description of the system. If oscillations stopped after a short time interval (as compared to TNF duration) in apoptotic cells, then model I (shorter pathway) should be chosen.
5 Conclusion The present study illustrates the usefulness of Boolean and piecewise linear models in the analysis of large complex networks. The qualitative dynamics that emerges from the network structure was studied, leading to predictions on the response to increasing duration of stimulation, response to overexpression of a given protein, or indication of which links/interactions play crucial roles in the regulation of apoptosis. Some quantitative aspects were also analyzed, such as the probabilities of survival or apoptosis and the frequency/period of oscillations, and were shown to be in remarkable agreement with experimental
32
M. Chaves et al.
data. Many other questions can be examined in this hybrid framework: for instance, extending the set of parameters (degradation and synthesis rates, threshold concentrations) and varying the relative strengths of anti- and proapoptotic links will lead to more refined models, capturing a wider range of kinetic variability. Although writing the logical rules requires some simplifications of the biological processes, discrete and hybrid models retain the essential qualitative properties of the network. The effect of the network structure on the qualitative dynamics of the system can be easily studied, even when kinetic details are not well known. This class of models can thus be a powerful method to generate predictions and test new hypotheses for complex biological networks. Acknowledgments The authors thank Peter Scheurich and Monica Schliemann for their many interesting and fruitful discussions.
References 1. R. Albert and H.G. Othmer. The topology of the regulatory interactions predicts the expression pattern of the drosophila segment polarity genes. J. Theor. Biol., 223:1–18, 2003. 2. G. Bernot, J.-P. Comet, A. Richard, and J. Guespin. Application of formal methods to biological regulatory networks: extending Thomas’ asynchronous logical approach with temporal logic. J. Theor. Biol., 229:339–347, 2004. 3. R. Casey, H. de Jong, and J.L. Gouz´e. Piecewise-linear models of genetic regulatory networks: equilibria and their stability. J. Math. Biol., 52:27–56, 2006. 4. M. Chaves, T. Eissing, and F. Allg¨ ower. Bistable biological systems: a characterization through local compact input-to-state stability. IEEE Trans. Automat. Control, 53:87–100, 2008. 5. M. Chaves, E.D. Sontag, and R. Albert. Methods of robustness analysis for boolean models of gene control networks. IEE Proc. Syst. Biol., 153:154–167, 2006. 6. N.N. Danial and S.J. Korsmeyer. Cell death: critical control points. Cell, 116: 205–216, 2004. 7. H. de Jong, J.L. Gouz´e, C. Hernandez, M. Page, T. Sari, and J. Geiselmann. Qualitative simulation of genetic regulatory networks using piecewise linear models. Bull. Math. Biol., 66:301–340, 2004. 8. T. Eissing, H. Conzelmann, E.D. Gilles, F. Allg¨ ower, E. Bullinger, and P. Scheurich. Bistability analysis of a caspase activation model for receptor-induced apoptosis. J. Biol. Chem., 279:36892–36897, 2004. 9. A. Faur´e, A. Naldi, C. Chaouiya, and D. Thieffry. Dynamical analysis of a generic boolean model for the control of the mammalian cell cycle. Bioinformatics, 22(14):e124–e131, 2006. 10. C. Frelin, V. Imbert, V. Bottero, N. Gonthier, A.K. Samraj, K. Schulze-Osthoff, P. Auberger, G. Courtois, and J.F. Peyron. Inhibition of the NF-κB survival pathway via caspase-dependent cleavage of the IKK complex scaffold protein and NFκB essential modulator NEMO. Cell Death Differ., 15:152–160, 2008.
Regulation of Apoptosis via the NFκB Pathway: Modeling and Analysis
33
11. T. Gedeon. Attractors in continuous-time switching networks. Communications on Pure and Applied Analysis, 2:187–209, 2003. 12. L. Glass. Classification of biological networks by their qualitative dynamics. J. Theor. Biol., 54:85–107, 1975. 13. L. Glass and S.A. Kauffman. The logical analysis of continuous, nonlinear biochemical control networks. J. Theor. Biol., 39:103–129, 1973. 14. A. Hoffmann, A. Levchenko, M.L. Scott, and D. Baltimore. The IκB-NFκB signaling module: temporal control and selective gene activation. Science, 298:1241– 1245, 2002. 15. A.E.C. Ihekwaba, D. Broomhead, R. Grimley, N. Benson, and D.B. Kell. Sensitivity analysis of parameters controlling oscillatory signalling in the NF-κB pathway: the roles of IKK and IκBα. IEE Syst. Biol., 1:93–103, 2004. 16. G. Lahav, N. Rosenfeld, A. Sigal, N. Geva-Zatorsky, A.J. Levine, M. Elowitz, and U. Alon. Dynamics of the p53-Mdm2 feedback loop in individual cells. Nat. Genetics, 36:147–150, 2004. 17. T. Lipniacki, P. Paszek, A.R. Brasier, B. Luxon, and M. Kimmel. Mathematical model of NFκB regulatory module. J. Theor. Biol., 228:195–215, 2004. 18. E.R. McDonald and W.S. El-Deiry. Suppression of caspase-8 and -10-associated RING proteins results in sensitization to death ligands and inhibition of tumor cell growth. Proc. Natl. Acad. Sci. USA, 101:6170–6175, 2004. 19. D.E. Nelson, A.E.C. Ihekwaba, M. Elliott, J.R. Johnson, C.A. Gibney, B.E. Foreman, G. Nelson, V. See, C.A. Horton, D.G. Spiller, S.W. Edwards, H.P. McDowell, J.F. Unitt, E. Sullivan, R. Grimley, N. Benson, D. Broomhead, D.B. Kell, and M.R.H. White. Oscillations in NF-κB signaling control the dynamics of gene expression. Science, 306:704–708, 2004. 20. E.L. O’Dea, D. Barken, R.Q. Peralta, K.T. Tran, S.L. Werner, J.D. Kearns, A. Levchenko, and A. Hoffmann. A homeostatic model of IκB metabolism to control constitutive NFκB activity. Mol. Syst. Biol., 3:111, 2007. 21. N.D. Perkins. Integrating cell-signalling pathways with NF-κB and IKK function. Nat. Rev. Mol. Cell Biol., 8:49–62, 2007. 22. M. Rehm, H. D¨ ußmann, R.U. J¨ anicke, J.M. Tavar´e, D. K¨ ogel, and J.H.M. Prehn. Single-cell fluorescence resonance energy transfer analysis demonstrates that caspase activation during apoptosis is a rapid process. J. Biol. Chem., 277:24506– 24514, 2002. 23. M. Schliemann. Modelling and experimental validation of TNFα induced pro- and antiapoptotic signalling. Master’s thesis, University of Stuttgart, Germany, 2006. 24. M. Schliemann, T. Eissing, P. Scheurich, and E. Bullinger. Mathematical modelling of TNF-α induced apoptotic and anti-apoptotic signalling pathways in mammalian cells based on dynamic and quantitative experiments. In Proc. 2nd Int. Conf. Foundations Systems Biology in Engineering (FOSBE), Stuttgart, Germany, pages 213–218, 2007. 25. R. Thomas. Boolean formalization of genetic control circuits. J. Theor. Biol., 42:563–585, 1973. 26. R. Thomas, D. Thieffry, and M. Kaufman. Dynamical behaviour of biological regulatory networks - i. biological rule of feedback loops and practical use of the concept of the loop-characteristic state. Bull. Math. Biol., 57:247–276, 1995.
Network-Based Models in Molecular Biology Andreas Beyer Biotechnology Center, Technische Universit¨at Dresden, 01062 Dresden, Germany
[email protected]
1 Introduction Biological systems are characterized by a large number of diverse interactions. Interaction maps have been used to abstract those interactions at all biological scales ranging from food webs at the ecosystem level down to protein interaction networks at the molecular scale. Organisms consist of thousands of cells with hundreds of different types. Cells in turn contain millions of molecules comprising thousands of different chemical species. Our genome contains about 23,000 protein coding genes [32], and the estimated number of chemically different proteins (considering splice variants and posttranslational modifications) is at least an order of magnitude larger. It is difficult to estimate the true number of different proteins, because there are no reliable methods yet for predicting splice variants. For example, the NCBI database (www.ncbi.nlm.nih.gov) currently lists about 440,000 protein entries—many of them may however be redundant. In addition, our cells contain many other molecules with catalytic or regulatory functions, such as ribosomal RNA, tRNA, and small interfering RNA (siRNA). Further, the cells contain thousands of different lipid species and other small molecules serving as structural components of the cell or as substrates for the biochemical reactions executed by the metabolic program. Hence, our body is coordinating the activity and reactions of hundreds of thousands if not millions of different chemical species [3]. Even a single cell is a prototypic example of a complex system [27]. Although biological systems follow all basic physical and chemical principles, they cannot be modeled sufficiently using standard methods from those two disciplines. Typical physical models describe a system as either a small number of different entities (e.g. mechanics) or a large number of very similar or even identical elements (e.g. thermodynamics). Likewise, also chemical reaction systems can only be appropriately described if the number of reacting species is small. However, the behavior and fate of organisms cannot N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 3, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
36
A. Beyer
be described appropriately without considering the fact that they consist of a large number of very different interacting elements. Networks or interaction graphs are one way to formalize the complex interactions of heterogeneous entities within and between cells. In their most simple form those interaction graphs only indicate the possibility of an interaction between two genes or proteins (Fig. 1, top). At the other end of the scale are detailed models based on ordinary or partial differential equations (Fig. 1, bottom). Those latter models are used for small, well-studied subsystems and they provide significantly more detailed insight into the dynamics than simple interaction maps. Many formal methods have evolved that cover the intermediate space between these two extremes [2, 11, 23, 30, 38, 49, 66, 72, 76]. The best models utilize the available data in an optimal way to provide as much insight into the biological system as possible. So, what is the distinct advantage of network-based methods in comparison to other approaches? As opposed to many alternative methods (such as ordinary or partial differential equations), network models establish a description of the system including all the different entities and their properties, even if the detailed knowledge about the properties and behavior of individual molecules is still very sparse. Network models are a popular way to formalize all the available knowledge about cellular systems in a consistent framework. For example, protein and gene interaction maps have been created for many important model species and for humans, covering thousands of genes and tens of thousands of interactions [45, 59, 60, 67]. Although these interaction maps are still incomplete and even though they only represent a static picture of possible interactions, they constitute the most complete picture of a cell that we have today (i.e. covering the largest number of genes or biomolecules). It is this ability to integrate and formalize knowledge and data about very diverse entities of the system (each gene is different from all other genes) in a consistent way that distinguishes this concept from basically any other existing modeling approach [7]. One should be aware though that “network-based approaches” actually cover a very broad and heterogeneous group of methods (Fig. 1), ranging from the above-mentioned static interaction graphs to systems of coupled differential equations (used e.g. for modeling metabolic networks). During the previous decades network-based modeling approaches have been used for describing cellular regulation and cellular metabolism. Networks have helped to structure and formalize existing knowledge, to summarize and integrate large measurements, and to predict system behavior. Important applications include a better understanding of diseases with the ultimate goal of developing new therapies. Even conceptually simple static protein interaction maps have been used to gain significant insights into how certain genes are associated with specific diseases. The study of Lage and co-workers [42] presents an excellent example: many genetic loci (i.e. regions on the genome) are statistically associated with the occurrence of certain diseases. However, usually this information is insufficient to mechanistically explain the relationship between the genetic locus and the disease. First of all, many genes may be
Network-Based Models in Molecular Biology
37
Static interaction maps: show potential of interaction
Conditional interactons: need condition specific protein abundance or protein activation data
coverage
can predict who affects whom, need regulatory information
level of detail
Causal (directed) interactions:
Logical networks: +
+ -
k1
k2
considers type of effect (repressive/activating) and potentially also Boolean rules (such as “need A AND B to activate C“)
Quantitative models: kinetic rate constants are known or derived from the data, can predict dynamics of system response
k3
Fig. 1. A hierarchy of network models. Depending on the available data and the research question, different network modeling approaches are chosen. The figure shows model types with increasing levels of detail and increasing data demand (top – down). Less detailed models tend to cover a larger number of genes/biomolecules. Note that only the most detailed category of models “quantitative models” allows for true simulation of network dynamics, e.g. using ordinary differential equations. Causal networks and logical networks allow at most for the simulation of the sequence of events or the order in which proteins/genes are activated, but quantifying the speed of processes is impossible with these simplified approaches.
located in the respective region of the genome and it is mostly unknown which of the genes is causal for the disease. Second, even if the causal gene is known, the molecular mechanisms linking the gene to the disease are usually elusive. Lage et al. addressed these problems by mapping all genes located in diseaserelated loci onto a protein-protein interaction network. They hypothesized that truly causal genes would cluster together in common protein complexes of the network. Indeed the authors found protein complexes significantly enriched with candidate genes. Often, these complexes also had a molecular relationship with disease phenotypes. Hence, the investigators not only identified potentially causal genes, but they also identified protein complexes that could aid in understanding the molecular mechanisms by which mutations alter disease susceptibility. This example demonstrated that even comparably simple networks can yield new insight for our understanding of diseases.
38
A. Beyer
2 Molecular Biological Networks Currently, three types of molecular networks are receiving the most attention in the scientific literature: metabolic networks, protein interaction networks, and gene interaction networks. Other popular network types are transcriptional regulatory cascades, which are derived from genome-wide expression data (Appendix 1). The availability of large datasets for these most popular networks has enabled extensive theoretical and computational analysis of the networks. Importantly, this preference does not always reflect biological significance. As discussed below, posttranscriptional regulatory networks are probably as important as transcriptional networks. However, methods for measuring the relevant interactions (e.g. protein-RNA binding) on a large scale are either not yet available or not as established as other methods (Appendix 1). Metabolic networks. These networks describe systems of biochemical reactions catalyzed by enzymes. Depending on the available data and the research question, different formalizations can be used [28, 63]: (i) enzymes can be the nodes (vertices) of the graph and two enzymes are connected if they catalyze subsequent steps in a reaction chain (i.e. the product of the first enzyme is a substrate for the second); (ii) metabolites can be nodes in the graph and metabolites are connected if they participate in the same reaction; (iii) stoichiometry can be considered if known, e.g. in metabolic flux analysis; and (iv) if kinetic parameters are known one can create systems of differential equations describing the dynamics of the system. Many other types of modeling schemes are used for depicting metabolic networks, including for example stochastic processes [62]. Protein-protein networks. Likewise, many different types of proteinprotein interaction networks have been used, utilizing the data in different ways; e.g. static protein interaction maps summarize either known measured or predicted protein interactions [59, 60, 67]. Here, the edges often have weights quantifying the probability of a true physical binding between the two proteins [15]. Other types of protein networks are regulatory networks, such as kinase-substrate cascades [55], protein complexes (often representing molecular machines such as the ribosome) [24, 40], or more detailed structural models of protein interactions [4]. Gene-gene networks. Gene-gene networks are not molecular networks, but in fact logical networks: they describe functional relationships between genes. For example, two genes may be linked if their products participate in the same process or pathway. Such functional networks have been created by integrating diverse evidence for common functions of genes [45, 59]. For example, the fact that two genes appear together in many species (common phylogenetic profile) indicates that the genes participate in a common process. Also, common expression patterns across a wide range of different conditions suggest similar functions of two genes. By integrating such evidence quantitatively using machine learning approaches it has been possible to create relatively
Network-Based Models in Molecular Biology
39
large maps of functionally related genes. Such a “functional network” has for example been used to better predict substrates of kinases [47]. This study nicely demonstrated the value of such data integration, since previous methods relying exclusively on kinase binding motifs suffered from a large number of false positives. Geneticists define a genetic interaction based on the phenotypes observed when the genes are knocked out: if the knock-out of one gene “masks” the phenotype of the other knock-out they are said to be linked [7, 9]. A prototypical example is the synthetic lethal interaction. In this case the knock-out of any single gene has no or only very little effect on viability, whereas the double knock-out of both genes creates a lethal phenotype. Such a synthetic lethal phenotype can be explained by redundant functions of the two genes e.g. in two independent pathways that can compensate for each other [35]. Hence, the fact that two genes create a synthetic lethal phenotype indicates that they participate in distinct pathways. Underlying the functional or genetic relationships are sequences of physical or biochemical interactions “connecting” the two genes. Thus, genetic interactions provide important functional information that can be used for inferring molecular pathways [7]. Other network types. Many other types of molecular interactions have systematically been studied using network approaches. For example, proteinDNA interactions are important for understanding transcriptional regulation, and they have been studied on a large scale for almost a decade [58, 77]. On the other hand, protein-RNA networks are substantially less researched, although the relevance of alternative splicing is immediately apparent and it is known that translation is also heavily regulated via RNA binding proteins [5]. Yet another prominent example is the use of logical networks for describing transcriptional regulatory cascades [19, 57]. These networks are similar to the above-mentioned transcription factor-DNA networks; however, such logical networks; may not always explicitly model the molecular mechanism underlying the regulatory relationship.
3 Identifying Molecular Biological Networks In recent years several new technologies have been developed for measuring all kinds of physical and genetic interactions on a large scale (Fig. 2, Appendix 1). For example protein-protein interactions can be measured with yeast two-hybrid (Y2H) or tandem affinity purification coupled with mass-spectrometry-based protein identification (TAP-MS). Protein-DNA interactions can be measured with chromatin immunoprecipitation and DNA microarrays (Appendix 1) can be used to identify the DNA fragments (ChIP-Chip). Likewise, techniques for the large-scale measurement of gene-gene interactions have been developed. These are just some examples to
40
A. Beyer Kinase - substrate interactions: protein chips binding motifs + other binding evidence eQTL + other binding evidence
Protein-protein interactions: yeast two-hybrid (Y2H) TAP-MS known interacting protein domains
Transcription factor - DNA interactions: TF binding motifs ChIP-Chip, ChIP-Seq knock-out + expression change ('buffering') over expression + expression change
Transcriptional cascades (TF - TF interactions): all methods of the above section time course analysis
= protein
= undirected interaction
= target gene
= directed interaction
Fig. 2. Inferring regulatory networks with high-throughput methods. The four types of interactions can be inferred using experimental high-throughput methods, computational methods, or combinations of the two. The methods listed are not comprehensive. Refer to Appendix 1 for details about the various methods. Advanced computational methods combine different evidences for each type of interaction. For example, TF motif information can be used in combination with ChIP-Chip experiments [6]. Likewise, time course data have been combined with TF binding motifs to infer regulatory cascades [57].
demonstrate the fact that today a wide range of interactions can be measured practically at a genomic scale. However, all of these methods are subject to considerable noise, and often results from different techniques only agree to a small extent [73]. Therefore, numerous bioinformatic approaches are under development for physical and genetic network quality assessment, integration, assembly, and annotation. Although all large-scale studies are subject to noise, the rationale for data integration is that observations of true interactions will reinforce or complement one another when combined across different studies and/or experimental techniques. For example, the independent observation of a protein-protein interaction by both Y2H and TAP-MS methods, or by two independent TAP-MS studies, renders this interaction more likely to be true [73].
Network-Based Models in Molecular Biology
41
Such evidences for interaction can be further supported by including other types of data that are not necessarily measurements of direct physical contact. For example, if the two genes have correlated expression profiles or similar patterns of occurrence across several conditions, these findings lend further support to the raw interaction measurement [53, 69]. Beyer et al. [7] review methods for integrating genetic interactions with physical binding data to further support the various types of interactions. Modern methods for interaction data integration use machine learning approaches or other statistical means for combining heterogeneous types of data in a consistent manner. Importantly, the methods assign different weights to different input data, acknowledging that not all types of evidence are equally predictive. These methods rely heavily on a set of “gold-standard”, or highly accurate, interactions which are used to evaluate the predictive utility of different types of evidence [50, 73]. The result is a statistical measure quantifying the likelihood that any given pair of biomolecules interacts (e.g. two proteins or a protein-DNA pair) [6, 33, 59, 64, 70]. Strictly speaking, these quantitative confidence scores describe the probability or reproducibility of the interaction, not the interaction strength. Nonetheless, there is some evidence that stronger interactions should be more reproducible, leading to higher scores [20]. The scores resulting from such analyses can be used to filter for highconfidence interactions and thereby remove potentially many false positive interactions contained in individual high-throughput measurements. Yet, the reverse problem of false negatives is equally pressing. Because most large-scale screens are conducted under only one or few conditions, it is not possible to fully capture the space of all possible interactions. Here again, data integration can help to mitigate false negatives, as interactions missing from one study can be detected using high-confidence interactions from another. Note that integrating more information can simultaneously reduce both the false-negative and false-positive rates: as the number of ways of detecting an interaction increases, the higher the chance it is found by several of these methods, and the lower the chance it is missed altogether or found by only one. The same notion applies to basically any other type of molecular or genetic interaction. For instance, another important problem is the identification of transcription factor (TF) target genes. Various approaches have been used to infer those interactions (Fig. 1, Appendix 1); however, no single method is perfect. Combining clues for TF-target interactions from different independent sources increases confidence and coverage [6]. For example, L¨ahdesm¨aki et al. [44] combined evidence from DNA binding motifs of TFs with other data such as nucleosome occupancy to infer a transcriptional regulatory network for the mouse. Likewise, Beyer et al. [6] combined experimental evidence from ChIPChip with TF motifs, phylogenetic information, expression data, and even physical protein binding data to infer a high-coverage and high-confidence transcriptional network for yeast.
42
A. Beyer
4 Dynamics of Molecular Biological Networks Many aspects of biological networks are time dependent or condition specific. Although all of the above-mentioned networks have been valuable in the past for better understanding biological processes, most of them ignore some important features of biological networks. Biological interactions are dynamic and condition specific. Only a small subset of all interactions (be it physical protein binding or logical genetic interactions) is constitutively active. Protein expression and activation depends on the cell type, cell state, environmental signals, and the history of the cell (previous states). Further, molecular interactions depend on the genomic sequence of the specific individual since mutations may alter interactions. Hence, the presence of the interactors as well as their ability to interact is highly variable. Even genetic interactions can be condition specific: the same double knock-out may be viable under one condition but lethal under another [9]. The reasons why current models ignore these aspects are certainly manifold, yet availability of data is one of the most important aspects. For example, protein-protein interactions are usually measured for only a single condition, sometimes not even in the original organism (e.g. in the case of Y2H, see Appendix 1). It is thus difficult to consider condition specificity of interactions in mathematical models. One way to address this problem is to take mRNA expression data into account, which are now routinely measured genome-wide using DNA microarrays (Appendix 1). Using these data it is possible to predict the presence or absence of proteins under specific conditions. Since a physical interaction is only possible if both partners are present, this also allows for predicting conditional interactions [16]. However, this approach still does not consider protein localization and activation. Even if two proteins are co-expressed, they may not be located to the same subcellular compartment, impeding an in vivo interaction. The best-studied aspect of molecular network dynamics is transcriptional adaptation. The broad availability of DNA microarrays allows for measuring genome-wide transcriptional profiles relatively easily and at low cost. Today it is a routine technology for measuring mRNA concentrations, and thousands of studies have been conducted during the last decade measuring mRNA expression changes in prokaryotes, in many eukaryotic model species, and in human samples. The two main databases of publicly available microarray data are ArrayExpress (www.ebi.ac.uk/arrayexpress/) and the Gene Expression Omnibus (www.ncbi.nlm.nih.gov/geo/), currently listing 3874 and 8408 experiments, respectively (as of April 2008). mRNA changes have been measured in response to external stimuli, following differentiation, between different tissue types, in diseased versus healthy tissue, and for numerous other applications. The transcript signatures have been used to identify not just individual genes responding to the given signal, but also entire pathways or subnetworks activated or deactivated under specific conditions. DNA microarrays are the most abundant tool in molecular biology for measuring the cellular response in an unbiased way. These studies are termed “unbiased” or “systematic” because
Network-Based Models in Molecular Biology
43
there is no need for a priori assumptions about which genes/proteins are likely to respond during the experiment. Kiesel et al. [36] used microarray time course data to study the transcriptional change during osteoclastogenesis (i.e. during the transition from precursor cells to mature osteoclasts). The differentiation of precursor cells into mature osteoclasts involves dramatic changes of the transcriptional program, thereby affecting the topology of the interaction network at the protein level. The authors identified co-expression networks associated with early and late response to the differentiation stimulus. A co-expression network is a graph linking two genes if the two genes are similarly expressed either during the specific experiment or at a range of different conditions. For the Kiesel study it was necessary to create two distinct networks to fully capture the complexity of the dynamical changes. One network described the early, and the second one the late response during differentiation. Accordingly, the two networks contained different pathways that are known to be associated with osteoclastogenesis. These findings emphasize the importance of considering the dynamics of transcriptional changes—often one may lose important details when looking at only two time points (before and after treatment, before and after differentiation, etc.). Whereas analyzing microarray time course data can in itself reveal important insights into the dynamics of transcriptional networks, combining those data with other interaction data is significantly more powerful. Expression data can be combined with transcription factor binding data, adding the dimension of protein-DNA interactions [23]. Thereby it becomes possible to infer the molecular mechanisms by which transcriptional networks change their state. For example, Ramsey et al. [57] combined time course expression data with transcription factor binding data to assess the regulatory program responding to macrophage activation. Putative regulatory relationships were identified by employing a novel method for identifying time-lagged correlation between transcription factors and potential target genes. Those interactions were later corroborated by additionally taking the binding affinity of transcription factors in upstream regulatory regions into account. Subsequent experiments confirmed that this combined analysis of expression and binding data significantly improved the quality of the inferred regulatory network. In a similar approach, Ernst et al. [19] analyzed yeast TF-DNA binding data in combination with respective expression data under various different stress conditions. They identified bifurcation points in the time course expression data indicating regulatory events. Along with the TF binding data they were able to identify TFs that were likely regulators of those bifurcations, i.e. they were regulating a specific subset of the genes. Alternatively, time course data of expression changes can be combined with physical protein interaction networks in order to identify pathways or pathway components that are differentially expressed [11, 30]. Ideker et al. [31] combined physical interaction networks with expression data and devised a method based on simulated annealing for identifying relevant subnetworks
44
A. Beyer
(modules) of the physical network. In this case, the network is not a coexpression network, but a network of proteins binding to other proteins or to DNA. Expression changes are mapped onto the physical network, i.e. they become the nodes’ attributes. The algorithm’s task is to identify the most significant subnetwork enriched for differentially expressed genes. The result will depend on the topology of the physical network and the strength (extent) of differential regulation of the individual genes. Several variants of this idea have been published since then [11, 13, 56, 61]. Most important however is the central idea: combining dynamic expression data with independently derived interaction networks significantly improves the statistical power of the analysis and provides much more insight into the underlying molecular mechanisms [7]. It is well established that protein concentrations are not only regulated at the transcriptional level, but also at the level of translation and protein turnover [5, 10]. These posttranscriptional processes affect the topology of interaction networks just as much as transcriptional changes. For example, Brockmann et al. [10] have shown that proteins responding early in signaling cascades and transcription factors in particular are subject to “translation on demand.” The coding mRNA of such proteins is constitutively expressed, but translation is blocked until the protein is actually needed. This allows for a much faster response compared to transcriptional regulation. Hence, the presence/absence of these network components is highly dependent on posttranscriptional processes, which are often neglected in studies assessing the dynamics of protein expression. It is a very important finding that the regulatory network components themselves are often not regulated at the transcriptional level and are therefore missed by studies only applying DNA microarrays for measuring transcriptional changes [8, 74]. The main bottleneck for studying posttranscriptional network changes more systematically are the experimental limitations of protein detection and quantification. Current state-of-the-art techniques employ mass spectrometry for identifying, characterizing, and quantifying proteins [1]. The current limits of this technology are high costs, relatively complicated protocols, data processing, limited number of detectable proteins (in the range of a few hundred), and limited reproducibility [14, 48]. Recently, significant progress has been made because of much more sensitive instruments, improved protocols, and better data analysis tools [14, 43, 48]. Hence, this progress suggests that in the near future posttranscriptional network dynamics can also be studied at a level of detail and scope comparable to that of mRNA changes [14, 22].
5 Dynamics on Molecular Biological Networks The previous section focused on the dynamic adaptation of the network topology, e.g. the presence or absence of network components. Here, we will address state changes of the nodes themselves, i.e. alterations or activities of biomolecules in response to external or internal stimuli.
Network-Based Models in Molecular Biology
45
Prototypic examples for such networks are signaling networks, in which proteins transmit information (signals) from one to the other via protein state changes. Most intra-cellular signals are transmitted through covalent protein modifications, e.g. via phosphorylation of specific residues. Kinase cascades “send” signals from membrane receptors or from intra-cellular receptors to proteins and other molecules, which ultimately changes the phenotype of the cell or the entire organism. State changes of regulatory proteins such as G-proteins, kinases, transcription factors or histones can be detected with antibodies specific for the respective protein changes. The alternative method of measuring those changes via mass spectrometry holds greater promise for unbiased large-scale studies, because it does not require a specific antibody for every possible protein modification. So far, those mass spectrometry based techniques are subject to the same limitations as the protein concentration measurements discussed above [17]. Fortunately, the same improved technologies that are developed for protein quantification can also be used to study dynamic changes of protein modifications and localization [41, 54, 75]. However, existing studies trying to elucidate the dynamics of cell signaling largely had to rely on the tedious measurement of isolated proteins. Only recently have new methods been developed for systematically identifying targets of kinases either experimentally [55] or using computational predictions [47] (see also Appendix 1). Despite being important for determining the topology of regulatory networks, those techniques still do not provide data on the dynamics or kinetics of network changes on a larger scale. Therefore, kinetic modeling of signaling cascades or protein transport has been restricted to either well-studied pathways such as the cell cycle or relatively simple pathways such as the osmotic shock response of yeast [38, 39, 72]. Due to the lack of sufficient kinetic parameters, researchers have begun to develop new methods for simulating information processing in biological signaling networks [25]. Most of these approaches formalize the logical information processing rather than quantifying the dynamics. For example, information such as “Gene A is activated if gene B is deactivated” can be formalized in logical models such as Boolean networks [2, 21, 29]. Various alternative methods have been used to infer the logical relationships in regulatory networks, including Petri nets [26, 65], Bayesian networks [51], and factor graphs [76]. A new method for the inference of regulatory pathways that combines physical with functional data was recently introduced by Suthram et al. [71]. The authors used expression quantitative trait loci (eQTL) data in combination with a physical protein network to infer molecular regulatory pathways in yeast. eQTL are statistical relationships between positions in the genome (loci) and the expression of a target gene. A strong correlation indicates that the respective locus contains a regulator of the target gene. Suthram et al. simulated the flow of information between the locus and the target gene as an electric current. The physical protein network serves in this case as the wiring diagram on which the information “flows.” The strength of current on any
46
A. Beyer
edge (interaction) is indicative for the importance of the interaction for the regulation of the target gene. By applying their method to yeast eQTL data the authors could infer several known and new regulatory relationships, and they were able to predict the directionality of information flow for hundreds of protein-protein interactions. The method developed by Suthram et al. enables the inference of causal relationships, but it does not lend any insight into the effect of interactions. For example, the currents do not predict whether the regulator increases or represses the activity of the target. Workman et al. [74] went further in this respect. Using ChIP-Chip data and knock-out expression measurements under DNA damaging conditions they could infer a causal network for DNA damage response. They used the method of factor graphs, which is a generalization of Bayesian networks. Factor graphs are minimal graph models explaining the observed (expression) data. Importantly, the method predicts whether any given interaction is activating or repressing. The down side is that this method requires significantly more comprehensive data than more simple approaches. These logical network models cannot fully capture the kinetics of signaling. However, at least some of them predict state changes in response to different inputs, they provide insights into the sequence of events, and they allow for analyzing the stability of the regulatory system and for finding “weak spots.” A weak spot is a gene in the signaling network whose knock-out would maximally alter the output. Those genes could be interesting drug targets, e.g. when looking for new targets in pathogens or when attacking tumor cells. Also, those weak genes could be causal for diseases, for example if they are mutated in patients carrying a certain inheritable disease. Metabolic networks are another important application of dynamic network modeling. They too are highly dynamic, and fully capturing their kinetics would allow for developing new drugs and for optimizing yields in biochemical reactors. However, modelers face similar problems as those in regulatory networks: although the kinetic properties of enzymes have been measured for decades, we are still far from completely covering all relevant enzymes in any multicellular eukaryote [49]. In addition, enzymes may behave completely differently in in vitro systems than in in vivo situation, where pH, temperature, and many other important parameters may differ [68]. Hence, complete dynamic modeling using differential equations is possible only for a relatively small set of well-studied subsystems. Fortunately, methods have been developed that do not require kinetic constants for the analysis of metabolic networks. For instance, Petri nets have also been used for analyzing metabolic networks [12]. One of the most mature methods is flux balance analysis (FBA) [34, 52]. FBA simulates a metabolic network assuming steady state (input balancing output), which greatly simplifies the data requirements. For example, elementary modes represent a minimal set of reactions necessary to produce a given product at steady state [66] (Fig. 3). These elementary modes, can be deduced just from the stoichiometric matrix. Hence, one only has to know the possible reactions in the system along with their educts and products to
Network-Based Models in Molecular Biology
(a)
S1
(b)
R2 R1
M1
M2
R4
P1
S1
R2 R1
R5
M1
M1
(d) M2
R5
R4
P1
S1
R2 R1
M2 R4
M1
P1
R5 R3
P2
P1
R3
R2 R1
R4
P2
P2
S1
M2
R5 R3
(c)
47
R3 P2
Fig. 3. Elementary flux modes. (a) A simple metabolic network consuming substrate S1 and producing products P1 and P2 via the reactions R1 through R5. (b – d) Elementary modes (highlighted) are minimum sets of reactions creating the products P1 (b, c) or P2 (d). Note that removing R1 affects all elementary modes, i.e. synthesis of all products. Removal of R4 disables synthesis of P1 only. {R1 }, {R4 }, and {R2, R3 } are minimal cut sets with respect to P1.
predict all possible chemical fluxes that do not lead to the accumulation of products under the steady state assumption. Depending on the metabolic network there might be many elementary modes leading from certain substrate(s) to specific product(s). Such a network would be redundant. However, even if there are many elementary modes, all of them might require one specific enzyme, thus this enzyme would be essential for synthesizing the respective product (e.g. the enzyme catalyzing reaction R1 in Fig. 3). The concept of elementary modes has been used to make a range of important predictions: for example Stelling et al. [66] were able to predict lethal genes in Escherichia coli by searching for enzymes whose knock-out would remove all possible elementary modes leading to essential products. Klamt [37] extended this idea to the concept of minimal cut sets: whereas Stelling and co-authors were looking for single genes whose knock-out would be detrimental to the organisms, the cut sets define the minimum set of genes required to turn off the synthesis of a given product (Fig. 3). This analysis could be instrumental for developing combinatorial antibiotics targeting different enzymes in bacteria such that their synergistic interaction would be lethal to the pathogens. In summary, the “reduced modeling approaches” that are currently popular do not strictly simulate the dynamics on (or of) the networks, but they simulate dynamic networks in a way that still leads to important conclusions. In most cases it would be impossible to derive those insights without
48
A. Beyer
these computational tools, given the complexity of regulatory or metabolic networks. Also, these less quantitative approaches have a higher chance of truly reaching a genome-wide scale and thus actually achieving a system-wide perspective. One of the main driving forces for progress in computational methods is the development of new experimental techniques. New types of data open up new possibilities for network simulation. For example, relatively cheap deep sequencing methods will aid the identification of all transcripts (protein coding and non-coding) in time courses, which will require a new dimension in transcriptional network modeling. Those future models will be able to incorporate the regulatory effect of micro-RNAs and any other type of non-coding RNA. Likewise, these technologies will generate detailed data on alternative splicing, since every transcript will be known in its entire sequence. Thus, new computational methods capturing the regulation of alternative splicing at a genomic scale will emerge. Another example is the above-mentioned progress in proteomics. It is hoped that it will lead to the creation of the first comprehensive maps of posttranscriptional regulation.
Acknowledgments I wish to thank Angela Simeone, Jacob Michaelson, and Antigoni Elefsinioti for critically reading the manuscript. This work has been funded by the Klaus Tschira Foundation.
Appendix 1: Large-Scale Detection of Interaction Networks Microarrays are used to measure the expression of all genes of an organism in a single experiment. By measuring time course samples or samples from different tissues, conditions, etc., it is possible to reveal transcriptional changes in response to stimuli or under disease conditions. Algorithms have been devised to infer regulatory dependences between genes (transcriptional regulatory networks) from those data. Protein chips are made to measure protein-protein interactions on a large scale. Here, selected proteins are fixed to a glass surface and interactions with unknown proteins in a sample can be measured, e.g. via fluorescence. If the “probe proteins” are antibodies for proteins of interest, the chips can be used to quantify protein amounts in the sample. Ptacek et al. [55] detected kinase substrates by fixing 4400 proteins onto a protein array. They incubated arrays with kinases (two arrays per kinase) and subsequently identified proteins that were phosphorylated.
Network-Based Models in Molecular Biology
49
Kinase binding motifs plus other binding evidence. Prediction of kinase substrates via the protein sequence alone generates many false positive predictions because short kinase binding motifs are not specific enough. However, provided a certain putative substrate contains a binding motif, actual binding can be corroborated if there is additional independent evidence that the two proteins bind directly or that they are at least involved in the same biological process. eQTL plus other binding evidence. Here again, weak evidence from expression quantitative trait loci (eQTL) is combined with other independent evidence for physical binding of the two proteins. Yeast two-hybrid. Two potentially interacting proteins are genetically fused with transcriptional activation domains. If both proteins bind in the nucleus of the yeast cells, the dimer binds the DNA and activates a reporter gene (e.g. GFP). Genes from other species (e.g. mouse or human) have to be transferred into yeast for this method. Interactions between proteins that cannot interact in the yeast nucleus but would bind in their native environment cannot be detected with this method. TAP-MS. “Bait proteins” are purified from a sample using tandem affinity purification (TAP). Other proteins associated with the bait (“prey proteins”) are identified with subsequent mass spectrometry (MS). Although TAP-MS measures the native in vivo situation, it cannot distinguish whether binding of a prey to the bait is direct or indirect (i.e. mediated via another intermediate prey protein). Also, the method cannot detect transiently binding proteins (unstable binding). Physical interactions measured with Y2H or TAP-MS are influenced by artifacts due to gene tagging, which can influence the functioning of the protein produced [18, 46]. Known interacting domains. This computational method searches for known protein-protein interaction domains in the sequences of candidate genes. The domains may be taken from crystal structures of interacting proteins. If the same two domains are found in other proteins with high sequence similarity, this indicates potential physical interactions. This method is applicable genome-wide. However, it is limited by the available crystal structures and it does not take the protein 3D structure into account. TF binding motifs are short DNA sequences that are targets of a specific transcription factor. They can be inferred, e.g. from a set of known binding regions/promoter regions of known target genes. The presence of a binding motif in a promoter of a potential target gene is usually not sufficient for clearly identifying the gene as a target. Therefore, binding motif information is usually supplemented with additional evidence, e.g. whether the motif is conserved upstream of orthologous genes in other species or whether the putative target is co-expressed with another known target gene of the same transcription factor.
50
A. Beyer
ChIP-Chip. Transcription factors (TF) are cross-linked (“fixed”) with DNA, and after fractionating the DNA the TF-DNA duplexes are purified via immunoprecipitation (i.e. with antibodies). Cross-linking is reversed and the DNA fragments are identified by hybridizing them to a DNA microarray. Thereby, it is possible to identify all binding sites of a TF for a given condition genome-wide in a single experiment. A related method (ChIPSeq) replaces the final step of DNA identification by high-throughput deep sequencing. Both methods only measure binding under the specific condition, i.e. DNA targets bound under different conditions are missed. Knock-out and expression change. Here one knocks out a regulator gene of interest and measures the expression difference between wild-type and the knock-out. Genes that are differentially expressed are likely to be targets of the regulator. The method can only detect target genes if the transcription factor is activated under the conditions tested and it cannot distinguish direct from indirect targets. Also, the knock-out itself will trigger a range of indirect responses that are not directly related to the function of the TF, because the cell tries to compensate for the knock-out. Over-expression and expression change. This approach is complementary to the preceding method, in that the transcription factor of interest is constitutively expressed at high levels. One then compares the expression of genes under normal and high expression. Genes that change their expression are likely to be targets. This method suffers from several of the above-mentioned problems as well. For example, it does not distinguish direct from indirect targets. However, it does not require that the TF is normally active under the condition tested. Time course analysis can be used to infer transcriptional regulatory cascades. The underlying hypothesis is that the activity of a transcription factor can to some degree be predicted from its mRNA level. One measures the expression levels of all genes with DNA microarrays for several time points. Using appropriate statistical methods one can then infer likely target genes from the fact that they are expressed after a certain TF is upregulated (or downregulated, depending on whether the TF is an activator or repressor).
Appendix 2: Some Important Definitions Alternative splicing, splice variant. Alternative splicing is a mechanism used by cells to generate different protein sequences from the same gene. All genes are transcribed into RNA and usually only a part of the transcript is used for synthesizing proteins. Some parts of the transcript (called introns) are “spliced out” (i.e. removed) before translation. Many genes splice different parts of their transcript depending on cell type or external conditions. This process of conditional splicing is called alternative splicing and the resulting gene sequences are called splice variants.
Network-Based Models in Molecular Biology
51
Binding motif. A short DNA or RNA sequence that is recognized by a binding protein. For example transcription factors recognize the specific site on the DNA to which they should bind based on a specific sequence of nucleotides. DNA hybridization. The binding of single stranded DNA to its complement (according to Watson–Crick base pairing). DNA hybridization is utilized to specifically bind sample DNA to probe DNA with a known sequence (e.g. on DNA microarrays). DNA microarrays are used to measure RNA concentrations as well as to identify DNA sequences in biological samples, and are also used for SNP detection, for re-sequencing, and for a range of other applications. Such arrays consist of glass slides to which short DNA sequences (“probes”) are fixed. The DNA probes are either synthesized oligonucleotides or amplified DNA fragments. DNA concentrations in a given sample are measured by hybridizing the labeled DNA from the sample to the complementary probes on the array. More DNA hybridizing to a given probe will be indicated by a stronger signal. Hence, the signal intensity is a measure of the abundance of the respective DNA sequence in the sample. RNA first has to be transformed into cDNA using reverse transcriptases. Genetic fusion. A variant of genetic manipulation; adding genes or gene fragments to another gene. Genotype. An individual’s specific genome sequence. Many genes have different variants (alleles). The pattern of alleles that someone inherited is the individual’s genotype. Kinase (protein kinase). A signaling protein adding phosphate groups onto substrate proteins. The substrate is thereby activated (it acquired a higher energy level), which may for example alter the structure of the substrate. The substrate itself can also be a kinase, in which case the substrate in turn can activate its substrates. Such chains of kinases are called kinase cascades. Macrophage activation. Macrophages are immune cells responsible for killing pathogens such as bacteria. The immune response of macrophages is triggered by pathogen-specific molecules such as bacterial lipids. Upon such signals, macrophages undergo a range of morphological and other changes to prepare for attacking pathogens and for “warning” the immune system. Mass spectrometry (MS). Used for identifying chemical molecules and for measuring their concentrations in a sample. MS separates fragments of molecules and measures the mass-to-charge ratio in different types of detectors. By computationally assembling the information about individual fragments it is possible to deduce the nature of the input molecules in the sample. Small molecules are measured directly without prior fragmentation. Osteoclasts are bone cells responsible for the desorption (destruction) of bone. Their counterparts are osteoblasts, which generate new bone mate-
52
A. Beyer
rial. Bone is constantly degraded and newly formed by these two types of cells. An excess of osteoclasts leads to osteoporosis (brittle bones). Phenotype. The expression of a genotype. Individuals may have different physiological or molecular characteristics based on their genotype. For example, eye and hair color are phenotypes determined by the respective gene variants (genotype). A phenotype is generally determined by both environmental and genetic factors. Biologists often refer to “the phenotype of a gene” as the physiological change in response to knocking out the respective gene. Phylogenetic profile. Describes the occurrence pattern of a gene in different species. Two genes occurring in the same species are said to have similar phylogenetic profiles. Simulated annealing is an optimization technique for finding global maxima (or minima) in complex fitness landscapes with many local optima. Simulated annealing starts searching for an optimum from some (random) parameter configuration. After a number of iterations the current parameters are randomized to some extent in order to overcome boundaries between local maxima/minima (“heating” of parameters). This procedure is repeated until convergence, while reducing the level of parameter randomization each time (“annealing”). Stoichiometry describes the type and number of molecules consumed and the type and number of molecules produced by a chemical reaction. Substrate. A molecule chemically changed/consumed by an (enzymatic) reaction. For example, proteins that are phosphorylated by kinases are called substrates of the kinases. Transcription. The process of copying a gene’s sequence into RNA. Polymerases are protein machines “reading” the sequence of a gene and producing the complementary RNA. Transcription factor (TF). A regulatory protein controlling the transcription of genes. TFs bind directly or indirectly (bridged via other proteins) to DNA and change the 3D structure of DNA, attract or block transcriptional machinery at the site, or alter other proteins in the vicinity (e.g. histones) to manipulate the transcription rate of the target gene. Translation. The process of synthesizing a protein from the respective messenger RNA (mRNA). Ribosomes are molecular machines (consisting of RNA and proteins) reading an mRNA sequence and translating it into the corresponding amino acid sequence.
References 1. Aebersold R, Mann M. (2003) Mass spectrometry-based proteomics. Nature. 422(6928):198–207. 2. Albert R, Othmer HG. (2003) The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. J Theor Biol. 223(1 ):1–18.
Network-Based Models in Molecular Biology
53
3. Alberts B, Johnson A, Lewis J, Raff M, Roberts K, Walter P. (2002) Molecular biology of the cell. Garland Science, New York. 4. Aloy et al. (2004) Structure-based assembly of protein complexes in yeast. Science. 303(5666):2026–9. 5. Beyer A, Hollunder J, Nasheuer HP, Wilhelm T. (2004) Post-transcriptional expression regulation in the yeast Saccharomyces cerevisiae on a genomic scale. Mol Cell Proteomics. 3(11 ):1083–92. 6. Beyer A et al. (2006) Integrated assessment and prediction of transcription factor binding. PLoS Comput Biol. 2:e70. 7. Beyer A, Bandyopadhyay S, Ideker T. (2007) Integrating physical and genetic maps: from genomes to interaction networks. Nature Rev Genet. 8:699–710. 8. Birrell GW, Brown JA, Wu HI, Giaever G, Chu AM, Davis RW, Brown JM. (2002) Transcriptional response of Saccharomyces cerevisiae to DNA-damaging agents does not identify the genes that protect against these agents. Proc Natl Acad Sci USA. 99(13 ):8778–83. 9. Boone C, Bussey H, Andrews BJ. (2007) Exploring genetic interactions and networks with yeast. Nat Rev Genet. 8(6):437–49. 10. Brockmann R, Beyer A, Heinisch JJ, Wilhelm T. (2007) Posttranscriptional expression regulation: what determines translation rates? PLoS Comput Biol. 3(3 ):e57. 11. Calvano SE et al. (2005) A network-based analysis of systemic inflammation in humans. Nature. 437(7061 ):1032–7. 12. Chen M, Hofestaedt R. (2003) Quantitative Petri net model of gene regulated metabolic networks in the cell. In Silico Biol . 3:347–365. 13. Chuang HY, Lee E, Liu YT, Lee D, Ideker T. (2007) Network-based classification of breast cancer metastasis. Mol Syst Biol. 3:140. 14. Collins SR et al. (2007) Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevisiae. Mol Cell Proteomics. 6(3):439–50. 15. Cox J, Mann M. (2007) Is proteomics the new genomics? Cell . 130(3 ):395–8. 16. de Lichtenberg U, Jensen LJ, Brunak S, Bork P. (2005) Dynamic complex formation during the yeast cell cycle. Science. 307(5710 ):724–7. 17. Domon B, Aebersold R. (2006) Mass spectrometry and protein analysis. Science. 312(5771 ):212–7. 18. Downard KM. (2006) Ions of the interactome: the role of MS in the study of protein interactions in proteomics and structural biology. Proteomics. 6: 5374–5384. 19. Ernst J, Vainas O, Harbison CT, Simon I, Bar-Joseph Z. (2007) Reconstructing dynamic regulatory maps. Mol Syst Biol . 3:74. 20. Estojak J, Brent R, Golemis EA. (1995) Correlation of two-hybrid affinity data with in vitro measurements. Mol Cell Biol. 15:5820–5829. 21. Faur´e A, Naldi A, Chaouiya C, Thieffry D. (2006) Dynamical analysis of a generic Boolean model for the control of the mammalian cell cycle. Bioinformatics. 22(14 ):e124–31. 22. Foss EJ, Radulovic D, Shaffer SA, Ruderfer DM, Bedalov A, Goodlett DR, Kruglyak L. (2007) Genetic basis of proteome variation in yeast. Nat Genet. 39(11 ):1369–75. 23. Gao F, Foat BC, Bussemaker HJ. (2004) Defining transcriptional networks through integrative modeling of mRNA expression and transcription factor binding data. BMC Bioinformatics. 5:31.
54
A. Beyer
24. Gavin et al. (2006) Proteome survey reveals modularity of the yeast cell machinery. Nature. 440(7084):631–6. 25. Gilbert D, Fuss H, Gu X, Orton R, Robinson S, Vyshemirsky V, Kurth MJ, Downes CS, Dubitzky W. (2006) Computational methodologies for modelling, analysis and simulation of signalling networks. Brief Bioinform. 7(4 ):339–53. 26. Goss PJ, Peccoud J. (1998) Quantitative modeling of stochastic systems in molecular biology by using stochastic Petri nets. Proc Natl Acad Sci USA. 95(12 ):6750–5. 27. Han JD. (2008) Understanding biological functions through molecular networks. Cell Res. 18(2):224–37. 28. Heinrich R, Schuster S. (1998) The modelling of metabolic systems. Structure, control and optimality. Biosystems. 47(1–2):61–77. 29. Helikar T, Konvalina J, Heidel J, Rogers JA. (2008) Emergent decision-making in biological signal transduction networks. Proc Natl Acad Sci USA. 105(6 ):1913–8. 30. Ideker T et al. (2001) Integrated genomic and proteomic analyses of a systematically perturbed metabolic network. Science. 292:929–934. 31. Ideker T, Ozier O, Schwikowski B, Siegel AF. (2002) Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics. 18 Suppl 1 :S233–40. 32. International Human Genome Sequencing Consortium (2004). Finishing the euchromatic sequence of the human genome. Nature. 431:931−945. 33. Jansen RC. (2003) Studying complex biological systems using multifactorial perturbation. Nature Rev Genet. 4:145–151. 34. Joyce AR, Palsson BO. (2008) Predicting gene essentiality using genome-scale in silico models. Methods Mol Biol. 416:433–57. 35. Kelley R, Ideker T. (2005) Systematic interpretation of genetic interactions using protein networks. Nature Biotechnol. 23:561–566. 36. Kiesel J, Miller C, Abu-Amer Y, Aurora R. (2007) Systems level analysis of osteoclastogenesis reveals intrinsic and extrinsic regulatory interactions. Dev Dyn. 236(8 ):2181–97. 37. Klamt S, Gilles ED. (2004) Minimal cut sets in biochemical reaction networks. Bioinformatics. 20(2 ):226–34. 38. Klipp E, Nordlander B, Kruger R, Gennemark P, Hohmann S. (2005) Integrative model of the response of yeast to osmotic shock. Nature Biotechnol. 23:975–982. 39. Klipp E. (2007) Modelling dynamic processes in yeast. Yeast. 24(11 ):943–59. 40. Krogan et al. (2006) Global landscape of protein complexes in the yeast Saccharomyces cerevisiae. Nature. 440(7084):637–43. 41. Kr¨ uger M, Kratchmarova I, Blagoev B, Tseng YH, Kahn CR, Mann M. (2008) Dissection of the insulin signaling pathway via quantitative phosphoproteomics. Proc Natl Acad Sci USA. 105(7 ):2451–6. 42. Lage K et al. (2007) A human phenome-interactome network of protein complexes implicated in genetic disorders. Nature Biotechnol. 25:309–316. 43. Lange V et al. (2008) Targeted quantitative analysis of Streptococcus pyogenes virulence factors by multiple reaction monitoring. Mol Cell Proteomics. [Epub ahead of print] 44. L¨ ahdesm¨aki H, Rust AG, Shmulevich I. (2008) Probabilistic inference of transcription factor binding from multiple data sources. PLoS ONE . 3(3 ):e1820. 45. Lee I, Date SV, Adai AT, Marcotte EM. (2004) A probabilistic functional network of yeast genes. Science. 306:1555–1558. 46. Legrain P, Wojcik J, Gauthier JM. (2001) Protein–protein interaction maps: a lead towards cellular functions. Trends Genet. 17:346–352.
Network-Based Models in Molecular Biology
55
47. Linding R et al. (2007) Systematic discovery of in vivo phosphorylation networks. Cell . 129(7 ):1415–26. 48. Malmstr¨ om J, Lee H, Aebersold R. (2007) Advances in proteomic workflows for systems biology. Curr Opin Biotechnol . 18(4 ):378–84. 49. Mo ML, Jamshidi N, Palsson BØ. (2007) A genome-scale, constraint-based approach to systems biology of human metabolism. Mol Biosyst. 3(9 ):598–603. 50. Myers CL, Barrett DR, Hibbs MA, Huttenhower C, Troyanskaya OG. (2006) Finding function: evaluation methods for functional genomic data. BMC Genomics. 7:187. 51. Needham CJ, Bradford JR, Bulpitt AJ, Westhead DR. (2007) A primer on learning in Bayesian networks for computational biology. PLoS Comput Biol . 3(8 ):e129. 52. Papin JA, Stelling J, Price ND, Klamt S, Schuster S, Palsson BØ. (2004) Comparison of network-based pathway analysis methods. Trends Biotechnol . 22(8 ):400–5. 53. Pellegrini M, Marcotte EM, Thompson MJ, Eisenberg D, Yeates TO. (1999) Assigning protein functions by comparative genome analysis: protein phylogenetic profiles. Proc Natl Acad Sci USA. 96:4285–4288. 54. Pflieger D, J¨ unger MA, M¨ uller M, Rinner O, Lee H, Gehrig PM, Gstaiger M, Aebersold R. (2008) Quantitative proteomic analysis of protein complexes: concurrent identification of interactors and their state of phosphorylation. Mol Cell Proteomics. 7(2 ):326–46. 55. Ptacek J et al. (2005) Global analysis of protein phosphorylation in yeast. Nature. 438:679–684. 56. Rajagopalan D, Agarwal P. (2005) Inferring pathways from gene lists using a literature-derived network of biological relationships. Bioinformatics. 21(6 ):788–93. 57. Ramsey SA et al. (2008) Uncovering a macrophage transcriptional program by integrating evidence from motif scanning and expression dynamics. PLoS Comput Biol . 4(3 ):e1000021. 58. Ren B et al. (2000) Genome-wide location and function of DNA binding proteins. Science. 290(5500 ):2306–9. 59. Rhodes DR et al. (2005) Probabilistic model of the human protein–protein interaction network. Nature Biotechnol. 23:951–959. 60. Rual JF et al. (2005) Towards a proteome-scale map of the human protein–protein interaction network. Nature. 437:1173–1178. 61. Samoilov M, Plyasunov S, Arkin AP. (2005) Stochastic amplification and signaling in enzymatic futile cycles through noise-induced bistability with oscillations. Proc Natl Acad Sci USA. 102(7):2310–5. 62. Schilling CH, Letscher D, Palsson BØ. (2000) Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathway-oriented perspective. J Theor Biol. 203(3):229–48. 63. Scott MS, Perkins T, Bunnell S, Pepin F, Thomas DY, Hallett M. (2005) Identifying regulatory subnetworks for a set of genes. Mol Cell Proteomics. 4(5 ): 683–92. 64. Sprinzak E, Altuvia Y, Margalit H. (2006) Characterization and prediction of protein–protein interactions within and between complexes. Proc Natl Acad Sci USA. 103:14718–14723. 65. Steggles LJ, Banks R, Shaw O, Wipat A. (2007) Qualitatively modelling and analysing genetic regulatory networks: a Petri net approach. Bioinformatics. 23(3 ):336–43.
56
A. Beyer
66. Stelling J, Klamt S, Bettenbrock K, Schuster S, Gilles ED. (2002) Metabolic network structure determines key aspects of functionality and regulation. Nature. 420(6912 ):190–3. 67. Stelzl U et al. (2005) A human protein–protein interaction network: a resource for annotating the proteome. Cell. 122:957–968. 68. Stryer L. (1995) Biochemistry. Freeman & Co, New York. 69. Stuart JM, Segal E, Koller D, Kim SK. (2003) A gene coexpression network for global discovery of conserved genetic modules. Science. 302:249–255. 70. Suthram S, Shlomi T, Ruppin E, Sharan R, Ideker T. (2006) A direct comparison of protein interaction confidence assignment schemes. BMC Bioinformatics. 7:360. 71. Suthram S, Beyer A, Karp RM, Eldar Y, Ideker T. (2008) eQED: an efficient method for interpreting eQTL associations using protein networks. Molec Syst Biol. 4:162. 72. Tyson JJ. (1991) Modeling the cell division cycle: cdc2 and cyclin interactions. Proc Natl Acad Sci USA. 88(16 ):7328–32. 73. von Mering C et al. (2002) Comparative assessment of largescale data sets of protein–protein interactions. Nature. 417:399–403. 74. Workman CT et al. (2006) A systems approach to mapping DNA damage response pathways. Science. 312:1054–1059. 75. Yan W, Hwang D, Aebersold R. (2008) Quantitative proteomic analysis to profile dynamic changes in the spatial distribution of cellular proteins. Methods Mol Biol . 432:389–401. 76. Yeang CH, Mak HC, McCuine S, Workman C, Jaakkola T, Ideker T. (2005) Validation and refinement of gene-regulatory pathways on a network of physical interactions. Genome Biol. 6(7 ):R62. 77. Zhu J, Zhang MQ. (1999) SCPD: a promoter database of the yeast Saccharomyces cerevisiae. Bioinformatics. 15:607–611.
Ecological Networks: Structure, Interaction Strength, and Stability Samit Bhattacharyya and Somdatta Sinha Mathematical Modelling and Computational Biology Group, Centre for Cellular and Molecular Biology, CSIR, Hyderabad 500007, India;
[email protected],
[email protected]
1 Introduction The fundamental building blocks of any ecosystem, the food webs, which are assemblages of species through various interconnections, provide a central concept in ecology. The study of a food web allows abstractions of the complexity and interconnectedness of natural communities that transcend the specific details of the underlying systems. For example, Fig. 1 shows a typical food web, where the species are connected through their feeding relationships. The top predator, Heliaster (starfish) feeds on many gastropods like Hexaplex, Morula, Cantharus, etc., some of whom predate on each other [52]. Interactions between species in a food web can be of many types, such as predation, competition, mutualism, commensalism, and ammensalism (see Section 1.1, Fig. 2). Mathematical ecologists have used dynamic models to explore how the size and connectivity of food webs determine the stability and long-term persistence of a community under fluctuations in density [41], invasion of new species [11], or nonlinear population dynamics [24]. There are two different approaches for modeling a food web: the static model and dynamic model. Static models describe the food web by a graph whose vertices are species and whose links are the interactions/relations between them. These models are primarily concerned with the robustness of the food web structure against modifications (i.e., removal and addition) of vertices and links. Based on the hierarchical position of the species in a food web, there exist two types of static models: the cascade model and the niche model. The dynamic models, on the other hand, account for the stability of food webs, and are represented by coupled ordinary differential equations, where different functional forms describe the type of interactions between the species. However, neither the static nor the dynamic models are useful for making long-term predictions of the changes in structural organization of food webs due to extinction or invasion of new species in the community. Other models of food webs — the assembly model and evolutionary model — mainly focus on this aspect. One N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 4, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
58
S. Bhattacharyya and S. Sinha
Fig. 1. Feeding relationship between a predator Heliaster and marine snails in the northern Gulf of California (adapted from [52]).
basic assumption for construction of these models is that, instead of being random as in earlier models, the existence and strengths of links between species here are based on their web history [17](see Section 1.2).
1.1 Some Basic Definitions A community in ecology comprises all species populations interacting in an area. An example of a community is a coral reef, where numerous populations of fishes, crustaceans, and corals coexist and interact. A food web in an ecosystem is an assemblage of various organisms that are interconnected with each other through their different life history processes, such as feeding and shelter. A trophic level in a food web consists of all the species that prey on the same species and are also preyed upon by the same species. Ecological interactions are the relationships between two species in an ecosystem. Based on either effects, or on mechanisms, these relationships can be categorized into many different classes of interactions as described below and shown in Fig. 2. Here, the arrow signifies the flow of resources in the network, and the sign represents the effect of one species on the other. These interactions vary greatly with respect to their duration and strength. In many cases, the interactions of two species may have different impacts under different conditions. This is particularly true in, but not limited to, cases where species have multiple and drastically different life stages. Predation is a biological interaction in which one species feeds on another. Most of the interactions in a food web are predatory. Figure 2(i) shows the network for this interaction, where species 2 preys on species 1. This interaction enhances the fitness of predators (indicated by “+”), but reduces the fitness of the prey species (shown by “−”). Example: There is common
Ecological Networks: Structure, Interaction Strength, and Stability
59
Fig. 2. Types of ecological interactions: (i) predation, (ii) competition, (iii) mutualism, (iv) commensalism, (v) ammensalism.
predation of carnivores on herbivores in a grazing food web. Parasitism is similar to predation by mechanism, as it enhances the fitness of the parasite, but impairs the host. Example: The mite Varroa jacobsoni, is a parasite of the honeybee. Although not severely, it disrupts the honeybee’s colony formation. Competition between two species occurs when they share a limited resource and each tends to prevent the other from accessing it. This reduces the fitness of one or both species, as is shown by “−” in Fig. 2(ii). In mutualism or symbiosis, two species provide resources or services to each other. This enhances the fitness of both species (shown by “+” in Fig. 2(iii)). Example: Pollination is an example of mutualism, which enhances the fitness of both the plant and the pollinator. Commensalism is an interaction, where one species receives a benefit from another species. This enhances the fitness of one species without any effect on fitness of the other species (shown by “0” in Fig. 2(iv)). In the marine aquatic ecosystem, the clown fish and sea anemone share such a relationship. In ammensalism, one species impedes or restricts the success of the other without being affected positively or negatively by its presence (shown by “−” and “0” respectively in Fig. 2(v)). Example: The black walnut tree (Juglans nigra) secretes a chemical (juglone) from its roots that harms or kills some species of neighboring plants.
1.2 Ecological Network Models Ecological networks (i.e., food chains and food webs) have been mathematically described by different types of models, which focus on different aspects of their structure. We give simple descriptions of a few as follows:
60
S. Bhattacharyya and S. Sinha
Cascade model. These models are built on the hierarchical positions of the species in the food chain and use the role of top-down forces (predator to prey) in shaping the ecological communities. In cascade models, high-ranked species prey on lower-ranked species in the food chain, and the probability of consumption depends on the number of connections with these other species. It has been shown that the mean number of species in the cascade model grows linearly with the number of the species present in the food chain [13]. Niche model. Like the cascade models, the niche models are also structural in nature. But unlike the cascade model, the rigid hierarchical effect is relaxed in the niche model by allowing looping and cannibalism. The “niche model” takes its name from the premise that each trophic species (i.e., a group of species that share the same predators and prey) belongs to a specific niche based on what it eats and, in turn, on what eats it. Recent work [74] has shown that many diverse real food webs can be better described by the niche model than by the cascade model, in particular with respect to features such as cycles and species similarities. Assembly model and evolutionary model. In this class of models, as the names suggest, the species composition and structure of the food web can change with time due to the ongoing introduction of new species and by species extinctions. As a consequence, these models focus mainly on the features of the food web after a sufficiently long time, when the size of the food web and its other properties stabilize. The primary concern of these models relates to the stability of the food web due to the introduction of new species into the system by immigration or speciation (assembly) or by altering one or a few individuals of existing species in the system (evolutionary), though the time scales for evolutionary models are longer than those for assembly ones [60]. A few species from a “pool” are added one by one to the existing network. The new species may add stability to the web, become extinct immediately after introduction because of its poor adaptation, or may cause one or more other species to become extinct due to competition for resources. Usually studies of these models involve the measurement of various properties of the underlying network and compare these with the data of real food webs to determine the robustness in a given time period [9]. Keystone species. This concept provides an important representation for understanding the organizing forces in ecological communities. A keystone species is one whose presence contributes critically to the diversity of life in the food web, and whose removal has a strong adverse impact on the community structure, even though the species may occupy only a small part of the ecosystem in terms of biomass or productivity. Keystone species play an important role in conservation biology [53, 55]. Community matrix. In an ecological network, which describes interactions between multiple species at different trophic levels, the community matrix represents the per capita direct effect of one species on other species in the community [35]. In simple words, the community matrix is a spreadsheet, where the rows and columns are species and other elements of their environment,
Ecological Networks: Structure, Interaction Strength, and Stability
61
and the entry records are calculations for describing the interactions among them. The matrix can be used to derive the stability and sensitivity to change in ecological networks. Alternative but related definitions are common in ecological literature [41, 78]. Interaction strength is a critical descriptor of the magnitude of effect of one species on the other in an ecological network. There are several interpretations with the common theme of being a measure of the effect of one species on another or on all others in the network [38, 40]. In this work, we have used “interaction strength” to represent the per capita direct effects of a species on another (e.g., the per capita rate of consumption of the prey species by the predator, “α” in the first equation of Model I in Section 2, which can also be modulated by prey preference).
The complexity of a large ecological network or a whole food web can be described by many indicators: number of trophic levels, number of species and their connections, density of interactions, etc. Each trophic module embedded in the entire food web may also have a similar complexity in its structure and interactions. There are two mutually nonexclusive aspects that underscore a long-standing problem in food web theory: Do “the details of population dynamics in one or a few modules change the structure of the whole system over time” [64]? The first aspect is structural, and involves the distributive pattern of trophic structures or motifs which modulates the real food web system [3, 10, 46]. The other aspect is related to the study of specific trophic modules in order to infer properties of the entire ecosystem dynamics [4, 23]. The first one essentially refers to the robustness of the system against removal of nodes in the functional integrity of the ecological network. In particular, the study involves how removing or replacing native species with exotic invaders can alter the food web structure, which could be measured by the number of secondary extinctions, and by the breakup of the network into smaller components. For instance, conceptualizing food webs as energy-flow networks, Allesina and Bodini [2] have indicated that it is the “dominating nodes” (removal of which would make a number of species disappear from the network) that act as an energy bottleneck for resources flowing to the other members of the food web. However, it has also been shown that removal of species with low connectivity sometimes may have a large effect on the persistence of a community, which reinforces the notion of keystone species in food web theory [18, 31]. The second aspect that is particularly important for understanding real ecological network dynamics is related to the distribution of interaction strengths, which determines how strongly the links in the trophic cascade are coupled. For example in a consumer-resource interaction, the strength is a function of the metabolic rate, ingestion rate, and preference of the consumer species for the resource species [43]. The theoretical finding that interaction strength is one of the key properties promoting persistence in nonlinear models of food webs has attracted considerable attention [19, 43, 63, 67]. It is indeed challenging to ecologists to quantify the strengths of species
62
S. Bhattacharyya and S. Sinha
interactions, identify the patterns that occur between species, and determine the mechanisms that cause interactions to vary across space and time in natural ecosystems. These topics are also important for several other reasons. First, ecosystems, on the whole, provide hospitable conditions for life. Understanding how the provision of this hospitability is affected by extinctions and alien introductions is important, because without knowledge of the strengths of species interactions, our predictions on the consequences of environmental impacts become indeterminate for any ecosystem with a reasonable degree of complexity [6]. Second, development of a general understanding of how ecological communities are structured can benefit from an analysis of the general properties of multispecies population dynamics models [41, 58]. Knowledge of the pattern of interaction strengths in natural ecosystems can help to guide the development of appropriate multispecies models. A number of recent studies consider the influence of interaction strength on the stability of food webs for real communities [6, 7, 49, 51] and in food web models with a large number of species [12, 25, 28, 61]. Martinez et al. [39] studied the effect of the variation of the interaction strength of omnivore links on the stability of large food webs. General patterns of food web structure also appear to be an emergent property of dynamical constraints on species interactions [5, 17]. However, in a more realistic study, the food web dynamics has been considered by introducing time-varying interactions among the adaptive foragers [20, 21, 30, 56, 71, 72]. Adaptation modifies predator-prey interaction strengths, and thus, acts on the topology of the network by eventually removing certain links with zero strength. As a consequence, the complexity of the food web is molded by how adaptive predators design their foraging strategy. Recently, it has also been shown that adaptation of foraging behavior and stability of food webs can lead to a rise in basal species richness and link density, which in turn, increases the emergent complexity of the food web [21, 30]. However, there still remains a significant gap in predictions on food web stability and the role of distribution of interaction strengths in the Food web. This key problem in ecology arises due to the basic difference between empiricists and theoreticians in understanding the concepts of stability, and interaction strength [6, 32]. Many theoretical investigations have focused on the definition of stability in model communities [11, 25, 36, 41, 42, 44]. Multiple definitions of stability have been proposed, some of them designed to have closer ties to empirical data [14, 15, 33, 37]. This is important because most of the earlier analytical studies evaluate linear stability of a community at equilibrium in the face of small perturbations, whereas empirical investigations focus on community changes (with no assumed equilibrium) in response to comparatively large perturbations, such as species removals, species additions, and physical disturbances [75]. The measurement of interaction strengths, on the other hand, actually centers around different concepts in the system, and the only consistent aspect is the use of the words “interaction strength”. Laska and Wootton [32] have clearly mentioned the difference in understanding the
Ecological Networks: Structure, Interaction Strength, and Stability
63
interaction strength for the theoretician and empiricist communities. However, even within theoretical or empirical investigations, there exists a diversity of indices that measure the link weight, or interaction strength. Nevertheless, this creates a critical problem in predicting the relative effects of strong or weak interactions in a community. For example, strong consumption intensity by a predator, or large energy flow from prey to predator, is not necessarily a good predictor of large dynamical effects on prey abundance [6, 50, 54, 62], nor is it necessarily a good predictor of strong interaction coefficients in the community matrix [16]. Similarly, strong interaction coefficients in the community matrix, which are defined by small perturbations, may not necessarily predict strong effects of a large perturbation such as species addition or removal [1, 79]. This gap between experiment and theory in understanding the concepts has remained a long-standing problem in ecological research. In spite of all the recent and ongoing research on networks in general, and food webs in particular, a new synthesis of the relationship between structure and dynamics of complex networks for ecological systems remains elusive. Ecological networks are unlike other networks (including other biological networks) [47], as the process of various interactions (predation, competition, mutualism, etc.) between organisms at different trophic levels ties up the entire organization in a unique way, which is an inherent and distinct feature of the ecological systems. Here, we propose, with simple examples, to explain how the dynamic interplay between the ecological network structure and interaction strengths regulates the structure of the network and the dynamics of the species in it. This may provide some interesting insights about the importance of interaction strengths in ecological network research.
2 Food Web Structure, Interaction Strength, and Stability Food web models are extensions of bioenergetic consumer-resource models, which by definition focus exclusively on trophic interactions. In a recent study, it was shown that predation is the most important process determining the community structure and dynamics [51]. There are a few important related factors that regulate the strength of this process, such as metabolic efficiencies, handling times, foraging strategies, and frequencies of encounters [21]. In the following section, we consider two simple ecological networks of the prey-predator interaction and discuss how the emergence of new functional components that alter interaction strengths can regulate the stability in food web dynamics. 2.1 The Models Model I. Figure 3(i) shows a prey-predator system where the predator species is commensal on the prey species. In this simple model, in the absence of
64
S. Bhattacharyya and S. Sinha
Fig. 3. Food web configurations of (i) Model I and (ii) Model II.
the predator (Y ), the prey species (X) follows a density-dependent logistic growth with r as its intrinsic growth rate, and K as the carrying capacity of the environment. However, in the presence of the predator, the growth of the prey is reduced due to predation of Y on X. This interaction follows a hyperbolic function with γ denoting the half saturation coefficient of predation and α deciding the strength of interaction, i.e., the per capita consumption rate (see [43] for an actual measure of the interaction strength). In the absence of prey, the predator species dies out exponentially at a rate d. On predation, the rate at which this food adds to the growth of the predator population is given by the conversion rate β. The rate of change of the prey (dX/dt) and predator (dY /dt) populations with time are governed by the following equations: X αXY dX = rX 1 − − dt K γ+X βαX dY = Y −d+ . dt γ+X For this study, the parameter values are taken as r = 0.5, K = 5, d = 3, γ = 0.8, and β = 0.7. The main parameter, α, which indicates the interaction strength of predation, is varied from 5.5 to 6.5 to describe the change in dynamics in this model network. Model II. Here, we consider the addition of a new structural component in the food web of Fig. 3(i), which is shown in Fig. 3(ii). It is assumed that the introduction of a virus species (V ), which can infect the prey species (X) in Model I, divides the prey population into two compartments: Susceptible (S) and Infected (I) with S + I = X, where the susceptible class follows the same growth laws as X in Model I. The flux between susceptible to infective compartments is dependent on the strength with which the virus attacks the prey following a simple law of mass action. However, this compartmentalization of the prey species also affects the predation strength; although the predator
Ecological Networks: Structure, Interaction Strength, and Stability
65
(Y ) can consume both the susceptible and the infected prey, it may have a higher preference towards the uninfected prey (S), and a concomitant lower one towards the infected prey (I). Thus, the earlier strong interaction α (in Model I) is now modified into two interactions with variable strength: one strong interaction augmented with one weak interaction (Fig. 3(ii)). The rate of change of the virus population (dV /dt) depends on the the infected prey population (I), as every dead and lysed infected prey releases virus into the environment, initiating a new infection cycle. The temporal evolution of this ecological network is given as follows: S dS ξαSY = rS 1 − − λSV − dt K γ + (S + I) (1 − ξ)αIY dI = λSV − − ηI dt γ + (S + I) dY βα(ξS + (1 − ξ)I) = Y −d+ dt γ + (S + I) dV = −μV + κηI, dt where V is the virus density and λ defines the strength of viral infection on the susceptible class of prey, and represents the “effective per host contact rate with viruses.” Parameter η denotes the death rate of the infected prey and μ is the death rate for the virus. κ denotes the “virus replication parameter,” i.e., the number of virus productions per infected individual due to lysis. The other parameter that regulates the interaction strength of predation, indicating the prey preference of the predator, is ξ (ξ ∈ (0, 1)). The exact choice of these parameter values is arbitrary, but they are kept within the same range as in [8, 22].
3 Results In Model I, the predation strength α is an important determinant of the dynamics of the prey and predator populations. As seen in the bifurcation diagrams of prey and predator populations (Fig. 4), both exhibit equilibrium dynamics for α < 5.6, but the steady state loses its stability and bifurcates to limit cycle oscillations with increasing amplitude for α > 5.6 (Fig. 4). We now show the results of the effect of modifying the structure of this simple two-species network due to, addition of the new link through the virus, which not only separates the prey species into two compartments, but also modifies the predation strength (Model II). For simulation of the Model II network, the new parameter values are chosen as λ = 0.002, η = 0.7, μ = 0.05, and κ = 13. The introduction of the new node (V ) and links to the existing module (Model I) has interesting effects on the population dynamics of the species that
66
S. Bhattacharyya and S. Sinha
Prey
6 4 2 0
Predator
0.6 0.4 0.2 0 5.5
5.7
5.9
6.1
α
6.3
6.5
Fig. 4. Bifurcation diagram of the prey and predator in Model I with increasing predation strength α. At α = 5.6 (approx.), the system undergoes a period-doubling bifurcation.
2
1
10
0
b
−1
10
−2
0
6
101
4
100
Infected
4
10
Susceptible
6 Infected
Susceptible
a
2
10−2
0
10
500
0 5.5
6
α
6.5
100 50 10 5 5.5
0.4 Virus
0.2
Predator
Virus
Predator
500 0.4
10−1
0.2 0
6
α
6.5
5.5
6
α
6.5
100 50 10 5 5.5
6
α
6.5
Fig. 5. Bifurcation diagram of all four populations–Susceptible prey, infected prey, predator, and virus–in Model II as function of interaction strength parameter α, for different prey preference: (A) ξ = 0.5, (B) ξ = 0.99.
depends on the interaction strength. As ξ regulates the predation strength by changing the prey preference of the predator, we analyzed Model II for two different values of this interaction strength: ξ = 0.99 indicating high preference for the susceptible prey and very low preference for the infected prey; and, ξ = 0.5, where the predator has no preference of one over the other. Figure 5 shows the bifurcation diagrams of Model II for the two cases, ξ = 0.5 and 0.99. Figure 5(A) shows that, at ξ = 0.5, there are two important changes that occur in the same range of predation strength, i.e., 5.5 < α < 6.5. First, the network reduces to only a “prey (S and I) and virus (V )” system
Ecological Networks: Structure, Interaction Strength, and Stability
67
with the predator population going to zero. This happens because, in the absence of predation, all of S is available for inducing strong viral infection, which converts the susceptible prey class to the infected one, and the predator does not have enough preys to survive through predation. Second, the dynamics of this prey-virus system remains stable with a large virus population and low prey populations. When the the predator has a strong preference for the S population, i.e., at ξ = 0.99, this situation continues for low predation strength (until α = 6.2), and the reduced prey-virus system remains stable (Fig. 5(B)). However, at higher predation strength (α > 6.2), the predator succeeds in surviving on predation and reduces the population of I strongly enough to reduce the production of V , which in turn reduces infection, thereby increasing S, which is then available for predation. This kind of a delayed feedback on S eventually induces oscillations in all four populations, albeit at higher α compared to Model I. This interesting phenomenon essentially underscores the fact that distribution of the type (+ or −) and the strength of interactions can play a significant role in food web structure and dynamics. It can change the structure of the network by inducing a species to go extinct, and also promote stability in an otherwise oscillatory system.
4 Discussion and Conclusion Community stability in ecology is primarily decided by the topological and functional architecture of the entire organization. Some studies have indicated that weak interactions are one of the most dominant threads in weaving natural communities in tune [50, 77], which is also reasserted by our simple models. Weak interactions have been proposed as the “glue” that binds large networks together [43], with ramifications for biodiversity. In particular, this has important implications for those species whose low abundance and weak per capita consumption rates might otherwise be taken as evidence of a negligible role [42]. Large network simulations have shown that the distribution of interaction strengths is strongly skewed towards weak interactions [29, 61]. Although the experimental quantification of interaction strength in field studies is difficult, preliminary contributions on the nature of distributions of interaction strengths within real food webs are slowly emerging [16, 76]. Similarly, the importance of weak interactions for dynamic stability and species coexistence has been suggested from matrix analyses of soil food webs, numerical simulations of small and large webs, and experimental manipulations [6, 32, 48, 59]. Our study, with two very simple yet realistic ecological networks, points towards some intriguing features. One point of interest is that the introduction of another species in a two-species prey-predator interaction network compartmentalizes the single prey species into two subgroups leading to additional diversity in the network. Such a node can modify the network structure by pushing the predator species to extinction simply based on the interaction strength and its preference level. At higher values of both these interaction
68
S. Bhattacharyya and S. Sinha
parameters, the full network structure persists. These features, i.e., the interaction strength and network structure, also regulate the population dynamics of the species. A combination of type and strength of interactions determines the dynamical stability of the species in the network. One natural extension of our study would be to introduce yet another class of prey species, Recovered, which represents the population of individuals that recover from the infection after a time, and either return to the susceptible class, or may be immune to further infections. This would, obviously, increase the complexity of the network by adding new nodes and interactions among them. However, this would contribute towards understanding the concept “diversity leads to stability” on large-scale food web processes. Most of the recent research on food web theory in ecology centers around the local dynamics of a community, but the evolution of food web dynamics across different spatial scales has also received considerable attention [26, 27, 45, 57, 73]. “Habitat fragmentation and its impact on life” is one of the most important issues of present research [66]. The destruction of habitat occurs due to a variety of environmental threats, such as habitat removal, invading alien species, or hunting, each of which may have different effects on food web structure. Given that they often act concomitantly, these may also interact with each other in unpredictable ways. Introduction of alien species poses a significant threat to global biodiversity by altering ecosystem processes, such as nutrient cycling, or disturbance regimes in a community [65], which, in turn, also affect the strength of the links. If the performance of interacting species is habitat dependent, then interaction strength may change with scale. Certain approaches such as hierarchical communities of competitors [69, 70] and neutral and quasi-neutral communities [68] have been adapted to show that community organization is relevant in determining the effects of habitat loss and spatial patterning. Such research on ecological network theory in the future would involve rigorous modeling approaches, both analytical and through simulations, in combination with field and laboratory experimental studies, to resolve the crucial questions in conservation and restoration ecology. Acknowledgments The authors are thankful to the anonymous referees for constructive, critical comments, and to the Department of Science and Technology, India, for financial support.
References 1. Abrams, P. et al. The role of indirect effects in food webs. In Food Webs: Integration of Patterns and Dynamics (eds G.A. Polis & K.O. Winemiller), 371–395, Chapman & Hall, New York (1996) 2. Allesina, S. and Bodini, A. Who dominates whom in the ecosystem? Energy flow and bottlenecks and cascading extinctions. J. Theor. Biol., 230, 351–358 (2004)
Ecological Networks: Structure, Interaction Strength, and Stability
69
3. Bascompte, J. and Melian, C. J. Simple trophic modules for complex food webs. Ecology, 86, 2868–2873 (2005) 4. Bascompte, J. et al. Interaction strength combinations and the overfishing of a marine food web. Proc. Natl Acad. Sci. USA, 102, 5443–5447 (2005) 5. Bastolla, U., Lassig, M., Manrubia, S. C. and Valleriani, A. Diversity patterns from ecological models at dynamical equilibrium. J. Theor. Biol., 212, 11-34 (2001) 6. Berlow, E. L. et al. Interaction strengths in food webs: issues and opportunities. J. Anim. Ecol., 73, 585–598 (2004) 7. Berlow, E. L., Brose U., and Martinez, N. D. The “Goldilocks factor” in food webs. Proc. Natl. Acad. Sci. USA, 105, 4079–4080 (2008) 8. Bhattacharyya, S. and Bhattacharya, D. K. Pest control through viral diseases: mathematical modeling and analysis. J. Theor. Biol., 238, 177–197 (2006) 9. Caldarelli, G., Higgs, P. G. and McKane, A. J. Modelling coevolution in multispecies communities, J. Theor. Biol., 193, 345–358 (1998) 10. Camacho, J. et al. Quantitative analysis of the local structure of food webs. J. Theor. Biol., 246, 260–268 (2007) 11. Case, T. J. Invasion resistance arises in strongly interacting species-rich model competition communities. Proc. Natl. Acad. Sci. USA, 87, 9610–9614 (1990) 12. Chen, X. and Cohen, J. E. Global stability, local stability and permanence in model food webs. J. Theor. Biol., 212, 223–305 (2001) 13. Cohen, J. E., Briand, F. and Newman, C. M. Community food webs. Biomathematics, 20, Springer-Verlag, Berlin (1990) 14. Dambacher, J. M. et al. Relevance of community structure in assessing indeterminacy of ecological predictions. Ecology, 83, 1372–1385 (2002) 15. Dambacher, J. M. et al. Qualitative stability and ambiguity in model ecosystems. Am. Nat., 161, 876–888 (2003) 16. De Ruiter, P., Neutel, A. M. and Moore, J. C. Energetics, patterns of interaction strengths, and stability in real ecosystems. Science, 269, 1257–1260 (1995) 17. Drossel, B. and McKane, A. J. Modelling food webs. In Handbook of Graphs and Networks (eds S. Bornholdt & H. G. Schuster), 218–247, Wiley-VCH, Berlin (2003) 18. Dunne, J. A. et al. Network structure and biodiversity loss in food webs: robustness increases with connectance. Ecol. Lett., 5, 558-567 (2002) 19. Emmerson, M. C. and Raffaelli, D. Predator-prey body size, interaction strength and the stability of a real food web. J. Anim. Ecol., 73, 399–409 (2004) 20. Garcia-Domingo, J. L. and Saldana, J. Food-web complexity emerging from ecological dynamics on adaptive networks. J. Theor. Biol., 247, 819–826 (2007) 21. Garcia-Domingo, J. L. and Saldana, J. Effects of heterogeneous interaction strengths on food web complexity. Oikos, 117, 336–343 (2008) 22. Ghosh, S., Bhattacharyya, S. and Bhattacharya, D. K. Role of viral infection in pest control: a mathematical study. Bull. Math. Biol., 69, 2649–2691 (2007) 23. Gross, T. et al. Long food chains are in general chaotic. Oikos, 109, 135–144 (2005) 24. Hastings, A. and Powell, T. Chaos in a 3-species food-chain. Ecology, 72, 896–903 (1991) 25. Jansen, V. A. A. and Kokkoris, G. D. Complexity and stability revisited, Ecol. Lett., 6, 498–502 (2003) 26. Keitt, T. H. Network theory: an evolving approach to landscape conservation. Ecological and Modeling for Resource Managers, Springer Berlin, 125–134, (2003)
70
S. Bhattacharyya and S. Sinha
27. Keitt, T. H. and Economo, E. P. Species diversity in neutral metacommunities: a network approach. Ecol. Lett., 11(1), 52–62, (2008) 28. Kokkoris, G. D. et al. Variability in interaction strength and implications for biodiversity. J. Anim. Ecol., 71, 362–371 (2002) 29. Kokkoris, G. D., Jansen, V. A. A., Loreau, M. and Troumbis, A. Y. Variability in interaction strength and implications for biodiversity. J. Anim. Ecol., 71, 362–371 (2002) 30. Kondoh, M. Does foraging adaptation create the positive complexity-stability relationship in realistic food-web structure? J. Theor. Biol., 238, 646–651 (2006) 31. Krause, A. E. et al. Compartments revealed in food-web structure. Nature, 426, 282–285 (2003) 32. Laska, M. S. and Wootton, J. T. Theoretical concepts and empirical approaches for measuring interaction strength. Ecology, 79, 461–476 (1998) 33. Law, R. and Morton, R.D. Permanence and the assembly of ecological communities. Ecology, 77, 762–775 (1996) 34. Lawton, J. H. Food webs. In Ecological Concepts: the Contribution of Ecology to an Understanding of the Natural World (ed. J. Cherret), 43-78, Blackwell, Boston (1990) 35. Levines, R. Evolution in Changing Environments: Some Theoretical Explanations. Princeton University Press, Princeton, NJ, USA (1968) 36. Logofet, D. O. Stronger-than-Lyapunov notions of matrix stability, or how ‘flowers’ help solving problems in mathematical ecology. Linear Algebra and Its Applications, 398, 75–100 (2005) 37. Loreau, M. et al. A new look at the relationship between diversity and stability. In Biodiversity and Ecosystem Functioning: Synthesis and Perspectives (eds M. Loreau, S. Naeem and P. Inchausti), 79–91, Oxford University Press, Oxford (2002) 38. MacArthur, R. H. and Levines, R. Strong, or weak interactions? Tansactions of the Connecticut Academy of Arts and Sciences, 44, 177–188 (1972) 39. Martinez, N. D. et al. Diversity, complexity, and persistence in large model ecosystems. In Ecological Networks, Linking Structure to Dynamics in Food Webs (eds Pascual, M. and Dunne, J. A.) Santa Fe Inst., Studies in the sciences of complexity. Oxford Univ. Press, 163–185 (2006) 40. May, R. M. Will a large complex system be stable? Nature, 238, 413–414 (1972) 41. May, R. M. Stability and Complexity in Model Ecosystems, Princeton University Press, Princeton, NJ, USA(1973) 42. McCann, K. S. The diversity–stability debate. Nature, 405, 228–233 (2000) 43. McCann, K. et al. Weak trophic interactions and the balance of nature. Nature, 395, 794–798 (1998) 44. McCann, K. and Hastings, A. Re-evaluating the omnivory–stability relationship in food-webs. Proc. Roy. Soc. of London, Series B, 264, 1249–1254 (1998) 45. Memmott, J. et al. Biodiversity loss and ecological network structure. In Ecological Networks: Linking Structure to Dynamics in Food Webs (eds. M. Pascual and J.A. Dunne), Oxford University Press, Oxford (2006) 46. Milo, R. et al. Network motifs: simple building blocks of complex networks. Science, 298, 824–827 (2002) 47. Montoya, J. M., Pimm, S. L. and Sole, R. V. Ecological networks and their fragility. Nature, 442, 259–264 (2006) 48. Montoya, J. M. and Sole, R.V. Topological properties of food webs: from real data to community assembly models. Oikos, 102, 614–622 (2003)
Ecological Networks: Structure, Interaction Strength, and Stability
71
49. Navarrete, S. A. and Berlow, E. L. Variable interaction strengths stabilize marine community patterns. Ecol. Lett., 9, 526–536 (2006) 50. Navarrete, S. A. and Castilla, J. C. Experimental determination of predation intensity in an intertidal predator guild: dominant versus subordinate prey. Oikos, 100, 251-262 (2003) 51. Otto, S. B., Berlow, E. L., Rand, N. E., Smiley, J. and Brose, U. Predator diversity and identity drive interaction strength and trophic cascades in a food web. Ecology, 89, 134–144 (2008) 52. Paine, R. T. Food web complexity and species diversity. Am. Nat., 100, 65–75 (1966) 53. Paine, R. T. A note on trophic complexity and community stability. Am. Nat., 103(929), 91–93 (1969) 54. Paine, R. T. Food webs - road maps of interactions or grist for theoretical development. Ecology, 69, 1648–1654 (1988) 55. Paine, R. T. A. Conversation on refining the concept of keystone species. Conservation Biology, 9(4), 962–964 (1995) 56. Petchey, O. L., Beckerman, A. P, Riede, J. O. and Warren, P. H. Size, foraging, and food web structure. Proc. Natl. Acad. Sci. USA, 105, 4191–4196 (2008) 57. Peterson, E. E., Theobald, D. M. and Ver Hoef, J. M. Geostatistical modeling on stream networks: developing valid covariance matrices based on hydrologic distance and stream flow. Freshwater Biology, 52, 267–279 (2007) 58. Pimm, S. L. The complexity and stability of ecosystems. Nature, 307, 321-326 (1984) 59. Polis, G. A. Stability is woven by complex webs. Nature, 395, 744-745 (1998) 60. Post, W. M. and Pimm, S. L. Community assembly and food web stability, Math. Biosci., 64, 169–192 (1983) 61. Quince, C. et al. Topological structure and interaction strengths in model food webs. Ecol. Model., 187, 389–412 (2005) 62. Raffaelli, D. G. Trends in research on shallow water food webs. Journal of Experimntal Marine Biology and Ecology, 250, 223–232 (2000) 63. Rooney, N. et al. Structural asymmetry and the stability of diverse food webs. Nature, 442, 265–269 (2006) 64. Sabo, J. L. et al. Population dynamics and food web structure - predicting measurable food web properties with minimal detail and resolution. In Dynamic Food Webs, Multispecies Assemblages, Ecosystem Development and Environmental Change (eds. de Ruiter, P. C. et al.) Theor. Ecol. Ser., Academic Press, 437– 452 (2005) 65. Schmitz, D. C. and Simberlo, D. Biological invasions: a growing threat. Issues in Sci. & Tech. 13, 33–40 (1997) 66. Singh, B. K., Subba Rao, J., Ramaswamy, R. and Sinha, S. The role of heterogeneity on the spatiotemporal dynamics of hostparasite metapopulation. Ecol. Model., 180, 435–443 (2004) 67. Singh, B. K., Chattopadhyay, J. and Sinha, S. The role of virus infection in a simple phytoplankton zooplankton system. J. Theor. Biol., 231, 153–166 (2004) 68. Sole, R. V., Alonso, D. and McKane, A. self-organized instability in complex ecosystems. Phil. Trans. Roy. Soc. Lond. Ser., B-Biol. Sci. 357, 667–681 (2002) 69. Stone, L. Biodiversity and habitat destruction - a comparative study of model forest and coral-reef ecosystems. Proc. Natl. Acad. Sci. USA, 261, 381-388 (1995) 70. Tilman, D. et al. Habitat destruction and the extinction debt. Nature, 371, 6566 (1994).
72
S. Bhattacharyya and S. Sinha
71. Uchida, S. and Drossel, B. Relation between complexity and stability in food webs with adaptive behavior. J. Theor. Biol., 247, 713–722 (2007) 72. Uchida, S., Drossel, B. and Brose, U. The structure of food webs with adaptive behaviour. Ecol. Model., 206, 263–276 (2007) 73. Urban, D. L., Goslee, S., Pierce K. B. and Lookingbill, T.R. Extending community ecology to landscapes. Ecoscience, 9, 200–212 (2002) 74. Williams, R. J. and Martinez, N. D. Simple rules yield complex food webs. Nature, 404, 180–183 (2000) 75. Woodward, G. and Hildrew, A. G. Body-size constraints on niche overlap and intraguild predation in a complex food web. J. Anim. Ecol., 71, 1063–1074 (2002) 76. Wootton, J. T. Estimates and tests of per-capita interaction strength: diet, abundance, and impact of intertidally-foraging birds. Ecological Monographs, 67, 45– 64 (1997) 77. Wootton, J. T. and Emmerson M. Measurement of interaction strength in nature. Annu. Rev. Ecol. Evol. Syst., 36, 419–444 (2005) 78. Yodzis, P. The indeterminacy of ecological interactions as perceived through perturbation experiments. Ecology, 69, 508–515 (1988) 79. Yodzis, P. and Innes, S. Body-size and consumer-resource dynamics. Am. Nat., 139, 1151–1175 (1992)
Signaling and Feedback in Biological Networks Sandeep Krishna, Mogens H. Jensen, and Kim Sneppen Center for Models of Life, Niels Bohr Institute, Blegdamsvej 17, 2100 Copenhagen, Denmark;
[email protected],
[email protected],
[email protected]
1 Introduction Cellular processes operate on a wide range of time and length scales to produce complex and intricate dynamics. It is a great challenge to understand both how these dynamical patterns are produced, as well as why they are produced; that is, what functional or evolutionary role do they play? This is one of the most fruitful areas in which to apply the ideas of complex networks. Living cells have all the prerequisites for a useful representation as networks. First, cellular systems contain numerous non-identical active components—genes, proteins, RNA, etc. These are the nodes of the network. Second, there are many interactions between these components, which form the links between the nodes. Not every pair of components interacts, so the resulting network is not fully connected, nor is it a tree or other simple topology. Thus, cellular networks provide plenty of scope for analysing their structure and graphtheoretic properties, and numerous studies have taken advantage of this (see [1] for reviews and [2–9] for some examples). Network representations of cellular systems can easily be augmented to address dynamical issues. Each node can be associated with a dynamical variable which could represent, for example, the concentration of that protein or the level of expression of that gene. Equations or rules governing the temporal dynamics of these variables can then be written, where the network structure determines which variables interact with each other. This usually requires encoding more information about the interactions into the network representation. For instance, apart from knowing that one node links to another, one needs to know the sign and strength of the interaction. However, in a network picture it is sometimes difficult to encode more detailed molecular information, such as whether the binding of a protein to DNA is accompanied by DNA looping, or whether a small molecule that binds to a protein can also bind equally well when that protein is bound to DNA. N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 5, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
74
S. Krishna, M.H. Jensen, and K. Sneppen
The question then is: What kind of physiologically useful processes can be illuminated by the kind of information that is easily represented in a network picture of a cell? One broad class of such processes is signal propagation. Signals need to be sent in response to environmental conditions in order to trigger the appropriate functional proteins, and need to be sent between proteins in order to perform necessary computations. For example, the presence of food metabolites in the surroundings triggers signals to proteins involved in transport and metabolism of those molecules; or a sudden change in the temperature triggers signals to proteins which buffer the cell against the shock. Network representations of cellular systems are particularly suited to study signal propagation because they precisely delineate the paths along which signals could travel. The next level of complication occurs when a signal loops back onto itself. Such feedback loops are at the core of every non-trivial computation performed by a cell [10–16]. Feedback loops are necessary for much non-trivial dynamical behaviour, in particular, oscillations and multistability, both of which are important for proper cellular function in different organisms. Our review will therefore introduce biological networks specifically with the intention of investigating signal propagation and feedback. We will describe simple measures for examining signal propagation on networks. We will use the organism-wide cellular network of E. coli to discuss whether the network structure has any particular properties which would affect the cost and specificity of signal propagation. The review will then continue by discussing feedback in sub-networks of mammalian and yeast cells. We will take one example each from a biological setting where, respectively, negative and positive feedback in the network structure play a crucial role in the dynamical behaviour of the system. Finally, we will conclude by looking at combinations of feedback loops. We show that two entangled feedback loops, which are common in bacterial cells, have dynamical properties that are quite different from those of their individual loops.
2 Signaling An organism-wide protein network of the bacterium E. coli can be extracted from the database EcoCyc [17] and represented as a directed, bipartite graph with 2846 protein nodes and 2774 reaction nodes [18]. The reaction nodes include all kinds of cellular reactions between proteins: transcription reactions, complex formations, protein modifications and metabolic reactions. Figure 1A shows the giant weakly connected component of this graph, consisting of 1938 reactions (of which 812 are transcription reactions, squares) and 1897 proteins (circles). Figure 1A also illustrates that the E. coli graph is composed of a large number of relatively small strong components (a strong component is a sub-graph where there is a directed path between every pair of nodes). Figure 1B compares this with the strong component structure of a randomised network with exactly the same number of nodes and links, as well as the same in- and out-degree (number of in- and out-links) of each node. The E. coli
Signaling and Feedback in Biological Networks
75
Fig. 1. E. coli protein reaction network. (A, Left) The graph is the largest weak component of a bipartite network, consisting of proteins (circles) and reaction nodes (promoters (squares), complex formations and modifications (black squares)). The two largest hubs, σ 70 and CRP , and their links, have been removed for ease of visualisation. (A, bottom left) Illustration of the procedure of making the strong component graph. (A, Right) The resulting strong component graph of the E. coli network. An arrow in the strong component graph indicates that there is a path connecting the two strong components in the original graph; nodes correspond to strong components of minimum size two. (B) The strong component graph for a randomized version of the E. coli network. The randomisation preserves the total number of nodes, total number of links and the number of in- and out-links of each node [18].
protein network is much more modular than the randomized network, an overall feature of regulation/signaling that was first suggested in [19]. In such a network, what we call “signals” are perturbations in the dynamical variables associated with the nodes. For instance, if they were all proteins, then a perturbation in the concentration of one protein would alter the concentration of all the proteins downstream from the original one. The simplest aspect of the structure of the network that influences signaling is the number of nodes that are downstream of any given starting node (note that this is a quantity that can be sensibly studied only with a directed graph representation of the network; in any connected undirected graph all nodes are downstream of each other). The possible signals emanating from the starting node are
76
S. Krishna, M.H. Jensen, and K. Sneppen
Fig. 2. The cumulative distribution of number of downstream targets s for nodes of the E. coli network (lower curve) and the randomised network (upper curve) [18].
obviously limited to reach only these nodes. The strong component graphs in Fig. 1 show particularly clearly how the network structure affects signaling possibilities. Within each strong component, every node can, in principle, send a signal to another node. But between strong components the possibilities are hugely reduced. Thus, the E. coli network structure already seems to be set up to allow plentiful signaling on short length scales, but to allow only very specific paths on longer length scales. In the random network, however, most nodes can send signals to almost the entire network (because most of the nodes are part of one giant strong component). A percolating structure like this is not conducive to specific signaling because every node has almost the entire network downstream of it. Figure 2 bolsters this conclusion, showing that in the E. coli network proteins have a much smaller number of downstream targets than in the randomised network. 2.1 Cost of Signaling Signaling is not just about reaching a downstream target. As a signal propagates, it needs other molecules to help it pass the message across consecutive reactions. Consider, for example, a signal initiated by an increase in the concentration of a given transcription factor. The promoter it influences may depend on other transcription factors, for example, in an or-gate construction. If that is the case, and the other transcription factor is already abundant, the promoter activity will not be influenced and thus the signal will not be transmitted. More generally, for each additional reactant along a reaction pathway, signal propagation becomes increasingly coupled to the overall state of the
Signaling and Feedback in Biological Networks
77
Fig. 3. (A) Schematic showing how the “cost” of a signaling path, A → F , is measured. In this case proteins B and D are necessary, giving a cost C = 2. (B) Cost of a signaling path as a function of its length for the real (solid) and randomised (dashed) E. coli networks [18].
molecules in the cell. The more reactions in the path, and the more reactants in each reaction, the more conditions that must be met for propagation of the signal. We quantify this cost C = C(path) for an arbitrary path from a starting protein to a target protein by simply counting the number of reactants along the entire path (not counting the protein nodes which are part of the path), as described schematically in Fig. 3A. If the same reactant is used several times, it is only counted once. Notice that the propagation of a signal does not necessarily mean an increased level of the proteins involved. The key point is that a change in input state should be transmitted to a changed output state of the end product. Our cost function is a simple measure of the complexity of handling such a signal and it could, in principle, be calculated between any pair of proteins where a path exists in the directed network. Figure 3B shows the average cost of signals propagating from one protein to another along the shortest path connecting them, as a function of the length l of that path. Each data point is the average over all pairs which are at the given distance. Except for paths of length two, the average cost for signals
78
S. Krishna, M.H. Jensen, and K. Sneppen
D
E
F
Fig. 4. The six largest strong components of the E. coli network (A–F), along with plots of the average cost, C(l) as a function of signaling distance. The grey areas show the range spanned by C(l) for 100 randomised versions of the subgraphs [18].
is significantly smaller for the real E. coli network than for a randomised networks (error bars are smaller than the symbol size). Figure 4 repeats this analysis for each of the six largest strong components in the network. These strong components capture distinct functional units associated, respectively, to (A) predominantly fatty acid metabolism, (B) the transcription network around σ factors, (C) PTS-sugar transport, (D) ABC transporters, (E) the FeII and FeIII transport system and (F) the chemotaxis module. Overall, we see that the cost within each module is fairly similar to the random expectation. 2.2 Conclusions About Signaling We have shown that the molecular network of E. coli is designed in a way which facilitates local signaling. On longer distances, signal transmission is a priori nearly impossible, but we find statistical evidence for signal pathways in terms of a lower signaling “cost” when we measure this by the number of co-factors needed to transmit a given signal. The fact that the E. coli network has a lower than randomly expected cost of signaling for paths longer than two steps shows that it contains many linear chains which have few incoming branches. That is, the real network is “stringy,” while the randomised network is more “bushy,” having relatively many more branched pathways. Topologically, a low cost is equivalent to less cross talk, which is indeed desirable [3, 19]. This picture of a stringy network of long linear chains applies to the large scale: the place where the real network optimizes specific signaling is between
Signaling and Feedback in Biological Networks
79
strong component modules, rather than within them. A final intriguing point is that at small scales, within modules, the network has widely different design features, as seen from Fig. 4. Some modules (C,F) are dominated by complex formation reactions, and others (D,E) by linear pathways, while the remaining (A,B) are densely interconnected. Obviously, signaling is not only limited by the topology of the network, but also by the type of chemical reactions that facilitate the signals. For example, in pure protein-protein interaction networks, Refs. [20, 21] show that proteins with high concentrations propagate signals to proteins at low concentrations, but not vice versa. Further, when most of a protein is present in an unbound form, rather than in a complex with other proteins, it inhibits propagation of signals through that node of the network. Thus, the overall picture of signaling in biological networks is that one needs careful engineering of both topology and protein binding chemistry in order to facilitate signal propagation over more than one or two reactions.
3 Feedback Figure 5 shows a number of feedback loops. Each node in each loop receives signals (perturbations) from the previous node and sends it on to the next node in the cycle. When the signal travels all the way around the loop, it will Negative feedback loops
a
Hes1
b
d
c p53
Mdm2
IkBα
lactose
β−galacto sidase
LacI
IkBα mRNA
NF−kB
Positive feedback loops
e
f cI
cI
Cro
g
lactose
lactose transporter
LacI
Fig. 5. Examples of positive and negative feedback loops. An ordinary arrow indicates activation, a barred arrow indicates inhibition. (a)–(d) Negative feedback loops found involving proteins important for, respectively, development [29], apoptosis [30], lactose consumption [31, 32] and the immune system [33]. (e)–(g) Positive feedback loops involving proteins important for, respectively, λ phage lysis-lysogeny decision and induction [34], and import of extracellular lactose [31, 32].
80
S. Krishna, M.H. Jensen, and K. Sneppen
act to either dampen (negative feedback) or enhance (positive feedback) the original perturbation. Whether the feedback is positive or negative depends on how the nodes interact. In Fig. 5 we use an ordinary arrow to indicate that a node activates the next node, and a barred arrow if a node inhibits the next node. Then, clearly, all loops with an odd number of repressors are negative feedback loops, while those with an even number of repressors are positive feedback loops. In cellular networks such feedback loops are quite common. Previous studies which searched for small “motifs” in cellular networks found very few feedback loops and an overabundance of feedforward loops [7]. However, these studies looked only at transcription factor networks. As soon as one includes metabolism, then it becomes quickly apparent that feedback loops are by far the most common motif, especially at the interface between the metabolic and regulatory networks of the cell [22]. This interface is quite extensive, as evidenced by the fact that around half of all transcription factors in E. coli have a binding site for small metabolic molecules. The sugar lactose is one such example, being involved in both a negative (Fig. 5c) and a positive feedback loop (Fig. 5g). Figure 5 also shows some other examples of negative and positive feedback loops without small molecules. Positive feedback loops are closely related to the existence of multiple stable states of the system, while negative feedback loops are associated with oscillations. In fact, for a very general class of systems, it has been shown that the existence of at least one negative feedback loop is necessary (but not sufficient) for oscillations, and a similar result holds for positive feedback and multistability [23–25]. References [26–28] study, both theoretically and through the construction of synthetic gene circuits, multistability in positive feedback networks. Ref. [35] further explores the connection between oscillations and negative feedback, showing how the structure of the underlying loop can be extracted from oscillating time series. 3.1 Negative Feedback and Oscillations in Mammalian Immune Response The simplest negative feedback loop is, of course, a protein which represses itself (Fig. 5a). There are many examples of such proteins: the main regulator of the E. coli response to UV damage, LexA, represses its own production [36]; Hes1, involved in development in mammalian cells, also represses transcription of its own gene [29]. A well-known synthetic negative feedback loop is the repressilator, which consists of three proteins each repressing each other [37] (the same structure as Fig. 5c). Here we will concentrate on the negative feedback loop shown in Fig. 5d containing the transcription factor, NF-κB, which is one of the central regulators of the immune system in mammalian cells. The NF-κB family of proteins is one of the most studied, being involved in a variety of cellular processes including immune response, inflammation and development. NF-κB can be activated by a number of external stimuli
Signaling and Feedback in Biological Networks
81
including bacteria, viruses and various stresses and proteins. In response to these signals it controls, directly and indirectly, over 150 genes including many chemokines, immunoreceptors, stress reponse genes and acute phase inflammation response proteins [33]. Nuclear NF-κB is known to activate production of IκBα, an inhibitor protein which inhibits nuclear import of NF-κB by sequestering it in the cytoplasm, thus forming a negative feedback loop. Experimentally, when the NF-κB system is suitably excited, the concentration of NF-κB in the nucleus begins to oscillate [10, 38]. How does the negative feedback loop of NF-κB produce oscillations? Physically, what is required for instability of the fixed point, and hence oscillations, is a time delay, i.e., a sufficient slowing down of the signal going a round the loop. (If a perturbation in the concentration of one variable instantaneously affects the concentration of the next one, and so on, then for a negative feedback loop, any perturbation will be immediately cancelled and the steady state will be stable.) In cellular systems many processes could produce time delays: (i) a process that takes a finite minimum time, (ii) many intermediate steps, (iii) a sharp response by some of the variables, (iv) saturated degradation, or (v) autocatalysis (see Ref. [39] for more details). In the NF-κB system it is, in fact, saturated degradation of IκB that is behind the oscillations. NF-κB forms a complex with its inhibitor protein IκBα. This complex has the curious property that the external stimulus (a protein kinase called IKK) leads to a degradation of IκBα only when it is bound in the complex, and not when it is unbound. As a result, the degradation rate of IκBα has an upper limit, i.e., is saturated, due to the limited amount of NF-κB present and hence the limited amount of complex that can form. Mathematically, it is possible to describe all the essential features of the NF-κB system using a very simple model consisting of only three variables [11], nuclear NF-κB (Nn ), cytoplasmic IκB (I) and IκB mRNA (Im ): dNn (1 − Nn ) INn =A −B , dt +I δ + Nn dIm = Nn2 − Im , dt (1 − Nn )I dI = Im − C . dt +I
(1) (2) (3)
The saturated degradation is the second term in the last equation. Other terms in the equations model processes like nuclear import and export of NF-κB, production of IκB, etc. (see [11] for more details). An obvious question is why the cell requires oscillations in NF-κB in response to inflammation. This is a subject of much debate currently, and there is no clear answer. However, our model of NF-κB provides a possible clue: One property of the oscillations of nuclear NF-κB (in Fig. 6) that stands out is that they are extremely spiky. The spikiness is extremely robust to changes
82
S. Krishna, M.H. Jensen, and K. Sneppen
Fig. 6. (Left) Oscillations of nuclear NF-κB (Nn ) (black curve) and cytoplasmic IκB (grey curve) for simulations of the model with A = 0.007, B = 954.5, C = 0.035, δ = 0.029 and = 2 × 10−5 (these parameter values are derived from the ones used in Ref. [10], see [11]). In order to facilitate comparison with the experimental plot (right, obtained from Ref. [38]), the x-axis has been limited to 600 minutes, but the oscillations are sustained.
Fig. 7. Sensitivity to IKK. (Left) Spike duration, the fraction of time Nn spends above its mean value, as a function of IKK concentration. (Right) Spike peak, the maximum concentration of nuclear NF-κB, as a function of IKK concentration. In both plots, the black dot shows the IKK value used in Fig. 6, which separates regions of spiky and soft oscillations [11].
in parameter values. In general, the existence and spikiness of the oscillations is very robust to changes in most of the parameters of the model [11]. However, the system shows a very sensitive response to change in one parameter: the external stimulus, IKK. Figure 7 shows that both the spike height (or peak level), as well as the spike duration, can change by large amounts in response to small changes in the IKK level. Notice that this sensitivity is particularly high in IKK ranges which are near the transition from spiky to soft oscillations. It can be shown that this sensitivity can be transmitted to genes that are affected by NF-κB, producing a gene response sensitivity
Signaling and Feedback in Biological Networks
83
that is much larger than that obtained by other typical mechanisms which do not involve oscillations [40, 41]. Thus, oscillations could be a by-product of designing the system to have a very high sensitivity to small changes in the external stimulus. 3.2 Positive Feedback and Bistability in Yeast Epigenetics Cells carry information handed down from their ancestors and are able to pass on information to their descendants. In many cases this “memory” is epigenetic—not stored in the DNA sequence—allowing cells with identical DNA to maintain distinct properties. Epigenetic cell memory implies alternative states that are stable over time and are inherited through cell division. One proposed mechanism for epigenetic cell memory invokes positive feedback loops in nucleosome modification [42]. Nucleosomes are protein complexes that package eukaryotic DNA, with a density of about one nucleosome per 200 base pairs (bp). The core nucleosome is composed of two molecules each of four core histone proteins. Nucleosomes may carry various chemical modifications (e.g. acetylation and methylation) at different amino acid positions on the different histones, conferring a large potential information capacity on each nucleosome. Specific additions and removals of these nucleosome modifications are carried out by classes of enzymes, including histone acetyltransferases (HATs), histone methylases (HMTs), histone deacetylases (HDACs) and histone demethylases (HDMs). At least some of these modifications affect the activity of nearby genes, in part because the modifications can alter the binding of regulatory proteins to the DNA. Positive feedbacks are present in this system because nucleosomes that carry a particular modification may recruit (directly or indirectly) the enzymes that catalyse similar modification of neighbouring nucleosomes. Thus, a cluster of nucleosomes may be able to maintain itself stably in a particular modification state. These states can be inherited through DNA replication because nucleosomes on the parental DNA strand are distributed to both daughter strands [43], and the enzymes recruited by these parental nucleosomes may then establish the parental modification pattern on the newly deposited nucleosomes. A specific case in which positive feedbacks in nucleosome modification result in multiple stable states occurs in the mating-type system of the eukaryote S. pombe (fission yeast) [44]. A ∼20 kbp region of S. pombe DNA containing two mating-type cassettes is normally in a stable “silenced” state, with the mating-type genes not expressed. In certain mutants where part of the silenced region is modified, the system is bistable, flipping between states where the ura4 gene is either expressed (active) or not (silenced). Each state is stable and heritable, with transitions occurring at roughly equal frequencies of ≈ 5 × 10−4 per cell division [44]. Switching appears to be stochastic and is determined by factors associated with the region itself. In the silenced state, but not the active state, the region is dominated by nucleosomes that are
84
S. Krishna, M.H. Jensen, and K. Sneppen
Fig. 8. Illustration of basic ingredients of the model: Each oval represents a nucleosome that can be methylated (M), unmodified (U) or acetylated (A). Enzymatic transitions (solid arrows) between the three states are in part random (controlled by a noise level 1 − α), and in part autoregulated by recruitment (dotted lines) of enzymes (open symbols) by nucleosomes in the M or A state [45].
methylated at a particular site. An HMT that can catalyse this modification and certain HDAC proteins are known to be important for silencing. One can construct a simple network model [45] (schematically shown in Fig. 8) of the nucleosome modification system that exhibits all this behaviour, based on three simplifying assumptions. (1) There are only three relevant kinds of nucleosomes: unmodified, methylated and acetylated; methylation and acetylation are mutually exclusive. (2) The nucleosomes are enzymatically interconverted as shown in Fig. 8, by HMT, HDAC, HDM and HAT enzyme(s). (3) The HDAC and HMT enzyme(s) are recruited by methylated nucleosomes; the HDM and HAT enzymes are recruited by acetylated nucleosomes. This is what makes the feedback positive. To model S. pombe we take a system consisting of a fixed number of N = 60 nucleosomes, arranged on a 1-dimensional (1D) string. The region is isolated from neighbouring DNA by boundary elements [46], which we assume to be inert. Each nucleosome may be methylated (M), unmodified (U) or acetylated (A). At each time step one selects a random nucleosome n1 and attempts one of two changes: (a) With probability α one attempts a change associated to enzymatic activity of an enzyme recruited by another nucleosome in the modeled region. That is, one selects another random nucleosome n2 and if this is in either an
Signaling and Feedback in Biological Networks
85
M or A state, the nucleosome n1 is changed one step toward this state. For example, when nucleosome n2 is an M: if n1 is an A, then it is changed to U and if n1 is a U it is changed to M. If nucleosome n1 and n2 are in the same state, or if n2 is a U, then no changes are made. (b) With probability 1 − α one attempts a change of the selected nucleosome n1 : A U is changed to an M with probability 13 , or an A with probability 1 1 3 whereas an A or an M is changed to U with probability 3 . One may view process (a) as occurring due to the action of enzymes recruited by nucleosomes in the region within the isolating boundaries, whereas (b) reflects extrinsic noise caused by unrecruited enzymes. Thus, a lower α value indicates a higher noise level. In Fig. 9 we illustrate the dynamics of the model. One observes a fluctuating number of the three kinds of nucleosomes. In the upper panel α is small (noise is high) and the system has only one stable state, in which the nucleosome modifications are distributed randomly along the chain. In the lower panel, with a higher α, the system exists either in a state dominated by methylated nucleosomes or a state dominated by acetylated nucleosomes, with occasional switches between the two states. As α is increased further (i.e., noise is reduced) the states become more stable, and the switching occurs less often. However, the fact that the epigenetic states in the mutant S. pombe have a finite stability demonstrates that noise in the form of disordered methylation-acetylation events plays a crucial role.
Fig. 9. Time development of the standard model [45] for a system consisting of N = 60 nucleosomes with respectively α = 0.40 (upper figure) and α = 0.64 (lower figure). The light grey curve shows the number of methylated, dark grey the number of acetylated and black the number of unmodified nucleosomes. Time t is measured in number of attempted nucleosome updates per nucleosome.
86
S. Krishna, M.H. Jensen, and K. Sneppen
This simplified model of epigenetic inheritance in eukaryotes provides some unexpected insights. First, it is very important that nucleosomes are modified by enzymes recruited by non-neighbouring nucleosomes. A “1D” variant of the model where nucleosomes can recruit enzymes to modify only one of their neighbours along the string does not produce bistability [45]. The difficulty of obtaining a clear two-state behavior in 1D arises for reasons similar to those preventing spontaneous magnetization in the 1D Ising model, or the helix-coil transition in polymer models [47, 48]. Second, it is also very important that the transition from, say, an M state to an A state requires two consecutive acetylation recruitments by nucleosomes in the A state, and therefore effectively has a rate ∝ A2 . Bistability is lost in variants where this two-step process is replaced by a single step [45]. The non-linearity produced by this kind of “cooperative” two-step modification appears to be essential for bistability. Most importantly, however, at low α, where the modification-demodification events are completely random (and hence there is no feedback), there is only one state where the nucleosome modifications are distributed completely randomly along the string. Thus, we can conclude that positive feedback is essential for bistability.
4 Combining Multiple Feedback Loops In the previous sections we investigated the basic properties of single negative and positive feedback loops. In cellular networks, however, there are multiple entangled feedback loops. This can already be seen in Fig. 5, where some of the proteins are present in more than one example (LacI in Fig. 5c and g; cI in Fig. 5e and f). In an effort to understand how feedback loops interact and the range of dynamical behaviour possible, we begin by examining two interacting feedback loops. Such two-loop network motifs are seen in a large class of cellular response systems designed to regulate the flux and concentration of small molecules. These systems control, via two feedback loops, the transport and metabolism pathways. Typically, these two loops are connected by a common transcriptional regulator that senses the concentration of the small molecule. For instance, in the arabinose utilization system in E. coli, when intracellular arabinose binds to the regulator AraC it alters its binding to DNA such that RNA polymerase and the protein CRP can bind and initiate expression of genes that increase import of extracellular arabinose as well as its metabolic consumption [49]. This is schematically shown in Fig. 10. Here, the transport is controlled by a positive feedback loop, while the metabolism is a negative feedback loop. This is, of course, not the only logical combination of feedback loops possible. Figure 11 (left column) shows four logically distinct combinations of entangled transport and metabolism feedback loops. In each case, the two feedback loops are connected by a transcriptional regulator (R) that senses the concentration of a particular small molecule (s). One loop regulates transcription of
Signaling and Feedback in Biological Networks
87
Fig. 10. Schematic illustration of molecular processes in a two-loop motif. This motif is found in the regulation of uptake and metabolism of, for example, maltose and arabinose [50, 49]. σ, s denote, respectively, extracellular and intracellular concentrations of the small molecule. The molecule binds to the regulator, R, forming the complex {Rs} which activates production of transport proteins, T , and metabolic enzymes, E. γ is a parameter controlling the metabolic rate per enzyme [13].
the transport proteins (T ) facilitating the influx of the small molecule, while the other controls transcription of enzymes (E) responsible for the metabolism of s. The signs show the logic of each feedback loop: positive (+) or negative (-). Each motif can then be described by a notation of two signs, e.g. (+ –), which means that the transport loop is positive and the metabolism loop negative. Thus, there are four logical structures: the socialist (– –), the consumer (+ –), the fashion (– +) and the collector (+ +) [13]. Each can, in turn, be implemented in two distinct but logically equivalent ways, depending on whether s inhibits or activates R. This we denote using the notation (+ – i) or (+ – a), where the i (respectively, a) indicates inhibition (activation) of R by s. Th i- and a-motifs with the same logic behave very similarly, so here we will concentrate on only the a-motifs. The socialist motif. We call the (– –) motif the socialist because at low levels of extracellular s (low σ) it increases transport and reduces the metabolism, while at high levels of extracellular s, it does the opposite. Thus, the two negative feedback loops help maintain s robustly within a small concentration range. Such behaviour would be ideal for a system responsible for maintaining homeostasis. And indeed, a regulatory system with this logic is found in the iron homeostasis system in mammals [51]: iron activates the ferric uptake regulator (Fur), which represses transcription initiation of iron uptake genes, and enhances production of iron-using proteins. For most organisms iron is essential for several proteins, but is poisonous at high concentrations. There,
88
S. Krishna, M.H. Jensen, and K. Sneppen
Fig. 11. Behaviour of four entangled feedback loop motifs. Plots show the steady state values of s (middle column) and influx (σT = γEs + s, right column) as a function of σ. In all plots, the black curve shows the behaviour for the two-loop motif. The two other curves show the behaviour when only the transport loop is active (E = 1) and when only the metabolism loop is active (T = 1) [13].
the (– –) motif maintains the loosely bound iron within a narrow concentration range, and at the same time allows a high consumption of iron molecules by certain proteins that bind iron strongly. The consumer motif. The (+ –) motif we term the consumer, because any amount of extracellular small molecule results in the increase of both transport and metabolism. Thus, it is ideal for food molecules. This logic is in fact typical for sugar transport and metabolism in prokaryotes. The gal [52] and lac [31, 32] operons in E. coli are the most well studied of such systems. They both use the sugar molecule to inhibit the transriciption factor
Signaling and Feedback in Biological Networks
89
regulating transport and metabolism, the (+ – i) motif. In contrast, maltose [50] and arabinose [49] work by activating the regulation of transport and metabolism, the (+ – a) motif. In natural systems, transport and metabolic genes can be part of a single operon, as in lac [31], or separate operons, as in gal [52]. The latter arrangement allows non-coordinated regulation of transport and metabolism and therefore can be engineered to become bistable. This was also demonstrated by experiments on modified lactose and arabinose systems [53, 54], where the accompanying negative feedback loop was eliminated by inactivating E or using a non-metabolisable analogue of s, in agreement with our predictions from a similar cutting of the metabolic loop in Fig. 11. The fashion motif. As the fashion motif (– +) is indeed the opposite of the consumer motif, both logically and functionally, it is not surprising that we have not found any simple example of it in the regulation of small molecules in living cells. However, its behaviour (and the reason we call it the fashion motif) can be illustrated in terms of a market model for a product which is desirable in small amounts. In such a scenario, the resource, s, is analogous to a fashion product, E to the consumers, and T to the producers. R can be considered the value of the product, measured in terms of how much people desire it. When there is plenty of the product s in the market, its value R decreases, which in turn decreases its consumption (a positive metabolism feedback loop) as well as the desire amongst producers to make more of it (a negative transport feedback loop), making it a (– +) motif. The non-monotonicity of the flux of the fashion motif translates in this analogy to a saturation of the market when a fashion product becomes too abundant: Fashion products are most profitable when their availability is below a certain threshold. When the fashion motif is supplemented with a positive feedback of R to itself, the collapse of fashion goods can occur with a remarkably small change in external supply, which is reminiscent of fashion “bubbles” in society [55]. Although the fashion motif does not make much rational sense for small molecule response systems, it may be seen as a mechanism for coherent behaviour in social organization. The collector motif. The collector motif (+ +) is the logical opposite of the (– –) motif. Functionally it allows accumulation of a large amount of s, and is thus also functionally opposite to the socialist motif. Accumulation could be important for short periods of time, for instance, when an animal is preparing for hibernation. However, in such cases the (+ +) motif should eventually be overridden by another system which starts the consumption of the molecule. Such double positive feedback loops may be found in transcription regulatory networks and circuits involved in development and cell differentiation, but we failed to find any examples of them in small molecule regulation. Turning to a human analogy, the collector motif can be illustrated by making an analogy between s and the weight of a person. Then this weight increases with the intake of food (the analogue of transport), and is consumed by exercise (the analogue of metabolism). In this analogy R represents the internal “state” of the person, his or her mindset. An increase in a person’s weight, s, increases, via this internal state, their likelihood to eat more (positive transport feedback
90
S. Krishna, M.H. Jensen, and K. Sneppen
loop) and also decreases their chance to exercise (positive metabolism feedback loop), thus forming a collector motif. The bistable behaviour of the collector motif would then contribute to a broadening of the weight distribution in human populations [60]. 4.1 Two-Loop Motifs are More Than the Sum of Their Single Loops Figure 11 also shows the behaviour of individual loops in these motifs, obtained by keeping either E or T fixed, thereby cutting feedback in one of the loops. The near constant value of s in (– –) comes from the metabolic loop’s ability to constrain s for low σ, and the transport loop’s ability to constrain s at high σ. Thus, the functionality of (– –) is dominated by the sub-motif that best prevents large variation of s and flux. The (+ –) obtains a steady increase in s and a step-like increase in flux with σ by using the negative metabolic loop’s ability to “smooth out” the bistability associated to the positive transport loop. The (– +) motif exhibits a remarkable non-monotonic behaviour of flux, which cannot be obtained from any of the sub-motifs. The (+ +) motif maximizes bistability, by extending it to the extreme of the two bistable regions of its sub-motifs. Overall, we can conclude that whole two-loop motifs are more than a simple sum of their parts. 4.2 Going Beyond Two Loops Our analysis of two entangled feedback loops creates a framework for analysing small molecule regulatory circuits composed of multiple entangled feedback loops. For instance, the regulation of iron in E. coli, while being dominated by interactions that form a socialist motif [56, 57], also contains a positive feedback on the metabolism side involving usage of iron in FeS clusters [58]. An investigation of this three-loop motif suggests that two metabolism loops, connected like this in “parallel” (as opposed to the “series” connection between a transport and metabolism loop), are additive in behaviour [13, 59]. Due to this additiveness, iron regulation in E. coli is able to minimise variation of both the concentration of iron (a property of the socialist part) as well as the flux (a property of the fashion part) [56]. This indicates that an interesting direction to extend these ideas might be to try to formulate “design principles” for combinations of parallel and serially connected feedback loops.
5 Concluding Remarks To extract a useful network representation to describe a particular cellular system, it is necessary to ascertain the sensible level of coarse-graining for that system — is it the whole-cell network, individual proteins/genes or something
Signaling and Feedback in Biological Networks
91
in between? There is, of course, no one answer to this question. In the examples above we have looked at a wide range of scales, from the entire E. coli network, to three or four component sub-networks, down to nucleosomes on DNA. On all these scales the dynamical behaviour is, however, constrained first by the available communication channels, and second by the logical properties of feedback loops in the network. To summarise, we extract the following main “lessons” from our case studies: • • • • •
The E. coli protein network is highly modular. The real E. coli network is more “stringy” than the randomised version, and this reduces constraints on signal propagation. Most feedback loops go through small molecules; there are very few in the transcription network. Biological function is coupled to the logic (positive/negative) of the feedback. Entangled feedback loops are “more” than a simple sum of their parts.
Acknowledgments We thank our collaborators, with whom much of the work described here was done: J. Axelsen, I. Dodd, M. Micheelsen, S. Pigolotti, S. Semsey, G. Thon and G. Tiana. We acknowledge support from The Danish National Research Foundation and the Villum Kann Rasmussen Foundation.
References 1. S. Bornholdt and H.G Schuster, eds., Handbook of Graphs and Networks: From the Genome to the Internet, Wiley-VCH, Weinheim (2002). 2. E. Ravasz, A.L. Somera, D.A. Mongru, Z.N. Oltvai and A.-L. Barabasi, Science, 297, 1551–1555 (2002). 3. S. Maslov and K. Sneppen, Science, 296, 910–913 (2002). 4. K. Sneppen, A. Trusina and M. Rosvall, Europhys. Lett., 69, 853 (2005). 5. A. Trusina, S. Maslov, P. Minnhagen and K. Sneppen, Phys. Rev. Lett., 92, 178702 (2004). 6. J. B. Axelsen, S. Bernhardsson and K. Sneppen, BMC Systems Biology, 2, 25 (2008). 7. S.S. Shen-Orr, R. Milo, S. Mangan and U. Alon, Nat. Genetics, 31, 64–68 (2002). 8. A. Samal, S. Singh, V. Giri, S. Krishna, N. Raghuram and S. Jain, BMC Bioinformatics, 7, 118 (2006). 9. S. Singh, A. Samal, V. Giri, S. Krishna, N. Raghuram and S. Jain, Eur. Phys. J. B, 57, 75–80 (2007). 10. A. Hoffmann, A. Levchenko, M.L. Scott and D. Baltimore, Science, 298, 1241– 1245 (2002). 11. S. Krishna, M.H. Jensen and K. Sneppen, Proc. Natl. Acad. Sci. USA, 103, 10840– 10845 (2006).
92
S. Krishna, M.H. Jensen, and K. Sneppen
12. E. Aurell, S. Brown, J. Johansen and K. Sneppen, Phys. Rev. E, 65, 51914 (2002). 13. S. Krishna, S. Semsey and K. Sneppen, Proc. Natl. Acad. Sci. USA, 104, 20815– 20819 (2007). 14. K.B. Arnvig, S. Pedersen and K. Sneppen, Phys. Rev. Lett., 84, 3005 (2000). 15. G. Tiana, M.H. Jensen and K. Sneppen, Eur. Phys. J. B 29, 135 (2002). 16. M.H. Jensen, G. Tiana and K. Sneppen, Febs Letters 541, 176 (2003). 17. P.D. Karp et al., Nucl. Acids Res., 35, 7577–7590 (2007). 18. J.B. Axelsen, S. Krishna and K. Sneppen, J. Stat. Mech., P01018 (2008). 19. L.H. Hartwell, J.J. Hopfield, S. Leibler and A.W. Murray, Nature, 402(6761), C47–52 (1999). 20. S. Maslov, K. Sneppen and I. Ispolatov, New J. Phys., 9, 273 (2007). 21. S. Maslov and I. Ispolatov, Proc. Natl. Acad. Sci. USA, 104, 13655–13660 (2007). 22. S. Krishna, A.M.C. Andersson, S. Semsey and Kim Sneppen, Nucl. Acids Res., 34, 2455 (2006). 23. R. Thomas, Quantum noise, Springer Series in Synergetics 9, Ed. Gardiner, Springer, Berlin, pp. 180–193 (1981). 24. E.H. Snoussi, J, Biol. Sys., 6, 3–9 (1998). 25. J.L. Gouz´e, J. Biol. Syst., 6, 11–15 (1998). 26. J.E. Ferrell Jr., Curr. Opin. Cell Biol., 14, 140–148 (2002). 27. D. Angeli, J.E. Ferrell and E.D- Sontag, Proc. Natl. Acad. Sci. USA, 101, 1822– 1827 (2004). 28. F.J. Isaacs, J. Hasty, C.R. Cantor and J.J. Collins, Proc. Natl. Acad. Sci. USA, 100, 7714–7719 (2003). 29. H. Hirata, S. Yoshiura, T. Ohtsuka, Y. Bessho, T. Harada, K. Yoshikawa and R. Kageyama, Science, 298, 840–843 (2002). 30. S.L. Harris and A.J. Levine, Oncogene, 24, 2899–2908 (2005). 31. F. Jacob and J. Monod, J. Mol. Biol., 3, 318–356 (1961). 32. P. Wong, S. Gladney and J.D. Keasling, Biotechnol. Prog., 13, 132–143 (1997). 33. H.L. Pahl, Oncogene, 18, 6853–6866 (1999). 34. M. Ptashne, A Genetic Switch: Phage Lambda Revisited, Cold Spring Harbor Laboratory Press Cold Spring Harbor(2004). 35. S. Pigolotti, S. Krishna and M.H. Jensen, Proc. Natl. Acad. Sci. USA, 104, 6533– 6537 (2007). 36. M. Schnarr et al., Biochimie, 73, 423–431 (1991). 37. M.B. Elowitz and S. Leibler, Nature, 403, 335–338 (2000). 38. D.E. Nelson, A.E.C. Ihekwaba, M. Elliott, J.R. Johnson, C.A. Gibney, B.E. Foreman, G. Nelson, V. See, C.A. Horton, D.G. Spiller et al., Science, 306, 704–708 (2004). 39. G. Tiana, S. Krishna, S. Pigolotti, M. H. Jensen and K. Sneppen, Phys. Biol., 4, R1 (2007). 40. C.Y. Huang and J.E. Ferrel Jr, Proc. Natl. Acad. Sci. USA, 93, 10078–10083 (1996). 41. A. Goldbeter and D.E. Koshland, Proc. Natl. Acad. Sci. USA, 78, 6840–6844 (1981). 42. G. Felsenfeld and M. Groudine, Nature, 421, 448 (2003). 43. A.T. Annunziato, J. Biol. Chem., 280, 12065 (2005). 44. G. Thon and T. Friis, Genetics, 145, 685 (1997). 45. I.B. Dodd, M.A. Micheelsen, K. Sneppen and G. Thon, Cell, 129, 813–822 (2007). 46. G. Thon, P. Bjerling, C.M. Brunner and J. Verhein-Hansen, Genetics, 161, 611 (2002).
Signaling and Feedback in Biological Networks 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60.
93
B.H. Zimm, Proc. Natl. Acad. Sci. USA, 45, 1601 (1959). H.A. Scherage, Pure and Applied Chemistry, 36 1 (1972). R. Schleif, Trends Genet., 16, 559–565 (2000). E. Richet and O. Raibaud, EMBO J., 8, 981–987 (1989). E. Mass´e and M. Arguin, Trends Biochem. Sci., 30, 462–468 (2005). M.J. Weickert and S. Adhya, Mol. Microbiol., 10, 245–251 (1993). E.M. Ozbudak, M. Thattai, H.N. Lim, B.I. Shraiman and A. van Oudenaarden, Nature, 427, 737–740 (2004). W.P. Smits, O.P. Kuipers and J.W. Veening, Nat. Rev. Microbiol., 4, 259–271 (2006). R. Donangelo and K. Sneppen, Physica A, 316, 581–591 (2002). S. Semsey, A.M.C. Andersson, S. Krishna, M.H. Jensen, E. Mass´e and K. Sneppen, Nucl. Acids Res., 34, 4960–4967 (2006). N. Mitarai, A.M.C. Andersson, S. Krishna, S. Semsey and K. Sneppen, Phys. Biol., 4, 164–171 (2007). F.W. Outten, O. Djaman and G. Storz, Mol. Microbiol., 52, 861–872 (2004). M. Werner, S. Semsey, K. Sneppen and S. Krishna, preprint (2008). U.S. EPA Exposure Factors Handbook, 1997, http://www.epa.gov/ncea/efh/
Topographic Spreading Analysis of an Empirical Sex Workers’ Network Johannes Bjelland,1 Geoffrey Canright,1 Kenth Engø-Monsen,1 and Valencia P. Remple2 1
2
Telenor R&I, 1331 Fornebu, Norway
[email protected],
[email protected], kenth.engø
[email protected] BC Centre for Disease Control Epidemiology, University of British Columbia, Vancouver, BC, Canada;
[email protected]
1 Introduction The problem of epidemic spreading over networks has received considerable attention in recent years, due both to its intrinsic intellectual challenge and to its practical importance. A good recent summary of such work may be found in Newman [8], while [9] gives an outstanding example of a non-trivial prediction which is obtained from explicitly modeling the network in the epidemic spreading. In the language of mathematicians and computer scientists, a network of nodes connected by edges is called a graph. Most work on epidemic spreading over networks focuses on whole-graph properties, such as the percentage of infected nodes at long time. Two of us have, in contrast, focused on understanding the spread of an infection over time and space (the network) [1, 3, 2]. This work involves decomposing any given network into subgraphs called regions [1]. Regions are precisely defined as disjoint subgraphs which may be viewed as coarse-grained units of infection—in that, once one node in a region is infected, the progress of the infection over the remainder of the region is relatively fast and predictable [3]. We note that this approach is based on the ‘Susceptible-Infected’ (SI) model of infection, in which nodes, once infected, are never cured. This model is reasonable for some infections, such as HIV—which is one of the diseases studied here. We also study gonorrhea and chlamydia, for which a more appropriate model is Susceptible-InfectedSusceptible (SIS) [7] (since nodes can be cured); we discuss the limitations of our approach for these cases below. In this paper we apply the “topographic” regions-analysis approach to an empirical sex network, built from interviews with female sex workers (FSWs) in Vancouver, Canada. (See [3] for a detailed discussion of the “topographic” N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 6, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
98
J. Bjelland et al.
approach.) The network consists of the FSWs themselves, plus their sex partners (paid and unpaid), as well as any partners of these partners which were known to the FSW. This method, beginning with 49 interviewed FSWs, gave a highly connected network of 553 nodes [10]. Furthermore, STI (sexually transmitted infection) status was obtained for many of these nodes. In particular, two of the nodes were identified as being HIV-positive, while 11 other nodes have either gonorrhea, chlamydia, or both. From the collected network data we build an adjacency matrix, where element aij = 1 if i has a link to j, and is zero elsewhere. (In the case of a weighted graph, element aij equals the strength of the link from node i to node j.) The principal eigenvector of the adjacency matrix is a measure of a node’s centrality in the graph and is called the eigenvector centrality or EVC. The EVC scores for the nodes in the (weighted or unweighted) network give the starting point for our approach: they are used for assigning the nodes to regions, and for predicting the spreading of disease within and between regions. The aims of this work are several. One goal is to extend our earlier topographic approach to a graph with weighted links. As we will see, this seemingly small change can have very large effects; but we will also see that the validity of our approach is confirmed, in spite of these large effects. This is because the modified approach (presented here for the first time) is consistent: we use the link weights to modify the graph’s adjacency matrix, and hence the nodes’ EVC values; and we use them again when we define the regions via the steepest-ascent graph (SAG). A second aim of this work is to try to exploit the insights gained from the topographic analysis, in order to find novel suggestions for preventive actions to hinder the spread of the disease in question. We find that our progress towards this second goal is considerably more modest than that towards the first goal. We will show “thought experiments,” based on the empirical graph topology and link strengths, for which our analysis is extremely useful. However, we will not find practical suggestions which are immediately promising for the given Vancouver FSW graph. There are several reasons for this. First, the HIV graph is so thoroughly protected by condom use that we find little to add in terms of ideas for preventive measures. Second, the graphs for gonorrhea and for chlamydia are so thoroughly well connected, and also so well infected, that we do not find small topological changes which can make a large difference. We note that our approach treats the network as static; hence any effects of network dynamics are not taken into account. We believe, however, that our qualitative results are fairly robust to the likely dynamics of this network, since its overall structure is thought to be fairly stable over time. Also, our analysis (once the network is mapped out—which can be time consuming!) is not computationally demanding, and so may be performed in essentially zero time compared to the time scale of epidemic spreading. Hence any suggestions resulting from the analysis may be implemented in something approaching real time.
Topographic Spreading Analysis
99
2 Uniform Transmission Model First we study the FSW graph without taking into account the link weights. That is, each sexual contact is given strength “1” in the adjacency matrix. This is logically equivalent to giving each link the same probability of transmission per unit time. Our purpose in doing this analysis is to be able to compare with the analysis done using non-uniform link strengths (transmission probabilities). As we will see, the differences are large and important. 2.1 Visualization and Bipartiteness Our topographic analysis includes a novel approach to graph visualization: we group the nodes into their respective regions, and lay out the whole graph according to the SAG [4]. We present the basic ideas here, and refer the reader to earlier papers [1, 3, 4] for details. We view the EVC of a node as a measure of its “well-connectedness” and hence of its “spreading power.” Then we single out local maxima of the EVC as being particularly important in spreading; we call these nodes Centers. Also, since EVC (being recursively defined) is “smooth,” we can speak of “neighborhoods” in the graph as having a typical EVC; and we conclude that spreading is fast in neighborhoods of high EVC, and slow in “lower” neighborhoods. We then define regions of the graph— one for each Center. Each node finds its region (mountain) by following a steepest-ascent path until it terminates at a local maximum (mountaintop, or Center). The set of steepest-ascent paths then forms a directed hierarchical tree graph (the SAG), which is useful both for visualizing the graph and for predicting the likely paths of fastest epidemic spreading. In a tree graph, any two nodes are connected by exactly one path, and there are no cycles (closed loops of links). The SAG for the unweighted FSW graph is shown in Fig. 1. We note several interesting points from this visualization. (i) there are many regions (17). (ii) All the Centers (most central nodes in each region) are men. (iii) Many regions are small, i.e., 1–3 nodes, while (iv) the bulk of the nodes (517/553) lie in one of the three largest regions (red—marked R in the figure, blue (B), dark grey (G)). (v) Every region is well connected to the largest, red, region. Hence the red region is expected to play a dominant role in any epidemic spreading. (vi) One HIV-positive node is in the red region, and the other is (while in its own region) well connected to the central part of the red region. Now we comment on these points. We believe that points (i)–(iii) derive from the fact that the graph is nearly bipartite. A bipartite graph consists of two sets of nodes, such that all links are made between the two sets, and there are no links between nodes in the same set. Now we suppose (which is almost true) that the FSW graph is a strictly bipartite graph composed of M and F nodes. If we further assume that an M node is a Center (local maximum of centrality), then all of its neighbors are (a) female, (b) highly central,
100
J. Bjelland et al.
Fig. 1. Regions visualization of the FSW network, with all links set to equal strength. Only the links in the SAG are shown here for visual clarity. The most central node in each region is enlarged. The three largest regions, which will be discussed further in the text, are labeled R (red), G (grey), and B (blue). - Male, - Female.
and (c) automatically excluded from being a Center. Thus bipartiteness will tend to favor one gender over another. By the same token, highly central M nodes are never neighbors of other M Centers, and so are candidate Centers themselves. Hence there may be a tendency for more, and smaller, regions. Points (iv)–(vi) tell us that this network is highly prone to infection: the many regions are not well isolated from one another, because of their common connection to the dense, infectious red region. Also, the two start nodes are in or near the central part of the red region, where spreading is fast. 2.2 Infectious Spreading on the Unweighted Graph We have simulated spreading on the uniform FSW network, by giving each link the same probability per unit time for spreading. The value used is thus arbitrary, as is the unit of time. We typically use a value of a few percent, since much larger values give a very unsmooth time evolution (equivalent to a poor time resolution). We report the results here because they are illustrative of the strengths and weaknesses of our method, for the case of multiple regions. (For reasons given below, these are the only multi-region simulations that we can perform with this graph.)
Topographic Spreading Analysis
101
Fig. 2. Same visualization as Fig. 1, except that all links are shown. The arrows mark the known HIV-positive nodes.
Taking the start (infected at t = 0) nodes as shown in Fig. 2 above, we find, as expected, that the regions as we define them here are again valid coarse units of infection. We also find that it is difficult to stop or even retard the infection, because of the topology of the graph. The upper part of Fig. 3 shows a typical epidemic progression, with the growth in the red, blue, and grey regions resolved. All three “take off” at about the same time, and the infection spreads rapidly. Measures to retard spreading in the red region— without resorting to large topological change—are not found to be effective. We find however that protecting one node—the Center of the grey region— drastically weakens the red/grey connection. We see in the bottom part of Fig. 3 the results when this is done: the red and blue regions take off as before, but the grey region’s takeoff is greatly retarded. This is an example of the kind of benefit that we believe can be obtained from our analysis. We also considered the more promising problem of an infection starting in the grey region—again motivated by the observed red ⇐⇒ grey bottleneck in the topology. The top of Fig. 4 shows that takeoff is retarded by a factor of about 3, compared to the former case (top of Fig. 3). It is retarded even further (about 7 times as slow) if we in addition protect the grey Center (bottom of Fig. 4).
102
J. Bjelland et al.
Fig. 3. HIV spreading simulation without (top) and with (bottom) measures to isolate the grey region from the red region. In each plot, there are four growth curves, showing the total growth of the infection (‘Sum’), and the growth for the red (R), grey (G), and blue (B) regions (the largest regions in the network).
Fig. 4. Same simulation as Fig. 3, except that the infection starts from a peripheral node in the grey region.
Topographic Spreading Analysis
103
3 Links Weighted with Transmission Probabilities In this section we add an important further element of realism by weighting the links of our FSW graph with transmission probabilities. We are forced in many cases to use rather crude approximations. Nevertheless, we feel that the resulting model is considerably closer to reality than the uniform model. Also (as we will see) it is strikingly different—in particular, each disease will have its own graph. That is, while the basic topology is the same as that in Fig. 2, the set of link weights depends on the disease—because these weights represent transmission rates (probability/time). In fact, for the HIV case, the topology itself is changed, since we set some link strengths to exactly zero. In practice, incorporating the link strengths into the analysis involves (1) building a weighted adjacency matrix W using the link strengths, (2) finding the corrected EVC as the dominant eigenvector of this matrix W , and (3) redefining “steepest ascent” to take account of the varying link strengths. The first two steps are clear; and we describe step (3) in Section 3.2. Of course, before doing any of this, we must find the link strengths. We describe our procedure for doing so in the next section. 3.1 Estimating the Probabilities For each link we want a single weight (number) which gives the probability per unit time of transmission from an infected node to an uninfected node. This probability is based on a number of factors which must be estimated from limited data. We list these factors schematically as follows: Transmission probability/unit time = [(unprotected probability/contact)(non-condom use prevalence) × (contacts/time)] + [(protected probability/contact)(condom use prevalence) ×(contacts/time)] Now we discuss each factor in turn. For each disease (HIV, gonorrhea or ‘NG’, and chlamydia or ‘CT’) we estimate (unprotected probability/contact) from Ref. [6]. See Table 1. To correct for condom use, we must know the frequency of condom use for each link (condom use prevalence). For 256 links (about 17% of them) we have an estimate for (condom use prevalence) from survey data [10]. We know very little about the remaining links, except for Table 1. Transmission probabilities/contact for NG (gonorrhea), CT (chlamydia), and HIV.
Unprotected Protected
NG 0.43 0.16
CT HIV 0.10 0.05 0.074 0
104
J. Bjelland et al.
whether they are a “client” relationship or a “non-client” relationship. We explain below how we generate link weights for the links for which we have no survey data. Estimates for (contacts/time) were available (again) for those links for which we obtained survey information; however, here we have yet another source of uncertainty. That is, each interviewed FSW reported contacts with “regulars” and also contacts with new or “non-regular” customers. We take the reported estimates of (contacts/time) for regulars as given. For the nonregulars, we assume that either (i) they will become regular in the future, or (ii) they will be replaced by other non-regular customers who play essentially the same role in the network. In short: we ignore the distinction beween cases (i) and (ii). We still need a reasonable estimate of contacts/time for non-regulars. We proceed as follows: for each FSW, we define T to be the total number of contacts per unit time (summed over all neighbors). Also we let P be the percentage of contacts from regulars, and let C be the number of contacts/time from regulars. Then clearly C = P T ; and since we can estimate both P and C from the survey data, we get an estimate of T (= C/P ). We then estimate the total contacts/time N for non-regulars to be N = T − C. Finally, we take, from the survey data, the expected number of non-regular neighbors (still for each FSW), and call this number K. We then (finally) get the expected contacts/time for each non-regular as N/K. Our model is clearly very crude, treating each non-regular in a very average way; but it enables us to move (as we will see) well beyond the equal-transmission-probability model, and so, we believe, much closer to reality. Now we come to the term due to protected sex. We estimate (protected probability/contact) by correcting the (unprotected probability/contact) data, using data for the correction due to condom use from [5]. We note here that we set (protected probability/contact) for HIV to be exactly zero. Not surprisingly, this will have dramatic effects on the spreading behavior—as we will see in Section 3.3. This completes our prescription for estimating link weights for those links for which we have survey data. We then used a very simple approach—which we find appropriate to the high degree of uncertainty in our data—to estimate the remaining link weights (transmission probabilities/time). Our solution here is to first divide all links (surveyed and not surveyed) into two groups: client and non-client. Then, for each group, we simply reproduced the distribution over the “surveyed” links so as to also assign transmission probabilities to all of the “non-surveyed” links. Since the survey data is discrete, the link-weight distribution obtained is never smooth. Hence we reproduced these discrete distributions by simply repeating (sampling) each value in the discrete distribution with a probability equal to its frequency in the distribution. That is: we do not attempt to create distributions for each parameter in the link-weight estimate; instead we simply copy the discrete link weight values obtained from the survey data onto the unknown links, with appropriate probabilities.
Topographic Spreading Analysis
105
3.2 SAG∗ Now we address another complication arising from the use of weighted links: we must reconsider the definition of the steepest-ascent graph (SAG), which is used both for assigning region membership and for visualization purposes. Our point here is simple, namely that the definition of steepest ascent should take account of the link strength. This rather obvious point has not been addressed in our earlier use of the SAG [1, 2, 3], because these earlier studies were applied to unweighted graphs. Hence we offer a brief account here of the modification used for weighted links. We recall that region membership is assigned by in essence asking each node to find the steepest path to the “top”—i.e., to the “nearest” local maximum of the EVC. The notion of local maximum is independent of link stength. Suppose, however, that a node N has two local maxima (Centers, C1 and C2 ) as neighbors: which region do we place N in? Since we want steepest-ascent paths to represent most likely spreading, it seems reasonable that a neighbor C1 with a very weak link to N should not be assigned the steepest-ascent path—even if it is somewhat higher (in EVC) than C2 . In other words, if we retain the notion that steepest ascent gives the right answer, then we clearly want to define the slope as being slope = Δy/Δx,
(1)
with Δx (‘distance’) decreasing with increasing link strength. Clearly, Δy is the EVC difference, as in earlier (unweighted) work; hence we simply need some reasonable definition for the “distance” Δx. We take here the simple heuristic Δx(i, j) = 1/W (i, j) with W (i, j) the link strength (tranmission probability) between nodes i and j. Our point here is then that node N may find that it is not simply in the region of its highest neighbor: instead, it will be placed in the same region as the neighbor N ∗ with the highest product Δy/Δx = [EV C(N ∗ ) − EV C(N )][W (N, N ∗ )]. In short, if its link to the highest neighbor is very weak, then (reasonably) it will be placed instead in the region of a neighbor with a stronger link. We believe this is consistent with our aim for defining regions—namely, that a region is a coarsegrained unit of infection, such that infection within a region is relatively fast and predictable. We call the resulting steepest-ascent graph SAG∗ (to distinguish it from the SAG, which does not take link strengths into account). We will see below that our spreading simulations can only give a limited test of our SAG∗ definition— since in one case (HIV) the weighted network breaks down, while in the other two (NG and CT) we only obtain a single region. Hence—while we retain a belief that our definition is promising—a thorough test will have to await application to a weighted graph which (i) has several regions, but yet (ii) is better connected than our HIV graph of the following section.
106
J. Bjelland et al.
3.3 HIV Graph The SAG∗ for our weighted HIV graph is shown in Fig. 5. We see immediately that the contrast with Fig. 1 is enormous. In particular, the 17 regions of Fig. 1 have multiplied many times. In addition (which is not so easily seen in the figure) some nodes are completely disconnected due to the zero-weight links, and hence do not appear in the figure at all. The apparently isolated nodes in the corner of the figure are one-node regions; such regions occur typically on the periphery of a graph, where all EVC values are small. What is even more striking is that adding all non-zero links to the SAG∗ picture of Fig. 5 makes very little change; that is, there are only six non-zero links which are not shown in the figure (four connecting the one-node regions to one other node each, and two other inter-region links). Hence we do not show the full graph: it is essentially that of Fig. 5. This means in turn that HIV spreading—while seemingly unstoppable in the picture obtained from Fig. 2—is in fact not a problem for this FSW network. In particular, the
Fig. 5. Regions analysis for the HIV graph, corrected with the transmission probability on each link. Note that the graph breaks into very many small regions, due to the (assumed) zero transmission probability for reliable condom use. The two enlarged nodes are known to be HIV-infected; the four nodes in the upper left corner are singlenode regions in the weighted graph.
Topographic Spreading Analysis
107
two HIV-positive (male) nodes (marked with large squares in Fig. 5) are each confined to an effective two-node network, consisting of themselves and their nonclient partner. Hence our expected picture of condom use for this empirical network implies that HIV spreading will be limited to the non-client partner relationships of the two infected nodes, and so has effectively zero probability of reaching the rest of this dense sexual network. Because the effective graph is so fragmented, and also because the HIVinfected nodes are effectively isolated, we have not performed spreading simulations on the weighted HIV graph. We note that the largest region in Fig. 5 has 24 nodes, with a FSW as the most central node in the region. In fact the strongly bipartite picture obtained from the unweighted graph (Fig. 1) has also broken down here: both male and female Centers of the many regions are found. This is however not so surprising, given the fragmented nature of the effective graph. 3.4 Gonorrhea Figure 6 shows the steepest-ascent (SAG∗ ) graph when we use link strengths approriate to gonorrhea. Since 100% condom use does not give 100% protection [5], the effective gonorrhea graph has all the same links as were present
Fig. 6. Region (SAG∗ ) visualization for the gonorrhea network NG. The enlarged nodes are known to be STI-infected.
108
J. Bjelland et al.
in Fig. 2; but they are reweighted. We see that the reweighting has still had a dramatic effect. In particular, the 17 regions found for the unweighted graph are now a single region for the weighted graph. Also, the Center of this one region (and so of the entire graph) is an FSW. An interesting aspect of the gonorrhea SAG∗ is that one of the few existing homosexual (FSW ⇐⇒ FSW) links plays a very central role in the graph: the link between the Center and the head of the large red subregion is homosexual. This means that the two women involved are highly central in the weighted graph, and also that the link strength between them (transmission probability for gonorrhea) is not too small. One might then propose to remove this link— which (as it is certainly requested and paid for by a male customer) should be possible. However as we will see below, removal of this link—or any single link—has little or no beneficial effect. (This conclusion is perhaps intuitively grasped from the fully linked visualization of Fig. 7 below.) SAGs of either type are strict hierarchical structures—that is, they are directed trees, with links pointing strictly towards the root (Center). This means that, for any given region, one can readily define subregions in terms of branches of the tree. We have picked out the five largest branches of the gonorrhea SAG∗ and color coded them. We see that it is visually meaningful to think in terms of subregions for this region.
Fig. 7. Same layout as in as Fig. 6, but with all non-zero links displayed.
Topographic Spreading Analysis
109
Figure 7 shows the NG-graph again, but with all links displayed. We note that presently infected nodes are enlarged and marked yellow (lighter grey in printed version) in Fig. 6 and in Fig. 7. From Fig. 6 we see two infected nodes lying at the heads of their (large) respective subregions, and hence only one hop from the Center. Also we see that every major subregion is already infected. This immediately suggests that preventing the further spreading of gonorrhea on this graph will be quite difficult. This pessimistic prognosis is also supported by the visualization of Fig. 7. Here we see that all the major subregions are well connected to one aother, with infected nodes lying in the heart of a dense cloud of links. We will test (and confirm) this pessimistic prediction via stochastic simulations—see Section 4. 3.5 Chlamydia In Fig. 8 we show the SAG∗ visualization of the chlamydia graph. Qualitatively we see much the same picture as for the NG graph: a single region, with an FSW at the Center of the region. In fact, the homosexual dyad that we found lying centrally in the NG graph is also central here—with the one difference that here the two FSWs have exchanged roles (Center and subregion head). Our SAG∗ visualizations suggest that the CT graph is perhaps even more well connected than the NG graph—in that there are very few subregions,
Fig. 8. Region (SAG∗ ) visualization for the chlamydia network CT. Enlarged nodes are known STI-infected nodes.
110
J. Bjelland et al.
and they are very large. And since (again) every major subregion is infected, we arrive at the same qualitative prognosis for this graph: it will be difficult to hinder the further spreading of the disease. We have also plotted the analog of Fig. 7 for chlamydia—that is, the full graph with all non-zero links. The result is again qualitatively like that of Fig. 7; hence we do not show it here.
4 Spreading on the Gonorrhea Graph For reasons already given, we have not run spreading simulations on all three disease graphs. The HIV graph is so heavily disconnected by the many condom-use-induced zero links that we see no point in running simulations on it. Of course, these links, involving as they do real sexual contact, do not have exactly zero probability for infectious spreading, even with 100% condom use. Also the reported rates of 100% condom use are most likely overstated in many cases. Hence it would be of interest to set the strength of these “zero HIV links” to some small but positive value, and to examine the resulting graph. We reserve this idea for future work. The remaining two graphs (NG and CT) are qualitatively very similar. Hence we have chosen to focus on one of them—the NG (gonorrhea) graph. We must emphasize immediately however that our simulations, being based on SI dynamics [8], do not accurately model the long-time dynamics of diseases such as gonorrhea and chlamydia. A more appropriate model would be the SIS model [7] in which Infected nodes become again Susceptible after a variable time period. We expect the SI model to give qualitatively correct results in the early stage of any infectious process—when few nodes are infected, and they have not had time to recover. Beyond this early stage the SI model can only overestimate the degree of spreading. Hence we present simulation results in this section, based on the SI model, with two principal caveats: • •
Takeoff of the disease will likely occur later for the more realistic SIS model than what we show here. The long-time infected fraction will not approach 100%, but rather a lower value.
With these caveats clearly in mind, we present some simulations on the gonorrhea graph. Our aim is to see what insights we can gain from our SAG∗ picture. We will focus principally on when the infection takes off. Because we simply compare different scenarios (and their takeoff times) with one another, we feel that our (comparative) conclusions are not greatly weakened by the caveats given above. Our procedure for simulation is the same as before: at each time step, each link ij has a probability pij = W (i, j) of transmitting the infection if exactly one of the pair ij is already infected. Our link strength data, when the unit
Topographic Spreading Analysis
111
of time is one day, have values which vary from a few percent down to about 10−4 . With these small values we can increment the simulator with a time step of one day, and get smooth results. Our simulations differ from one another in three ways: (i) the choice of “start” nodes which are infected at t = 0; (ii) the choice of a set of “immune” nodes which cannot be infected; and (iii) sometimes, the choice of links which are to be blocked from transmission (removed). Choices (ii) and (iii) allow us to test various strategies for hindering spreading. In the real world of human sexual behavior, accomplishing either of these effects may be quite difficult; but we test them here simply to see what can be achieved. First we simulate the reference case, in which those nodes which are known to be infected are the start nodes (see again Figs. 6 and 7), and we immunize no nodes or links. We find (Fig. 9) that the infection takes off very fast—as anticipated in Section 3.4. Specifically, we see that the takeoff time is very short—just a few days. This is consistent with the fact that the infection has already reached three very central (as defined by EVC) nodes. This latter fact is consistent with two interpretations: either (i) the infection has recently come to this dense network, and it is on the verge of taking off, or (ii) the infection has been present for a long time, and has reached an equilibrium (and rather low) level. 600
500
Infected nodes
400
300
200
As−is Center Within 1 hop from center STI red region + head of region 50 random
100
0
0
50
100
150
200 time
250
300
350
400
Fig. 9. Spreading simulations for gonorrhea, based on the SI model, and using various prevention strategies. “As-is” = known infected start nodes and no strategy; the other scenarios involve immunizing various nodes, as described in the text. The unit of time is one day.
112
J. Bjelland et al.
We do not have sufficient empirical information to favor one of these interpretations over the other. If the first one is correct, it implies that one can expect a strong growth of infection rate in a relatively short time. If the second is correct, then our model is likely inadequate, not only in the SI aspect but probably in other aspects as well. We remind the reader that our topographic analysis is most useful in understanding the spreading of new infections over fairly static networks; hence it may be useful in case (i), but has little to say about case (ii). Now, in order to test our ideas further, we assume case (i). Based on our SAG∗ picture, we formulate various immunization strategies and test them via simulation. We have tried (a) immunizing the Center node; (b) immunizing the Center and all nodes within one hop of the Center (subregion heads); (c) immunizing the two infected nodes in the large red subregion, plus that subregion’s head node; and (d) immunizing 50 nodes chosen at random. Results for all of these cases are shown in Fig. 9. A simple conclusion is starkly obvious: none of these immunization strategies is able to retard the takeoff. In fact, the only clear difference is the trivial and useless one: that the long-time infected fraction is reduced by the number of immunized nodes [for example, by 14 for scenario (b), and by 50 for scenario (d)]. In short: as strongly suggested by Fig. 7, the NG network is sufficiently well connected, and sufficiently well infected, so that we find no simple strategy which is at all effective in retarding the takeoff. In order to investigate a different kind of test of the utility of our method of analysis, we next “cure” all infected nodes, and explore scenarios in which we can choose the start nodes freely. Our principal aim is to test the following hypothesis: that time to takeoff is strongly determined by distance from the Center of the SAG∗ . Some simple tests of this hypothesis are shown in Fig. 10. Here we show the progression of infection for three scenarios: (e) the Center is the only infected start node; (f) a node roughly halfway between the Center and the periphery is the start node; and (g) a very peripheral node is the start node. The results of Fig. 10 strongly support our hypothesis. Takeoff times vary from a few days to about 50 days to almost 150 days, as we move the start node outward in the SAG∗ . We also see, in the bottom half of the figure, that our earlier picture [3, 2] of the movement of the infection “front” over the topography is confirmed here: the infection [assuming it doesn’t start at the top as in (e)] moves slowly at first, until it begins to reach more central nodes, at which point it speeds up, while moving “uphill” (towards the Center); subsequently it moves “downhill,” slowing down all the while. While we have seen this dynamic pattern many times before, this is the first time we have tested it on a graph with weighted links (and with the EVC appropriately corrected via the weighted adjacency matrix). While Fig. 10 offers anecdotal evidence for our hypothesis, we also have statistical data. We have in fact run one-start-node simulations for each node on the graph, 10 times for each node, and recorded the average time needed to
Topographic Spreading Analysis
113
Infected nodes
600 500 400 300
100 0
Mean EVC infected nodes
Central node Medium Central Not central
200
0
50
100
150
200 time
250
300
350
400
0
50
100
150
200 time
250
300
350
400
0.2 0.15 0.1 0.05 0
Fig. 10. Three spreading simulations, based on three chosen scenarios, each with a single start node. We see that distance from the Center node (in a metric defined by the SAG∗ ) correlates strongly with time to takeoff. The lower part of the figure shows the average EVC of the newly infected nodes.
reach an infection number of 300 nodes (about 60%). To measure “distance” from the Center, we define the dual notion of “closeness”: a node’s closeness to the Center is simply the product of the link strengths over the (unique) path to the Center in SAG∗ . Thus many weak links give low closeness, while few strong links give high closeness; and both the number of hops and the link strengths of the hops affect the result. Figure 11 gives a scatter plot for average infection time vs closeness, for all nodes in the graph except the Center node. We see a strong decreasing relationship: closer nodes need less time to infect the graph. Thus we find from these results further strong support for our hypothesis.
5 Summary and Discussion In this chapter we have extended the topographic approach to the problem of epidemic spreading over networks to a problem involving two new features. First, the network is real: it is an empirical sex network, with some nodes known to be infected with the STIs HIV, gonorrhea, and chlamydia. Second, we have data which allow us to assign non-uniform link strengths (transmission probabilities), and we have generalized the topographic approach to incorporate these link strengths.
114
J. Bjelland et al.
time
103
102
101 −12 10
10−10
10−8
10−6 closeness
10−4
10−2
100
Fig. 11. Time needed for a single start node to infect 300 nodes, as a function of that start node’s “closeness” to the graph’s Center (averaged over 10 experiments for each start node). Closeness is measured entirely in terms of the modified steepest-ascent graph SAG∗ . We see a thorough statistical corroboration of the results of Fig. 10.
To help in illuminating the effects of incorporating link strengths, we first performed the analysis by ignoring these weights. We visualized the resulting unweighted FSW network, and simulated the progress of HIV on this network (using uniform transmission probabilities). We found some interesting effects from the almost-bipartite nature of the unweighted network. We also found that the network is very highly connected—with the two HIV-infected nodes very close to the network’s Center—so that retarding the spread of HIV was difficult. Nevertheless we were able to show significant benefits to be obtained from our analysis, for some hypothetical cases involving start nodes placed elsewhere. Incorporation of empirically obtained link strengths had large consequences. Each disease yielded a distinct weighted graph, by affecting the transmission probabilities. We found (using our assumption that perfect condom protection was possible) that the HIV graph broke down into many small components. While our visualization may still have some value, we saw no value in running simulations on these small components.
Topographic Spreading Analysis
115
Simulations on the gonorrhea graph gave results much like those on the unweighted FSW graph: the graph was very well connected, and the alreadyinfected nodes had rather central positions. The result was that we were unable to find simple topological fixes, inspired by our analysis, which could significantly retard spreading. However, we were able to find strong evidence confirming the basic applicability of our analysis to spreading. Specifically, we showed that our own notion of a node’s distance from the Center of the graph correlated strongly with the time needed for that node to infect the graph. We emphasize that this is the first application of the topographic approach to a weighted graph. Performing this analysis has required generalizing our earlier definition [3] of steepest ascent. The results we obtain here, based on this new, generalized definition, are very promising. Hence—even as we fail to come up with promising, concrete suggestions for hindering the spread of STIs in the Vancouver sex network—we feel that our results confirm the applicability of our approach to understanding spreading in the real-world case of a network with non-uniformly weighted links. We see a clear need for two obvious extensions of this work. First, it would be useful to reconnect the HIV graph, by assigning small but non-zero probabilities to the 100%-condom-use links. This would allow for a more meaningful regions analysis and the accompanying testing by simulations (perhaps over a long time scale). Second, our approach is most simply understood and applied for diseases for which SI spreading is appropriate (such as HIV). The application to gonorrhea or chlamydia would be greatly strengthened if one could generalize the method to the SIS and/or SIR case. This is an interesting challenge for future work. The data used arrive from self-reported infection status ([10]). To validate our model, empirically collected retrospective data on actual prevalence and incidence of the infections could be obtained. This is also recommended for future work. Finally, we remind the reader of the motivation for this work. We believe that the topographic analysis, based on EVC, is extremely useful for understanding epidemic spreading on a coarse scale. The analysis itself is not computationally demanding; hence it can be performed in essentially real time. Thus, we hope that our approach can be useful for disease prevention, in those cases for which the network can be mapped in reasonably short time—that is, short compared to both the time scale for infectious spreading, and the time scale for significant topology changes. The results presented here do not offer any immediate solution to the problem of STIs in the Vancouver FSW network, but they do add further support to our belief that this approach may be useful for this problem, and for others.
116
J. Bjelland et al.
Acknowledgments GC and KEM acknowledge partial support from the Future and Emerging Technologies unit of the European Commission through Project DELIS (IST-2002-001907). VPR acknowledges the financial and in-kind support, respectively, of the BC Medical Services Fdn and HIV/STI Prevention and Control, BC Centre for Disease Control.
References 1. G. Canright and K. Engø-Monsen. Roles in networks. Science of Computer Programming, pages 195–214, 2004. 2. G. Canright and K. Engø-Monsen. Epidemic spreading over networks: a view from neighbourhoods. Telektronikk, 101:65–85, 2005. 3. G. Canright and K. Engø-Monsen. Spreading on networks: a topographic view. In Proceedings, European Conference on Complex Systems, 2005. 4. G. S. Canright and K. Engø-Monsen. Some relevant aspects of network analysis and graph theory. In J. Bergstra and M. Burgess, editors, Handbook of Network and Systems Administration. Elsevier, Amsterdam, 2007. 5. K. Holmes, R. Levine, and M. Weaver. Effectiveness of condoms in preventing sexually transmitted infections. Bull World Health Organ, 82:454–461, 2004. 6. A. M. Jolly, M. E. Moffatt, M. V. Fast, and R. C. Brunham. Sexually transmitted disease thresholds in Manitoba, Canada. Ann Epidemiol, 15:781–788, 2005. 7. M. Kretzschmar, Y. T. P. H. van Duynhoven, and A. J. Severijnen. Modeling prevention strategies for gonorrhea and chlamydia using stochastic network simulations. American Journal of Epidimiology, 144:306–317, 1996. 8. M. Newman. The structure and function of complex networks. SIAM Review, 45:167–256, 2003. 9. R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys Rev Lett, 86:3200–3203, 2001. 10. V. P. Remple, D. M. Patrick, C. Johnston, M. W. Tyndall, and A. Jolly. Clients of indoor commercial sex workers: Heterogeneity in patronage patterns and implications for HIV and STI propagation through sexual networks. Sexually Transmitted Diseases, May 2007.
Spectral Characterization of Network Structures and Dynamics Anirban Banerjee1 and J¨ urgen Jost2 1
2
Max Planck Institute for Molecular Genetics, Ihnestr. 63-73, 14195 Berlin, Germany;
[email protected] Max Planck Institute for Mathematics in the Sciences, Inselstr.22, 04103 Leipzig, Germany, and Santa Fe Institute, Santa Fe, NM 87501, USA;
[email protected]
1 Introduction Mathematically, graphs defy a systematic and complete classification, and empirically, the graphs representing networks come in a bewildering multitude. We have developed some tools [8, 9, 10] that at least allow for a rough classification of graphs that reflects the difference in the empirical domains from which network data are produced and that does not depend on sophisticated visualization tools. As such, a graph is a rather simple formal structure. It consists of nodes or vertices that are connected by edges or links. These nodes then represent the elements of a network (and we shall often not distinguish between the network and its underlying graph), and the edges represent relations between them. These could be chemical interactions as in intracellular networks of genes, proteins, or metabolites, synaptic connections between neurons, physical links in infrastructural networks, links between Internet pages, co-occurrences between words in sentences or on text pages, email contacts between people, co-authorships between scientists, and so on. This structure then can be expected to be somehow adapted to the function of the network, by evolution, self-organization, or design. In turn, any dynamics supported by the network will be constrained by this underlying structure. Our approach is based on associating certain mathematical objects—which ultimately just yield some numbers—to a graph which reflect its structural properties and which in particular encode the constraints on the dynamics that it can support. The mathematical objects will be an operator, the graph Laplacian (a discrete analogue of the Laplace operator in real analysis), and its eigenfunctions, and the numbers alluded to will be the eigenvalues of that operator.
N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 7, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
118
A. Banerjee and J. Jost
2 Growing Networks Empirical networks usually do not spring into existence, but rather grow to their present or final state from smaller beginnings. Naturally, such a growth process involves the sequential addition of nodes and links (connections). Usually, nodes are added at random, but their link formation with other nodes (already present in the network) is often not entirely random. This link formation will follow some rule that typically is still stochastic but also involves properties of those nodes that are candidates for receiving a link. When that rule is such that there is a higher chance of receiving links from those nodes that already have many connections than from those with fewer connections, we have some form of preferential attachment. Such a rule is known to lead to a scale-free degree distribution of the nodes in the network; that is, the number of nodes in the final network that have k links behaves like some power k −α , for some positive exponent α. The first such rule was proposed by Simon [44], and it directly stipulated that those nodes that have more connections also have a higher chance of receiving additional ones (“the-rich-get-richer” principle). This rule and the effects resulting from it were then systematically investigated by Barab´ asi–Albert [2, 11], and subsequently, many empirical networks were found to exhibit such a power-law degree distribution. It would be, however, premature to draw systematic consequences about other network properties from such a power-law degree distribution. In fact, there are many rules for network growth that are plausible in many areas of application that indirectly lead to such a kind of preferential attachment, but can lead to networks with properties that are otherwise rather different from those of the schemes of Simon and Barab´ asi–Albert. For instance, Jost– Joy [28] investigated the “make-friends-with-the-friends-of-your-friends” rule where a new node first forms one link with a randomly selected node in the network and then preferentially makes further links with neighbors of that node. Since the chance of a node being a neighbor of some randomly chosen node depends on its degree, these subsequent links then also constitute some preferential attachment, and the resulting degree distribution will follow a power law. However, other properties of that network are rather different from those obtained by the direct preferential attachment scheme. In particular, because of the preference for local connections, the network diameter will be typically much larger. Even the opposite scheme, where a node preferentially forms additional links with nodes from which it has a large distance, does not lead to a network with a very small diameter. For creating a network with a small diameter, it is rather more efficient that nodes directly use preferential attachment, that is, preferentially form links with other nodes that have a high degree and are therefore well connected in the network. Of course, the most efficient way to achieve a small diameter in a sparse network is to connect every node to one single central node. Another crucial difference between a “make-friends-with-the-friends-ofyour-friends” network and a “the-rich-get-richer” network is that the first
Spectral Characterization of Network Structures and Dynamics
119
eigenvalue of the make friends network will be much smaller, implying for instance that dynamics on such a network are much more difficult to synchronize, as will be explained below. In fact, spectral properties like the behavior of the first eigenvalue of scale-free networks were analyzed in [3, 4], and it was pointed out that the scaling exponent and the first eigenvalue are essentially independent parameters for a network. Of course, when networks are produced by a certain stochastic scheme or drawn from some probability distribution on the space of networks, then that scheme or distribution will also lead to some typical spectral behavior, as systematically investigated in [29]. However, when we only know whether a network is scale free, we should be careful about inferring other network properties. It might be a wiser strategy to find out more about the underlying network evolution rule, like the above “make-friends-with-the-friends-of-your-friends” principle, the Cameo principle of Blanchard–Kr¨ uger [12], or whatever is plausible in the given empirical domain. One important class of rules for which there is much evidence in various domains is the one of node duplications. That means that instead of randomly attaching a new external node, we take some node i already present in the network and double it in the sense that we create a new node i that forms links with all or some of the neighbors of i. It may or may not also form a link with i itself. Again, since the chance of another node j of being a neighbor of the randomly chosen node i and therefore receiving new connections from i depends on the degree of j, we do get a preferential attachment scheme. Again, however, as we shall see below, such a node duplication leads to some specific spectral properties that are not shared by networks arising from different schemes. There also exist other distinctions within the class of scale-free networks. An important one is whether the nodes of high degree are assortative, i.e., prefer connections with other high degree nodes, or disassortative, i.e., avoid connections with high degree nodes and rather form links with low degree nodes.
3 Graph Operators and their Spectral Properties We have already seen several important network parameters or properties, like the diameter, the synchronizability, the degree sequence (counting the number of nodes of degree k in the network as a function of k ∈ N), and the assortativity. Of course, there are many others, like the clustering coefficient, which expresses the relative frequency of triangles, that is, triples of nodes that are pairwise connected. The clustering coeffient is defined as C :=
3 × number of triangles . number of connected triples of nodes
The normalization is that C becomes one for a fully connected graph.
(1)
120
A. Banerjee and J. Jost
Certain properties characterize specific classes of graphs. Complete graphs are those where every vertex is connected with all others. Of course, for large graphs, this is an unrealistic situation, as they are typically sparse, in the sense that the average vertex has connections to only a small fraction of the vertices present in the graph. A graph is bipartite when it consists of two classes inside each of which there are no connections. A graph is bipartite iff it has no closed paths of odd length. In particular, for a bipartite graph, the clustering coefficient C vanishes. A complete bipartite graph is one where each member of one class is connected with all members of the other class. Trees are special bipartite graphs. They have the minimal number of edges, N − 1, that is needed to make a graph of N vertices connected. One may also consider more general structural properties, like cohesion, or functional aspects, like robustness against the destruction of links or the elimination of nodes. Clearly, no such list of parameters and properties can be exhaustive. Also, it may not be easy to understand the relations, if any, between those parameters and properties. In this situation, we have developed the spectral approach to the description of networks. As we shall explain, this means the analysis of the density of eigenvalues of a natural operator associated to a network, the graph Laplacian. While these eigenvalues do not always fully determine a graph, they nevertheless capture all important geometric properties, in a more or less explicit form. Plotting the density of eigenvalues also yields a representation of a graph that can be readily visually inspected. (In contrast, explicit presentation of the nodes and links becomes rather opaque once the graph exceeds some moderate size of, say 1–200 nodes.) Moreover, can easily manipulated by moving the nodes around in a plane. We now formally introduce the graph Laplacian and its spectrum. We represent our network structurally as a graph Γ which we assume to be finite and connected; let it have N vertices. Vertices i, j ∈ Γ connected by an edge of Γ are called neighbors, i ∼ j. The number of neighbors of a vertex i ∈ Γ is called its degree ni . For functions v from the vertices of Γ to R, we define the normalized Laplacian (henceforth simply called the Laplacian) as Δv(i) :=
1 v(j) − v(i). ni j,j∼i
(2)
This operator is different from the algebraic graph Laplacian Lv(i) := ni v(i)− j,j∼i v(j); see, e.g., [13, 14, 20, 32, 35]. In particular, the spectrum of Δ is different from that of L; Δ, however, has the same spectrum as the Laplacian investigated in [15] (in fact, the two operators are equivalent, differing only by a multiplier). The normalized Laplacian is the operator underlying random walks and conservative diffusion processes on graphs. Therefore, it seems to be the more natural operator from a geometric or physical perspective. However, the algebraic Laplacian does possess certain nice algebraic properties that are not shared by the normalized Laplacian, like a trace formula, see [22].
Spectral Characterization of Network Structures and Dynamics
121
Nevertheless, in our empirical studies, we have found that the Laplacian considered here seems to be a better tool for distinguishing different classes of graphs by spectral properties. We now recall some elementary properties, see, e.g., [15, 26]. The Laplacian is symmetric for the product ni u(i)v(i) (3) (u, v) := i∈V
for real-valued functions u, v on the vertices of Γ (and because of this symmetry, we need not consider complex-valued functions). The eigenvalues of Δ therefore are real. Δ is nonpositive in the sense that (Δu, u) ≤ 0 for all u. With the following convention, the eigenvalues λ then are nonnegative: Δu + λu = 0.
(4)
A nonzero solution u is called an eigenfunction for the eigenvalue λ. Since Γ has N vertices, Δ has N eigenvalues, not necessarily distinct, as some of them might occur with higher multiplicity. The smallest eigenvalue is λ0 = 0, with a constant eigenfunction. This eigenvalue is simple because we assume that Γ is connected; in general, the multiplicity of the eigenvalue 0 equals the number of connected components, with the corresponding eigenfunctions being ≡ 1 on one and ≡ 0 on all other components. Returning to our case of a connected graph Γ , then λk > 0
(5)
for k > 0 where we order the eigenvalues as λ0 = 0 < λ1 ≤ · · · ≤ λN −1 . For the largest eigenvalue, we have λN −1 ≤ 2.
(6)
In particular, the spectrum of Δ is always confined to the interval [0, 2], regardless of the size of the graph. This is not true for the algebraic graph Laplacian L, and this property of Δ allows for an easy comparison of the spectra of graphs irrespective of their sizes. We have equality in (6) iff the graph is bipartite. Thus, a single eigenvalue determines the global property of bipartiteness. More generally, a graph is bipartite iff whenever λ is an eigenvalue, then so is 2 − λ. Thus, the characteristic spectral property of a bipartite graph is that its spectrum is symmetric about 1. For instance, for a complete graph of N vertices, λ1 = ... = λN −1 =
N , N −1
(7)
122
A. Banerjee and J. Jost
that is, there is only one nontrivial eigenvalue, NN−1 , occurring with multiplicity N − 1. Among all graphs with N vertices, this is the largest possible value for λ1 and the smallest possible value for λN −1 . Thus, the characteristic spectral property of complete graphs is that there is this eigenvalue with the highest possible multiplicity. Many qualitative properties of graphs can be characterized by inequalities or other relationships between their eigenvalues. For instance, Monasson [36] carried out a systematic investigation of the spectrum of a small-world graph as the superposition of a regular ring and a random graph. Also, [23] develops a method for (re)constructing a graph from its spectrum. We should point out, however, that in general it is not possible to uniquely determine a graph from its spectrum. In fact, there exist isospectral graphs, that is, different graphs with the same eigenvalues. For instance, all complete bipartite graphs with the same number N of vertices have the same eigenvalues. Actually, they possess the eigenvalues 0 and 2 with multiplicity 1 and the eigenvalue 1 with multiplicity N − 2. Any graph with that spectrum is a complete bipartite graph, but among bipartite graphs of N vertices, the two classes may have different sizes N1 , N2 , as long as N1 + N2 = N , of course. We now rewrite the eigenvalue equation (4) as 1 u(j) = (1 − λ)u(i) for all i. (8) ni j∼i We observe that when the eigenfunction u vanishes at i, then also u(j) = 0.
(9)
j∼i
The converse also holds, except for the case λ = 1 when (9) holds at all points regardless of whether the eigenfunction vanishes there or not. We now consider motifs, that is, small subgraphs of Γ of a particular type, and analyze what happens to the spectrum when performing some natural operations with motifs. As our motif, we take some graph Λ. We start with motif joining: Here, the motif Λ is a graph that is independent of Γ . Let j0 be a vertex of Λ. We assume that Λ has eigenvalue λ and an eigenfunction uλ that vanishes at j0 , i.e., uλ (j0 ) = 0. We then form a graph Γ¯ by identifying the vertex j0 with an arbitrary vertex i of Γ . The new graph then also possesses the eigenvalue λ, with an eigenfunction that agrees with uλ on Λ and vanishes at the other vertices, that is, those coming from Γ . Thus, a motif Λ can be joined to an existing graph with a preserved eigenvalue and a localized eigenfunction when the joining occurs at one (or several) vertices where that eigenfunction vanishes. We next consider motif duplication: Here, the motif Λ is a subgraph of Γ , with vertices j1 , . . . , jm . Let the function u on the vertex set of Λ satisfy 1 u(j) = (1 − λ)u(i) for all i ∈ Λ and some λ, (10) ni j∈Λ,j∼i
Spectral Characterization of Network Structures and Dynamics
123
where ni is the degree of the vertex i in Γ . Let Γ¯ be obtained from Γ by doubling the motif Λ, that is, by adding vertices i1 , . . . , im and their connec/ Λ that are neighbors of jα . tions as in Λ and connecting each iα with all i ∈ Then the graph Γ¯ possesses the eigenvalue λ with an eigenfunction uλ that is nonzero at most of the vertices of Λ and its double; it agrees with u on Λ, with −u on the double of Λ. Thus, the eigenvalue λ is produced by motif duplication with symmetric eigenfunction balancing. We point out that for this effect it is essential that there be no connections between a node jα and its double iα . The simplest motif is a single vertex, and the corresponding motif duplication is the doubling of a single vertex j0 ∈ Γ . According to the general scheme, we add a new vertex i0 and connect i0 with all neighbors of j0 . This generates an eigenvalue 1, with an eigenfunction u1 that is nonzero only at j0 and i0 , with u1 (j0 ) = 1, u1 (i0 ) = −1. In the analysis of empirical networks, we often find that the spectral plot has a high peak at the eigenvalue 1. In such a situation, a natural hypothesis is that this network evolved via a sequence of vertex doublings. In fact, vertex duplication with subsequent random edge deletion has been proposed in different application fields as a mechanism for network growth that can reproduce qualitative properties of empirical networks, e.g., for the Internet [30], for protein-interaction networks [6, 45, 46, 47], or for citation networks [31], although the precise rules can differ between those investigations, for instance, whether the duplicated node and its copy are connected or not. The next simplest motif consists of two connected vertices. Thus, we consider an edge in Γ connecting two vertices j1 , j2 . Equation (10) then becomes 1 u(j2 ) = (1 − λ)u(j1 ), nj1 with the solutions
1 u(j1 ) = (1 − λ)u(j2 ), nj2
1 λ± = 1 ± √ . nj1 nj2
(11)
(12)
The duplication of an edge thus yields the eigenvalues λ± which are symmetric about 1. Also, when the degree of j1 or j2 is large, λ± are close to 1. The next motifs consist of three vertices. When we have a chain of vertices j1 , j2 , j3 for which j2 is connected to both j1 and j3 , but without a connection between j1 and j3 (that is, the motif is not a triangle), we obtain the eigenvalues 1 1 1 ( + ). (13) λ = 1, 1 ± nj2 nj1 nj3 The other motif with three vertices is a triangle, with vertices j1 , j2 , j3 . In this case, from (10), we obtain the cubic equation (1 − λ)3 nj1 nj2 nj3 − (1 − λ)(nj1 + nj2 + nj3 ) − 2 = 0 for λ.
(14)
124
A. Banerjee and J. Jost
4 Functional and Dynamical Aspects Determined by the First Eigenvalue In this section, we shall argue that the first nontrivial eigenvalue λ1 plays a special role for understanding important network properties. λ1 is also called the spectral gap, because it is equal to the difference λ1 − λ0 as λ0 = 0. λ1 admits the variational characterization 2 j∼i (v(i) − v(j)) : ni v(i) = 0}. (15) λ1 = min{ 2 v i ni v(i) i A function v attaining this minimum then is an eigenfunction for λ1 . Since the numerator in (15) only takes pairs of neighboring vertices into account, λ1 can become quite small when the graph consists of two large subgraphs that are connected by few edges. In (15), we can then achieve a small value by taking some function that equals a positive constant on one of those subgraphs and a negative constant on theother hand, where the two constants are adjusted so that the normalization i ni v(i) = 0 is satisfied. Therefore, it is intuitively clear that λ1 can be estimated against the Polya–Cheeger constant h(Γ ) of our graph Γ , which is defined as follows. Letting |E| denote the number of edges contained in an edge set E, we define h(Γ ) := inf{
|E0 | }, min( i∈V1 ni , i∈V2 ni )
(16)
where removing E0 disconnects Γ into the components V1 , V2 . We then have the estimates (see [15] for proofs) 1 h(Γ )2 ≤ λ1 ≤ 2h(Γ ). 2
(17)
Incidentally, this implies the inequality h(Γ ) ≤ 4
(18)
for any connected graph. Turning to dynamical aspects, we consider a dynamical system with coupling structure given by Γ . More specifically, we consider the coupled equation for a function u depending on the nodes i ∈ Γ and evolving in discrete time n∈N (f (u(j, n)) − f (u(i, n))). (19) u(i, n + 1) = f (u(i, n)) + ni j,j∼i Here, f : [0, 1] → [0, 1] is some function; the functions we have in mind are those whose iteration generates some chaotic dynamics, like the logistic map f (x) = 4x(1 − x).
(20)
Spectral Characterization of Network Structures and Dynamics
125
What is important about f is its Lyapunov exponent, N −1 1 log |f (¯ u(n))|; N →∞ N n=0
μ0 = lim
The Lyapunov exponent μ0 is positive for chaotic dynamics f . is a coupling parameter, usually in the range 0 ≤ ≤ 1. The specific question we wish to ask is whether, or better, under what circumstances, the solution u of (19) synchronizes, that is, asymptotically, lim (u(i, n) − u(j, n)) = 0 for all nodes i, j.
n→∞
(21)
This question can be understood as asking about the stability of a synchronized solution u(i, n) = u ¯(n) (22) that solves u ¯(n + 1) = f (¯ u(n)).
(23)
Systematic studies of synchronization are [42, 41]. It was then found in [27, 43] that a sufficient condition for such stability is 1 + e−μ0 1 − e−μ0 < < . λ1 λN −1
(24)
In practice, the left inequality, the one involving λ1 , is the crucial one here. In particular, when the eigenvalues satisfy appropriate conditions, we can have a stable synchronized solution that is chaotic (μ0 > 0). Note that the first eigenvalue even determines the synchronization of dynamics with transmission delays between the nodes, see [5].
5 Spectral Plots and What They May Tell Us In this final section, we describe how (a smoothed version of) the density plot for the eigenvalues of the Laplacian of a network yields a good heuristic clustering scheme for networks from different empirical domains. More precisely, we shall see that the spectral plots of different networks from the same domain typically look rather similar to each other, but different from those for networks from different domains. Also, these spectral plots often suggest suitable hypotheses about the dominant evolution mechanisms of the underlying networks. Let us give some examples that summarize some of the discussion in the preceding sections. • •
A high peak at the eigenvalue 1 may indicate many successive node duplications. This is readily visible in many of our spectral plots. Likewise, as analyzed above, see (12), (13), (14), duplications of small motives leave characteristic traces in the spectrum.
126
A. Banerjee and J. Jost 0.04
0.03
a
b
0.035 0.025 0.03 0.02
0.025 0.02
0.015
0.015 0.01 0.01 0.005
0.005 0
0.5
0
1
1.5
2
0.06
0
0.5
1
1.5
2
0.06
d
c 0.05
0.05
0.04
0.04
0.03
0.03
0.02
0.02
0.01
0.01
0
0
0
0.5
1
1.5
2
0 0
0.5
1
1.5
2
Fig. 1. (a) Protein-protein interaction network of Helicobacter pylori. Network size = 710. Data collected from http://www.cosinproject.org [Download date: 25 Sept. 2005]. (b) Metabolic network of Helicobacter pylori. Size of the network = 940. Nodes represent substrates, enzymes, and intermediate complexes. Data used in [24]. Data source: http://www.nd.edu/∼networks/resources.htm. [Download date: 22 Nov. 2004]. (c) Autonomous Systems (ASS) topology of the Internet. Every vertex represents an AS, and two vertices are connected if there is at least one physical link between the two corresponding ASS. AS graph of 1998/04/02. Network size = 3522. Data collected from http://www.cosinproject.org and data used in [18] [Download date: 23 September 2005]. Main source: BGP routing data collected by University of Oregon Route Views Project, then processed and made available in various formats at the Global ISP interconnectivity by AS number page of NLANR (National Laboratory of Applied Network Research). (d) Word-adjacency networks of a text in Spanish language. Size of the network = 11558. Data downloaded from http://www.weizmann.ac.il/mcb/UriAlon [Download date 3rd Feb. 2005]. Data used in [34].
Spectral Characterization of Network Structures and Dynamics
127
0.02
0.025
a
b
0.018 0.016
0.02
0.014 0.015
0.012
0.01
0.008
0.01
0.006 0.004
0.005
0.002 0
0
0.025
0.5
1
1.5
2
0
0
0.5
1
1.5
2
0.5
1
1.5
2
0.012
c
d 0.01
0.02
0.008 0.015 0.006 0.01 0.004 0.005
0
0.002
0
0.5
1
1.5
2
0
0
Fig. 2. (a) Foodweb network from “Florida bay in wet season”. Data downloaded from http://vlado.fmf.uni-lj.si/pub/networks/data (main data resource: Chesapeake Biological Laboratory. Web link: http://www.cbl.umces.edu/). [Download date 21 Dec. 2006]. Network size 128. (b) Foodweb network from “Ythan estuary”. Data downloaded from http://www.cosinproject.org. [Download Date 21 Dec. 2006]. Network size 135. (c) The network of hyperlinks between weblogs on US politics, recorded in 2005 by Adamic and Glance [1]. Network size 1222. Data downloaded from http://www-personal.umich.edu/∼mejn/netdata [Download date: 23 April 2007]. (d) Neuronal connectivity of Caenorhabditis elegans. Network size 297. Data used in [49, 50]. Data Source: http://cdg.columbia.edu/cdg/datasets [Download date: 18 Dec. 2006]. (e) E-mail interchanges between members of the Univeristy Rovira i Virgili (Tarragona) [21]. Network size 1133. Data downloaded from http://deim.urv.cat/∼aarenas/data/welcome.htm [Download date: 21 March, 2007].
128
A. Banerjee and J. Jost 9
x 10−3
e
8 7 6 5 4 3 2 1 0
0
0.5
1
1.5
2
Fig. 2. (Continued)
•
•
As follows from Section 4, the presence of many small eigenvalues indicates that the graph consists of many components that, while possibly connected densely inside, are only very loosely connected to each other. That is, the graph consists of many different “communities.” As indicated, this has important dynamical implications for the synchronizability of the graph. When the highest eigenvalue equals 2, or, more generally, when the spectrum is symmetric about 1, the graph is bipartite; see the discussion after (6). Thus, an approximate such symmetry, or an eigenvalue very close to 2, will indicate that the graph is close to being bipartite (we hope to present more precise estimates elsewhere). Also, a bipartite graph can readily support period 2 oscillations of coupled dynamics, so again, there are direct dynamical implications here. Also, when a graph is bipartite, a random walk on it need not converge to a stationary distribution. More generally, such convergence properties are related to the small and large (close to 2) eigenvalues. Thus, these eigenvalues will affect the properties of random search schemes on the underlying graph.
In the Figs. 1 through 4, we can clearly see that networks from the same empirical domain yield similar spectral plots. Also, we can distinguish different classes of spectral plots with specific characteristic features. A more detailed analysis of those classes can be found in [10]. The investigation of the graph properties that can be detected from spectral plots has just begun, and we expect significant advances in the detailed understanding of classes of empirical graphs from systematic investigations of their spectra.
Spectral Characterization of Network Structures and Dynamics 0.01
129
0.025
a
0.009
b 0.02
0.008 0.007
0.015
0.006 0.005
0.01
0.004 0.003
0.005
0.002 0.001 0
0
8
0.5
1
1.5
0
2
x 10−3
9
c
0.5
1
1.5
2
x 10−3
d
8
7
0
7
6
6 5
5 4
4 3
3
2
2
1 0
1 0
0.5
1
1.5
2
0
0
0.5
1
1.5
2
Fig. 3. (a) Topology of the Western states power grid of the United States [49]. Network size 4941. Data downloaded from http://cdg.columbia.edu/cdg/datasets [Download date: 1 March 2007]. (b) Jazz band network. Nodes represent jazz bands. Two bands are connected if a same musician played in those two bands. Network size 198. Data downloaded from http://deim.urv.cat/∼aarenas/data/welcome.htm [Download date: 17 March 2008]. Data used in [19]. (c) Co-authorships between scientists posting preprints on the High-Energy Theory E-Print Archive, http://arxiv.org/archive/hepth between 1 Jan. 1995 and 31st Dec. 1999 [37]. Network size 5835. (d) Co-authorships of scientists working on network theory and experiment [38]. Network size 379. (c,d) Data downloaded from http://www-personal.umich.edu/∼mejn/netdata [Download date: 23 April 2007].
130
A. Banerjee and J. Jost 6
x 10−3
7
x 10−3
a
b 6
5
5 4 4 3 3 2
2
1
0 0
1
0.5
7
0 0
2
1.5
1
1
0.5
1.5
2
x 10−3
c 6 5 4 3 2 1 0 0
0.5
1
1.5
2
Fig. 4. Electronic circuits. (a) With size = 122. (b) With size = 252. (c) With size = 512. Data downloaded from http://www.weizmann.ac.il/mcb/UriAlon [Download date: 15 March 2005]. Data used in [33].
References 1. L.A. Adamic and N. Glance, The political blogosphere and the 2004 US election: Divided they blog, in Proceedings of the WWW-2005 Workshop on the Weblogging Ecosystem (2005) 2. R. Albert, A.-L. Barab´ asi, Statistical mechanics of complex networks, Reviews of Modern Physics 74, 2002, 47–97 3. F.M. Atay, T. Bıyıko˘ glu, J. Jost, Synchronization of networks with prescribed degree distributions, IEEE Trans. Circuits and Systems I 53(1), 2006, 92–98 4. F.M. Atay, T. Bıyıko˘ glu, J. Jost, Network synchronization: Spectral versus statistical properties, Phys. D 224, 2006, 35–41 5. F.M. Atay, J. Jost, A. Wende, Delays, connection topology, and synchronization of coupled chaotic maps, Phys. Rev. Lett. 92(14), 2004, 144101
Spectral Characterization of Network Structures and Dynamics
131
6. A. Banerjee, J. Jost, Laplacian spectrum and protein-protein interaction networks, preprint 7. A. Banerjee, J. Jost, On the spectrum of the normalized graph Laplacian, Lin. Alg. Appl. 428, 2008, 3015–3022 8. A. Banerjee, J. Jost, Graph spectra as a systematic tool in computational biology, Discr. Appl. Math., to appear 9. A. Banerjee, J. Jost, Spectral plots and the representation and interpretation of biological data, Theory Biosc. 126, 2007, 15–21 10. A. Banerjee, J. Jost, Spectral plot properties: Towards a qualitative classification of networks, NHM 3, 2008, 395–411 11. A.-L. Barab´ asi, R.A. Albert, Emergence of scaling in random networks, Science 286, 1999, 509–512 12. P. Blanchard, T. Kr¨ uger, The “Cameo” principle and the origin of scale-free graphs in social networks, J. Stat. Phys. 114, 1399–1416, 2004 13. T. Bıyıko˘ glu, J. Leydold, P. Stadler, Laplacian Eigenvectors of Graphs, Springer Berlin, 2007 14. B. Bolob´ as, Modern Graph Theory, Springer, Berlin, 1998 15. F. Chung, Spectral Graph Theory, AMS, Providence, RI, 1997 16. F. Chung, L.Y. Lu, Complex Graphs and Networks, AMS, Providence, RI, 2006 17. S.N. Dorogovtsev, J.F.F. Mendes, Evolution of Networks, Oxford University Press, Oxford, 2003. 18. M. Faloutsos et al., On power-law relationships of the Internet topology, SIGCOMM, 1999. 19. P.M. Gleiser, L. Danon, Community structure in Jazz, Advances in Complex Systems (ACS) 6(4), 2003, 565–573 20. C. Godsil, G. Royle, Algebraic Graph Theory, Springer, Berlin, 2001 21. R. Guimera et al., Self-similar community structure in a network of human interactions, Physical Review E 68, 2003, 065103(R) 22. M. Horton, H. Stark, A. Terras, What are zeta functions of graphs and what are they good for? In Quantum graphs and their applications, Contemp. Math., Amer. Math. Soc., Providence, RI, 415, 2006, 173–189 23. M. Ipsen, A.S. Mikhailov, Evolutionary reconstruction of networks, Phys. Rev. E 66(4), 046109, 2002 24. H. Jeong et al., The large-scale organization of metabolic networks, Nature 407, 2000, 651–654 25. J. Jost, Mathematical methods in biology and neurobiology, monograph, to appear 26. J. Jost, in: J.F. Feng, J. Jost, M.P. Qian (eds.), Networks: From Biology to Theory, 35–62, Springer, Berlin, 2007 27. J. Jost, M.P. Joy, Spectral properties and synchronization in coupled map lattices, Phys. Rev. E 65(1), 2002, 016201 28. J. Jost, M.P. Joy, Evolving networks with distance preferences, Phys. Rev. E 66, 2002, 36126–36132 29. D.H. Kim, A. Motter, Ensemble averageability in network spectra, Phys. Rev. Lett. 98, 2007, 248701 30. J. Kleinberg et al., The Web as a Graph: Measurements, Models, and Methods, LNCS 1627, 1999, 1–17 31. P. Krapivsky, S. Redner, Network growth by copying, Phys. Rev. E 71, 2005, 036118 32. R. Merris, Laplacian matrices of graphs – A survey, Lin. Alg. Appl. 198, 1994, 143–176
132
A. Banerjee and J. Jost
33. R Milo et al., Network motifs: Simple building blocks of complex networks, Science 298, 2002, 824–827 34. R. Milo et al., Superfamilies of evolved and designed networks, Science 303, 2004, 1538–1542 35. B. Mohar, Some applications of Laplace eigenvalues of graphs, in: G. Hahn, G. Sabidussi (eds.), Graph Symmetry: Algebraic Methods and Applications, 227– 277, Springer, Berlin, 1997 36. R. Monasson, Diffusion, localization and dispersion relations on “small-world” lattices, Europ. Phys. J. B 12, 1999, 555–567 37. M.E.J. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA 98, 2001, 404–409 38. M.E.J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74, 2006, 036104 39. M. Newman, The structure and function of complex networks, SIAM Review 45, 2003, 167–256 40. S. Ohno, Evolution by Gene Duplication, Springer, Berlin, 1970 41. L.M. Pecora, T.L. Carroll, Synchronization in chaotic systems, Phys. Rev. Lett. 64, 1990, 821–824 42. A. Pikovsky, M. Rosenblum, J. Kurths, Synchronization – A Universal Concept in Nonlinear Science, Cambridge University Press, Cambridge, 2001 43. G. Rangarajan, M.Z. Ding, Stability of synchronized chaos in coupled dynamical systems, Phys. Lett. A 296, 2002, 204–212 44. H. Simon, On a class of skew distribution functions, Biometrika 42, 1955, 425–440 45. R. Sol´e et al., A model of large scale proteome evolution, Adv. Compl. Syst. 5, 2002, 43–54 46. A. Vazquez et al., Modelling of protein interaction networks, ComPlexUs 1, 2003, 38–44 47. A. Wagner, How the global structure of protein interaction networks evolves, Proc. Roy. Soc. B 270, 2003, 457–466 48. A. Wagner, Evolution of gene networks by gene duplications — A mathematical model and its implications on genome organization, Proc. Nat. Acad. Sciences USA 91(10), 1994, 4387–4391 49. D.J. Watts, S.H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393, 1998, 440–442 50. J.G. White et al., The structure of the nervous system of the nematode Caenorhabditis elegans, Phil. Trans. Royal Soc. of London Series B-Bio. Sc. 314, 1986, 1–340 51. P. Zhu, R.C. Wilson, A study of graph spectra for comparing graphs. In Proc. of British Machine Vision Conf. (MBVC), Sep 2005 52. K.H. Wolfe, D.C. Shields, Molecular evidence for an ancient duplication of the entire yeast genome, Nature 387(6634), 1997, 708–713
Dynamics of Social Complex Networks: Some Insights into Recent Research Sergi Lozano ETH Zurich, Swiss Federal Institute of Technology, UNO D11, Universit¨ atstr. 41, 8092 Zurich, Switzerland;
[email protected]
1 Introduction: Social Networks as Complex Networks Social networks analysis (that is, the study of interactions among social actors from a structural viewpoint) has a long tradition covering several decades [1, 2, 3]. This sort of study has usually been performed over small social networks, and the limitation of size has conditioned the visibility of complexity [4, 5]. However, the situation has changed significantly in recent times due to basically two reasons. First, there is an increasing availability of larger social datasets (obtained in most cases from information and communication technologies). Secondly, a large number of physicists and other scholars from complexity science have started to take active interest in the field. New perspectives and tools have been provided by these ‘newcomers’, which in combination with the expertise and knowledge accumulated by ‘classical’ social network analysts, has formed the basis of a multidisciplinary field suitably termed the science of networks [6, 7]. This research has led to the formal definition of the complexity exhibited by social networks against the following simple ‘check list’ [5]. 1. The network must consist of a large number of nodes showing substantial heterogeneity. Here we understand heterogeneity to mean diversity of degree. 2. Its structure has to present an ‘intricate architecture’, that is, a topology that cannot be expressed in terms of simple patterns (like ‘regular’ or ‘completely random’) but must include several degrees of freedom. 3. This topological complexity is translated into the global system behavior in the form of ‘emergent phenomena’, i.e. even simple local interaction rules lead to a performance of the whole system that is richer than the sum of local effects. 4. This influence of local feedbacks over the macroscopical behavior can be manifested, in particular, as nonlinearities in the operation of the processes N. Ganguly et al. (eds.), Dynamics On and Of Complex Networks, Modeling and Simulation in Science, Engineering and Technology, DOI: 10.1007/978-0-8176-4751-3 8, c Birkh¨ auser Boston, a part of Springer Science+Business Media, LLC 2009
134
S. Lozano
that shape the network itself (i.e. sudden emergencies of determined structural features are observed when a certain external parameter exceeds a certain threshold value). Regarding the fulfillment of this list of requirements by social networks, Vega-Redondo refers to the results of previous studies about social structure to confirm that social networks satisfy the first two. Following the same reasoning, we notice that the other two requirements (covering dynamic aspects) are repeatedly recognized in social phenomena, for instance, collective behavior and social mobilization [8, 9] (third point), or the emergence of hierarchical social structures from interactions at an individual level [10, 11] (fourth point). Once confirmed that social networks are indeed complex networks, in this chapter we will focus on the dynamic aspects of this complexity (the two later points in the check list above). More concretely, we will overview some of the recent research that addresses dynamics on and of social networks from the perspective of complex systems. The rest of the chapter is structured as follows. The second section is devoted to works dealing, as separate topics, with the analysis of social phenomena over static social networks and with the time evolution of the social structure. The third section focuses on the coevolution of social structure and phenomena, stressing the importance of this interplay from the complexity viewpoint. Finally, the last section summarizes the whole chapter and points out some ideas about the future evolution of the field.
2 Approaching the Dynamics on and of Social Networks Separately The majority of recent studies on social networks, from a complexity perspective, treat dynamics on and of social networks as different lines of research. In the first case, each node (social actor) is considered to be a dynamical system whose state evolves, in part, as a function of the topological features of the underlying static social substrate. Taking into account the intricate patterns (using the same expression as that in the Introduction) characterizing social networks, this scenario results in the nonlinear global behaviors already mentioned. In the second case, the whole network is considered to be a dynamical system with a topological state that evolves according to local rules. Investigations along this line have discovered that certain social rules at a local (individual) interaction level can forge some of the referred ‘intricate structural patterns’. In accordance with this scheme, we will address these two research lines separately. 2.1 Dynamics on Social Networks Topology is an important aspect that is always present in social dynamics [12]. Accordingly, social networks analysis has placed great importance on studying
Dynamics of Social Complex Networks
135
the influence of social networks and the individual’s role in the evolution of different social phenomena. A good example of this can be found in the research devoted to diffusion of innovations [13, 14]. This perspective has resulted in an in-depth knowledge of the most important structural characteristics of social networks and their influence on the behavior of the social actors, as has been recognized by scholars recently entering the field from complexity science [6, 7] (although some ‘traditional’ social network analysts claim that this effort by the ‘newcomers’ is not quite appreciable [1]). The incorporation of these ‘newcomers’ has not changed this orientation, but has reinforced it by contributing new analyses and modeling methodologies. The works ensuing from this combination of tools and perspectives have uncovered very relevant results. Some of them, for example, have related the emergence and resilience of cooperation in social groups with certain structural features of its social network, such as the degree heterogeneity [15, 16, 17] or the community structure [18]. Others have shown that scale-freeness and the small-world phenomenon can influence the consensus time of opinions in a population [19, 20] and even force scenarios with coexisting domains of opposite opinions [21]. In order to further understand the various tools and perspectives developed for explaining and modeling social networks, it is useful to resort to the exhaustive recent reviews on game theory [22], opinion dynamics [12, 23], language dynamics [12] or spreading phenomena [5]. Finally, as a sample of work addressing social dynamics on networks, the first chapter of Part in this book presents a work centered on the study of epidemic spreading [24]. In this work, the authors apply a mesoscopic (neither individual nor global, but intermediate) structural approach to predict and understand the spreading of an incurable disease (like HIV) over an empirical static network. First, they study the division into subnetworks or regions of a real social network of sexual contacts obtained by means of interviews. They also deduce qualitative predictions about infection spreading from the observed topological features. Second, they use a computational model to numerically contrast these predictions and design possible protection strategies suitable in this particular case. This work represents an important contribution to the literature on diseases spreading, since it highlights the analysis and visualization possibilities of mesoscopic approximations. 2.2 Dynamics of Social Networks The second separated approach that we are going to consider in this section is based on the study of network processes, that is, “series of events that create, sustain and dissolve social structures” [25]. Logically, this sort of study requires the use of time in addition to the structural description. However, in the past social networks analysis mainly focused on the study of static social networks and their influence over individual and collective behavior [6]. Borgatti [26] argues that one of the reasons behind such an orientation was the
136
S. Lozano
difficulty to obtain longitudinal empirical data. As has been pointed out in the Introduction, this scenario has changed lately with the increasing availability of large social datasets obtained from different information and communication technologies (email traffic, mobile phone calls, activities within peerto-peer systems, social media and social networking websites, etc.). Taking advantage of this new availability, scholars have developed different methodologies to understand the evolution of social networks using these data as input [25, 27, 28]. The (generally) large size of these datasets has given rise to especially interesting applications from a complex network perspective. On one side, we find works that try to deduce the basic mechanisms ruling social network processes. To do that, the authors analyze the evolution of these social datasets from a statistical point of view (macroscopic level) [4], focusing on their modular structure (mesoscopic or intermediate level) [29, 30, 31], or addressing key individual properties such as centrality (microscopic level) [32]. On the other side, following the example of seminal works by Watts and Strogatz [33] and Barab´ asi and Albert [34], datasets are also used to validate simple models based on single mechanisms that forge complex social-like features. In these works, empirical data are contrasted against the models’ simulations in terms of structural parameters at different topological scales. For example, some of these works present extensions of Barab´asi’s preferential attachment models and are focused on the degree distribution [35, 36]. Others present variants of the seceder model (where the mechanism conditioning topological evolution is based on each agent’s efforts to differentiate from the crowd) [37]. Finally, in Ref. [38] the authors propose a model where each agent is assigned a set of social values (representing different social attributes), and ties are established in the function of the social distances among agents (differences between their social attributes) and α, a parameter quantifying the homophily in the system (the individuals’ preference to establish and maintain links with other individuals they feel similar to). Interestingly, for different values of α the resulting social network presents different modular structures, while preserving general topological features of social networks (such as assortativity or high clustering).
3 Coevolution: Social Networks and Phenomena The separation into two different lines of research presented in the previous section has been the common approximation to social complex networks until recently. However, from real life observations we conclude that there is, normally, a certain interdependency among the evolution of both the social structure and the behavior of each one of the social actors [39]. Consider a friendship network as an example. On one side, friendship relationships (network links) are the path used, for instance, to cooperate, inform or imitate behaviors. Thus, the structure conditions different social processes related to
Dynamics of Social Complex Networks
137
these actions (like cooperation and diffusion of habits, for example). On the other side, the stronger the friendship relation among two people, the more probable that they introduce each other to new friends, modifying their mutual ‘friendship local neighborhood’ and, consequently, the whole structure of the network. In general, networks exhibiting such a feedback loop are called coevolutionary or adaptive networks [40]. This interdependency has clear implications from a complexity point of view. If structural patterns of social networks can induce nonlinearity in social phenomena evolving over them and, likewise, social network processes forge the emergence of complex structural features, a coevolutive scheme has to lead, necessarily, to scenarios exhibiting extremely rich behaviors. In their recent review on adaptive networks, Gross and Blasius [40] suport this assertion by reporting a list of four ‘hallmarks’ typically presented by adaptive networks in general (and social networks in particular): • • • •
Self-organization towards a dynamical critical state. Emergence of ‘specialized’ roles from an initially homogeneous population. Formation of complex global topologies (even from very simple local rules). Highly complex macroscopical dynamics due to the interaction of local states and topological complexity.
In the following, we will review some recent works that have addressed interesting sociological topics from an adaptive networks’ perspective. We will also identify some of the preced hallmarks in the referred examples. 3.1 Cooperation in Coevolutive Models In Ref. [41], Skyrms and Pemantle claim to “(..) create models that are more true to life (..)” by incorporating coevolution among structure and strategies in evolutive game theory models. Since then, some authors have proposed models where players’ strategies depend on the structure but, at the same time, they can modify the connectivity in their local neighborhood in order to maximize the payoff of a certain strategy (modifying, as an aggregated effect, the whole topology at the macroscopic level). Cooperation among individuals and, more concretely, the evolution of oneshot versions of the Prisoner’s Dilemma played over adaptive networks, have been intensively studied. In the results of these works, we can find some of the four ‘complexity hallmarks’ in coevolving networks listed previously. For example, in some cases the authors identify the formation of scale-free topologies (which present a power-law distribution) [42, 43] and the emergence of differentiated roles and hierarchies [42, 44, 45]. Moreover, regarding system dynamics, Ebel and Bornholdt [46], Eguiluz and co-workers [42] and Zimmermann and Eguiluz [44] report large avalanches of strategy changes when the system approaches the final state, identifying a sort of self-organized critical behavior. As a particular case, [47] analyzes a scenario where topological changes occur much faster than changes of individuals’ strategies. The authors find
138
S. Lozano
that the evolution of individual strategies in this situation no longer corresponds to the Prisoner’s Dilemma, but to a sort of coordination game, leading to a situation more favorable to cooperation. This result highlights the effect of separating the time scales of structural and individual dynamics. Notice that the scenarios considered in the previous section (with static networks or nonevolving nodes) can be seen as particular extreme cases of coevolving networks with completely separated time scales (i.e. one of the two time scales is so large compared with the other that it is not considered). In accordance with the importance of the relation between the two different time scales in coevolutive scenarios, we find (as we will see in the following subsections) several works that analyze this influence and that consider the cases with one aspect (network or individuals) static as bounding cases. 3.2 Communication and Diffusion of Information in Social Networks The interplay between communication within a population of socioeconomic agents and its underlying social structure, is an interesting social topic that deserves further study [48]. Taking business relationships as an example, an agent would presumably like to occupy a network position that is as strategic as possible in terms of information reception and processing (close to the other agents in terms of average distance or with a high betweenness, for instance). Moreover, since the socioeconomical environment is usually volatile (keeps changing), actors need to be continuously looking for better contacts and ‘fresh opportunities’ [49, 50]. Taking into account such a dynamical scenario, where the “who communicates with whom” and the social structure are strongly entangled, this issue is especially suitable to be studied from a coevolutive viewpoint. Following this perspective, we can find recent works focused on an individual’s movements across the social structure to reach strategic positions while minimizing linking costs [51, 52], or works targeting key positioned individuals [48]. Other authors investigate the impact of communication on social structure both quantitatively (more or less comunication) and qualitatively (different communication strategies) [53]. In general, the models employed in these works generate social structures that present complex patterns like modular structures [48]. Furthermore, some of these works report interesting behaviors of the modeled system like selforganization to states close to the transition between fragmented and ordered states [51], sharp phase transitions and resilience of the structure [49, 50]. 3.3 Opinion and Cultural Dynamics Opinion and cultural dynamics are other important social topics which have been addressed from a coevolutive viewpoint.
Dynamics of Social Complex Networks
139
Centola and co-workers [54] presented a coevolutionary version of Axelrod’s model on dissemination of culture [55]. As in the seminal model by Axelrod, they represent cultural traits and features by numerical values that are transmitted (copied) among individuals in contact, with the difference that the topology of interactions among individuals also evolves. More concretely, agents can erase and rewire links to neighbors with whom they have no common social trait (i.e. the affinity among them is 0). The model presents a complex relationship between heterogeneity and cultural diversity, in which a high diversity can reduce cultural group formation while simultaneously increasing social connectedness. The coevolutive approach has also been used in several recent works addressing opinion formation processes. In Refs. [56, 57, 58, 59], authors propose coevolutive versions of the two-state voter’s model [60] to study consensus in populations’ opinions. In this kind of model, interactions between agents are enhanced or penalized (or even broken) according to whether they succeed in reaching an agreement or not. From a complex network point of view, these models are used to explore the transition between different states, with a special interest in the emergence and duration of metastable states reached before the consensus. Another model of opinion formation based on a coevolutive approach that has received considerable attention is proposed in [61]. This model is especially interesting regarding time-scale separation. In each time step, a rewiring (structural change) or an opinion imitation (evolution of local state) occurs with certain probabilities φ and 1 − φ, respectively. Therefore, by tuning φ the authors can easily recover one of the two extremal single-evolving cases (static network or nonevolving nodes) or travel along different intermediate scenarios. By studying the whole range of possible situations, the authors find that the model undergoes a continuous phase transition as φ is varied, from a regime in which opinions are highly diverse to one in which most individuals hold the same opinion. 3.4 Spreading Phenomena Last but not least, there is a growing literature on spreading (epidemics, diseases, infections) phenomena from an adaptive network perspective. We find an example of this in the series of works proposing and analyzing an adaptive version of the SIS (Susceptible-Infected-Susceptible) model, where susceptible individuals try to avoid infection by erasing their links with the infected population [62, 63, 64]. This sort of work analyzes how different levels of rewiring modify the dynamics of the adaptive SIS model (note that this implies, once again, studying the effect of having separated time scales). One common observation is that high levels of rewiring lead to the self-organization of the susceptible population into a unique, densely connected cluster. In the case of eventual infection of an individual in the cluster, this sort of organization favors a rapid spreading of the disease, which is seen as an avalanche of state change from a macroscopic viewpoint.
140
S. Lozano
We also mention the work presented in [65], where the authors propose an innovative coevolutionary model of HIV infection spreading through the use of dynamic complex networks. On one hand, the state of each individual (her health situation) is determined by means of a Markov process that takes into account both topological data (such as the number of infected neighbours) and information regarding the HIV infections (probability of infection and progression from HIV to AIDS, for instance). On the other hand, the social structure of the population is defined at each time step in a function of certain statistical features and the state of nodes (nodes with AIDS are removed from the network). The authors find a good correspondence between simulation results and real demographic historical epidemiological data from the United States. Moreover, this epidemiological prediction model could be integrated in related decision support systems (regarding anti-drug policy, for instance).
4 Conclusions Summarizing, the analysis of social networks’ dynamics has been revealed to be an outstanding application of the complex network theory, as is demonstrated by the huge (and increasing) amount of work developed in the field during recent years. Two factors have contributed definitively to this success: the availability of large longitudinal social datasets obtained from communication technologies, and the massive integration of scientists from complexity science (especially physicists) to social networks analysis. In this chapter, we have provided a general view of recent research in this area. Following the evolution of the literature in the field, we have first referred to works treating dynamics on and of social networks separately, and later have addressed a more recent approach integrating both sorts of dynamics in a coevolutive scheme. In both cases, but especially in the last one, we have also echoed the results reported by authors regarding some of the points proposed by Vega-Redondo’s check list in the Introduction (emergence of nontrivial structural patterns, nonlinear macroscopical behaviors induced by local processes, etc.). When talking about coevolutive models, we have also stressed the effect of having more or less separated time scales for dynamics on and of social networks. Finally, regarding the future evolution of the research on the dynamics of social complex networks, it is expected to keep growing, as the availability of datasets is increasing and the field continues to attract scholars. Nevertheless, to ensure this growth, issues like the ethical implications of social data collection and analysis [66, 67], the integration among different disciplines and perspectives within the aforementioned science of networks should be seriously addressed.
Dynamics of Social Complex Networks
141
References 1. Freeman, L.C.: The Development of Social Network Analysis: A Study in the Sociology of Science. Empirical Press, Vancouver (BC Canada) (2004). 2. Scott, J.: Social Network Analysis: A Handbook. SAGE Publications, London (2000). 3. Wasserman, S., Faust, K.: Social Networks Analysis: Methods and Applications. Cambridge University Press, New York (1994). 4. Holme, P., Edling, C.R., Liljeros, F.: Structure and time evolution of an Internet dating community. Social Networks 26, 155–174 (2004). 5. Vega-Redondo, F.: Complex Social Networks. Cambridge University Press, New York (2007). 6. Watts, D.J.: Six Degrees: The Science of a Connected Age. W. W. Norton & Company Inc., New York (2003). 7. Barab´ asi, A.-L.: Linked: The New Science of Networks. Perseus Publishing, Cambridge (USA) (2002). 8. Coleman, J.: Foundations of Social Theory. Harvard University Press, Cambridge, MA (1990). 9. Gould, R.V.: Collective action and network structure. American Sociological Review 58 (2), 182–196 (1993). 10. Gould, R.V.: The origins of status hierarchies: A formal theory and empirical test. American Journal of Sociology 107 (5), 114378 (2002). 11. Epstein, J.M.: Generating classes without conquest. In: Generative Social Science: Studies in Agent-Based Computational Modeling. Princeton University Press, Princeton, NJ (2007). 12. Castellano, C., Fortunato, S., Loreto, V.: Statistical physics of social dynamics. Reviews of Modern Physics (Accepted) 348 (2008). 13. Rogers, E.M.: Diffusion of Innovations (5th ed.). Free Press, New York (2003). 14. Valente, T.W.: Models and methods for innovation diffusion. In: Carrington, P., Scott, J., Wasserman, S. (ed) Models and Methods in Social Network Analysis. Cambridge University Press, New York (2005). 15. Abramson, G., Kuperman, M.: Social games in a social network. Phys. Rev. E 63, 030901 (2001). 16. Duran, O., Mulet, R.: Evolutionary prisoners dilemma in random graphs. Physica D 208 (3–4), 257–265 (2005). 17. Santos, F.C., Pacheco, J.M., Lenaerts, T.: Evolutionary dynamics of social dilemmas in structured heterogeneous populations. Proc. Natl. Acad. Sci. 103, 3490– 3494 (2006). 18. Lozano, S., Arenas, A., Sanchez, A.: Mesoscopic structure conditions the emergence of cooperation on social networks. PLoS ONE 3(4): e1892 doi: 10.1371/ journal.pone.0001892 (2008). 19. Castellano, C., Loreto, V., Barrat, A., Cecconi, F., Parisi, D.: Comparison of voter and Glauber ordering dynamics on networks. Phys. Rev. E 71 (6), 066107 (2005). 20. Sood, V., Redner, S.: Voter model on heterogeneous graphs. Phys. Rev. Lett. 94 (17), 178701 (2005). 21. Castellano, C., Vilone, D., Vespignani, A.: Incomplete ordering of the voter model on small-world networks. Europhys. Lett. 63 (1), 153158 (2003). 22. Szab´ o, G., F´ ath, G.: Evolutionary games on graphs. Phys. Rep. 446 (4–6), 97–216 (2007).
142
S. Lozano
23. Stauffer, D.: Sociophysics Simulations II: Opinion Dynamics. arXiv:physics/ 0503115v1 [physics.soc-ph] (2005). 24. Bjelland, J., Canright, G., Engø-Monsen, K., Remple, V.P.: Topographic spreading analysis of an empirical sex workers network. In: (ed). Springer, Berlin (2008). 25. Doreian, P., Stokman, F.N. (ed): Evolution of Social Networks. Routledge, London (1997). 26. Borgatti, S.P.: The State of Organizational Social Network Research Today. Dept. of Organization Studies. Boston College, Boston, MA (2003). 27. Snijders, T.A.B.: Models for longitudinal network data. In: Carrington, P., Scott, J., Wasserman, S. (ed) Models and Methods in Social Network. Analysis. Cambridge University Press, New York (2005). 28. Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, Oxford (2003). 29. Palla, G., Barab´ asi, A-L., Vicsek, T.: Quantifying social group evolution. Nature 446 (5), 664–667 (2007). 30. Eckmann, J.-P., Moses, E., Sergi, D.: Entropy of dialogues creates coherent strutures in e-mail traffic. PNAS 101 (40), 14333–14337 (2004). 31. Onnela, J.-P., Saram¨ aki, J., Hyv¨ onen, J., Szab´ o, G., Lazer, D., Kaski, K., Kert´esz, J., Barab´ asi, A.-L.: Structure and tie strengths in mobile communication networks. PNAS 104 (18), 7332–7336 (2007). 32. Braha, D., Bar-Yam Y.: From centrality to temporary fame: Dynamic centrality in complex networks. Complexity 12 (2), 59–63 (2006). 33. Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998). 34. Barab´ asi, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999). 35. Jin, E.M., Girvan, M., Newman, M.E.J.: Structure of growing social networks. Phys. Rev. E 64, 046132 (2001). 36. Roth, C.: Generalized Preferential Attachment: Towards Realistic Social Network Models. ISWC 4th Intl Semantic Web Conference. (2005). 37. Gr¨ onlund, A., Holme, P.: Networking the seceder model: Group formation in social and economic systems. Phys. Rev. E 70, 036108 (2004). 38. Bogu˜ na, M., Pastor-Satorras, R., D´ıaz-Guilera A., Arenas A.: Models of social networks based on social distance attachment. Phys Rev E 70, 056122 (2004). 39. Lazer, D.: The co-evolution of individual and network. J. Math. Sociol. 25, 69108 (2001). 40. Gross T., Blassius, B.: Adaptive coevolutionary networks: A review. J. R. Soc. Interfac 5 (20), 259–271 (2007). 41. Skyrms, B., Pemantle, R.: A dynamic model of social network formation.