Research 

Synchronization and Collective Dynamics in Complex Networks

Group members at Rensselaer:
Gyorgy Korniss (PI)
current graduate students: Qiming Lu
former graduate students: Hasan Guclu,  Balazs Kozma,
Collaborators:
Mark Novotny (Co-PI, Mississippi State Univ.), Zoltan Toroczkai (Notre Dame), Matthew Hastings (CNLS, Los Alamos), Kevin Bassler (University of Houston), Zoltan Racz (Eotvos University, Budapest), Boleslaw Szymanski (Computer Science, and Center for Pervasive Computing and Networking, Rensselaer)
 

Supported by NSF  DMR-0426488  under the Information Technology Research Initiative, 
the Research Corporation, and Rensselaer.

News coverage in printed and electronic media on our group's work

Recent talks:
"Random Walks, Resistor Networks, and Synchronization in a Noisy Environment in Weighted Complex Networks",
(NetSci 2007: International Workshop and Conference on Network Science, New York Hall of Science, Queens, New York, May, 2007)
"Naming Games in Spatially-Embedded Random Networks'',
(American Association for Artificial Intelligence Fall Symposium Series, Alexandria, VA, October, 2006)
"Synchronization in Weighted Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency",
(Workshop in Optimization in Complex Networks, CNLS, Los Alamos National Laboratory, June, 2006)
Synchronization, Transport Efficiency, and Scaling in Small-World Networks'',
(Physics Colloquium, Emory University, September 23, 2005)
"Synchronization and Extreme Fluctuations on Networks and Application to Scalable Parallel Discrete-Event Simulations'',
(NSF/ITR Materials Theory Workshop and Review, The Materials Computation Center at the University of Illinois, Urbana-Champaign, June 17, 2004)
"Extreme Fluctuations in Small-World-Synchronized Autonomous Systems'',
(SPIE Second International Symposium on Fluctuations and Noise, Maspalomas, Gran Canaria, Spain, May 27, 2004)

