Optimization in Complex Networks

PROGRAM

Sunday, June 18, Pre-registration, 8:00 - 9:00 pm at Hilltop House Hotel.

	Monday June 19	Tuesday June 20	Wednesday June 21	Thursday June 22

8:15 - 8:30	OPENING
8:30 - 9:10	Newman	Dobson	Reichhardt	Sales-Pardo

9:10 - 9:50	Ravasz	Eckmann	Kim	Almaas

9:50 - 10:30	Korniss	Havlin	Erzan	Werley
10:30 - 10:50	COFFEE BREAK
10:50 - 11:30	Zecchina	Minnhagen	Burda	CLOSING

11:30 - 12:10	Motter	Bassler	Segre

12:10 - 12:30	Aaron Clauset	Jin Yang	Eduardo López
12:30 - 2:00	LUNCH
2:00 - 2:40	Perelson	Nishikawa	Barrat

2:40 - 3:20	Chertkov	Hastings	Anghel

3:20 - 4:00	Pecora	Vespignani	Kahng
4:00 - 4:20	COFFEE BREAK
4:20 - 5:00	Edwards	Teuscher	Bradbury Science Museum Visit

5:00 - 5:20	Thadakamalla	Güçlü

5:20 - 5:40		Outkin
	Posters (6pm)	Posters (6pm)
			Banquet (7pm)

Every invited speaker has 30 minutes reserved for his/her talk
and
10 minutes reserved for questions

