Networks

Poster Guideline: each poster has a reserved space of 4 feet horizontal by 8 feet vertical.

	Himanshu Agrawal	Vertex Connectivity Distribution in Networks Constructed from Gene Expression Data
	We study properties of networks constructed from gene expression data obtained from many types of carcinomas. Under appropriate conditions the networks show a connectivity distribution characterized by a power-law behavior in the tails with an exponent of unity. This implies that these networks are extremely inhomogeneous and contain few very highly connected genes and a large number of genes with low connectivity. This has important consequences in the study of various genetic networks and associated biological processes. These results also imply that various carcinomas are consequence of malfunction of a few genes that regulate the expression of a large number of other genes.

	Maximino Aldana-Gonzales	Boolean Dynamics of Networks with Scale-free Topology
	I implement the scale-free topology into the Boolean network model proposed by Stuart Kauffman in 1969 to describe generically the dynamics involved in the processes of gene regulation and cell differentiation. In the original Kauffman model, the network topology is homogeneously random and the parameters of the model have to be fine-tuned in order to achieve the dynamical stability required by living organisms to perform with reliability. Such fine-tuning is contrary to experimental observations. However, when the scale-free topology is implemented into the Kauffman model, stable dynamics are obtained without fine-tuning the parameters of the model. Additionally, by analyzing how perturbations propagate through the network, one can conclude that the scale-free topology provides the network with both the dynamical stability and the evolvability essential for living organisms to perform with reliability and at the same time to adapt and evolve. It seems that the scale-free topology favors the evolution and adaptatioin of the network functioning.

David L. Alderson

Cascading Failures in Congestion-Sensitive Flow Networks

This research lends perspective and insight into the behavior of cascading failures in infrastructure networks through the study of congestion-sensitive processing systems. Using an approach based on ideas from dynamical systems and network flow problems, we develop an analytical framework appropriate for the study of large-scale failure dynamics in data communications and transportation systems. We illustrate how congestion-sensitivity at the level of the individual node results in unstable local behavior and creates the potential for global cascading failure. We describe optimal control policies that use admission control to maximize system performance while preventing congestion collapse.

While the development of this theoretical framework is motivated by a desire to understand the long-range problem of building robust infrastructure systems, the insight from this research applies to significant problems of immediate consequence. We show how simple parallel processing models appropriately capture the load balancing challenges of certain computer systems. We also describe how systems comprised of components in tandem are an appropriate representation for interstate highway systems and railroads. Throughout this research, particular attention is placed on the identification tensions and tradeoffs in the operation and design of these complex networks as well as on the development of robust management strategies.

	Marian Anghel	Markets and Competition on Social Networks
	We study the effects of inter-agent communication on the evolution of a market within the minority-game framework. The inter-agent communications create a complex (social) network with small-world character which forms the substrate for another highly dynamic, adaptive, and directed network, the action network. The latter is defined by those inter-agent communication links on the substrate along which the passed information/prediction is acted upon by the other agent. We define a basic agent-agent communication scenario in which the agents use a reinforcement learning algorithm to select the best predictor among the neighboring agents it is linked to, including himself. We show that when the substrate network is highly connected, the action network develops high degree hubs, defining a robust leadership structure, with a scale-free character, which then dominates the evolution of the game. We also show that, in certain realistic parameter ranges, the agents can spontaneously generate a high degree of cooperation, facilitated by the underlying information network, making the market almost maximally efficient.
	Co-Authors: Z. Toroczkai, K. Bassler and Gy. Korniss

	Ping Ao	Calculating Robustness of Gene Regulatory Network in Phage lambda Life Cycle And Four Component Theory of Complex Network Dynamics
	The bacteriophage lambda is one of the few living organisms whose behaviors, both qualitative and quantitative, have been systematically characterized experimentally. It is an excellent test ground for our understanding of biological behaviors as an integrated network on the whole organism level. In order to mathematically understand the quantitative behavior of the network, we have developed a new framework of stochastic nonlinear network dynamics. We have found that under a fairly general condition, any first order stochastic differential equations can be rewritten, via a gauged singular decomposition, into the normal form, where there are four components: the drive, the transverse force, the dissipation, and the stochastic force. The robustness of the network is predominatedly determined by the drive. The drive also determines the destination of the network in which powerful statistical mechanical methods can be used to find numerous properties of the network. Based on the biochemical model and this developed theory for the dynamical structure of complex networks, we have performed a theoretical study on the phage lambda life cycle. We find a quantitative agreement between the theoretical calculation and the experimental observation in the protein concentration level, the lysis frequency in the lysogen culture, and the lysogenization frequency for the recently published mutants of OR. We also find the desired robustness for lambda genetic switch. This is the first successful example in the calculation of biological function of a real living organism. It indicates that not only we have a correct understanding of underlying chemical and physical processes we also start to reach the quantitative accuracy in predicting complex systems behaviors
	Co-Authors: L. Hood, L. Yin, and X.-M. Zhu

	Marcio Argollo de Menezes	Fluctuations in network dynamics
	Many natural and technological networks act like conduits for various dynamical processes, ranging from mass transfer by chemical reactions in the cell to packet transfer on the Internet. While the topological properties of such networks have been intensely studied in the past years, the characterization and classification of dynamical processes taking place on links and nodes of such networks is still an undeveloped task. We collected data on the time dependent activity of five natural and technological networks, finding that each system obeys a unique scaling law characterizing the coupling of the time averaged signal measured on a node i with about the average, which can be written as s_i~ <f>^a. We show that the observed scaling exponent a is determined by the competition between the system's internal collective dynamics and changes in the external environment, allowing us to predict the relevant scaling exponents. As high can lead to dynamical bottlenecks and jamming, these findings impact the predictability and failure prevention of transportation networks.
	Co-Authors: A.-L. Barabási

	Gil Benkö	GENERATING PREBIOTIC CHEMISTRIES FOR THE STUDY OF GENERIC GRAPH PROPERTIES
	We use a Toy Model of chemistry to analyze chemical reaction networks (CRN) as they occur in our metabolism, in industrial processes and in the atmosphere. Molecules are represented in terms of usual structural formulae for an extremely simplified quantum mechanical energy calculation, chemical reactions are implementated as graph rewriting rules corresponding to reaction mechanisms. A CRN is thus generated from an initial list of molecules transparently and close to chemical reality so that the generic graph properties of very large CRNs can be investigated. In particular, we study here the degree distribution and cliquishness of CRNs arising from models of prebiotic chemistry. Our simulations show that chemical networks do not fall into a single class of the small-world network classification scheme by Amaral et al.
	Co-Authors: Christoph Flamm, Peter F. Stadler

	Luis M.A. Bettencourt	Tipping the balances of a small world how accessing information conditions the structure of social networks
	Recent progress in the large scale mapping of social networks is opening new quantitative windows into the structure of human societies. These networks are largely the result of how we access and utilize information. Here I show that a universal decision mechanism, where we base our choices on the actions of others, can explain much of their structure. Such collective social arrangements emerge from successful strategies to handle information flow at the individual level. They include the formation of closely-knit communities and the emergence of well-connected individuals. The latter can command the following of others while only exercising ordinary judgment.

	Ashish Bhan	Global and local connectivity properties of some biological networks: implications of duplication models
	A class of dynamical models of network growth is proposed to explain the structure of some biological networks. These partial duplication models have previously been shown to generate scale-free connectivity, and may be important for gene regulatory networks. Several other network growth models, however, also produce the global property of power-law distribution of connectivity. Recently, local properties, like "modularity" or "hierarchical organization" have been identified as key systems properties of biological networks. Here we study both the global and local properties of networks under partial duplication growth. We find that these models, unlike most others, produce global and local properties that match the networks derived from gene expression data very well. We study networks derived from gene expression time-series data using a simple, linear model, and examine data from other biological and man-made sources.
	Co-Authors: David J. Galas and T. Gregory Dewey

	Denis Boyer	Slow Dynamics in Complex Networks
	We show that the nonequilibrium dynamics of systems with many interacting elements located on complex networks can be much slower than on regular networks. As an example, we study the growth of regions of consensus in a model of social agents who have to choose between two conventions and are located on a Watts-Strogatz network. Physically speaking, this problem is equivalent to study the phase ordering dynamics of the Ising model after a quench in the ferromagnetic phase at zero temperature. In one and two dimensions, small-world features produce dynamically frozen configurations, disordered at large length scales, analogous of random field models. This picture differs from the common knowledge (supported by equilibrium results) that assortative (or ferromagnetic) short-cuts connections favor order and uniformity. If a small "thermal" noise is present, total order can be abruptly achieved after a long period of stagnation. Small systems reach consensus faster than large ones. At intermediate times, more densely connected systems evolve slower; however, they are more prompt to jump to ordered states at large times. We briefly discuss some implications of these results on the dynamics of social changes.
	Co-authors: Octavio Miramontes

	Alvaro A. Cardenas	Worm Detection in Complex Networks
	Worms are programs that self-propagate across a network by exploiting security flaws in widely-used services offered by vulnerable computers in the network. In order to locate the vulnerable computers, the worm probes different computer addresses at the specific port number of the service it is looking for. By exploiting the security flaw in the service, the worm usually can execute arbitrary code with elevated privileges, allowing it to copy and execute itself in the compromised machine. In order to reproduce, the worm scans for new vulnerable machines from each new compromised computer. We want to automatically detect a worm, via change detection statistics, as soon as possible in order to minimize the number of compromised hosts. We focus on the fact that the self propagating code will try to use specifi vulnerabilities that can be identified with certain port numbers. So we assume that the traffic monitoring variable is the connection attempts (probes) to a given TCP/UDP port number(s). We also assume most of the times a probability distribution on the traffic observations. We create different scale-free network topologies with a delay of one unit step per edge for simulating the communication among different nodes. The simulations can be placed in the framework of the distributed Intrusion detection system. It is observed that in scale-free networks a very small set of the highly connected nodes is sufficient for detection and aggregation only improves the performance of the nonparametric statistics. If we select sensors at random or if we monitor a random network, then aggregation is very important for detection. Most of the parametric statistics perform comparably under a wide variety of conditions. The best performance on average is always obtained by parametric statistics measuring a change in the mean. When the traffic deviates significantly from the assumed traffic distribution, the best performance is produced by the nonparametric statistics. The variation of the detection delay vs the average time for an alarm was also very robust in scale-free networks, whereas in random networks the false alarm increases severely the detection delay.
	Co-Author: John S. Baras

	Shr-Jing Chen	The Preisach Model for Magnetic Hysteresis
	In this poster, a brief description of hysteresis is first given of modelling ferromagnetic systems by the Preisach approach . Then, assuming values for the coefficients in the model, hysteresis curves are computed. To test the ability of the Preisach model to analyze the experimental data, different levels of random error are used to modify the computed curves in order to simulate measured data. This "data" is then inverted to determine the Preisach distributions and their associated hysteresis curves. Comparison to the "noise-free data" shows that the model is fairly robust when used for analyzing measurement. Finally two characteristic properties of the Preisach model are discussed :congruency and "wiping-out"(or return point memory). The restrictions which these inherent mathematical properties of the model impose on representing real material behavior are pointed out .

	Margaret S. Cheung	Solvation in Protein Folding Analysis, Combination of Theoretical and Experimental Approaches
	An effort of combining theoretical analyses and protein engineering methods has been made to probe the folding mechanism of SH3 utilizing an Energy Landscape Theory and novel Ö-value analysis. Particularly emphasis was given to core residues and the effect of desolvation during the folding event. Experimentally that was probed by replacing the core valines by isosteric threonines. These mutations have the advantage of keeping core structurally invariant while affecting the core stability relative to the unfolded state. Although the valines that form the core appear spatially invariant, the folding kinetics of their threonine mutants varies, indicating their different participation in the transition state ensemble. Theoretical studies predicted the distribution of folding kinetics of threonine mutants without previous knowledge of the measured rates. This initial success encourages further investigations of providing molecular details behind these macroscopic phenomena.
	Co-Authors: A. M. Fernandez-Escamilla, M. C. Vega, M. Wilmanns, J. N. Onuchic, L. Serrano.

