How Well Can We Learn over Networks?

Network science deals with issues related to the aggregation, processing, and diffusion of information over graphs. While interactions among agents can be studied from the perspective of cluster formations, degrees of connectivity, and small-world effects, it is the possibility of having agents interact dynamically with each other, and influence each other’s behavior, that opens up a plethora of notable possibilities. For example, examination of how local interactions influence global behavior can lead to a broader understanding of how localized interactions in the social sciences, life sciences, and system sciences influence the evolution of the respective networks. For long, system theory has focused on studying stand-alone dynamic systems with great success. Nowadays, rapid advances in the biological sciences, animal behavior studies, and in the neuroscience of the brain, are revealing the striking power of coordination among networked units. These discoveries are motivating deeper studies of information processing over graphs in various disciplines including signal processing, machine learning, optimization, and control.

In this presentation, we examine the learning behavior of adaptive networked agents over both strongly-connected and weakly-connected graphs and describe some interesting patterns of behavior on how information flows over graphs. In the strongly-connected case, all agents are able to learn the desired true state within the same accuracy level even when different agents are subjected to different noise conditions and to different levels of information. In contrast, in the weakly-connected case, a leader-follower relationship develops with some agents dictating the behavior of other agents regardless of the local information clues that are sensed by these other agents. The findings clarify how asymmetries in the exchange of data over graphs can make some agents totally dependent on other agents. This scenario arises, for example, from intruder attacks by malicious agents or from failures by critical links.