Publications of our group:
"Naming Games in Two-Dimensional and Small-World-Connected Random Geometric Networks",
Qiming Lu, G. Korniss, and B.K. Szymanski, Physical Review E 77, 016111 (2008).
"Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency'',
G. Korniss, .Physical Review E 75, 051121  (2007).
"Extreme Fluctuations in Noisy Task-Completion Landscapes on Scale-Free Networks",
H. Guclu, G. Korniss, Z. Toroczkai, Chaos 17, 026104 (2007).
"Diffusion Processes on Small-World Networks with Distance-Dependent Random Links'',
B. Kozma, M.B. Hastings, and G. Korniss, Journal of Statistical Mechanics: Theory and Experiment, P08014 (2007).
"Naming Games in Spatially-Embedded Random Networks'',
Qiming Lu, B.K. Szymanski, and G. Korniss, in Proceedings of the 2006 American Association for Artificial Intelligence Fall Symposium Series, Interaction and Emergent Phenomena in Societies of Agents (AAAI Press, Menlo Park, CA, 2006) pp. 148—155.
"Scaling in Small-World Resistor Networks'',
G. Korniss, M.B. Hastings, K.E. Bassler, M.J. Berryman, B. Kozma, and D. Abbott, Phyiscs Letters A 350, 324 (2006).
"Synchronization Landscapes in Small-World-Connected Computer Networks'',
H. Guclu, G. Korniss, M.A. Novotny, Z. Toroczkai, and Z Racz, Physical Review E 73, 066115  (2006).
"Diffusion Processes on Power-Law Small-World Networks'',
B. Kozma, M.B. Hastings, and G. Korniss, Physical Review Letters 95, 018701 (2005).
"Extreme Fluctuations in Small-World-Coupled Autonomous Systems with Relaxational Dynamics",
H. Guclu and G. Korniss,  Fluctuation and Noise Letters  5, L43 (2005).
"Extreme Fluctuations in Small-Worlds with Relaxational Dynamics'',
H. Guclu and G. Korniss,  Physycal Review E  69, 065104(R) (2004).
"Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations'',
G. Korniss, M.A. Novotny, H. Guclu, Z. Toroczkai, and P.A. Rikvold, Science299, 677 (2003).
"Roughness Scaling for Edwards-Wilkinson Relaxation in Small-World Networks'',
B. Kozma, M.B. Hastings, and G. Korniss, Physical Review Letters 92, 108701 (2004).
"Small-World Synchronized Computing Networks for Scalable Parallel Discrete-Event Simulations'',
H. Guclu, G. Korniss, Z.  Toroczkai, and  M.A. Novotny, in Complex Networks, edited by E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai, Lecture Notes in Physics Vol. 650 (Springer-Verlag, Berlin, 2004) 255--275.
"Critical Phenomena in a Small World'',
M.B. Hastings and B. Kozma, in Complex Networks, edited by E. Ben-Naim, H. Frauenfelder, and Z. Toroczkai, Lecture Notes in Physics Vol. 650 (Springer-Verlag, Berlin, 2004) 277--297.
"Competition-Driven Network Dynamics: Emergence of a scale-free Leadership Structure and Collective Efficiency'',
M. Anghel, Z. Toroczkai, K.E. Bassler, and G. Korniss, Physical Review Letters 92, 058701 (2004).
"Stochastic Growth in a Small World'',
B. Kozma and G. Korniss, in Computer Simulation Studies in Condensed Matter Physics XVI,  edited by D.P. Landau, S.P. Lewis, and H.-B. Schüttler, Springer Proceedings in Physics Vol. 95 (Springer-Verlag, Berlin, 2004), pp. 29-33.
"Virtual Time Horizon Control via Communication Network Design'',
Z. Toroczkai, G. Korniss, M. A. Novotny, and H. Guclu, in Computational Complexity and Statistical Physics, edited by A. Percus, G. Istrate, and C. Moore, Santa Fe Institute Studies in the Sciences of Complexity Series (Oxford University Press, 2004, in press).
"Magnetic Small-World Nanomaterials: Physical Small-World Networks'',
 M.A. Novotny, X. Zhang, J. Yancey, T. Dubreus, M.L. Cook, S. Gill, T. Norwood, A.M. Novotny, and G. Korniss, arXiv:cond-mat/0410589 (2004).