Sehyo Charley Choe

Pros and cons of network connectivity in a competitive population

In today’s competitive world, the desire for individual gain may sometimes seem at odds with any desire to benefit the common good. While it is hoped that globalization will bring collective benefit, we have also been made aware of the dangers that can result from ‘action at a distance’ through such global network connectivity. Here we provide a simple, yet highly non-trivial, model to investigate the effects of global connectivity on individual gain and the common good. We find that increasing the connectivity among members of a competitive population can lead to a breakdown of the class-structure associated with individual wealth or success. However it is also accompanied by an increase in overall wastage. These two effects saturate at surprisingly low values of the connectivity, exhibiting properties typically associated with magnetization in physical systems.

Our work specifically considers the role of connectivity in BAR (Binary Agent Resource) games - in particular, the El Farol bar problem of Brian Arthur and the binary variant introduced subsequently by Challet and Zhang [1]. Our work was inspired by Ref. [2], but contains a number of important generalizations. Agents are connected with probability p, and then allowed to exchange information about each others’ strategies when deciding their actions. This simple setup leads to several interesting changes in global behavior: for example, in the wealth distribution, intrinsic volatility and efficiency in allocating the global resource. Our results can be explained quantitatively using an extension of the Crowd-Anticrowd theory [3], in which agents using correlated/anticorrelated strategies form crowds/anticrowds and then act in the same/opposite way.

Co-Authors: Sean Gourley, Pak-Ming Hui, Neil F Johnson

	Gerardo Chowell	Halting Epidemics in Proximity Networks
	We present an efficient intervention strategy for stopping the spread of epidemics in proximity networks. Proximity networks are obtained from integrating time-dependent spatial contact graphs over a finite period of time. We argue that when the incubation period of the disease is much longer than the time scale for the dynamics of the contact graphs, the epidemics can equivalently be studied as on a static network, given by the proximity graph. Given a giant component in the proximity network, we identify a percolating critical substructure in it, which is responsible for the fast spread of the disease. We show that through vaccination of the nodes, which make up this substructure, the giant component is broken in a rather efficient way, and the spread of the disease is stopped.
	Co-Authors: Z. Toroczkai

	Reuven Cohen	Scale free networks - structure and applications
	Networks with a broad degree distribution, and in particular scale-free networks were shown to be common in many natural and artificial systems. We discuss the structural properties of random scale-free networks. We show the average distance between nodes is smaller in scale free networks than in regular (Erdos-Renyi) random networks. We discuss percolation properties of scale free networks and show that a class of scale free networks are resilient to random breakdown but sensitive to intentional attacks on the most highly connected nodes. We show that even for non-resilient networks the percolation critical exponents are of a different universality class than regular high dimensional percolation. We give applications of the obtained results for designing robust networks, and also a novel immunization strategy.
	Co-Authors: Daniel ben-Avraham and Shlomo Havlin

	Rich Colbaugh	Analysis of Complex Networks Using Limited Observations
	Complex networks have attracted considerable attention in the scientific community, and in popular culture, in recent years. Networks provide a natural framework for modeling and analyzing a wide range of systems in nature and society, and their behavior is often quite interesting and surprising. For instance, it is by now well-known that many complex networks exhibit a "robust, yet fragile" character, and various analysis frameworks (e.g., self-organized criticality, highly optimized tolerance, complex additive systems) have been proposed to explain this phenomenon. This paper considers a much less studied, but equally important, property of complex networks: despite the complexity of these systems, it is often possible to extract "deep", quantitative information about them using only limited, qualitative observations of their behavior. We offer an explanation for this property, and propose a mathematically rigorous, systematic process for extracting the desired information. With a system modeling and analysis framework in hand, we turn to a series of "real world" examples which illustrate the basic ideas and demonstrate the power of the proposed methodology. We begin by showing that it is possible to accurately and robustly identify important agents and collaborating agents in organizations by studying only the patterns of agent communication (e.g., who sends whom email) without regard to the content of the communication; the particular application of these results to terrorist and criminal networks is also explored. This basic result is extended to provide a method of identifying, and predicting, the occurrence of important events within social networks. We then consider biological networks, and present algorithms which use only network topology data and basic evolutionary principles to accurately identify "lethal" genes in the gene regulatory network of the yeast S. cerevisiae and functional modules in the metabolic network of the bacterium E. coli .
	Co-Authors: Kristin Glass, and Mauro Trabatti

	Horace Crogman	States and Transitions in Floppy Coupled Rotor Models
	It is well known that when the dipole moment of a symmetric rotor lies along the main symmetry axis it gives a comparatively simple spectrum. However, in a floppy molecular system made of two coupled rotors there can be reorientation of axes resulting in a multiplicity of structure and a more complex spectrum. This is further complicated by level splitting depending sensitively on coupling strength. We have investigated effects on levels and the spectrum over different types of coupling and a range of coupling strength. States range from a weakly coupled angular momentum bases to more Born-Oppenheimer-like states, which we label as Body-Oriented-Angular or BOA-constricted bases. Analogous effects were first investigated by Seaton, Fano, Jungen, Harter and Patterson in simpler cases involving a diatomic rotor coupled to an electron varying between high Rydberg orbitals in a low l-uncoupling limit and l-uncoupled molecular orbitals. Here we consider two full quantum rotors between analogous limits of coupling. Considerations of molecular symmetry and goodness of quantum labels also play an important role in sorting out the dynamics and spectral effects.
	Co-Authors: William G. Harter

	Lawrence David	Learning a Simulated Genetic Network using Dynamic Bayesian Networks
	We present a study on the efficaciousness of constructing dynamic Bayesian networks in order to reverse-engineer genetic networks from time-series data. Because large data sets of gene expression in known networks is relatively scare, we simulate a bistable genetic network and employ it in the creation of stochastic time-series data sets. We utilize a greedy search algorithm in the determination of our DBNs, due to the exponential quantity of possible networks for any given set of genes. Using this greedy algorithm, as well as our synthetic data, we investigate how factors such as data set size, discretizations choices, and network size and connectivity ultimately influence successful network recovery with DBNs.
	Co-Authors: Anshul Kundaje, Chris Wiggins

	Julio S. Espinoza Ortiz	Network Model for Trabecular Bones
	Networks of conductances are used to study transport phenomena in disordered systems. Applications to disordered networks cover dielectric breakdown , metal insulator transitions, and brittle fracture in disordered solids. So far, such models have provided insights on critical phenomena, scale-invariant disorder, and size dependence of the system. We present an expression for the mean breakdown strength of electrical and elastic networks. As expected it depends on the size of the system, the fraction of remained elements on the network and the critical exponent. We carefully examine these dependence, computing the critical indices and connecting this theory with the Finite Size Scaling Theory. Finally, It is also shown that disordered elastic and electric networks exhibits analogs of several known mechanical features of trabecular bones. We can show the existence of a stress backbone and derive a relationship between BMD (Bone Mineral Density) and bone Strength. These tools can be used to effectively manage osteoporosis treatment.
	Co-Authors: Chamith S. Rajapakse and Gemunu H. Gunaratne

	Annette M Evangelisti	A tractable method for computing the distribution of receptor-ligand aggregation size
	Our goal is to provide a tractable framework to study large and complex multivalient ligand-binding systems on the surface of cells. This research will further the understanding of cell signaling. An important factor in the chain of events that results in cell signaling is the number of receptors aggregated on the surface of a cell. The usual methods for determining the distribution of aggregates over time exceeds the computational power and storage capacity of current computers and are not valid for systems with small numbers of molecules. The specific aim of this work is to provide a tractable algorithm that gives the distribution of aggregate size over time, and is valid for small and large numbers of molecules. We will verify the proposed algorithm by comparing the predicted data to experimental and analytical results. We will also prove the polynomial running time of the algorithm. The computer code will serve as a template for building software to predict the distribution of aggregates over time for large and complex problems involving multivalent ligand and multivalent receptors.
	Co-Authors: William S Hlavacek

	James R. Faeder	Combinatorial Complexity in Receptor Signaling
	Cells are exquisite detectors that constantly monitor their environment through the use of cell surface receptors. To date almost all the effort in cell signaling has been to identify the molecules that participate in specific signaling cascades and to understand their interactions. The ultimate goal of the work in cell signaling, however, is to understand how the components in a signaling cascade function together as a system to direct cellular responses to changes in the extracellular environment. The first problem one is faced with in modeling a signaling cascade is how to deal with the large numbers of ways in which the component molecules may combine and modify each other. For example, we have recently developed a model for the initiating events in signal transduction through the immune recognition receptor, FcåRI, which is the primary receptor involved in allergic response. The model involves only four components, a bivalent ligand, the receptor, and two tyrosine kinases, yet the known interactions among these components gives rise to at least 354 different possible signaling complexes that are coupled through a network of 3680 chemical reactions. The model makes accurate predictions of experimental timecourses of receptor and kinase phosphorylation and also more subtle properties such responses to changes in the binding properties of the ligand and the kinases. It is also capable of much more complex behavior than can be measured using standard experimental approaches. Here we describe several different approaches we have taken to characterize complex signaling networks. We ask the following questions: Are all chemical species and reactions in the network equally .important.? What measures should be used to characterize importance? Can reduced dimensional models be developed without compromising predictive capabilities? What assumptions are implicit in more conventional modeling approaches and are these justified? When can the behavior of such networks be characterized by a simple pathway description? Our poster will present at least partial answers to all of these questions.
	Co-Authors: Michael L. Blinov, William S. Hlavacek, Carla Wofsy, Antonio Redondo., and Byron Goldstein

	Michael A. Gilchrist	Analyzing Proteome Structure: A Statistical Approach
	While numerous high-throughput datasets on yeast protein-protein interactions exist, the error rates in these datasets can be quite high. Consequently, it is difficult to know how to interpret such data when analyzing proteome structure. To address these problems we have developed a simple bayesian statistical framework for (a) estimating the error rates associated with a particular dataset, (b) interpreting experimental results in light of these error rates and (c) integrating information across datasets. Comparing our results to a reference set of known interactions we find that we can accurately calculate the probability two proteins interact based on the available experimental data.
	Co-Authors: L.A. Salter, A. Wagner

