Victor Amelkin successfully defends his PhD on the topic of "Analysis, Modeling, and Control of Dynamic Processes in Networks".
Committee: Ambuj K. Singh (chair), Francesco Bullo, John R. Gilbert, Xifeng Yan
Abstract: Dynamic network processes occur in many areas of human life. Information spread in social networks, collaboration dynamics in organizational networks, heat diffusion in a material networks, traffic jam propagation in road networks, and distributed synchronization in robotic networks are just a few examples. The studies of network processes subdivide into three areas: analysis of the process through the data produced by it, design of mathematical models based on the knowledge about the process' domain, and design of control mechanism that guide the network process towards the desired evolution pattern. My work targets design of methods to advance the knowledge frontier in each of these areas.
In the first part of the talk, I will review my work on the analysis of polar opinion dynamics in social networks. I will highlight the Social Network Distance (SND)---a distance measure that quantifies the amount of change happening between two time points in a large social network with respect to an opinion dynamics model defining the likely opinion propagation scenarios. I will show how to design such distance measure using Earth Mover's Distance based upon the classical transportation problem, compute it in linear time, and use it for anomaly detection and user opinion prediction applications.
In the second part of the talk, I will focus on the modeling of polar opinion dynamics, and describe a non-linear DeGroot-type model for polar opinion dynamics, that captures the opinion formation process' dependence upon the opinion itself (e.g., neutral persons easily change their opinions, while polarized users are more resilient to persuasion). For this model, I will review its connection to psychological theories, as well as the use of non-smooth Lyapunov functions and LaSalle's Theorem for the theoretical analysis of its asymptotic behavior.
In the third part of the talk, I will discuss my results on the problem of social control. The existing socio-psychological opinion dynamics models expose the tools through which businesses can influence the opinion distribution of a social network's users. For example, "the adversary" can change the opinions of a limited number of users in the network, causing a cascading shift of the opinion distribution. Clearly, such controllability of opinion distribution may be potentially harmful for the society, and needs to be countered using legitimate tools available to the social network. One such tool is link recommendation. I will describe a link recommendation mechanism that disables external attacks upon the user opinion distribution in the network. While the underlying optimization problem is NP-hard, I will provide a heuristic, drawing upon the theory of Markov chains, that solves the problem approximately, is computable in pseudo-linear time, and performs well in experiments.