"Roughening of the (1+1) interfaces in two-component surface growth with an admixture of random deposition'',
A. Kolakowska and M. A. Novotny, and P. S. Verma, arXiv: cond-mat/0403341 (2004).
"On the Evolution of Time Horizons in Parallel and Grid Simulations'',
L.N. Shchur, M.A. Novotny, arXiv: cond-mat/0401229 (2004).
"On the Possibility of Quasi Small-World Nanomaterials'',
M. A. Novotny, Shannon M. Wheeler, arXiv: cond-mat/0308602 (2003).
"A Discrete-Event Analytic Technique for Surface Growth Problems'',
A. Kolakowska and M. A. Novotny, Physical Review B 69, 075407 (2004).
"Update statistics in conservative parallel discrete event simulations of asynchronous systems'',
A. Kolakowska, M. A. Novotny, and P.A. Rikvold, Physical  Review E 68, 046705 (2003).
"Algorithms for Faster and Larger Dynamic Metropolis Simulations'',
M.A. Novotny, A.K. Kolakowska, and G. Korniss, in Proceedings of The Monte Carlo Method in the Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm}, edited by J. E. Gubernatis (Los Alamos, NM, June, 2003), pp. 240-247.
"Algorithmic Scalability in Globally Constrained Conservative Parallel Discrete-Event Simulations of Asynchronous Systems'',
A.K. Kolakowska, M.A. Novotny, and G. Korniss, Physical Review E 67, 046703 (2003).
"Statistical Properties of the Simulated Time Horizon in Conservative Parallel Discrete-Event Simulations'',
G. Korniss, M.A. Novotny, A.K. Kolakowska, and H. Guclu, SAC 2002, Proceedings of the 2002 ACM Symposium on Applied Computing, Madrid , Spain, 2002 ( invited paper), pp. 132-138.
"Going through Rough Times: from Non-Equilibrium Surface Growth to Algorithmic Scalability'',
G. Korniss, M.A. Novotny, P.A. Rikvold, H. Guclu, and Z. Toroczkai, Materials Research Society Symposium Proceedings Series, Vol. 700, Fall Meeting, Boston, 2001 ( invited paper), pp. 297-308.
"Non-equilibrium Surface Growth and Scalability of Parallel Algorithms for Large Asynchronous Systems'',
G. Korniss, M.A. Novotny, Z. Toroczkai, and P.A. Rikvold, in Computer Simulation Studies in Condensed Matter Physics XIII,  edited by D.P. Landau, S.P. Lewis, and H.-B. Schüttler, Springer Proceedings in Physics Vol. 86  (Springer-Verlag, Heidelberg, 2001) p. 183-188.
"From Massively Parallel Algorithms and Fluctuating Time Horizons to Non-equilibrium Surface Growth'',
G. Korniss, Z. Toroczkai, M.A. Novotny,  and P.A. Rikvold, Phys. Rev. Lett. 84, 1351 (2000).
"Parallelization of a Dynamic Monte Carlo Algorithm: A Partially Rejection-Free Conservative Approach'',
G. Korniss, M.A. Novotny, and P.A. Rikvold,  Journal of Computational Physics153, 488 (1999).
Comment on "Extremal-point Densities of Interface Fluctuations in a Quenched Random Medium'',
Z. Toroczkai and G. Korniss, Physical Review E 64 048101 (2001).
"Extremal-point Densities of Interface Fluctuations'',
Z. Toroczkai, G. Korniss, S. Das Sarma, and R.K.P. Zia, Physical Review E 62, 276 (2000).


Parallel discrete-event simulation is an invaluable computational tool to investigate the dynamical behavior of complex systems. Such systems include battlefield models, models for the spread diseases and epidemics, cell-phone communication networks, dynamics of materials, and financial markets, some of these being dauntingly relevant in everyday life. As the number of available nodes (or CPUs) on today's massively parallel architectures increases to hundreds of thousands, or grid-computing networks proliferate over the Internet, designing efficient, scalable, and autonomous synchronization schemes becomes an extremely challenging task. In particular, synchronizing that huge number of CPUs using some kind of central control is beyond hope.
    To understand the scalability and performance of these synchronization/computing networks, we consider the simulation process itself as a complex evolving interacting system, consisting of a large number of nodes (CPUs) and an underlying communication network, facilitating synchronization between the nodes. Using powerful tools and frameworks from statistical physics and non-equilibrium growth phenomena, such as coarse-graining and finite-size scaling, we identify the relevant node-to-node processes on the network. The universal features of the resulting effective stochastic non-equilibrium model describe the progress of the individual CPUs (given by the computational tasks completed) during the simulation. Based on the statistical properties of this progress landscape, also referred to as the synchronization landscape, we analyze, design, and develop algorithms, which optimize simulation speed and data management at the same time. Our recent research focuses on the role of the underlying communication network in achieving well-controlled ("smooth") synchronization landscapes. In particular, we considered "small-world"-like communication networks, where each node communicates only with a few others, i.e., no global "intervention" is involved. This type of complex network (producing the "six degrees of separation") is well known from social systems and social dynamics to be capable of facilitating the spread of information in a highly efficient manner. In our case, small-world communication networks provide a near-uniform progress of the nodes (CPUs) in an autonomous fashion, yielding a scalable algorithm in both computing and data management phases. This research involves collaboration with Mark Novotny at Mississippi State University, and with Zoltan Toroczkai and Matthew Hastings at CNLS Los Alamos.

Working f90 massively parallel source codes.
 