Kristin Glass

Complex Systems Analysis of Biological Networks

Complex networks provide a natural framework for modeling and analyzing a wide range of systems in nature and society, and recent advances have greatly increased the analytical power and practical utility of this framework. Networks provide a global perspective on the system which complements and unifies the local results obtained in more traditional "reductionist" studies, and this perspective can be quite informative. Very recently, some of these complex networks concepts have been applied to biological systems. For example, preliminary studies have been conducted which suggest that the topology of biological networks may contain useful information regarding the robustness and functionality of the associated biological systems. While these studies are important and intriguing, fully exploiting the potential of network-based analysis in biology will require approaches which appropriately represent and investigate the dynamics of these complex systems.

We have developed a dynamical approach to modeling and analyzing complex networks and have applied the methodology to technological and social systems in a series of national security applications; recently, we have begun to study biological networks using this approach. System modeling is performed within an agent-based framework, with each agent possessing a hybrid dynamical system structure and interacting with other agents through the appropriate complex network. Our approach to analyzing these complex networks of agents is mathematically rigorous, and has allowed interesting results to be established for broad classes of systems. For instance, we have shown that systems whose evolution is driven by response to previous failures and adoption of innovations will generically exhibit a robust, yet sensitive character and will reach configurations at which "deep" information regarding their behavior can be extracted using only limited observations. The implications of these results for biological network modeling and robustness analysis are intriguing. For instance, using this approach, we have identified essential genes in the gene regulatory network of the yeast S. cerevisiae using only network topology data and basic evolutionary principles; 75% of the genes we predicted to be essential are characterized as "lethal" in the Saccharomyces Genome Deletion Project data set, with the remaining 25% being labeled "unknown." We have developed algorithms which, using only topological information, separate the metabolic network of the bacterium E. coli into functional modules which are in excellent agreement with the functional modules identified in biochemical and genetic studies. We have also applied these algorithms to the protein interaction network of S. cerevisiae and identified functional complexes which are in agreement with the complexes identified using tandem-affinity purification and mass spectrometry.

