Research Activities > Programs > Nonlinear Dynamics of Networks

Nonlinear Dynamics of Networks

CSIC Building (#406), Seminar Room 4122.

Network Constrained Coalitional Dynamic Games and Evolution of Network Topologies

John Baras

University of Maryland

Abstract:   We investigate the dynamics of evolving networks in order to understand dynamic phenomena of families of graph processes. The major motivation comes from the fundamental need to develop a unifying analytical and optimization framework for the design, operation and performance evaluation of networks of autonomous agents. The new fundamental view is that agents in such a network are dynamic entities that collaborate because via collaboration they can accomplish objectives and goals much better than working alone, or even accomplish objectives that they cannot achieve alone at all. Yet the benefits derived from such collaboration require some costs (or expenditures), for example due to communications. Or in equivalent terms, the collaboration is subject to constraints (static and dynamic) such as energy, communication, trust, organizational relations and structures . Understanding and quantifying this tradeoff between the benefits vs the costs of collaboration, leads to new methods that can be used to analyze, design and control/operate networks of agents. Multiple metrics for benefits and costs can be considered within this framework. An important, yet not emphasized todate, aspect of collaboration is the role of topologies and connectivities linking the agents. We develop a dynamic constrained coalitional games mathematical framework, which results in dynamic processes characterizing the evolution of the network over time, the so-called network formation process. We demonstrate, via our framework, how the metrics of benefit and cost control the dynamics, their convergence or divergence, and the structure of the resulting equilibria (i.e generated networks). We demonstrate via probabilistic methods that connectivities related to small world graphs provide efficiency from the point of view of speed up of convergence of distributed algorithms on networks. Next we show that expander graphs offer dramatic advantages with respect to many problems that need to be solved in a distributed manner in collaborative control and communication over networks. This works because several key distributed algorithms and information dissemination algorithms work very fast on such graphs. By examining the dynamic graph processes resulting from our type of games we show that such topologies can be maintained easily with simple controls. These topologies are efficient from the perspective of costs yet lead to fast convergence of distributed algorithms from the benefits perspective. We show how they can be self-generated in response to cost-benefit tradeoffs. Finally, we show that by appropriate selection of multiple metrics the resulting networks display modular structures. These ideas and methods introduce a new look in networks. They separate control from communication architecture. We illustrate by several examples from biology, sociology and economics where such networks naturally appear and form.

University of Maryland    

UM Home | Directories | Calendar
Maintained by CSCAMM
Direct questions and comments to

CSCAMM is part of the
College of Computer, Mathematical & Natural Sciences (CMNS)