Contributed talks are 15 minutes and 5 minutes questions

	Eivind Almaas	Modelling of cellular metabolic networks
	During the last few years, much effort has been focused on understanding dynamical aspects of complex networks. The cellular metabolism, where nodes correspond to metabolites and links indicate chemical reactions, is an excellent model system where computational predictions for dynamics can be compared with experimental results. I will present recent insights [1,2] on the optimal organization of cellular metabolism. We find that, while most metabolic reactions have small fluxes, the metabolism\'s activity is dominated by an interconnected sub-network of reactions with very high fluxes. For the bacteria H. pylori and E. coli and the yeast S. cerevisiae, the metabolism responds to changes in growth conditions by reorganizing the rates of select reactions predominantly within this high-flux backbone [1]. Furthermore, these networks are organized around a metabolic core -- a set of reactions that are always in use. Strikingly, the activity of the metabolic core reactions is highly synchronized, and the core reactions are significantly more essential and evolutionary conserved than the non-core ones [2]. [1] E. Almaas, B. Kovacs, T. Vicsek, Z. N. Oltvai and A.-L. Barabasi. Nature 427, 839 (2004). [2] E. Almaas, Z. N. Oltvai and A.-L. Barabasi.PLoS Comput. Biol. 1(7):e68 (2005).

	Marian Anghel	Numerical experiments in power grid cascade control
	We introduce a stochastic model that describes the quasi-static dynamics of an electric transmission network under perturbations introduced by random load fluctuations, random removing of system components from service, and random repair times for the failed components. We implement optimal system corrections for removing line overloads in a damaged or stressed transmission network based on an automatic dispatching of sources (generators) and sinks (bus loads). We use a linear approximation to the network flow equations which provides a good estimation to the flow of real power through the transmission lines. Because of the linear nature of the equations, it is straightforward to apply linear programming techniques that optimize the dispatching of sources and sinks and eliminate the network overloads associated with a damaged system. The degree of tolerance of the magnitude of line overloads is an automatic control (optimization) parameter that is adjusted to trade off automatic load shed without propagating cascades versus reduced load shed and an increased risk of propagating cascades. We use this stochastic model to numerically investigate the optimal cascade control of a large transmission network (ERCOT), as load demand increases, stressing the power transmission network, and as we vary the random failure times and the average system repair time. We discuss the conditions under which overload tolerance can reduce the overall cost of operating the system.
	K. Werley

	Alain Barrat	Dynamics of the Naming Game on complex networks
	The Naming Game is a model of non-equilibriun dynamics for the self-organized emergence of a linguistic convention or a communication system in a population of agents with pairwise local interactions. We present a study of its dynamics on complex networks, that can be considered as the most natural topological embedding for agents involved in language games and opinion dynamics. Except for some community structured networks on which metastable phases can be observed, agents playing the Naming Game always manage to reach a global consensus. Convergence on complex networks is shown to achieve a trade-off between agents embedded on regular lattices and agents allowed to interact on a complete graph, with small memory capacity requirements and fast convergence times.
	Co-authors: A. Baronchelli, L. Dall'Asta, V. Loreto

	Kevin E Bassler	Optimal congestion-gradient driven transport on complex networks
	We present a study of transport on complex networks with routing based on local information. Particles hop from one node of the network to another according to a set of routing rules with different degrees of congestion awareness, ranging from random diffusion to rigid congestion-gradient driven flow. Each node can be either source or destination for particles and all nodes have the same routing capacity, which are features of ad-hoc wireless networks. It is shown that the transport capacity increases when a small amount of congestion awareness is present in the routing rules, and that it then decreases as the routing rules become too rigid when the flow becomes strictly congestion-gradient driven. Therefore, an optimum value of the congestion awareness exists in the routing rules. It is also shown that, in the limit of a large number of nodes, networks using routing based on local information jam at any nonzero load. Finally, we study the correlation between congestion at node level and a betweenness centrality measure.

	Zdzislaw Burda	Zero-range migration and condensation on networks
	We discuss a stochastic process which describes particles hopping between neighboring sites of a lattice with hopping rates depending only on the occupation of the departure site. The process usually leads to a particle condensation on one site. We compare statical and dynamical properties of the condensate for homogenous and heterogenous lattices.

	Mikhail Chertkov	Understanding and Improving Belief Propagation for Graphical models withh loops
	Considering a discrete and finite statistical model of a general position we introduce an exact expression for the partition function in terms of a finite series. The leading term in the series is the Bethe-Peierls (Belief Propagation)-BP contribution, the rest are expressed as loop-contributions on the factor graph and calculated directly using the BP solution. Local gauge symmetry transformations that clarify an important invariant feature of the BP solution are revealed. The individual terms change under the gauge transformation while the partition function remains invariant. The requirement for all individual terms to be non-zero only for closed loops in the factor graph (as opposed to paths with loose ends) is equivalent to fixing the first term in the series to be exactly equal to the BP contribution. Application of the loop calculus for improving decoding of LDPC codes in the error-floor domain is briefly discussed. This talk will be based on two recent papers by V. Chernyak (Wyane State U.) and the speaker -- http://arxiv.org/abs/cond-mat/0603189 and cond-mat/0601487.
	Co-authors: V. Chernyak

	Ian Dobson	Criticality, Self-Organization, And Cascading Failure In Electric Power System Blackouts
	The large-scale electric power transmission networks that underpin our society occasionally fail in spectacular cascading blackouts. The failures propagate in a rich variety of ways, including redistributed network flows surpassing thresholds. Simulations of the cascading failure in blackouts suggest phase transitions in blackout risk as power system loading is increased. Viewing the slow upgrade of the transmission network as complex system dynamics suggests an explanation for the observed power-law distribution of the sizes of North American blackouts. The network upgrade process continually improves the components that fail in blackouts so that the network engineering is viewed as part of the complex dynamics. We propose to efficiently determine blackout risk from cascading failure simulations by estimating how much failures propagate. This is joint work with Benjamin Carreras at Oak Ridge National Laboratory, Tennessee and David Newman at the University of Alaska- Fairbanks and Kevin Wierzbicki at the University of Wisconsin.
	Co-authors:. B. Carreras, D. Newman and K. Wierzbicki

	Jean-Pierre Eckmann	Triangles in Graphs
	In this talk, I will present some results on (random) graphs with many triangles. Because these are very small ensembles in the set of all random graphs, some surprising behavior seems to appear. Most of the results are conjectural, and I hope someone in the audience will find a way to prove them.

	Jeremy S. Edwards	Computational Analysis of Metabolic Networks
	Systems biology is likely to have a great impact on the biological sciences in the future. For example, whole genome sequencing, DNA microarrays and proteomics are providing information that can be used to reconstruct cellular networks. However, in order to fully exploit these data, we must develop mathematical and computational methods to interpret and predict the behavior of cellular networks. In this talk, I will describe our computational and techniques for elucidating metabolic network behavior. I will discuss a constraints based approach for determining the flux in metabolic networks without the requirement of kinetic parameters. I will also demonstrate how we have been able to utilize this approach to study the adaptation of metabolic networks, and I will describe a high throughput genome sequence approach that can be used to study the genetic changes associated with adaptation.

	Ayse Erzan	Modelling the topology and dynamics of Content Based Networks
	A content-based network model [1,2] represents the information associated with each node by one or more a Boolean strings. The rule for the formation of a bond between a pair of nodes calls for the matching of a "key" string with a substring of the corresponding "lock." This elementary rule is very generic. By varying the distribution of the information associated with the nodes, one may independently modulate different topological properties of the network[3,4], such as the degree distribution, clustering coefficient or the k-core decomposition[5]. The k-core decomposition turns out to be the most stringent check, discriminating between different models which may yield similar results with respect to other features. Using our content-based network with random strings for the Transcription factors and the Promoter Regions[6], we have been able to model the gene regulatory network of Yeast to great accuracy, using only the experimentally known distribution of the information content of the Transcription Factors[7] and varying the exponent of the length distribution of the intergenic regions[8] (where the Promoter Regions are found) to optimize the k-core fit. The dynamics of emergent content based networks are found to be much more stable and robust with respect to external perturbations in comparison to random scale free networks.[9] 1. D. Balcan, A. Erzan, "Random model for RNA interference yields scale free network, " Eur. Phys. J. B, 38, 253-260 (2004) 2. M. Mungan, A. Kabakcioglu, D. Balcan,A. Erzan, "Analytical solution of a stochastic content-based network model," J. Phys A: Math Gen. 38, 9599-9620 (2005). 3. A. Kabakcioglu, M. Mungan, D. Balcan,A. Erzan, in preparation. 4. Y. Sengun, A. Erzan, "Content based networks with duplication and divergence," Physica A, to appear. 5. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, A. Vespignani, "k-core decomposition: a tool for the visualization of large scale networks," cs.NI/0504107. 6. B. Alberts et al., The Molecular Biology of the Cell (Garland Science, N.Y., 2002)Chapter 9. 7. C.T. Harbison et al., "Transcriptional regulatory code of a eukaryotic genome," Nature. 431, 99-104 (2004). 8. Th. Oikonomou and A. Provata, "Non-extensive trends in the size distribution of Coding and Non-coding DNA sequences in the Human Genome," Eur. Phys. J. B, in press. 9. D. Balcan and A. Erzan, "Dynamics of Content-Based Networks," Proceedings of ICCS 2006 (Lecture Notes Series, Springer Verlag), to appear; "Random Boolean Dynamics on Content-Based Networks," in preparation.

	Matthew B. Hastings	Community Detection as an Inference Problem
	Community detection is a well-studied problem with applications to biological, social, and other networks. Remarkably, however, there is no good definition of this problem. In this talk, we show that one of the standard tests of community detection algorithms, the "four groups" test due to Newman and Girvan, provides a precise definition of community detection as a problem in Bayesian inference. We then apply techniques used for other Bayesian inference problems, in particular the belief propagation algorithm developed for decoding error-correcting codes in communication over a noisy channel, to develop a very accurate and fast community detection algorithm.

	Shlomo Havlin	Weighted Networks: Optimal Paths and Super-Highways
	We study the statistical properties of optimal paths in weighted complex networks with general distribution of weights. We find a general criterion for the strength of disorder and show the relation of optimal paths to percolation, in both strong and weak disorder limits. Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centralit, the number of times a node (or link) is used by transport paths. One component, superhighways, is the infinite incipient percolation cluster, for which we find that nodes (or links) with high centrality dominate traffic. For the other component, roads, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. This finding is useful since one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways. References: 1. Lopez et al Phys. Rev. Lett. 94, 248701 (2005) 2. Braunstein et al, Phys. Rev. Lett. 91, 168701 (2003) 3. Yiping et al, Phys. Rev. Lett. 96, 068702 (2006) 4. Wu et al, Phys. Rev. Lett. 96, 148702 (2006)

	Byungnam Kahng	Fractality versus Self-similarity in Scale-free Networks
	Fractal scaling---a power-law behavior of the number of boxes needed to tile a given network with respect to the lateral size of the box---is studied. We introduce a new box-covering algorithm that mimics the random sequential packing algorithm; this algorithm enables effective computation and easy implementation. Fractal networks are viewed as comprising a skeleton and shortcuts. The skeleton, embedded underneath the original network, is a special type of spanning tree based on the edge betweenness centrality; it provides a scaffold for the fractality of the network. When the skeleton is regarded as a branching tree, it exhibits a plateau in the mean branching number as a function of the distance from a root. For non-fractal networks, on the other hand, the mean branching number decays to zero without forming a plateau. Based on these observations, we construct a fractal network model by combining a random branching tree and local shortcuts. The scaffold branching tree can be either critical or supercritical, depending on the small-worldness of a given network. For the network constructed from the critical (supercritical) branching tree, the average number of vertices within a given box grows with the lateral size of the box according to a power-law (an exponential) form in the cluster-growing method. The distribution of box masses, i.e., the number of vertices within each box, follows a power law $P_m(M)\sim M^{-\eta}$. The exponent $\eta$ depends on the box lateral size $\ell_B$. For small values of $\ell_B$, $\eta$ is equal to the degree exponent $\gamma$ of a given scale-free (SF) network, whereas $\eta$ approaches the exponent $\tau=\gamma/(\gamma-1)$ as $\ell_B$ increases, which is the exponent of the cluster-size distribution of the random branching tree. Next, we show that the fractality and self-similarity are disparate notions in SF networks. We study the origin of scale invariance (SI) of the degree distribution under the coarse-graining that a varying number of vertices belonging to a community or a box in fractal analysis is grouped into a supernode. The renormalized degree $k^{\prime}$ of a supernode scales with its box mass $M$ as $k^{\prime} \sim M^{\theta}$. The two exponents $\eta$ and $\theta$ can be nontrivial as $\eta \ne \gamma$ and $\theta < 1$. They act as relevant parameters in the renormalization transformation. The SI appears either when $\gamma \le \eta$ or under the condition of $\theta=(\eta-1)/(\gamma-1)$ when $\gamma> \eta$, irrespective of whether the original SF network is fractal or non-fractal.
	Co-authors: J.S. Kim, K.-I. Goh, G. Salvi, E. Oh, and D. Kim

	Doochul Kim	Application of replica method to scale-free networks: spectral density> and spin-glass transition.
	Structural and dynamics properties of complex networks are often calculated through averages over an approriate ensemble of graphs. This process is akin to the disorder averages to which the replica method is successively applied. Here, we formulate the replica method for a class of graph ensembles where the links, although inhomogeneous, are independently created. We then apply the formalism to find the spectral densities of scale-free networks and the spin-glass transitions of the Ising model defined on scale-free networks.

	György Korniss	Synchronization and Flow Optimization in Weighted Complex Networks with Resource or Cost Constraints
	By obtaining the spectrum of the networkLaplacian, we treat two prototypical problems onthe same footing: the behavior of the \"height-height\" correlations (or the\"roughness\") in synchronization landscapes innoisy environments and the effective two-pointresistance of the same network. Here, we focus onweighted complex networks and the associatednetwork Laplacian where the strength of a link isproportional to $(k_{i}*k_{j})^{\\beta}$; $k_{i}$and $k_{j}$ are the degrees of the nodesconnected by the link. Further, the total costassociated with such a distribution of the link\"quality\" in the network is fixed. We determinethe optimal value of the exponent $\\beta$ fornetworks with heterogeneous (scale-free) andclose-to-homogenous (small-world) degreedistributions, given the above constraint. [1] A.E. Motter, C. Zhou, and J. Kurths, Phys.Rev. E 71, 016116 (2005). [2] C. Zhou and J. Kurths, Chaos 16, 015104(2006). [3] E. Lopez, S.V. Buldyrev, S. Havlin, and H.E.Stanley, Phys. Rev. Lett. 94, 248701 (2005). [4] B. Kozma, M.B. Hastings, and G. Korniss,Phys. Rev. Lett. 95, 018701 (2005). [5] G. Korniss, M.B. Hastings, K.E. Bassler, M.J.Berryman, B. Kozma, and D. Abbott, Phys. Lett. A350, 324 (2006).

	Peter Minnhagen	Scale-free directed networks and in-out-link correlations
	Two classes of directed networks are discussed. One class is self-organizing into scale-free degree-distributions in the in- and out-link degrees, as a direct consequence of the Friendly Merging strategy which is a simplified strategy for company merging. It is shown that this network structure is to large extent described by an even simpler model A. An important feature of this network structure is the correlation between in- and out-link degrees for a node of a given size. These correlations are described in some detail. It is shown that metabolic networks have very much the same network structure and hence the same in-out link correlations. The other class is self-organized by the Hostile Merging strategy and gives rise to a different network structure which to large extent is described by a model B. This alternative is briefly discussed and compared to a yeast transcriptional network.

	Adilson E. Motter	Network-based Manipulation of Cellular Metabolism
	I will discusss a theoretical framework for the in silico prediction of environmental changes and mutations of enzyme-encoding genes capable of enhancing or suppressing the production of specific metabolic compounds.

	Mark E.J. Newman	Modularity, community structure, and the spectral properties of networks
	Many networks of interest in the sciences are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has been the subject of a considerable volume of recent research. One highly effective approach is the optimization of the quality function known as ``modularity'' over the possible divisions of a network. The modularity can in turn be expressed in terms of the eigenvectors of a particular characteristic matrix for the network, which we call the modularity matrix, and this expression leads to a new spectral method for community detection that returns results as good or better than competing methods in shorter running times. We illustrate the method with applications to a variety of networks from different fields.

	Takashi Nishikawa	Maximum Performance at Minimum Cost in Network Synchronization
	We consider optimization problems on synchronization of general oscillator networks: maximization of synchronizability and minimization of synchronization cost. By developing an extension of the well-known master stability framework to the case of non-diagonalizable Laplacian matrices, we show that the solution sets of the two optimization problems coincide and are simultaneously characterized by a simple condition on the Laplacian eigenvalues. Among these optimal networks, a large number can be intuitively characterized as being hierarchical, which may provide insights into the mechanism behind similar structures observed in real complex networks in which synchronization plays a significant role. We also prove the fact that most of the optimal networks are non-diagonalizable, which necessitates the extension of the master stability framework. By using oriented spanning trees, we explicitly and systematically construct simultaneous solutions to the optimization problems, even under a network topological constraint.
	Co-authors:

	Louis Pecora	Dynamics of oscillators in Semi-Random Networks
	Semi-random networks include smallworld networks and scale-free networks. Much work done on the statistical properties of such networks (average distance between nodes, robustness to losing connections) and some work on the dynamics of network evolution, but little has been done in treating dynamics on the networks, that is examining the behavior of the nodes as oscillators linked with the network topology. Starting with a simple, but fundamental type of dynamics, synchronization of all oscillators -- the uniform state in a continuium system, we ask, how does the network topology affect dynamics on the lattice if the nodes are oscillators? We show that we can use a master stability approach to synchronization stability to probe synchronization in arbitrary systems in a direct and generic way. This general formulation allows us to say something about the patterns in the desynchronization of the oscillators. We also compare the results for semi-random networks to highly regular networks/graphs and show using graph theory why simple, smallworld networks may be the best topology to attain synchronization of the nodes.
	Co-authors:

	Alan Perelson	Optimizing Influenza Vaccination and Vaccines
	This talk will be a slight departure from the standard epidemiological model on a network. Rather than considering the spread of influenza, I will present an agent-based model of the immune response to influenza infection and the effects of vaccination.I will introduce the idea of shape space and show how one can represent flu strains and antibody molecules as points in this space. Using notions of distance in shape space, one can then examine the effects of multiple flu infections or annual flu vaccinations. I will then show that under some circumstances people who get repeated annual flu vaccinations can do worse than people who only get occasional vaccinations, while under other circumstances they do better. This then raises the issue of optimizing the flu vaccine to avoid the potential negative effects of multiple exposures to flu or flu vaccines.
	Co-authors:

	Erzsébet Ravasz	Networks in Protein Folding
	Fast and reliable folding to a unique three dimensional shape is crucial for protein functionality. The consensus in protein folding today is that most functional proteins evolved to have free energy landscapes with a funnel structure. The general conditions an amino-acid sequence must obey in order to produce a fast and reliably folding protein are still largely unknown. We take a networks approach to protein folding by identifying different protein conformations with nodes, while an elementary step of the system (rotation around a bond) that takes one configuration to another is defined as a link. The energies of configurations are scalar quantities associated with each node. Using this approach we can show that the scale-free nature of the observed protein conformation networks can be explained by simple results obtained on gradient networks. We also show the sufficient conditions for a configuration network model that is able to produce funneled landscapes.
	Co-authors: Zoltán Toroczkai and Gnana Gnanakaran

	Cynthia Reichhardt	Boolean models for genetic regulatory networks
	The genetic regulatory networks responsible for cell differentiation and cell cycle control can be modeled by Boolean logic networks of varying connectivity, in which each node in the network represents a gene. We describe the underlying motivation for these models, and propose a new method for categorizing the strategy functions assigned to each node based on symmetry properties of Ising hypercubes. Under biologically relevant conditions, interactions between nodes strongly restrict the available phase space of the network, implying that the experimentally observed conservation of wild-type phenotype may arise automatically due to the combinatoric properties of the underlying genetic network.

	Marta Sales-Pardo	Extracting and representing the hierarchical organization of complex systems
	Extracting meaning and understanding from the growing sea of biological data is one of the greatest scientific challenges facing us. Here, we introduce and validate a method that is able to accurately extract the hierarchical organization of complex networks. To validate our method, we apply it to both model and real-world networks, including the air-transportation network, an electronic circuit, an email exchange network for a Catalan university, and several metabolic networks. Our method thus opens the door to obtaining, in an unsupervised manner, multi-scale representations of complex systems.

	Daniel Segre	Perturbing networks: computational approaches to the evolution and organization of metabolism
	We are interested in the evolutionary dynamics of biological networks, in particular in the interplay between response to genetic and environmental perturbations, genomic-level functional organization, and optimal adaptation. By implementing steady state (flux balance) models of whole-cell biochemical networks, and computing epistatic interactions resulting from double gene deletions, one can make new hypothesis about the organization of genes and pathways into hierarchical modules. To go beyond single organisms, and learn about metabolism at the ecosystem level, different approaches may be required. By relying on reaction topology and a network expansion algorithm it is possible to study the effect of key molecules (such as oxygen) on the evolution of life.

	Christof Teuscher	Wires Growing in a Chip Near You: On the Future of Complex Nanoscale Interconnect Networks
	With ongoing miniaturization, the importance of interconnects on electronic circuits has outrun the importance of transistors as a dominant factor of performance. It is believed that technology alone cannot solve the global interconnect challenges and that simple scaling will no longer satisfy performance requirements as feature sizes continue to shrink. In addition, future nanoscale electronics and novel fabrication methods, such as self-assembly, bear many challenges, but also unique opportunities for novel interconnect paradigms. In this talk I will first discuss the complex networks of electronic chips and highlight specific challenges. Next, I will outline possible and unconventional ways to build Nature-inspired complex interconnect networks for future nanoscale electronics. Self-assembling and interconnecting multi-billion component systems in a largely random manner would likely lower circuit fabrication costs significantly while such an alternative interconnect network would offer very interesting properties in terms of transport characteristics and robustness.

	Alessandro Vespignani	Epidemic spreading in complex metapopulation systems
	Networks which trace the activities and interactions of individuals, social patterns, transportation fluxes and population movements on a local and global scale have been analyzed and found to exhibit complex features encoded in large scale heterogeneity, self-organization and other properties typical of complex systems. We review the impact of these complex features on the behavior of epidemic spreading processes. We discuss the effect of the heterogeneity of real world transportation networks in realistic meta-population models for the forecast of the large scale spreading of emerging diseases. The optimization of containment policies and their dependence on the underlying network are discussed for specific diseases.

	Kenneth Werley	Using Unphysical AC Solutions to Fix (Dispatch) Severely Damaged Electric Power Transmission Systems
	The identification of critical elements in electric power transmission networks involves evaluating severely damaged systems. Unfortunately, commercial AC solvers often fail to converge to power-flow solutions under severe contingency conditions. Without solutions, network-fixing algorithms, including generation dispatching and load shedding, cannot be applied to evaluate the severity of the contingency. A Quasi-linear AC Solver (QACS) developed at Los Alamos, provides a more robust solution finder. Even though these solutions may be highly inaccurate, or even unphysical, (in voltage collapse regimes), they can be used by automatic tools to identify and fix network problems. An example applies this unique approach to a solution with negative voltages to identify and optimally modify the network to achieve accurately computed operation within design limits.
	Co-authors:

	Riccardo Zecchina	Optimization over dense networks of constraints
	Many combinatorial optimization problems like, e.g. network reconstruction, machine learning and multi-user decoding, can be represented in terms of a dense graph of interacting constraints, each one involving an extensive number of discrete variables. Such problem are extraordinarily difficult to solve for traditional local search heuristics and often sub-optimal solutions have to be accepted. In this talk I will discuss how to deal with these problems by message-passing algorithms originally designed for sparse graphs. As applications I will consider learning in networks of switch-like synapses and reconstruction of regulatory networks fromexpression data.