Co-Authors: Rich Colbaugh and Mauro Trabatti

	Kwang-Il Goh	Proteome-wide analysis of the yeast protein interaction network and its in silico model
	Understanding of how the protein interation networks of living organisms are organized might be the first stepping stone in unveiling how life works on a fundamental ground. Here (i) we integrate the protein interaction data from various publicly available sources resulting in 16174 interactions between 5002 proteins, which is the largest ever analysed. (ii) Through this dataset, we construct the protein interaction network (PIN) and investigate its topological features. We find that 98% proteins form a giant cluster and the mean degree is about 6.44. Besides, we measure various quantities characterizing its topological features, obtaining the assortativity coefficient r~-1.4, and the clustering coefficient C ~ 0. 13. We also investigate the degree distribution, the degree-degree correlation function, the hierarchical modularity, etc. The measured values of such quantities are compared with those from other datasets. (iii) Moreover we introduce an in silico model for the PIN evolution. While existing in silico models are successful in explaining only a part of the topological features we obtained, our model reproduces successfully the topological features mostly.
	Co-Authors: B. Kahng, and D. Kim

	Debra S. Goldberg	Assessing Experimentally-Derived Protein Interactions Using Network Topology
	Determining the function of genes and proteins is one of the greatest challenges in biology today. Many of the high-throughput experimental methods developed recently to address this need are both expensive and error-prone. Although the uncertain nature of these experimentally-derived networks necessarily impacts network-derived inference, the function of uncharacterized proteins can still be inferred from them. While the data may be susceptible to errors, the structure of the underlying biological system produces patterns that are reflected in the overall observed network topology. The topology of genomic networks has been studied considerably in recent years. This knowledge of network topology can be used to improve confidence measures for protein interactions. While much analysis has been done on network topology, little has been done to use network properties to improve our understanding of individual edges in experimentally-derived graphs. We have shown that the network properties of neighborhood cohesiveness [8] and degree distribution can both be used to improve confidence assessment of error-prone networks such as yeast two-hybrid protein interaction data. By ascertaining how well each protein-protein interaction (edge) fits the pattern of the network, we stratify even those edges with identical experimental evidence. We propose that such techniques would be applicable to many biological networks, and promises to improve the quality of inference from error-prone genomic networks.
	Co-Authors: Sharyl Wong, and Frederick P. Roth

	Sebastián Gonçalves	A Social Model for the Evolution of Sexual Transmitted Diseases
	We have introduced recently a model for the spread of sexually transmitted diseases, in which the social behavior is incorporated as a key factor for the further propagation of the infection. The system may be regarded as a society of agents where in principle anyone can sexually interact with any other one in the population. The social behavior is taking into account by means of what we call the promiscuity parameter, which defines the per individual daily probability of going out to look for a sexual partner, abandoning its eventual mate.In terms of this parameter, we find a critical behavior for the evolution of the disease. That is, for a semi-Gaussian distribution of population promiscuity of width $p$, the critical value has the following relation with the disease infectivity $\beta$ and the infective period $\tau$ (in years): $p^{2}_{c}\beta\tau = 0.65$ in the all singles case. This value of the epidemic threshold is below the classical epidemiologist prediction, given by the basic reproductive number, $R_0 = 1$ [2]. Different distributions for the population promiscuity are tested, showing that the threshold is weakly sensitive to them.
	Co-Authors: M Kuperman, M. Ferreira da Costa Gomes

	Venkatesh Gopal	Small Worlds: How and Why
	We investigate small-world networks from the point of view of their origin. While the characteristics of small-world networks are now fairly well understood, there is as yet no work on what drives the emergence of such a network architecture. In situations such as neural or transportation networks, where a physical distance between the nodes of the network exists, we study whether the small-world topology arises as a consequence of a tradeoff between maximal connectivity and minimal wiring. Using simulated annealing, we study the properties of a randomly rewired network as the relative tradeoff between wiring and connectivity is varied. When the network seeks to minimize wiring, a regular graph results. At the other extreme, when connectivity is maximized, a `random' network is obtained. In the intermediate regime, a small-world network is formed. However, unlike the model of Watts and Strogatz (Nature, vol. 393}, p.440 (1998)), we find an alternate route to small-world behaviour through the formation of hubs, small clusters where one vertex is connected to a large number of neighbours.
	Co-Authors: N. Mathias

Hasan Guclu	Stochastic Growth in a Small World and Applications to Scalable Parallel Discrete-Event Simulations	*POSTER*
We consider a simple stochastic growth model on a small-world network. The same process on a regular lattice exhibits kinetic roughnening, governed by the Kardar-Parisi-Zhang equation. In contrast, when the interaction topology is extended to include a finite number of random links for each site, the surface becomes macroscopically smooth. The correlation length of the surface fluctuations becomes finite and the surface grows in a mean-field fashion. Our finding provides a possible way to establish control {\em without} global intervention in non-frustrated agent-based systems. A recent application is the construction of a fully scalable algorithm for parallel discrete-event simulation.

	Peter Holme	Prisoners' dilemma in real-world acquaintance networks
	We study Nowak and May�s spatial prisoners� dilemma game driven by mutations (random choices of sub-optimal strategies) on empirical social networks. The time evolution of the cooperation level is highly complex containing spikes and steps between quasi-stable levels. A statistical characterization of the quasi-stable states and a study of the mechanisms behind the steps are given. Most transitions between quasistable states can be described as the result of a mutation on a high-degree vertex. We argue that the crucial structural ingredients causing the observed behavior is a broad degree distribution and that the connections within vertices of highest degree are rather sparse. Based on these observations we construct model networks with a similarly complex time evolution of the cooperation level.
	Co-Authors: J. E. Johnson, S. Nussinov, Z. Nussinov

	Susan Holmes	Statistical Analysis and Simulations of Ant Networks
	What regulates foraging activity in ant networks? In a society without any central control, individuals decide which task to perform. We found that harvester ants (Pogonomyrmex barbatus ) use the rate of brief antennal contacts in decisions whether to perform midden work, which is piling and sorting the colony refuse pile or midden. We have thus constructed what we call the interaction networks, each new interaction between two ants creates an edge in the interaction graph. Theoretical work investigates how the use of encounter rates affects the dynamics of task allocation. Physiological studies showed that ants of different task groups differ in cuticular hydrocarbons. Laboratory tests showed that cuticular hydrocarbons are used in nestmate recognition, suggesting that task-specific differences in odor are the cue assessed during antennal contact. Thus task-specific differences in hydrocarbons make it possible for ants to use rates of antennal contact in task decisions. We found that task-specific differences in cuticular hydrocarbons depend on external conditions, which explains how ants of different task groups come to differ in odor. Our work extends these results to field studies of foraging behavior and study of simulated ant colonies on which we have total control. Task allocation in social insects. Behavioral plasticity in social insects is especially interesting because colonies adjust to environmental change through the aggregated responses of individuals. Social insect colonies perform various tasks, such as foraging, nest work, and brood care. As environmental conditions and colony needs change, so do the numbers of workers engaged in each task. Task allocation is the process that adjusts the numbers of workers engaged in each task in a way appropriate to the current situation. Task allocation operates without central or hierarchical control. A basic question about social insects is how individuals, using local information about their surroundings and each other, in the aggregate produce the complex behavior of colonies. How does a worker decide what to do next? The process that relates individual decisions to local information determines how quickly and how accurately a colony can change its effort when conditions change.
	Co-Authors: D. Gordon and B. Schafer

	Cristian Huepe	Phase Transitions in Self-Driven Many-Particle Systems and Related Non-Equilibrium Models: a Network Approach
	We investigate the conditions that produce a phase transition from an ordered to a disordered state in a family of models of two-dimensional elements with ferromagnetic-like interactions. This family is defined to contain under the same framework the XY-models, the Self-Driven Particles Model introduced by Vicsek et al., and the vectorial network model in which a given fraction of elements interact through direct random connections. This last model is analogous to an XY-system on a network, and as such can be of interest for a wide range of problems. It captures the main aspects of the interaction dynamics that produce the phase transition in other models of the family. The network approach allows us to show analytically the existence of a phase transition in this vectorial network model, and to compute its relevant parameters for the case in which all elements are randomly connected. Finally, we show that a qualitatively equivalent phase transition appears whenever a small amount of long-range interactions are present (or built over time), regardless of other equilibrium or nonequilibrium properties of the system.
	Co-Author: Maximino Aldana

	Adriana Iamnitchi	Small-World Patterns in Data-Sharing Communities
	Studies show that the graph in which nodes are Web pages and edges are the associated hyperlinks has small-world properties [1, 2]. However, this static property is 'wired' in the Web structure and does not reflect usage patterns. Usage patterns are captured by the aggregate file popularity distribution which has been shown to follow a Zipf law for the Web [3]. However, this latter metric does not capture the mapping between users and the subset of files in which each of them is interested: the overall popularity of an individual file appears as an aggregate over all users in the system. We study the relationships that form among users based on the data subsets in which they are interested. We capture and quantify these relationships by modeling the system as a data-sharing graph. We define the data-sharing graph of a system as a graph whose nodes are the data consumers, such as users or their machines' IP addresses and whose edges connect pairs of nodes with activity that satisfies a similarity criterion: for example, they connect nodes that access at least m common files during a time interval. We refine this definition on three concrete examples: the Web, a high-energy physics collaboration, and the KaZaA peer-to-peer system. Our main finding is that the data-sharing graphs of the three very different systems we studied are all small worlds [4] for a range of similarity criteria and time intervals. Our results lead us to conjecture that similar patterns exist in many other data-distribution systems. The challenge is now to understand how to exploit these patterns-for example, to (a) build better location mechanisms, as suggested in [5]; and/or (b) build more efficient data delivery mechanisms. Caching is generally employed in data distribution systems to save bandwidth and to reduce data access latency-for example, by placing proxy caches topologically 'close' to clients. In a data processing system, for example, where deriving new data implies significant computational effort, a group cache based not on proximity but on shared data usage could save CPU cycles and reduce latency in data delivery.
	Co-Author: M. Ripeanu, and I. Foster

	Marta Ibañes	A Mathematical Model Linking a Dynamic Activation of Notch with Side-Specific Expression of Nodal in Early Chick Embryonic Left-Right Asymmetry
	The problem of how left-right asymmetry is established during embryo development has received much attention at the molecular level in recent years. The identification of several genes that display side-specific patterns of expression has provided an entry point for understanding the molecular and cellular mechanisms underlying asymmetric morphogenesis (e.g., heart looping and position, gut coiling direction, etc.). Asymmetric expression of Nodal in the lateral plate mesoderm is a critical and conserved feature, necessary for normal left-right development. We have recently shown that Notch activity is necessary and sufficient for Nodal expression around the node, which, in turn, is required for left-sided expression of Nodal in the lateral plate mesoderm. Here we present a mathematical model for the upstream mechanisms involved in Nodal expression. The model corresponds to the spatio-temporal interactions within a network involving Delta, Notch, Serrate, and Fringe during developmental stages HH4-6, which lead to the activation of Notch signaling in the left side around the node. Ultimately, this activation induces the expression of Nodal in the same region, thus linking upstream genetic and epigenetic factors to the left-sided expression of Nodal. The model is based on coupled partial differential equations describing the kinetic reactions of the protein network. A thorough description of the model as well as several predictions on the type of interactions are presented.
	Co-Authors: D. Rasskin-Gutman, A.Raya, and J.C. Izpisúa-Belmonte

	Shalev Itzkovitz	Subgraphs in random networks
	Understanding the subgraph distribution in random networks is important for modelling complex systems. In classic Erdös networks, which exhibit a Poissonian degree distribution, the number of appearances of a subgraph G with n nodes and g edges scales with network size as <G> ~ N^n-g. However, many natural networks have a non-Poissonian degree distribution. Here we present mean- field equations for the average number of subgraphs in an ensemble of random sparse directed networks, characterized by an arbitrary degree sequence. We find new scaling rules for the commonly occurring case of directed scale-free networks, in which the outgoing degree distribution scales as P(k) ~ k^-^g. Considering the power exponent of the degree distribution, , as a control parameter, we show that random networks exhibit phase transitions between three regimes, where in each regime the subgraph number of appearances follows a different scaling law,<G> ~ N`^a` where a= n - g + m - 1 for g< 2, a= n - g + m + 1 - for 2 < g < c, and a= n - g for g> g_c, where m is the maximal outdegree in the subgraph, and g_c = m+1. We find that certain subgraphs appear much more frequently than in Erd½os networks. These results are in very good agreement with numerical simulations. This has implications for detecting network motifs, subgraphs that occur in natural networks significantly more than in their randomized counterparts.
	Co-Authors: R. Milo, N. Kashtan, G. Ziv, U. Alon

	Jaewook Joo	Behavioral response and epidemic threshold on scale-free networks.
	Many diseases spread through human populations by contact between infective individuals and susceptible individuals. It has been reported that epidemic threshold on unstructured scale-free networks is null. We applied a model of behavioral response in order to limit contact rate of an infectives when his connectivity goes large. This model illustrates the principal of time budget in behavioral ecology. Each individual has a limited amount of time to share with his contacts. As a result, contact rate saturates as connectivity goes large. We considered three different types of functional responses: linear, cyrtoid, and sigmoid. For all three types of responses, we obtained finite epidemic threshold.
	Co-Authors: Joel Lebowitz

	Nadav Kashtan	Efficient algorithms for detecting network motifs
	Natural networks have recently been shown to display network motifs: a small set of characteristic patterns which occur much more frequently than in randomized networks with the same degree sequence. Existing algorithms for detecting network motifs act by exhaustively enumerating all subgraphs in the network. This approach is limited for large networks and for high-order subgraphs. Here we present novel algorithms which allow detection of network motifs at a run time which is asymptotically independent of the network size. We present results for high-order subgraph statistics in large networks which were previously beyond reach, and comment on the roles of these motifs in biological and technological networks.
	Co-Authors: S. Itzkovitz, R. Milo, U. Alon

	Dong-Hee Kim	Embedded scale-free trees in complex networks: communication kernels
	We investigate the properties of embedded trees that make kernels of communication in complex networks. To evaluate the importance of links in communication, we construct weighted networks by assigning the edge-betweenness centrality of an original network to the weight of each link. For those weighted networks, we define and measure corresponding quantities to degree, clustering coefficient, and assortativity. Using the minimum spanning tree technique, we extract the trees maximizing total weight of selected links from the networks. In the real network data, we find that all embedded trees shows scale-free behavior and their betweenness centrality (BC) distributions have the universal exponents 2.0(1). On the other hand, in the Barabasi-Albert model, the embedded scale-free tree shows BC exponent of 2.2 as same as one of the original network. To understand the presence of trees with BC exponent of 2.2, we propose a tree model that contains an adaptation in the growing process.
	Co-Authors: Hawoong Jeong

	Jong-Won Kim	Effects of Random Noise on Growing Network Models
	We investigate effects of a random noise on network systems. In particular, we consider a simple class of growing network models whose topological structure is determined by the preferred attachment $A_k$. We introduce a noise induced attachment $\Tilde{A}_k$ which includes fluctuations in the number of links of individual nodes due to a random noise. We carry out numerical simulations to show that the topological structure of networks is determined not only by $A_k$ but also by the strength of the noise. Analytic and numerical solutions are also presented to support this observation. In addition, we also study the stability of networks against attacks under the noisy condition. Similarly, we introduce a noise induced preferred deletion $\Tilde{B}_k$ and show that a noise is an essential feature to determine the stability of networks.
	Co-Authors: Holger Kantz

	Sohyoung Kim	Inference of gene regulation network topology by perturbation analysis with NN-TIM (neural network-based topology inference method
	This study addresses the problem of identifying the large-scale topology of gene regulation networks from features that can be derived from Microarray data sets. Understanding large-scale structures of gene regulation is fundamentally important in biology. Three main classes of network models ?exponential networks, scale-free networks, and small-world networks ?have been used to describe topological features of various naturally occurring systems. Recent analysis of network properties of known biological networks has shown that they display scale-free features, but it is not yet clear whether the scale-free features are generic to all biological networks. The problem is that only limited information on actual biological pathways and their connectivity is available. To overcome these limitations and to expand the knowledge of biological network topology, we propose a novel method for inferring network topology from microarray data. The proposed method is more robust than current reverse engineering approaches because it does not require inferring individual connections. Preliminary results with simulated data are encouraging: A trained neural network was able to classify networks as random or scale-free with 90% accuracy, and the mean connectivity was predicted with 85% to 90% accuracy. Our results indicate that the neural network-based topology inference method (NN-TIM) can predict the class of topology and mean connectivity of a network without knowing the underlying connectivity of structures from measured time series data.
	Co-Authors: John N. Weinstein, John J. Grefenstette

	Robin Koytcheff	Systematic identification of statistically significant network features
	Recently there has been some interest in (and evidence for) the existence of statistically significant features in natural and artificial networks. However, the evidence for such features has been limited by the difficulty in identifying them in an unambiguous and principled way. Here we construct and test an efficient and principled approach to identify, automatically and systematically, statistically significant features in networks. By formulating a primitive alphabet from the set of possible manipulations of a matrix representation of the network, and exploiting fast operations in numerical linear algebra, we find an search mechanism. It is anticipated that this will result in a publicly-available OCTAVE/MATLAB code which will answer questions such as those posed in the novel work of Orr et al. [Nature Genetics 2002].
	Co-Authors: Etay Ziv, Chris Wiggins

	Montiago X. LaBute	QUANTUM CHEMICAL CALCULATIONS OF PHOSPHATE TRANSFER REACTION PATHS IN PROTEIN KINASES AND THE STRUCTURAL BASIS FOR ENTHALPY BARRIER SENSITIVITIES
	Protein kinases are ubiquitous in cell signaling pathways. These enzymes catalyze phosphate transfer which provides the dominant mechanism of signal transduction in both eukaryotic and prokaryotic cells. We have computed an ab initio reaction path for the phosphate transfer reaction on a ~250 atom system using density functional theory, coupled with the nudged elastic band method (NEB). We find an exceedingly low enthalpy barrier (~5 kcal/mol), nearly isoenergetic reactant and product states, and an associative reaction mechanism where the phosphate binds to the serine side-chain prior to abstraction of the hydroxyl proton by a highly-conserved aspartic acid. To address the question of sampling of different conformations (on (nano- and microsecond timescales) and solvent de-phased vibrational motions (femto- to picosecond) on the phosphate transfer, we have developed an analytic function fit to B3LYP/3-21G calculations in order to screen molecular dynamics trajectories by applying NEB to this potential to generate reaction paths. We then identify optimal conformations (low enthalpy barrier) as a function of principal components of the protein motions. Alternatively, reaction pathways computed by QM/MM methods utilizing a linear-scaling electronic structure code (MOPAC) will also be shown.
	Co-Authors: G.H. Henkelman, K. Németh

Charles H. Lee

Optimal Planning and Scheduling for a Mars Relay Communication Network

Mars will be continuously explored this decade and beyond by many concurrent spacecrafts. Presently the Mars Global Surveyor and Mars Odyssey 2001 are orbiting and mapping Mars. Future Mars missions within the next few years include the twin Mars Exploration Rovers, Mars Express, and Mars Beagle this year, Mars Reconnaissance Orbiter in 2005, Mars Netlanders, Mars Scouts in 2007, and Mars Science Laboratory in 2009. At different time periods in the future, these missions are overlapped and previous studies indicate that during such periods existing deep space communication infrastructure cannot handle all Mars communication needs. There has been much coordination between various Mars projects and the Deep Space Network to ensure communication resources are effectively utilized so that valuable science and engineering data from Mars orbiters and landers can be accommodated. A plausible solution is to perform optimal resource allocation for the Mars relay communication network; a network consisting of multiple surface units and orbiters on Mars and the Deep Space Stations. Unlike direct-to-earth, a relay communication, either in real-time or store-and-forward, can increase network science data return, reduce surface unit's direct-to-earth communication demands, and enable communication even when the surface unit is not facing Earth. It is the objective of this paper to take advantage of the relay operation to efficiently plan and schedule the network communications.

Our work in achieving optimal planning and scheduling for the relay communication network include (i) modeling and simulating the overall end-to-end forward-and-backward network link capabilities as time-varying resources by incorporating spacecraft dynamics, telecom configurations and other limiting factors such as planet occultation, weather, etc.; (ii) developing mathematical formulations to describe the actual operational constraints such as lander's local Sun angle restriction, time for acquisition and calibration, lander and orbiter one-to-one communication, return science data volume requirement, onboard storage capacity, network latency, radio frequency interference, mission priority, orbiter-to-orbiter communication capability, DSN's multiple spacecraft per antenna capability, etc; (iii) formulating the objective function by means of maximizing the network data throughputs and minimizing the total network transmitting times, and finally (iv) solving the resulting high-dimensional nonlinear constrained optimization problem. Detailed mathematical framework for our Mars relay network and numerical simulation and optimization for a Mars relay network consists of Earth stations and multiple landers and orbiters will be presented. The research in this article was carried out at the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration.

Co-Author: Kar-Ming Cheung

	Choong-seop Lee	Mechanism of self-organization in Networks of Competing Boolean Agents
	It was recently discovered that a Kauffman network of Boolean agents who compete in an evolutionary game that punishes those in the majority can self-organize to a nontrivial, complex state. The self-organized state has a broad distribution of attractor lengths, similar to a critical network. The dynamical mechanism responsible for the self-organization and stabilization of that state will be presented. It selectively punishes agents with homogeneous strategy tables when the attractor length is short and punishes agents with inhomogeneous strategy tables when the attractor length is long. The mechanism is robust and is expected to be important to the evolutionary dynamics of a number of other network systems.
	Co-Authors: Yong Lee, and Kevin E. Bassler

	Deok-Sun Lee	Sandpile on scale-free networks
	We investigate the avalanche dynamics of the BakTangWiesenfeld (BTW) sandpile model on scalefree (SF) networks, where threshold height of each node is distributed heterogeneously, given as its own degree. We find that the avalanche size distribution follows a power law with an exponent t. Applying the theory of multiplicative branching process, we obtain the exponent t and the dynamic exponent z analytically as a function of the degree exponent g of SF networks as t = g/(g-1) and z=(g-1)/(g-2) in the range 2 < g < 3 and mean field values t = 1.5 and z = 2.0 for g > 3. The analytic solution supports our numerical simulation results. We also consider the case of uniform threshold, finding that the two exponents reduce to the mean field ones.
	Co-Authors: K.-I. Goh, D.-S. Lee, B. Kahng and D. Kim

	Katharina Anna Lehmann	Metabolic Network Evolution How to get really rich - fast and easy!
	It is well known, that the degree-distribution of metabolic networks follows a power-law. There are especially two dynamic models in which growing graphs develop such a power-law-like degree-distribution: in the first, a new node attaches to an old node with a probability proportional to the degree of the latter. This is a model of preferential attachment.The second model, published by Fabrikant et al., introduces some kind of weighted trade-off: Every new node pops up randomly in a 2D-space and evaluates all old nodes in a weighted sum of their distance to it and their centrality given by any centrality measure. They could show that this attitude will for a certain scale of weightfactor in the sum yield power-law-like degree distributions. The question now is: Can these models be applied to growing metabolic networks in evolution? On the first sight we clearly have to reject this idea, since mutation happens on the level of the DNA which changes the structure of enzymes. But enzymes are represented as edges in a metabolic network, not as new nodes, searching for links to old ones! So, there are as a first approximation now new nodes in evolution but emerging edges. In the following we will give a brief theoretical, biological argument why and how these models could nevertheless be the basis for dynamically changing metabolic networks. A metabolic network with an apropiate reduction can be viewed as a map of chemical similarity: Every link states that the two substances are transformed into one another by a biochemical reaction and therefore their structure will not differ too much. Similarly a mutation on the active center of an enzyme will not change the preferred substrate to much. That means that all neighbors of the old substrate have a significantly higher probability to take part on the new reaction. If there is already a highly connected node in a metabolic network, it has a much higher area of neighbors from which to get nodes from than a normal connected one. There is a second argument: If a substance gains a new enzyme by which it is transformed its concentration will be decreased. That could lead to lethality or a less ability to survive for the whole organism. Such a new 'sink' of a substance is the easier countervailed the more ways to synthesize it are in a cell. This number of ways is described by the number of links a node has. In summary: A new link in a metabolic network will be easier acquired by a well connected node and it will be easier maintained by a well connected node. We take this a basis of a biological motivated model of "The rich get richer".
	Co-Authors: M. Kaufmann

	Fredrik Liljeros	How sexually connected are the Swedes?
	We confront the question whether the majority of heterosexual individuals in Sweden are likely to be connected in one giant network component of heterosexual contacts despite the fact that the majority of sexual contacts presumably take place between individuals that i) live geographically close to each other, and ii) resemble each other socially. An approximate analytic method that only needs information about individuals' number of sexual partners for determining the existence of such giant component is borrowed from Mark Newman's work on the "Ripple effect" (Feld 1991, Newman 2003). The method is applied to Swedish survey data, and shows that the majority of the Swedes are connected to each other through sexual relationships. This result holds true for lifetime sexual partners, and may surprisingly also hold true for partners during last twelve months. The result shows that public health message "Your are sexually connected to many more people than you think" adequately can be used.
	Co-Authors: Johan Giesecke

	Zonghua Liu	Propagation and immunization of infection on general networks with both homogenous and heterogeneous components
	We consider the entire spectrum of architectures of general networks, ranging from being heterogeneous (scale-free) to homogeneous (random), and investigate the infection dynamics by using a three-state epidemiological model that does not involve the mechanism of self-recovery. This model is relevant to realistic situations such as the propagation of a flu virus or information over a social network. Our heuristic analysis and computations indicate that, (1) regardless of the network architecture, there exists a substantial fraction of nodes that can never be infected, and (2) heterogeneous networks are relatively more robust against spreads of infection as compared with homogeneous networks. We have also considered the problem of immunization for preventing wide spread of infection, with the result that targeted immunization is effective for heterogeneous networks.
	Co-Authors: Ying-Cheng Lai, and Nong Ye

	Jonathan P. Mason	Evolving Complex Networks With Desired Dynamics
	Complex networks underlie the dynamics exhibited by a wide range of physical, biological and engineered systems. Recent studies have focused on the structure of such networks, and examined how the structure is linked to functional properties such as robustness and error tolerance. In complex networks, however, a theory to predict the dynamics based on the network structure is lacking, and consequently, it is often unclear what structural architecture is needed to produce desired dynamics. Here we show that complex networks with desired dynamics can be obtained by evolving their structure rather than by designing it from the outset. We study a class of differential equations that have been proposed as a mathematical model of genetic networks, and construct and experimentally analyze an electronic circuit that displays the same dynamics as the differential equations. These networks can display a variety of behaviors, including fixed points, limit cycles and chaos. Here we focus on limit cycles and show that it is possible to evolve complex networks that display stable oscillations of a specified cycle length. We also demonstrate that there is an optimal evolution rate for obtaining such dynamics. This work offers novel insights into how mutations can alter network dynamics, and provides a new strategy for designing electronic circuits.
	Co-Authors: Jim Collins, Paul Linsay, Leon Glass

	Chris Myers	Software systems, biochemical networks, and the organization of specific, evolvable function
	Software design focuses on organizing systems of collaborating components (such as classes, methods, subroutines, and modules) which can be flexibly combined to provide complex functionality while also being highly evolvable. Software collaboration graphs { such as call graphs and class collaboration graphs { describe the relationships among those components, and examination of collaboration graphs from several open-source software systems reveals intriguing scale-free, small-world networks. While the emergent structure of these graphs lies outside the realm of design, some features can be traced to software engineering practice, and a simple model of evolving software systems based on refactoring processes captures some of the basic features of the observed systems. Perhaps more importantly, however, software design emphasizes techniques for functional organization in collaborative, evolving systems, and as such, may provide insight into the structure and function of biochemical networks by highlighting the roles of genericity, polymorphism, and encapsulation in supporting collaborative solutions that are both specific and evolvable.

	Takashi Nishikawa	Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
	Small-world and scale-free networks are known to be more easily synchronized than regular lattices, which is usually attributed to the smaller network distance between oscillators. Surprisingly, we find that networks with a homogeneous distribution of connectivity are more synchronizable than heterogeneous ones, even though the average network distance is larger. We present numerical computations and analytical estimates on synchronizability of the network in terms of its heterogeneity parameters. Our results suggest that some degree of homogeneity is expected in naturally evolved structures, such as neural networks, where synchronizability is desirable.

	Eulsik Oh	Intra-modular and inter-modular synchronization in complex networks
	Many complex networks in real world comprises modular structures functionally or geometrically, displaying intra- or inter-modular cooperations. Here we investigate collective synchronization phenomena through a model of coupled oscillators on prototypical a couple of module-invaded real world networks, the protein interaction network and the Internet on autonomous system level. We find that while for the former, modules are so strongly interconnected that the entire system is synchronized almost simultaneously as the coupling constant increases, for the latter, however, they are weakly connected, so that each module is synchronized with weakly-tied modes and the entirely system is gradually synchronized as the coupling constant increases. We confirm such behaviors through in silico models.
	Co-Authors: K. Roh, H. Hong, B. Kahng and D. Kim

	Janet M. Oliver	Topographical Analysis of the IgE Receptor Signaling Pathway of Mast Cells
	During receptor-mediated signal transduction, membrane lipid composition is remodeled, membrane proteins redistribute to multiple specialized membrane domains and cytoplasmic proteins undergo reversible binding interactions with these domains. Topography is critical to function in signaling pathways, and the flow of information though cells is as easily disrupted by protein mislocation as by protein inactivation by mutation or drug treatment. Our goal is to build a predictive model of signal transduction through the high affinity IgE receptor, FceRI, in mast cells that integrates the biochemical properties of membrane proteins and lipids with their topographical locations and, ultimately, 3-dimensional cell shape. Here, we describe methods to map and analyze the distributions of the high affinity IgE receptor (FceRI), as well as a subset of FceRI –associated signaling proteins and lipids, during signaling. The methods involve labeling proteins and lipids on both the extracellular and cytoplasmic face of membrane sheets with antibody-coated nanogold particles (typically 5 and 10 nm particles specific for 2 distinct signaling components), followed by high resolution transmission electron microscopy to localize the particles and relevant surface features (clathrin-coated pits for example). Gold particle positions are then acquired automatically from digitized images taken at the lowest magnification that still permits identification of the smallest gold particles. The analysis team has developed an algorithm based on thresholding for rapidly and accurately identifying 10nm particles, and a more costly but effective algorithm based on filtering to identify 5nm particles. As neither algorithm is completely accurate, they have also developed a user interface that allows for the easy addition of missed particles and removal of false identifications. The next task is the analysis of the clustering (and subsequently coclustering) of these particles. Our team has gained significant information on gold particle clustering by performing statistical analyses of the gold particle data using the Hopkins statistic and ideas related to Ripley's K function. Statistical analysis is followed by clustering analysis. Our clustering algorithm is based on aggregating into clusters all particles that are within a given distance of each other. This relatively direct algorithm provides intuitively correct cluster sizes and is not sensitive to modest changes in the cutoff distance. Dendrogram analysis is being implemented to determine if this can give improved cluster analysis. The second phase of the project will be the development of geometric models that reflect the topographic features of mast cell surfaces in 3 dimensions and superimposing upon these models the topographical distribution of selected transmembrane proteins. We expect ultimately to build a predictive model of signal transduction in mast cells that encompasses not only the biochemical properties of signaling proteins and lipids, but also the positions and interactions of multiple proteins and lipids and 3-dimensional cell shape. Creating such models is clearly the first step towards novel treatments for diseases like cancer and autoimmune disorders that very often involve the disruption of signal transduction pathways.
	Co-Authors: Stanly L. Steinberg, Bridget S. Wilson, Jun Zhang, Karin Leiderman, Janet R. Pfeiffer

	Jonathan Ozik	Growing Networks with Geographical Attachment Preference: Emergence of Small Worlds
	We investigated a one dimensional growing network with distance dependent attachment probability. Starting with m₀ attached nodes along a ring, we build our network iteratively, with each iteration containing the following steps: a) a new node is added to the ring of nodes at a random location along the ring, b) the ring is expanded by one unit, and c) the new node attaches to m older nodes in the ring according to an attachment probability proportional to (1/d)^a, where d is the distance between the new node and the target node along the ring’s circumference and a is a parameter that we vary. We find that, by varying a we create networks with different properties (e.g., average clustering, diameter). In particular, for large a , we observed small world networks.
	Co-Authors: Edward Ott, Brian Hunt

	Avner Peleg	Interactions between non-ideal solitons in optical fibers
	We study the interaction between two non-ideal solitons from different frequency channels propagating in an optical fiber. The interaction may be viewed as an inelastic collision, in which energy is lost to continuous radiation due to non-zero third order dispersion (TOD). We develop a perturbation theory with two small parameters: the TOD coefficient and the reciprocal of the inter-channel frequency difference. We find that the leading contribution to radiation emitted during the collision is proportional to the TOD coefficient divided by the square of the frequency difference. The source term for this radiation is identical to the one produced by perturbation of the second order dispersion coefficient. The only other effects up to third order of the theory are shifts in phase and position. We propose a general recipe for using this perturbation method for studying soliton interactions under other forms of perturbations, and for studying interactions between non-ideal solitons of equations other than the nonlinear Schrodinger equation.
	Co-Authors: M. Chertkov, Y. Chung, and I. Gabitov

	Erzsébet Ravasz	Hierarchical Organization of Complex Networks
	Many real networks in nature and society share two generic properties: they are scale-free and they display a high degree of clustering. We show that the scale-free nature and high clustering of real networks are the consequence of a hierarchical organization, implying that small groups of nodes form increasingly large groups in a hierarchical manner, while maintaining a scale-free topology. In hierarchical networks the clustering coefficient follows a strict scaling law, which can be used to identify the presence of a hierarchical organization in real networks. We find that several real networks, such as the World Wide Web, actor network, the Internet at the domain level and the semantic web obey this scaling law, indicating that hierarchy is a fundamental characteristic of many complex systems. We the focus on the metabolic network of 43 distinct organisms and show that many small, highly connected topologic modules combine in a hierarchical manner into larger, less cohesive units, their number and degree of clustering following a power law. Within Escherichia Coli we find that the uncovered hierarchical modularity closely overlaps with known metabolic functions.
	Co-Authors: Albert-László Barabási, and Zoltán Oltvai

	Cynthia Reichhardt	Morphology, Hierarchical Structure, and Horton Analysis of Riverlike Networks of Vortices
	Through realistic simulations, we analyze the morphology and statistical properties of networks of vortex flow in flux-gradient-driven superconductors. We derive a phase diagram of the different network morphologies, which include a dense network regime where flow can occur anywhere; a braided network regime where flow is restricted to certain regions, and a Hortonian network regime where Horton's laws of length and branching ratio are obeyed in agreement with geophysical rivers. We also consider the fractal dimension, tortuosity, and voltage noise spectrum in the different regimes. A drop in tortuosity when the networks change from braided to unbraided is accompanied by a significant drop in noise power. We compare our results to experiment.
	Co-Authors: Charles Reichhardt, A.P. Mehta, F. Nori

	Juan G. Restrepo	Local branching laws and scaling in bifurcating networks
	We study how the local branching laws in bifurcating networks, which include the arterial tree, airways and river networks, determine their scaling properties. A number of variables defined globally on these kinds of networks can be determined from local laws governing the bifurcations. When the same law is valid throughout the whole network, power law scaling emerges asymptotically. We propose a systematic method to deal with the general case, in which these laws not only are different on different scales, but are also stochastic. This is relevant in practice, given the great scatter in the data for bifurcations in the arterial tree. We apply these ideas to experimental data of the airways and arterial tree of the lung, and find that a generalized version of the scaling exponent x defined by r_0^x = r_1^x + r_2^x has a behavior different from what is commonly believed. Instead of having a smooth transition from x=2 for the larger vessels to x=3 for the small vessels, it has a more complex behavior. We think this fact should be further investigated, both by experiment and theory.
	Co-Authors: Edward Ott, Brian Hunt

	Kyoohyoung Rho	Identification of essential and functionally moduled genes through the microarray assay
	Motivation: With the increasing availability of the microarray technology, many in silico methods for analyzing the microarray data have been developed recently. While all the methods are useful for clustering genes, they cannot give any information needed to identify essential genes. Here we introduce an in silico method to select essential genes through the microarray assay. Results: We construct a graph of genes, called the gene transcription network, based on the Pearson correlation coefficients of the microarray expression level. Links are connected between genes following the order of the pair-wise correlation coefficients. We find that there exist two meaningful fractions of links connected, p_m and p_s, where the number of clusters becomes maximum and the connectivity distribution follows a power law, respectively. Interestingly, one of the clusters at p_mcontains a high density of essential genes having almost the same functionality. Thus the deletion of all genes belonging to that cluster can lead to lethal inviable mutant efficiently. Such an essential cluster can be identified in a self-organized way. Once we measure the connectivity of each gene at p_s.Then using the property that essential genes are likely to have more connectivity, we can identify the essential cluster by finding the one having the largest mean connectivity per gene at p_m. We confirm our method with the yeast microarray data.
	Co-Authors: Hawoong Jeong, Byungnam Kahng

Luis Rocha

Extraction and Semi-metric Analysis of Social and Biological Networks

We discuss the extraction of social networks from co-occurrence data in several electronic resources such as the World Wide Web, as well as the extraction of networks of genes and other biological entities from both gene expression experiments and collections of electronic documents. These associative networks are represented as weighted graphs whose edges denote degrees of proximity or its inverse, a distance function.

We discuss how most distance graphs obtained violate the triangle inequality expected of Euclidean distances. This type of distance function is known as a semi-metric. We show that the semi-metric behavior of these distance graphs, can be used for identifying specific implicit associations in the graph, and thus useful to identify trends in communities associated with the sets of documents from where associations were extracted.

In this poster we describe our work on inferring relevant associations from, as well as characterizing, semimetric distance graphs. We present the idea of semi-metric distance graphs, and introduce ratios to measure semi-metric behavior. The discussion is based on empirical evidence from different sources such as a large database of scientific publications associated with the Active Recommendation Project at the Los Alamos National Laboratory (http://arp.lanl.gov), collections of newspaper articles about terrorism, a web-site devoted to interdisciplinary science (the Principia Cybernetica Project web site http://pespmc1.vub.ac.be/), biomedical collections of publications, data from word free association experiments, and random distance graphs.

Finally, we discuss how loosening the metric requirement of distance graphs extracted from document collections, results in a methodology capable of both discovering important associations for recommendation algorithms and quantifying the completeness and amount of latent knowledge stored in a document network. Most important, this methodology is one we loose when metric distance graphs are required.

	Meg Romeis	Simulation of infectious disease spread across realistic social networks
	The Epidemiologic Simulation system (EpiSims) is one component of the Urban Infrastructure Suite (UIS) developed at Los Alamos for the Department of Homeland Security. EpiSims is an agent-based simulation of disease spread across a realistic urban social network. The simulation relies on individual activity patterns developed within UIS for a synthetic population of approximately 1.5 million persons, and it follows person-to-person transmission of disease through the resulting time-dependent social network. Because the simulation keeps track of each person's health status, EpiSims allows for changes in each person's activity pattern due to changes in his/her health. Related projects have studied characteristics of the network affecting disease propagation and have developed algorithms for efficiently approximating these characteristics on very large networks.
	Co-Authors: Stephen Eubank, Christopher L. Barrett and the EpiSims Team: http://episims.lanl.gov

	Sameet Sreenivasan	Efficient Immunization methods in Small-World networks
	We study a strategy of immunization on a generalized small world network. The approach, in contrast to targeted approaches, does not require any knowledge on the topology of the network and performs significantly better than random immunization. We apply the acquaintance immunization strategy where a random fraction of nodes is chosen and a nearest neighbor of each of these nodes is immunized. We demonstrate the efficiency of this method on a small world model which incorporates both the scale-free degree distribution of the nodes as well as the high clustering coefficients seen in real social networks.
	Co-Authors: Shlomo Havlin, Sergey Buldyrev, H. E. Stanley.

	Greg Stephens	Dissociated Neural Cultures: A Realistic Model Complex Network
	Nervous systems, and the brain in particular, provide important examples of complex networks rich in both spatial structure and temporal activity. Furthermore these networks are organized for a very definite purpose, examples being the execution of complex information processing in cortical structures or the control of motor tasks by spinal cord networks. Recent progress in growing neurons in culture now allows for unprecedented quantitative access to the dynamical processes underpinning the formation of a living neural network. With a cultured neural network it is possible to measure structural morphology together with the neural spike patterns characterizing the functional activity of the network elements. As the cultures grow and mature the time evolution of the network is also observable. Here we describe the background for some of these experiments and present a preliminary analysis of the emerging functional networks.
	Co-Authors: Luis M.A. Bettencourt, Enrique Claverol-Tinture,and Guenter Gross

	Daniel Stouffer	Robust patterns in food web structure
	The species comprising an ecosystem are connected through intricate trophic relationships defining complex networks---the so-called food webs. Understanding the structure and mechanisms underlying the formation of these complex webs is of great importance in ecology. For example, food web structure provides insight into the behavior of ecosystems under perturbations such as the introduction of new species or the extinction of existing species. First, we show analytical and numerical results for a recently proposed model for food webs in the ecologically meaningful limits. Then, using these results as a guideline, we analyze the properties of several community trophic webs from a variety of environments, including freshwater, marine-freshwater interfaces, and terrestrial environments. We show that there are robust patterns that describe the properties of the trophic webs considered.
	Co-Authors: Roger Guimera, Daniel Stouffer, Juan Camacho, Luis A. N. Amaral

	Reiko Tanaka	The Internet as a Complex Systems: Designed Topologies
	The Internet offers an attractive case study in complex networks, since our understanding of the underlying technology together with the ability to do detailed measurements means that any conjectures about "emergent" properties can be unambiguously resolved, though often not without substantial effort. For example, topological interconnection of computers and routers that make up the Internet has recently been the subject of both theoretical and measurement studies. These have produced strikingly contradictory claims, reminiscent of earlier debates about SOC vs HOT models for the statistics of forest fires and other large scale systems. What turns out to be critical to the real Internet connectivity is the technological constraints on the hardware, and the functional requirements on the resulting network for performance and robustness, enabled by an elaborate suite of software protocols that sit on top of the hardware infrastructure. Thus not only does the actual network graph have certain structural properties, but necessarily all functional networks also have these same structural properties. Put another way, of all the mathematical possibilities of hardware connectivity, only a vanishingly small subset can be built to satisfy hardware constraints, and a further vanishingly small subset of these provide acceptable performance. We develop a simplified and abstract model of these constraints and illustrate how "good" networks do have rare but highly structured network graphs, and how these can produce power laws in degree distributions. In striking contrast, we can also define a much larger class of "scale-free" graphs which also have the same power law degree distributions, but are the most generic or most likely graphs with this distribution. Interestingly, all scale-free networks necessarily have extremely poor performance and robustness properties, exactly the opposite of all "good" networks. Fortunately, and necessarily, the Internet is very far from scale-free or criticality.
	Co-Authors: Lun Li and John Doyle

	Alexei Vazquez	Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
	The linear preferential attachment hypothesis has been shown to be quite successful to explain the existence of networks with power-law degree distributions. It is then quite important to determine if this mechanism is the consequence of a general principle based on local rules. In this work it is claimed that an effective linear preferential attachment is the natural outcome of growing network models based on local rules. It is also shown that the local models offer an explanation to other properties like the clustering hierarchy and degree correlations recently observed in complex networks. These conclusions are based on both analytical and numerical results of different local rules, including some models already proposed in the literature.

	Erik Volz	New methods for mapping human contact patterns and the spread of infectious diseases through networks
	There have been many theoretical advances in recent years concerning contagion processes on networks. As yet, however, there has been little empirical comparison of this theory to real data of how diseases spread through networks. The difficulty in application of these models to empirical research is the frequent lack of data about the structure of social networks. Many disease-afflicted populations are "hidden" in so far as their network structure cannot be determined by standard survey techniques. Examples include injection drug users who are afflicted with AIDS and who do not want to share information about their community because their behavior is stigmatized. This work builds on the development of Respondent Driven Sampling (RDS), a recent advance in mapping the social networks of hidden populations. RDS utilizes chain referrals of interviewees to collect data on the probability that a person with a given set of characteristics will share a link with someone with any other combination of characteristics. Homophily based on common characteristics is the most fundamental basis for clustering in social networks, and so these crosscutting probabilities reveal community structure in the network that can have implications for disease transmission. It is possible to construct random graphs based only on RDS data, and to use these graphs as a model for the contact patterns along which diseases spread. This research shows that in the limit of large population-size, bond-percolation processes can be solved on these graphs exactly, and the threshold infectiousness for an epidemic to occur may be determined. For networks with smaller groups, it is still possible to determine the threshold infectiousness with computer simulations.

	Oleg K. Vorov	Decoding multivortex networks in rotating Bose-Einstein condensates
	We give analytically solvable theory of the sequential phase transitions of weakly interacting harmonically trapped Gross-Pitaevsky Bose-Einstein condensate in the multi-vortex rearrangement process while the rotational velocity is increased. The phases are classified according their C_n symmetries, that allows to construct shell-model vortex theory, decoding the structures and the sequence of multivortex configurations appearing as the angular frequency grows. We give expressions for the critical velocities, it angular momentum magic numbers and forbidden gaps, ground state energy etc in terms of elementary functions. The results are in perfect agreement with the numerical findings.
	Co-Authors: P. Van Isacker and M. S. Hussein

	Jevin West	The Game of Leaf: Evidence that Stomatal Networks are Cellular Computers
	Some biological processes seem a lot like computation, but to date convincing evidence for this identification is lacking. To probe whether a network of real (as opposed to simulated) biological agents can plausibly be said to perform computation, we have experimentally studied the dynamics of the collective opening and closing of stomata on the surfaces of leaves of the plant Xanthium strumarium L. (cocklebur). Stomata are micron-size pores that regulate the exchange of gases between a plant's interior and the atmosphere. Stomata open in bright light, primarily to take in CO2 for photosynthesis. A secondary consequence of stomatal opening is increased rate of water evaporation. Thus, a plant is continually confronted with a kind of cost-benefit problem: how should average stomatal aperture be adjusted (as environmental conditions vary) so that, in aggregate, sufficient CO2 is taken up while excessive water loss is prevented. The plant's problem is exacerbated by its need to process and respond to heterogeneous information from widely separated parts without having a brain or central nervous system to oversee and coordinate such tasks. We propose that plants may solve their global cost-benefit problem by "cellular computation." A cellular computer consists of spatially separated processing units (like stomata) that can share information among only a small number of local neighbors, yet, when properly "wired and programmed," can produce results relevant to the entire system. The dynamics of such "emergent, distributed computation" is characterized by persistent correlations in both space and time. Crucially, the dynamics also harbors coherently propagating data structures ("particles of information") that permit distant regions of the system to eventually communicate. We used chlorophyll fluorescence as a spatially explicit probe of stomatal aperture. Chlorophyll fluorescence from leaves can be spatially patchy even under fixed, seemingly homogeneous, environmental conditions. The shape and intensity of fluorescence patches can vary over time and involve 10s to 1000s of stomata behaving in concert. Stomata are clearly "wired together"-presumably through short-range hydraulic and chemical interactions-but are they programmed to compute? Our analyses of temporal and spatial correlations associated with patchy episodes reveal long-tail, power laws, as would be expected in cellular computation. In addition, by recoding our fluorescence images to detect intensity-change trends, we observe particle-like propagation of information over the surfaces of our leaves. We therefore conclude that collective stomatal dynamics is consistent with the view that leaves are computers.
	Co-Authors: David Peak, Keith Mott

Christopher C. Whalen

Transmission of Tuberculosis in Tight Contact Networks

Tuberculosis is a persistent pathogen of humans that causes 2 million deaths per year worldwide. The bacteria, Mycobacterium tuberculosis (MTB) is transmitted by the airborne route, usually after close and prolonged contact. With the advent of molecular techniques, it is now possible to type strains of MTB and assign individuals with the same strain to part of a chain of transmission, or a cluster.

In a human population, the transmission of MTB behaves like a complex adaptive system that self-organizes into relatively small clusters of cases. This abstract will present the evidence for transmission as a complex adaptive system and will then show data about the transmission of MTB in African households.

Tuberculosis as Complex Adaptive System

Transmission of MTB in human populations is the result of interactions between infectious and susceptible individuals. When viewed as a whole, the behavior of tuberculosis in the population behaves like a complex adaptive system. The size of clusters from different populations follows the familiar power law (y = b*10^{-(cluster
size – 1)*}^q) with most clusters of small size and a few large clusters (Table).

Site	B (se)	Th (se)
SF	41.2 (2.89)	0.29 (0.02)
Neth	153.4 (9.76)	0.36 (0.02)
Amst	279 (49.5)	0.89 (0.75)
Ak	101.6 (13.4)	0.53 (0.05)

DNA Fingerprinting

Epidemics of infectious disease depend on the probability of transmission given adequate contact, the frequency of adequate contact, and the duration of infectiousness. The frequency and nature of contact among infectious and susceptible persons depends on the underlying social and contact networks. In a field epidemiological study, we have determined the secondary attack rate of tuberculosis in African households, that is, tight contact networks. We have found that 3% of contacts have culture-proven tuberculosis, but not all contacts shared the same strain of MTB as the index case. The secondary attack rate was 1.7% in these households. The determinants of transmission were malnutrition in the contact, young age, and HIV infection in the contact.

In summary, tuberculosis behaves like a complex adaptive system that organizes into distinct clusters with the same strain. Transmission of tuberculosis in tight contact networks, such as households, is consistent with predominance of smaller cluster sizes. Future work will test the hypothesis that MTB is transmitted through small world-networks. Further study of large clusters with weak-links between contacts may shed light on how tuberculosis is propagated and sustained in a population. Insights from network analysis may lead to novel public health approaches for controlling the spread of this disease.

	Xinhao Ye	Multi-scale Methodology for Biochemical Engineering
	Today it is widely accepted that the nature of the complex phenomena in bioprocess is its complex structures of networks. To decipher inherent network properties in biochemical reaction networks, biotechnologist usually resorts to stoichiometric analysis with network topology. It is safely an appropriate tool to provide insightful information of network functionality, robustness and even gene regulation at steady state conditions^[1] . However the drawback of such analysis is also obvious that it could provide the information only of certain steady state conditions, and is inept to understand and predict the spatial and temporal phenomena of complex structures at different scales. Thus multi-scale methodology was needed to make it available to solve these questions. Through descriptive, correlative and variational analysis as described by Li & Kwauk^[2], we mined the accumulated data from engineering scale (process monitoring of fed-batch fermentation), enzyme scale ( kinetic constants from continuous cultures and flux control coefficient from metabolic control analysis) and gene scale ( nonlinear dynamics of regulation of Promter, for example integreated effectes of repression, derepression and induction on aox1 gene), then applied artificial neural networks (ANNs) to establish a novel expert system for real-time parameter estimation and metabolic pathway analysis in industrial fermentation process. Recently we have utilized this expert system to optimize the production of a heterogeneous protein, rPhytase, by methylotrophic yeast, Pichia pastoris and to successfully direct the scale-up process from laboratory (5 L) to industry (500 L).
	Co-Authors: Meijin Guo, Haifeng Hang, Ju Chu, Siliang Zhang

	Valentin P. Zhigulin	Competitive Dynamics on Directed Small World Networks
	Recently there had been a surge of interest in the properties of small world networks. However, most of the studies concentrated on statistical properties such as clustering, mean path length, etc. Only few types of dynamics on small world networks have been considered to date, mostly of the damage spreading variety. In this work Lotka-Volterra -type competitive dynamics on directed small world networks is studied. Limit cycle dynamics on the regular circular substrate is observed and its properties are studied analytically. Randomization of the substrate leads to the appearance of networks with chaotic or fixed point dynamics. Frequency of occurrence in the ensemble of networks for each type of dynamics is calculated as a function of the number of shortcuts. Unlike statistical properties, these probabilities of dynamical regimes are found to depend strongly on the method of randomization (rewiring vs addition of shortcuts). In the case of rewiring limit cycle dynamics is found to persist deep into the small world region. Unlike rewiring, addition of shortcuts induces the transition from limit cycle to chaotic dynamics.
	Co-Authors: Mikhail I. Rabinovich

Liqiang Zhu

Changes in Neural Interaction During Adaptation

A wealth of evidence suggests that motor learning involves many areas of the brain including the primary motor cortex (M1), which is believed to be responsible for voluntary movements. The aim of this paper is to characterize, quantitatively, interactions among M1 neurons in a local network and how they change in response to movement perturbations in a series of controlled experiments with monkeys.

In our study, a monkey is trained to learn a new skill, moving arm to reach a target under the influence of external perturbations. The spike trains of multiple neurons in M1 are recorded simultaneously. We utilize the methodology of directed transfer function to quantify the causal interactions between the neurons. We find that the coupling between the motor neurons tends to increase during the adaptation but return to the original level after the adaptation. We also utilize the method of unitary events analysis to evaluate the synchronization level among neurons. It is surprising that, during the adaptation, the averaged synchronization level among neurons decreases even when coupling strength increases. To understand the possible mechanism underlying this phenomenon, we investigate a numerical network model, which consists of Hodgkin-Huxley neurons. We find that when excitation and inhibition in the network are near balanced, the changes of coupling strength measurement and synchronization level are opposite. The experimental and numerical observations suggest that, at the beginning of the adaptation, collective strength of inhibitory synapses increases relative to excitatory synapses, resulting in a more balanced network, and so higher firing rates and lower synchronization could be observed. Increased inhibition also results in more metabolic activity. At the end of adaptation, the network has been re-organized such that the balance between inhibition and excitation return to original levels, also the metabolic activity does.

Co-Authors: Ying-Cheng Lai, Frank C. Hoppensteadt, Jiping He

	Etay Ziv	ARMO: an algorithm for Automatic Recursive MOdularity
	The identification of functionally distinct subnetworks within larger networks is an emerging problem in systems biology. Much of the topology-inspired work in this area has focused on defining similarity measures which are local in nature and focus on some chosen locally-defined feature. We have constructed a novel algorithm based on gloabl properties to decompose the network iteratively and quickly into modules and submodules and which makes no prior assumptions on the topology. It is anticipated that this will result in a publicly-available OCTAVE/MATLAB code which will automatically and recursively modularize arbitrary networks.
	Co-Authors: Robin Koytcheff, Chris Wiggins

	Vladimir Gudkov	Applications of Generalized Entropies to Network Analysis
	We apply mutual entropies and generalized (Renyi) entropies to measure the changes in topologies of networks. Some functions of these entropies are sensitive to particular properties of networks. These algorithms are extremely fast and are often capable of running in real time on rather large and complex networks to identify aberrant processes, and changes topologies in real time (a fraction of a second), and thus allow not only for dynamical monitoring, but also for the construction of potentially automated system responses that can avert intrusions, system failures, or flow bottlenecks.
	Co-Authors: J. E. Johnson

	Vladimir Gudkov	A Novel Approach to Network Analysis via a Continuous Evolution of a Physical Analog
	A general novel approach mapping discrete, combinatorial, graph-theoretic problems onto “physical” models - namely n-simplexes in (n-1)-dimensions - is applied to network classification, graph equivalence problem and to the NP complete problem of finding the largest clique within a network. It is shown to solve these long standing problem in polynomial, short, time.
	Co-Authors: J. E. Johnson, S. Nussinov, Z. Nussinov

	Edward Lyman	Phase transitions far from equilibrium
	We present the phase diagram of a simple lattice gas model driven far from equilibrium, mapped by Monte Carlo simulation. Two species of particles hop on a square lattice, interacting through excluded volume and nearest neighbor attractions. Depending on the difference between the total numbers of each particle, two distinct continuous transitions are observed. Detailed analysis of the transitions is complicated by the presence of anisotropies introduced by the dynamics.
	Co-Authors: B. Schmittmann

	Adilson E. Motter	Small-world phenomenon in scale-free networks
	The small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance. We find, surprisingly, that many scale-free networks are more sensitive to attacks on short-range than on long-range links. This result, besides its importance concerning network efficiency and/or security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.
	Co-Authors: Takashi Nishikawa, and Ying-Cheng Lai

	Girish Nathan	Network Models for trabecular bones
	Transport Phenomena in Random Networks applied to Biophysics: We study electrical and elastic networks as models to study phenomena in disordered systems. In particular we have realized analytical and numerical studies in order to obtain an expression for the mean breakdown strength for these systems. The motivation for this study is to develop a method to relate the mean strength of bones to its mass and its trabecular structure, in order to provide a non invasive method to diagnose bone strength and to help in management of osteoporosis.
	Julio Ortiz, Chamith Rajapakse, Gemunu Gunaratne

	Matthew Hastings	Random Networks and Renormalization Group
	We consider the properties of vibrational dynamics on random networks, with random masses and spring constants. The localization properties of the eigenstates contrast greatly with the Laplacian case on these networks. We introduce several real-space renormalization techniques which can be used to describe this dynamics on general networks, drawing on strong disorder techniques developed for regular lattices. The renormalization group is capable of elucidating the localization properties, and provides, even for specific network instances, a fast approximation technique for determining the spectra which compares well with exact results.

	Lun Li	Theoretical Foundations for Internet Technology

	Co-Authors: S.H. Low, J.C. Doyle

	Hildegard Meyer-Ortmanns	Proposal of a complexity measure for networks
	We propose a novel measure for classifying the complexity of networks where the complexity refers to the structural and functional diversity of networks. We use graph theoretical notions that have been developed for Dynamical Linked Cluster Expansions. In that context the graphical representation serves only as a conventional tool for handling a large number of analytical contributions. Here it is supposed to be a quantitative measure for the various functions a network can fulfill.

	João G. Oliveira	Interfacial Fluctuations in a Sandpile
	We study the nature of interfacial fluctuations of a local limited sandpile model in one dimension, which displays self-organized criticality (SOC). Contrary to naive expectations, we observe that the roughness exponent depends on the way it is measured. We trace this surprising behaviour to the existence of a nontrivial steady state profile of the sandpile surface.
	Co-Authors: J. F. F. Mendes and G. Tripathy

	Vera Povolna	Fedora: FEDeration Of Research Assets
	Fedora is a technology which enables the rapid development of special purpose HTTP servers designed for the analysis and integration of biological and chemical information. These servers containing seemingly disparate data can communicate with one another via a web browser and provide the capability to mine data for complex relationships. The Fedora servers include a metabolic pathway network (Empath), Protein-Ligand Association Network (Planet), Traditional Chinese Medicines (TCM), the World Drug Index (WDI), and others.
	Co-Authors: David Weininger, Scott Dixon

	Mikhail V. Simkin	Read Before you Cite!
	We report a method of estimating what percentage of people who cited a paper had actually read it. The method is based on a stochastic modeling of the citation process that explains empirical studies of misprint distributions in citations (which we show follows a Zipf law). Our estimate is that only about 20% of citers read the original.
	Co-Authors: V.P. Roychowdhury

Poster Titles and Abstracts