# Complex networked systems

### From CYPHYNETS

## Connections & Complexity: Large-Scale Distributed Networks and their Dynamics

Perhaps, the best word that summarizes the behavior of today’s global society is connectivity [1]. The pervasive influence of networks in all aspects of life - biological, physical, and social - has led researchers on the quest to discover fundamental principles underpinning complex networked systems. Network phenomena manifest themselves in all aspects of biological diversities, from biochemical reactions and neural networks to insect swarms and complex ecological systems [2]. These effects are also visible in fundamental physics, for example in lattices ensembles of particles in statistical physics and spin networks in most variants of quantum gravity. They are also found in such diverse engineered systems as power grids, communications networks, irrigation networks and transportation infrastructures. Connectivity is also visible in all sorts of human social interactions such as collaboration, coordination and exchange of information, thus enabling the necessities and conveniences of modern life. All such network phenomena share a common principle — the emergence of global behavior from local interactions via adaptation and cooperation. Thus systematic studies of these remarkably diverse and pervasive examples hold great promises for solving numerous engineering and scientific problems. Research on networked sensing & control systems has already enabled the design, analysis and deployment of new types of networks, from sensory to robotic and from wireless to adhoc.

In Figure 1, two prominent aspects of the complexity of complex networked systems have been depicted. Researchers in autonomous system have recently made many landmark achievements that reflect the high-level of expertise in dealing with the complexity of individual system dynamics. In 2005, a driverless vehicle autonomously covered 130 miles of desert territory in less than seven hours to win the DARPA grand challenge on robotics [13]. By the same year, tactical- and theater-level unmanned aerial vehicles had flown over 100,000 flight hours in support of combat missions around the globe. On the other hand much of the current work on large-scale networks assumes that individual agents have very simple or no dynamics. It is therefore time to push the frontiers of this research and envision systems made up of hundreds or perhaps thousands of reliable robotic platforms, linked by reliable communication networks for applications hitherto unthinkable [3]. However, the realization of such distributed dynamical systems is hindered by several challenges.

It is worth noting that the main challenge in this field has shifted from difficulties in manufacturing to the lack of theoretical foundations for provably correct design and deployment. There are many gaps in the fundamental understanding of collective dynamics of networks. There is a need to develop tools, abstractions, and approximations that provide a rigorous mathematical basis in order to explain common concepts across fields; model uncertainties characterized by noisy and incomplete data; incorporate experimental measurements; and find systems that are both robust and secure [1], [2]. Many of these issues are structural: how does one characterize the wiring diagram of a metabolic network or a food web or the Internet or the visual cortex? Are there any unifying principles underlying their topology?

Another important question is whether there are common laws that explain the modes of information propagation in diverse networks such as insect colonies, the world-wide web, electrical power grids, citation networks of scientists etc? If so, can these principles be used to construct optimal coordination strategies for various applications of networked sensing & control? One of the most important issues in studying information propagation is the role of feedback (Figure 2). How do networks self-stabilize globally using only local information? What is the minimum information that needs to be exchanged among agents to reliably close the loop over noisy communication channels while obeying bandwidth requirements? Studies on the effects and limitations of feedback in networks are of critical importance to congestion control, network protocols and cross-layer optimization for traditional networks. They are also leading to new applications such as remote robotic surgery and deep-space mission control. Needless to say, that these studies have direct relevance to the many outstanding scientific problems mentioned above. The two issues, namely the topological structure of distributed systems and information feedback & propagation are the focal points of my research on complex networks. In both questions, one needs to understand the complex interplay between the four basic ingredients of a dynamic network: sensing, communication, computation, and control.

As the size and complexity of such systems increase, the spatial interactions between subsystems become intractable for design and analysis by traditional methods alone. One highlight of my research has been to capture such seemingly intractable complexities by combining traditional techniques of systems theory with novel abstractions from graph theory and algebraic topology [4]. These abstractions are concise, robust and provably correct representations of the redundant geometric information in the system. They are strongly motivated by the physical characteristics of networks, such as sensory and communication constraints. Moreover, they allow a natural gluing of local information into global network characteristics. Although there is a wealth of work on computational applications of graph theory and algebraic topology, the unique characteristics of networked control systems has led me to think about new methods and algorithms that are well suited for actual realization. These methods are distributed and cognizant of network limitations such as information routing constraints, bandwidth and energy.

In my doctoral thesis and postdoctoral work, I have succeeded in demonstrating the promise of this research philosophy for several problems. One highlight of my doctoral thesis is a motion planner for dynamic reconfigurable networks that uses a combination of graph embedding techniques, semi-definite programming and standard motion planning. In another study, I solved the blanket coverage problem for sensor networks using a novel application of computational algebraic topology, resulting in several degrees of robustness and simplification over standard algorithms. In my postdoctoral work, I have generalized these results to the dynamic coverage scenario (See figure). This has been done by combining ideas from hybrid control systems, discrete-differential geometry and harmonic analysis to get a distributed verification algorithm for all dynamic coverage algorithms. In another work, I have proposed some decentralized algorithms for computing certain topological invariants. These invariants have been shown to be related to network characteristics such as information routing in communication networks, coverage gaps in sensor networks and coordination mechanisms in multi-agent robotics. In short, all these studies support the hypothesis that a common language to describe many types of network phenomenon can be obtained by the correct mathematical abstractions that focus on two most fundamental aspects of networked systems, namely distributed information propagation and topology characterization.

## References

[1]. Linked: How Everything Is Connected to Everything Else and What It Means, Albert-Laszlo Barabasi, Plume, 2003

[2]. Network Science, National Research Council, National Academies Press, 2005

[3]. “A Robot in Every Home,” Bill Gates, Scientific American, Dec 2006.

[4]. Sensor Topology for Minimal Planning (SToMP), DARPA-DSO program. [1]

[13]. The Grand Challenge in Robotics, DARPA. [2]