Источник: http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/
Computer/OptimzationNetworks_Chaos-28Jun07.pdf

Optimization in Networks

Adilson E. Motter
Department of Physics and Astronomy and Northwestern Institute on Complex Systems,
Northwestern University, Evanston, Illinois 60208, USA

Zoltan Toroczkai
Department of Physics,
University of Notre Dame, Notre Dame, Indiana 46556, USA

(Received 1 June 2007; accepted 1 June 2007; published online 28 June 2007)

  The recent surge in the network modeling of complex systems has set the stage for a new era in the study of fundamental and applied aspects of optimization in collective behavior. This Focus Issue presents an extended view of the state of the art in this field and includes articles from a large variety of domains in which optimization manifests itself, including physical, biological, social, and technological networked systems. © 2007 American Institute of Physics.

  One of the broadest areas of research, optimization has a very long history. It comprises the variational principles in physics and engineering, the survival-of-the-fittest principles that pervade biology and economics, the founding hypotheses of numerous computer algorithms, and the frameworks for addressing the improvement of efficiency in various contexts. Whether a fact or a goal, a natural process or a man-made system, the apparently ubiquitous striving for optimization generates continuing appeal among researchers. But what is new about optimization in networked systems?

  Optimal behavior is most often connected to a function that the system performs. In numerous cases the function is multivariate or multifaceted. For example, the power grid has as its main role the transport of electric energy while minimizing generation and distribution costs and maximiz­ing at the same time reliability and quality of service. How network structure influences the global performance of such systems is probably the question that is posed most frequently in network research. Conversely, the notion of a network acts as a unifying theme in systems optimization. Indeed, with the increasing abundance of empirical and theoretical results, numerous optimization questions involving apparently unrelated systems can be addressed using a common formalism of complex networks of interacting units.

FIG. 1. (Color) Illustration of levels of abstraction represented as networks that underlie a complex system, in this case an urban area. What network is relevant to an optimization problem depends on the specific research question at hand. The inlay images are courtesy of the TRANSIMS and EpiSims teams at LANL and Virginia Bioinformatics Institute

  Traditionally, optimization has a strict mathematical definition, which refers to obtaining the solutions that strictly extremize a well-defined functional. Here we adopt a looser definition of the word by extending it to include a tendency of the system to improve its behavior as a result of a selection pressure naturally or artificially imposed. Many real-world problems are complex, with a very large parameter space. Accordingly, most quests for finding "the" optimizing or "the" best solution are doomed to failure or are not realistic. Finding a "good enough solution" or a "better solution", perhaps even in an iterative manner, becomes, however, a workable alternative. Processes in nature follow this path. Nature has evolved biological systems under pressure towards increasingly optimal behavior and much can be learned by studying the behavior of these systems. Despite the complexity of the problems, the original work on scale-free networks already suggested that there could be some general principles in network optimization: many realistic networks, including the Internet and collaboration networks, tend to grow and evolve much in the same way as some biological systems do. If selection is important in biology, then it is expected to be important in other evolving systems as well.

