Victor Amelkin – Job Application Materials

Supply chains are the backbone of the global economy. Disruptions to them can be costly. Centrally managed supply chains invest in ensuring their resilience. Decentralized supply chains, however, must rely upon the self-interest of their individual components to maintain the resilience of the entire chain.

We examine the incentives that independent self-interested agents have in forming a resilient supply chain network in the face of production disruptions and competition. In our model, competing suppliers are subject to yield uncertainty (they deliver less than ordered) and congestion (lead time uncertainty or, "soft" supply caps). Competing retailers must decide which suppliers to link to based on both price and reliability.

In the presence of yield uncertainty only, the resulting supply chain networks are sparse. Retailers concentrate their links on a single supplier, counter to the idea that they should mitigate yield uncertainty by diversifying their supply base. This happens because retailers benefit from supply variance. It suggests that competition will amplify output uncertainty. When congestion is included as well, the resulting networks are denser and resemble the bipartite expander graphs that have been proposed in the supply chain literature, thereby, providing the first example of endogenous formation of resilient supply chain networks, without resilience being explicitly encoded in payoffs. Finally, we show that a suppliers investments in improved yield can make them worse off. This happens because high production output saturates the market, which, in turn lowers prices and profits for participants.

Existing socio-psychological studies show that the process of opinion formation is inherently a network process, with user opinions in a social network being attracted to a certain average opinion. One simple and intuitive incarnation of this notion of an opinion attractor is the average π^Tx of user opinions x weighted by the users' eigenvector centralities π. This value is a lucrative target for control, as altering it essentially changes the mass opinion in the network. Since any potentially malicious influence upon the opinion distribution in a society is undesirable, it is important to design methods to prevent external attacks upon it.

In this work, we assume that the adversary aims to maliciously change the network's average opinion by altering the opinions of some unknown users. We, then, state an NP-hard problem—DIVER—of disabling such network opinion control attempts via strategically altering the network's users' eigenvector centralities by recommending a limited number of links to the users. Relying on Markov chain theory, we provide perturbation analysis that shows how eigencentrality and, hence, our problem's objective change in response to a link's addition to the network. The latter leads to the design of a pseudo-linear-time heuristic, relying on efficient estimation of mean first passage times in Markov chains. We have confirmed our theoretical and algorithmic findings, and studied effectiveness and efficiency of our heuristic in experiments with synthetic and real-world networks.

For decades, scientists have studied opinion formation in social networks, where information travels via word of mouth. The particularly interesting case is when polar opinions—Democrats vs. Republicans or iOS vs. Android—compete in the network. The central problem is to design and analyze a model that captures how polar opinions evolve in the real world.

In this work, we propose a general non-linear model of polar opinion dynamics, rooted in several theories of sociology and social psychology. The model's key distinguishing trait is that, unlike in the existing linear models, such as DeGroot and Friedkin-Johnsen models, an individual's susceptibility to persuasion is a function of his or her current opinion. For example, a person holding a neutral opinion may be rather malleable, while "extremists" may be strongly committed to their current beliefs. We also study three specializations of our general model, whose susceptibility functions correspond to different socio-psychological theories.

We provide a comprehensive theoretical analysis of our nonlinear models' behavior using several tools from non-smooth analysis of dynamical systems. To study convergence, we use non-smooth max-min Lyapunov functions together with the generalized Invariance Principle. For our general model, we derive a general sufficient condition for the convergence to consensus. For the specialized models, we provide a full theoretical analysis of their convergence—whether to consensus or disagreement. Our results are rather general and easily apply to the analysis of other non-linear models defined over directed networks, with Lyapunov functions constructed out of convex components.

Analysis of opinion dynamics in social networks plays an important role in today's life. For predicting users' political preference, it is particularly important to be able to analyze the dynamics of competing polar opinions, such as pro-Democrat vs. pro-Republican. While observing the evolution of polar opinions in a social network over time, can we tell when the network evolved abnormally? Furthermore, can we predict how the opinions of the users will change in the future? To answer such questions, it is insufficient to study individual user behavior, since opinions can spread beyond users' ego-networks. Instead, we need to consider the opinion dynamics of all users simultaneously and capture the connection between the individuals' behavior and the global evolution pattern of the social network.

In this work, we introduce the Social Network Distance (SND)—a distance measure that quantifies the likelihood of evolution of one snapshot of a social network into another snapshot under a chosen model of polar opinion dynamics. SND has a rich semantics of a transportation problem, yet, is computable in time linear in the number of users and, as such, is applicable to large-scale online social networks. In our experiments with synthetic and Twitter data, we demonstrate the utility of our distance measure for anomalous event detection. It achieves a true positive rate of 0.83, twice as high as that of alternatives. The same predictions presented in precision-recall space show that SND retains perfect precision for recall up to 0.2. Its precision then decreases while maintaining more than 2-fold improvement over alternatives for recall up to 0.95. When used for opinion prediction in Twitter data, SND's accuracy is 75.6%, which is 7.5% higher than that of the next best method.