``Dynamic Phase Diagram for a Periodically Driven Kinetic Square-lattice Ising Ferromagnet: Finite-size Scaling Evidence for the Absence of a Tri-critical Point'',
Snapshots of the fluctuating time horizon in the steady state for 10,000 processing elements (PEs) (a) for the regular one-dimensional lattice topology; (b) for a "small-world" network communication topology for synchronization.
 
 
 
 


Biological Invasion in Multi-Species Population Dynamics

Group members at Rensselaer:
Gyorgy Korniss (Co-PI)
graduate students: Lauren O'Malley
undergraduate students: Joseph Yasi, James Basham, Matt Nagy
Collaborators:
Thomas Caraco (PI, SUNY Albany), Zoltan Racz (Eotvos University, Budapest),

Supported by NSF DEB-0342689  under the "Quantitative Environmental and Integrative Biology" focus area

Recent talks:
"Time Scales and Finite-Size Effects in the Invasive Spread of an Advantageous Mutation under Preemptive Competition",
(Complex Systems Colloquium, Center for Nonlinear Studies (CNLS), Los Alamos National Laboratory, NM, January 30, 2006, invited talk).
"Nucleation and Spread of an Invasive Allele'',
(Physics Colloquium, University of Houston, Houston, TX, June 7, 2005, invited talk)
"Nucleation and Global Time Scales in Ecological Invasion under Preemptive Competiton'',
( SPIE Third International Symposium on Fluctuations and Noise, Austin, TX, May 25, 2005)
"Dynamic phase transition and finite-size effects in a periodically  driven spatially extended bistable system'',
(Non-Equilibrium Summer Institute at the Center for Nonlinear Studies (CNLS), Los Alamos National Laboratory, NM, July 3, 2003, invited talk)

Related publications:
"Ecological Invasion, Roughened Fronts, and a Competitor's Extreme Advance: Integrating Stochastic Spatial-Growth Models",
L. O’Malley, G. Korniss, and T. Caraco, Bulletin of Mathematical Biology (submitted, 2007).
"Ecological Invasion: Spatial Clustering and the Critical Radius",
A. Allstadt, T. Caraco, and G. Korniss, Evolutionary Ecology Research 9, 375 (2007).
"Fisher Waves and Front Roughening in a Two-Species Invasion Model with Preemptive Competition",
L. O'Malley, B. Kozma, G. Korniss, Z. Racz, T. Caraco, Physical Review E 74, 041116 (2006).
"Fisher Waves and the Velocity of Front Propagation in a Two-Species Invasion Model with Preemptive Competition",
L. O'Malley, B. Kozma, G. Korniss, Z. Racz, T. Caraco, in Computer Simulation Studies in Condensed Matter Physics XIX,  edited by D.P. Landau, S.P. Lewis, and H.-B. Schüttler, Springer Proceedings in Physics (Springer, Berlin, in press).
"Invasive advance of an advantageous mutation: nucleation theory",
Lauren O'Malley, James Basham, Joseph A. Yasi, G. Korniss, Andrew Allstadt, Tom Caraco, Theoretical Population Biology 70, 464-478 (2006).
"Spatial Dynamics of Invasion: The Geometry of Introduced Species'' ,
G. Korniss and T. Caraco, Journal of Theoretical Biology 233, 137--150 (2005).
"Nucleation and Global Time Scales in Ecological Invasion under Preemptive Competition'', L. O'Malley, A. Allstadt, G. Korniss, T. Caraco, in Fluctuations and Noise in Biological, Biophysical, and Biomedical Systems III, edited by N.G. Stocks, D. Abbott, and R.P. Morse, Proceedings of SPIE Vol. 5841 (SPIE, Bellingham, WA, 2005), pp. 117-124.
"Invasive Allele Spread under Preemptive Competititon" ,
J.A. Yasi, G. Korniss and T. Caraco, in Computer Simulation Studies in Condensed Matter Physics XVIII,  edited by D.P. Landau, S.P. Lewis, and H.-B. Schüttler, Springer Proceedings in Physics Vol. 105 (Springer, Berlin, 2006) pp. 165--169.
"Absence of  First-Order Transition and Tricritical Point in the Dynamic Phase Diagram of a Spatially Extended Bistable System in an Oscillating Field'',
G. Korniss, P.A. Rikvold, and M.A. Novotny,  Physical Review E 66, 056127 (2002).
``Dynamic Phase Transition, Universality, and Finite-size Scaling in the Two-dimensional Kinetic Ising Model in an Oscillating Field'', G. Korniss, C.J. White, M.A. Novotny, and P.A. Rikvold, Physical Review E 63, 016120 (2001).


Better understanding the processes that allow one species to invade the habitat of another will help answer fundamental questions in ecology. Just as importantly, understanding the processes of biological invasion to the point of prediction should enhance our capacity to respond effectively to invading species that impose economic problems on agriculture and threaten native biodiversity across North America.
    Ecologists recognize that biological invasion often depends on the way invaders are initially clustered, but current models and approaches poorly approximate consequences of this spatial clustering. In our recent efforts, we considered models where the invasive plant species is introduced into a habitat occupied by a common resident (i.e., native) plant. We assume that introduction of the invader is a rare stochastic process---it occurs randomly and with a low probability---but nonetheless can occur anywhere in the habitat. The introduced species competes with the resident for resources under pre-emptive competition. Our class of models captures essential features of competition between clonal plants. For example, the exotic Crested Wheatgrass, an invasive species found across the northern Great Plains, has substantially reduced diversity of native grasses.
    Our model's main result predicts the decline of the resident species resulting from clusters of invading species. The invasion process begins locally with a random seeding of invader clusters (starting as small "nuclei"), which subsequently can grow, and eventually will occupy the whole system. Invader clusters are initially well separated. As invasion proceeds, invader clusters grow and coalesce, and ultimately drive the resident species extinct. To characterize the process quantitatively, we borrow nucleation theory from the physics, the kind of theory that for example, explains how a crystal grows. In the limit of a low-invader introduction rate and a large habitat, the time-dependent decay of the resident species' density is given by Avrami's law (used elsewhere in the physical sciences to predict the growth of nonliving organisms), also confirmed by large-scale Monte Carlo simulations.
    Avrami's law was originally formulated in the late 1930's to describe how solids transform from one state of matter ("phase") to another as they crystallize, for example. Since then, nucleation theory and Avrami's law have also been applied successfully to predicting chemical reaction rates and formations of magnetic "domains" (zones of magnetism) in materials. To our knowledge, this is the first application of Avrami's law to ecological systems. Our results have general significance since the shape of the species' invading patterns, to a large extent, is independent of the details of how they are the introduced to a small local area. Essentially, only the small introduction rate, the pre-emptive nature of the competition, and a large habitat to be invaded are required to generate the spatially clustered invasion dynamics described by Avrami's law. We currently investigate models, where, analogously to introduction of the invasive species from "external" sources, introduction of an invasive allele is driven by rare mutation. This line of study provides a phenomenological picture for the invasive spread of an advantageous mutation. This project is in collaboration with Prof. Thomas Caraco (Department of Biological Sciences, SUNY Albany).
Multi-cluster invasion mode (governed by nucleation and growth) in lattice Monte Carlo simulations. White represents empty sites, blue and red correspond to sites occupied by resident and  invasive species, respectively. Introduction of the invasive species is a rare stochastic process, occuring where resource is available (empty sites). The resident and invader species compete preemptively and spread via local clonal propagation.
 


 
Extreme Fluctuations in Network Dynamics

Group members at Rensselaer:
Gyorgy Korniss (PI)
graduate students: Hasan Guclu, Qiming Lu 
Collaborators:
Boleslaw Szymanski (Computer Science, Rensselaer), Zoltan Toroczkai (CNLS, Los Alamos)
 

Supported by Renselaer's Seed Grant

Recent talks:
``Extreme Fluctuations in Small-World-Synchronized Autonomous Systems'',
(SPIE Second International Symposium on Fluctuations and Noise, Maspalomas, Gran Canaria, Spain, May 27, 2004, invited talk)
``Extreme Fluctuations in Small-Worlds with Relaxational Dynamics'',
(NIPS 2003 Workshop: Robust Communication Dynamics in Complex Networks, Whistler, Canada, December 13, 2003, invited talk)