BROAD VIEW OF NETWORK OPTIMIZATION

  There are fundamentally four major types of optimiza­tion problems related to networked systems (the constraints are considered to be implicit in the functional).

  Type I: Structural Optimization. Find a graph G(V,E), where V is the set of nodes and E is the set of edges that extremize a given structural functional F[G].

  Type II: Dynamics Optimization on Static Graphs. For a given graph G(V,E) and a dynamical system Ф on G,

  Ф( x, x', {α}, t ) = 0          (1)

  find the values of the parameters {α} that extremize a global functional F[Ф] of the dynamics . The variables x are quantities associated with properties of the nodes and edges in the network.

  Type III: Structural Optimization for Dynamics. Given the dynamical system (1) and a set of parameters {α}, find a graph G(V,E) for which a global functional F[Ф] of the dynamics is extremized.

  Type IV: Dynamics-Driven Network Optimization. If the graph of the network evolves in time [i.e., G(V,E) = G(V,E,t)], either through an independent dynamics or through coupling to the dynamics in (1), find the values of the parameters {α} for which a global functional F[G,Ф] of the dynamics Ф and of the graph G(V,E,t) is extremized.

  Type I is a purely graph theoretic problem in that one looks for structures that have some specified properties. For example, given a fixed degree sequence on N nodes, con­struct a graph that minimizes the diameter. Problems involving optimal assignment of edge-weights and -directionality also belong to this class. Type II is a "flow extremization" problem. For example, given a roadway network, what should be the speed limit for cars on every street such that jamming is minimized? Type III commonly occurs in design problems: given a flow dynamics, such as packet flow in packet switched networks, find the graph structures optimal for information throughput. Other important examples in­clude the optimization of synchronous and coherent behavior. Type IV is also common, though sometimes very difficult to solve because properties of both graph structure and dy­namics are allowed to change. This is also the most relevant case to the study of emergent properties in evolving systems. Robustness and vulnerability problems fall into this class when the flow through the network can change the structure, which in turn changes the flow. Prime examples of this are cascading failures in networked systems, such as power grids (see the article by Dobson in this issue).

  Optimization in complex networks is thus of broad significance, incorporating static and dynamical properties and serving as an instrument to analyze and control the evolution and function of both natural and engineered systems.

THIS FOCUS ISSUE

  This Focus Issue brings together contributions on network structure and dynamics, with emphasis on optimization problems and their applications to infrastructure and biologi­cal systems. Key topics discussed include the optimization in the evolution and functioning of biological systems, optimization and cost balance analysis in the design of infrastruc­ture networks, and optimization principles emerging from the interplay between network structure and dynamics.

  In the context of technological and infrastructure networks, Danila consider routing optimization in net­work transport, Dobson discuss how competition be­tween efficiency and robustness leads to a SOC-based model for the power-grid dynamics, Guclu study how fluctuations and synchrony in distributed processing networks relate to the network structure, Gulbahce addresses the optimization of jamming on gradient networks, while Teuscher analyzes the impact of performance metrics in network-on-chip designs.

  In the context of biological networks, Almaas studies metabolic flux patterns derived from flux-balance optimiza­tion assumptions, Balcan and Erzan discuss a statistical physics description of content-based networks that can serve as models for gene regulatory networks, Mahmoudi consider the propagation of external regulatory information and asynchronous dynamics in random Boolean networks, and Riecke study a rich variety of dynamical states in the activity of small-world networks of excitable neurons.

  Other dynamical processes are also considered. Barrat address the emergence of consensus in linguistic con­ventions, Bogacz consider condensation and far from equilibrium dynamics on networks, and Freire analyze synchronization and complex spatio-temporal patterns in networks of cellular automata.

  More related to the structural properties of the networks, Bianconi studies how the degree distribution follows from the extremization of a free-energy function, Kim and Kahng derive spectral densities for an important class of weighted complex networks, Kim analyze the fractal properties of complex networks, and Minnhagen and Bernhardsson study how the degree distribution relates to maximization of information.

  Summing up, optimization of performance and robust­ness is a common property of naturally evolved systems and is a desirable property in most man-made systems. There is now increasing evidence that the functioning of complex systems as diverse as cellular metabolism and power grids lies deep in the properties of underlying complex networks. This evidence has generated increasing interest on dynamical processes in complex networks and on how the interplay between these processes and network structure influences the performance and robustness of the system. Notably, established areas such as resource management, epidemic spreading, communication processes, synchronization dynamics, cellular biology, and cascading failures are at the leading edge of the current research on network optimization. We hope that this Focus Issue will provide the reader with an up to date overview of this exciting area of research.

ACKNOWLEDGMENTS

  We would like to thank the Center for Nonlinear Studies and the Complex Systems Group at Los Alamos National Laboratory, particularly Robert Ecke, Adam Shipman, Donald Thompson, and Elissa Vigil, for sponsoring and coordinating the Workshop that led to this Focus Issue. We specially thank Chaos Editorial Office members Janis Ben­nett and David Campbell for their prompt assistance and all the authors for their invaluable contributions.

1. D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks", Nature (London) 393, 440-442 (1998).
2. A.-L. Barabasi and R. Albert, "Emergence of scaling in random net­works", Science 286, 509-512 (1999).
3. R. Ferrer i Cancho and R. V. Sole, "Optimization in complex networks", Lect. Notes Phys. 625, 114-126 (2003).
4. T. Nishikawa, A. E. Motter, Y.-C. Lai, and F. C. Hoppensteadt, "Smallest small-world network", Phys. Rev. E 66, 046139 (2002).
5. R. Guimera, A. Arenas, A. Diaz-Guilera, F. Vega-Redondo, and A. Ca-brales, "Optimal network topologies for local search with congestion", Phys. Rev. Lett. 89, 248701 (2002).
6. The Structure and Dynamics of Networks, edited by M. E. J. Newman, A.-L. Barabasi, and D. J. Watts (Princeton University Press, Princeton, NJ, 2006).
7. A. E. Motter, M. A. Matias, J. Kurths, and E. Ott, "Dynamics on complex networks and applications", Physica D 224, vii-viii (2006).
8. G. Caldarelli, Scale-Free Networks: Complex Webs in Nature and Tech­nology (Oxford University Press, London, 2007).
9. L. da F. Costa, F. A. Rodrigues, G. Travieso, and P. R. Villas Boas, "Characterization of complex networks: A survey of measurements", Adv. Phys. 56, 167–242, 2007.
10. S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, "Critical phenom­ena in complex networks", arXiv:0705.0010.
11. S. Eubank, H. Guclu, V. S. A. Kumar, M. Marathe, A. Srinivasan, Z. Toroczkai, and N. Wang, "Modelling disease outbreaks in realistic urban social networks", Nature (London) 429, 180-184 (2004).
12. A. E. Motter, "Cascade control and defense in complex networks", Phys. Rev. Lett. 93, 098701 (2004).
13. B. Danila, Y. Yu, J. A. Marsh, and K. E. Bassler, "Transport optimization on complex networks", Chaos 17, 026102 (2007).
14. I. Dobson, B. A. Carreras, V. E. Lynch, and D. E. Newman, "Complex systems analysis of series of blackouts:
15. H. Guclu, G. Korniss, and Z. Toroczkai, "Extreme fluctuations in noisy task-completion landscapes on scale-free networks", Chaos 17, 026104 (2007).
16. N. Gulbahce, "Optimization in gradient networks", Chaos 17, 026105 (2007).
17. C. Teuscher, "Nature-inspired interconnects for self-assembled large-scale network-on-chip designs", Chaos 17, 026106 (2007).
18. E. Almaas, "Optimal flux patterns in cellular metabolic networks", Chaos 17, 026107 (2007).
19. D. Balcan and A. Erzan, "Content-based networks: A pedagogical over­view", Chaos 17, 026108 (2007).
20. H. Mahmoudi, A. Pagnani, M. Weigt, and R. Zecchina, "Propagation of external regulation and asynchronous dynamics in random Boolean net­works", Chaos 17, 026109 (2007).
21. H. Riecke, A. Roxin, S. Madruga, and S. A. Solla, "Many attractors, long chaotic transients, and failure in small-world networks of excitable neu­rons", Chaos 17, 026110 (2007).
22. A. Barrat, A. Baronchelli, L. Dall'asta, and V. Loreto, "Agreement dynam­ics on interaction networks
23. L. Bogacz, Z. Burda, W. Janke, and B. Waclaw, "Balls-in-boxes conden­sation on networks", Chaos 17, 026112 (2007).
24. J. G. Freire, O. J. Brison, and J. A. C. Gallas, "Spatial updating, spatial transients, and regularities of a complex automaton with nonperiodic ar­chitecture", Chaos 17, 026113 (2007).
25. G. Bianconi, "A statistical mechanics approach for scale-free networks and finite-scale networks", Chaos 17, 026114 (2007). D. Kim and B. Kahng, "Spectral densities of scale-free networks", Chaos 17, 026115 (2007).
26. J. S. Kim, K.-I. Goh, B. Kahng, and D. Kim, "A box-covering algorithm for fractal scaling in scale-free networks", Chaos 17, 026116 (2007). P. Minnhagen and S. Bernhardsson, "Optimization and scale-freeness for complex networks", Chaos 17, 026117 (2007).
27. C. L. Barrett, R. J. Beckman, K. P. Berkbigler, TRANSIMS Vol. 4 - Calibrations, Scenarios, and Tutorials, Los Alamos Unclassified Report 00-1766, August 2004.