Ph.D Thesis

Ph.D StudentDyagilev Kirill
SubjectModeling, Prediction and Design of Dynamic Behavior in
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Shie Mannor


In this thesis we discuss three aspects of dynamic phenomena in complex networks such as economic and social networks.

First, we consider the phenomenon of dynamic network formation and model it using a game theoretic approach. Namely, the evolution of the network is modeled as dynamics of a network formation game (NFG), where the behavior of nodes is governed by some kind of distributed protocol. We focus on an NFG with prohibitive cost of redundant links and show that the best-response dynamics of this NFG may lead to formation of a grossly inefficient network in terms of social welfare. We address this inefficiency by introducing two symmetry-breaking dynamics that converge to fairly efficient networks after a number of steps polynomial in the size of the network.

Second, we consider the phenomenon of product propagation in social networks. We model the emergence of paths by which the product propagates from its origin to nodes in the social network as an NFG. We show that the expected convergence time of the best-response dynamics of this NFG grows at least exponentially in the size of the network. To address this slow rate of convergence, we propose two dynamics in which product promoters are less myopic than in the best-response dynamics. We show that these dynamics convergence (in expectation) to efficient network within a number of steps polynomial in the size of the network.

Finally, we consider dynamics of information propagation in a real-world mobile call data. We build two probabilistic generative models for information propagation paths that accurately predict their size and topology. We also show how social relations described by information propagation paths can be leveraged for customer retention.