Contributed Talks

	Aaron Clauset	How Do Networks Become Navigable?
	Networks created and maintained by social processes, such as the human friendship network and the World Wide Web, appear to exhibit the property of navigability: namely, not only do short paths exist between any pair of nodes, but such paths can easily be found using only local information. It has been shown that for networks with an underlying distance metric, algorithms using only local information perform extremely well if there is a power-law distribution of link lengths. However, it is not clear why or how real networks might develop this distribution. In this talk we describe a decentralized "rewiring" process, inspired by surfers on the Web, in which each surfer attempts to travel from their home page to a random destination, and updates the outgoing link from their home page if this journey takes too long. We show that this process does indeed cause the link length distribution to converge to a power law, achieving a routing time of O(log^2 n) on networks of size n.
	Co-authors:

	Hasan Güçlü	Statistics of Extreme Fluctuations in Small-World-Synchronized Computing Networks
	Synchronization is a fundamental problem in natural and artificial coupled multi-component systems. We investigate to what extent small-world couplings (extending the original local relaxational dynamics through the random links) lead to the suppression of extreme fluctuations in the synchronization landscape of such systems. In the absence of the random links, the steady-state landscape is "rough" (strongly de-synchronized state) and the average and the extreme height fluctuations diverge in the same power-law fashion with the system size (number of nodes). With small-world links present, the average size of the fluctuations becomes finite (synchronized state). For exponential-like noise the extreme heights diverge only logarithmically with the number of nodes, while for power-law noise they diverge in a power-law fashion. The statistics of the extreme heights are governed by the Fisher–Tippett–Gumbel and the Fréchet distribution, respectively. We also study the extreme-value scaling and distributions in scale-free networks. We illustrate our findings through an actual synchronization problem in parallel discrete-event simulations.
	Co-authors:

	Eduardo López	Universal Behavior of Optimal Paths in Weighted Networks with General Disorder
	We study the statistics of the optimal path in lattices, random and scale-free networks, where weights w are taken from a general distribution P(w). We find that different types of disorder lead to the same universal behavior. Specifically, we find that a single parameter (S~AL^{-1/nu} for d-dimensional lattices, and S~AN^{-1/3} for random networks) determines the distributions of the optimal path length, including both strong and weak disorder regimes. Here nu is the percolation connectivity exponent, and A depends on the percolation threshold and P(w). We show that for a uniform P(w), Poisson or Gaussian, the crossover from weak to strong does not occur, and only weak disorder exists.

	Alexander V. Outkin	Best Response Dynamics and Neural Networks
	We consider a population of players in a setting that allows analyzing local as well as global interaction using the formalism of automata networks. We show that best response is a special case of a biased majority (minority) imitation. We demonstrate that the stochastic dynamics of the system will always have a stationary distribution. In a special case of asynchronous updating and logistic noise, this distribution is of Boltzmann type. We further show that with a Boltzmann distribution, the long-run equilibria are associated with a minimum of a cost function. Comparison of our results with the existing literature suggests robustness of the previous long-run equilibrium results. In the case of differentiation games, we demonstrate the sensitivity of long-run equilibrium to the choice of interaction structure.

	Hari P. Thadakamalla	Local search and heterogeneities in weighted complex networks
	We present a new algorithm based on a network measure, local betweenness centrality (LBC), for search in complex networks that are heterogeneous in node degree and edge weights. LBC search utilizes both the heterogeneities and performs the best in scale-free weighted networks. We also show that unlike high-degree search, the scaling of LBC search algorithm with network size decreases for larger heterogeneities. Further, we demonstrate that the information used by LBC search is optimal since it performs as well as BC (betweenness centrality) based search that considers the maximum information available about a node’s first neighbors.

	Jin Yang	Modeling and simulation of signal transduction networks with molecular finite automata - reducing combinatorial complexity
	To simulate cell signaling systems using a chemical reaction model, a set of biochemical species and their reactions must be specified. However, the chemical reaction approach to quantitatively study cell signaling systems is less efficient in both computational and analytical respects. Here we propose a computer science formalism to describe individual proteins as computing devices referred to as molecular finite automata (MFA) and the dynamics of cell signaling systems as interactions among MFA. Models specified with the formal structure of MFA explicitly represent the internal dynamics and environmental information of signaling proteins. Large-scale protein-protein interaction networks featuring combinatorial complexity, which is computationally intractable for reaction models, can be efficiently simulated using a MFA-based model framework.