Information spread in networks: games, optimal control, and stabilization

Khanafer, Ali

Permalink

https://hdl.handle.net/2142/72769 Copy

Description

Title

Information spread in networks: games, optimal control, and stabilization

Author(s)

Khanafer, Ali

Issue Date

2015-01-21

Director of Research (if dissertation) or Advisor (if thesis)

Basar, Tamer

Doctoral Committee Chair(s)

Basar, Tamer

Committee Member(s)

• Belabbas, Mohamed Ali
• Liberzon, Daniel M.
• Raginsky, Maxim
• Srikant, Rayadurgam

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Game Theory
• Optimal Control
• Stackelberg Games
• Distributed Averaging
• Epidemics
• Stabilization
• Positive Systems
• Lyapunov Theory
• Pontryagin's Maximum Principle
• Potential Theory
• Network Analysis and Control
• Network Games
• Diffusion
• Security
• Superivsory Control
• Switched Systems
• Differential Games
• Graph Theory
• Limited Control
• Sparse Resource Allocation
• Vaccination
• Distributed Control

Abstract

"This thesis focuses on designing efficient mechanisms for controlling information spread in networks. We consider two models for information spread. The first one is the well-known distributed averaging dynamics. The second model is a nonlinear one that describes virus spread in computer and biological networks. We seek to design optimal, robust, and stabilizing controllers under practical constraints. For distributed averaging networks, we study the interaction between a network designer and an adversary. We consider two types of attacks on the network. In Attack-I, the adversary strategically disconnects a set of links to prevent the nodes from reaching consensus. Meanwhile, the network designer assists the nodes in reaching consensus by changing the weights of a limited number of links in the network. We formulate two problems to describe this competition where the order in which the players act is reversed in the two problems. Although the canonical equations provided by the Pontryagin's Maximum Principle (MP) seem to be intractable, we provide an alternative characterization for the optimal strategies that makes connection to potential theory. Further, we provide a sufficient condition for the existence of a saddle-point equilibrium (SPE) for the underlying zero-sum game. In Attack-II, the designer and the adversary are both capable of altering the measurements of all nodes in the network by injecting global signals. We impose two constraints on both players: a power constraint and an energy constraint. We assume that the available energy to each player is not sufficient to operate at maximum power throughout the horizon of the game. We show the existence of an SPE and derive the optimal strategies in closed form for this attack scenario. As an alternative to the ""network designer vs. adversary"" framework, we investigate the possibility of stabilizing unknown network diffusion processes using a distributed mechanism, where the uncertainty is due to an attack on the network. To this end, we propose a distributed version of the classical logic-based supervisory control scheme. Given a network of agents whose dynamics contain unknown parameters, the distributed supervisory control scheme is used to assist the agents to converge to a certain set-point without requiring them to have explicit knowledge of that set-point. Unlike the classical supervisory control scheme where a centralized supervisor makes switching decisions among the candidate controllers, in our scheme, each agent is equipped with a local supervisor that switches among the available controllers. The switching decisions made at a certain agent depend only on the information from its neighboring agents. We provide sufficient conditions for stabilization and apply our framework to the distributed averaging problem in the presence of large modeling uncertainty. For infected networks, we study the stability properties of a susceptible-infected-susceptible (SIS) diffusion model, so-called the n-intertwined Markov model, over arbitrary network topologies. Similar to the majority of infection spread dynamics, this model exhibits a threshold phenomenon. When the curing rates in the network are high, the all-healthy state is the unique equilibrium over the network. Otherwise, an endemic equilibrium state emerges, where some infection remains within the network. Using notions from positive systems theory, we provide conditions for the global asymptotic stability of the equilibrium points in both cases over strongly and weakly connected directed networks based on the value of the basic reproduction number, a fundamental quantity in the study of epidemics. Furthermore, we demonstrate that the n-intertwined Markov model can be viewed as a best-response dynamical system of a concave game among the nodes. This characterization allows us to cast new infection spread dynamics; additionally, we provide a sufficient condition, for the global convergence to the all-healthy state, that can be checked in a distributed fashion. Moreover, we investigate the problem of stabilizing the network when the curing rates of a limited number of nodes can be controlled. In particular, we characterize the number of controllers required for a class of undirected graphs. We also design optimal controllers capable of minimizing the total infection in the network at minimum cost. Finally, we outline a set of open problems in the area of information spread control."

Graduation Semester

2014-12

Permalink

http://hdl.handle.net/2142/72769

Copyright and License Information

Copyright 2014 Ali Khanafer

Owning Collections