Related publications:
"Extreme Fluctuations in Noisy Task-Completion Landscapes on Scale-Free Networks",
H. Guclu, G. Korniss, Z. Toroczkai, Chaos 17, 026104 (2007).
"Threshold-Controlled Global Cascading in Wireless Sensor Networks'',
Q. Lu, G. Korniss, and B.K. Szymanski, in Proceedings of the Third International Conference of Networked Sensing Systems (INSS 2006) (Transducer Research Foundation, San Diego, 2006) pp.164-171; arXiv:cs.NI/0606054.
"Extreme Fluctuations in Small-World-Coupled Autonomous Systems with Relaxational Dynamics",
H. Guclu and G. Korniss,  Fluctuation and Noise Letters  5, L43 (2005).
"Extreme Fluctuations in Small-Worlds with Relaxational Dynamics'',
H. Guclu and G. Korniss,  Physycal Review E  69, 065104(R) (2004).
Comment on "Extremal-point Densities of Interface Fluctuations in a Quenched Random Medium'',
Z. Toroczkai and G. Korniss, Physical Review E 64 048101 (2001).
"Extremal-point Densities of Interface Fluctuations'',
Z. Toroczkai, G. Korniss, S. Das Sarma, and R.K.P. Zia, Physical Review E 62, 276 (2000).


Many of our important technological, information, and infrastructure systems can be viewed as a complex network with a large number of components. The network consists of nodes (components of the system) and links connecting the nodes. The links facilitate some form of interaction dynamics between the nodes. Examples (with the processes inducing the interaction between the nodes) include high-performance scalable computing networks (synchronization protocols for massive parallelization), load-balancing schemes (relocating jobs among processors), the Internet (protocols for sending/receiving packets), or the electric power grid (generating/transmitting power between generators and buses). Many of theses systems are autonomous (by design or historical evolution), i.e., they lack a central regulator (including the electric power grid since the deregulation of the 1990's). Thus, fluctuations in the "load" in the respective network (data/state savings or task allocation in parallel simulations, traffic in the Internet, or voltage/phase in the electric grid) are determined by the collective result of the individual decisions of many interacting "agents" (nodes). As the number of processors on parallel architectures increases to hundreds of thousands, grid-computing networks proliferate over the Internet, or the electric power-grid covers, e.g., the North-American continent, fundamental questions on the corresponding dynamical processes on the respective underlying networks must be addressed.
    Typically, large fluctuations in the above networks are to be avoided (e.g., for scalability or stability reasons). In the absence of global intervention or control, this is a difficult task. For example, for a distributed parallel simulation scheme to remain scalable, the spread between completion times of tasks performed on different processing nodes of a computer network must remain bounded over time. As another example, for an AC power grid to remain stable, the frequency and the phase of all power generation must remain synchronous within narrow limits; a 2Hz drop below 60Hz would build up sufficient heat in its bearings to destroy the generator.
    In addition to the average load in the network, knowing the typical size and the distribution of the extreme fluctuations is of great importance from a system-design viewpoint, since delays or failures are often triggered by extreme events occurring on an individual node. Motivated by the above examples it becomes clear that understanding the stochastic and network effects on the extreme fluctuations in coupled multi-component systems is of great importance for the performance and stability of processing and infrastructure networks.   
    In a different context, we are also investigating extreme events, or "outliers" as the input signal for certain cascading mechanisms in wireless sensor networks. Spreading reliable information fast across sensor networks with efficient and autonomous control is a challenging task. Our objective in this project is to develop and study extreme-event detection/suppression schemes in wireless sensor networks to prevent global false alarms. Such schemes are important to exclude false alarms triggered by individual sensor failures or local erroneous measurements. This project involves collaboration with Prof. Boleslaw Szymanski (Computer Science, Rensselaer).