Files in this item
Files  Description  Format 

application/pdf Ali_Khanafer.pdf (8MB)  (no description provided) 
Description
Title:  Information spread in networks: games, optimal control, and stabilization 
Author(s):  Khanafer, Ali 
Director of Research:  Basar, Tamer 
Doctoral Committee Chair(s):  Basar, Tamer 
Doctoral Committee Member(s):  Belabbas, Mohamed Ali; Liberzon, Daniel M.; Raginsky, Maxim; Srikant, Rayadurgam 
Department / Program:  Electrical & Computer Eng 
Discipline:  Electrical & Computer Engr 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(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 wellknown 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 AttackI, 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 saddlepoint equilibrium (SPE) for the underlying zerosum game. In AttackII, 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 logicbased 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 setpoint without requiring them to have explicit knowledge of that setpoint. 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 susceptibleinfectedsusceptible (SIS) diffusion model, socalled the nintertwined 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 allhealthy 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 nintertwined Markov model can be viewed as a bestresponse 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 allhealthy 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. 
Issue Date:  20150121 
URI:  http://hdl.handle.net/2142/72769 
Rights Information:  Copyright 2014 Ali Khanafer 
Date Available in IDEALS:  20150121 
Date Deposited:  201412 
This item appears in the following Collection(s)

Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois