Abstract To understand how supply uncertainty affects the structure of supply chain networks we consider a setting where retailers and suppliers must establish a costly relationship with each other prior too engaging in trade. Suppliers, with uncertain yield, announce wholesale prices, while retailers must decide which suppliers to link to based on their wholesale prices. Subsequently, retailers compete with each other in Cournot fashion to sell the acquired supply to consumers. We find that in equilibrium retailers concentrate their links among too few suppliers, that is, there is insufficient diversification of the supply base. We find that either reduction in supply variance or increase in mean supply, increases a supplier's profit. However, these two ways of improving service have qualitatively different effects on welfare: improvement of the expected yield by a supplier makes everyone better off, whereas change in the variance of the yield impacts system members differently.

We study the incentives that independent self-interested agents have in forming a resilient supply chain network in the face of disruptions and competition. Competing suppliers are subject to yield uncertainty and congestion. Competing retailers make sourcing decisions based on price and reliability. Under yield uncertainty only, retailers---benefiting from supply variance---concentrate their links on a single supplier, counter to the idea that they should mitigate yield uncertainty by multi-sourcing. When congestion is added, the resulting networks resemble bipartite expanders known to be resilient, thus, providing the first example of endogenously formed resilient supply chains.

The process of opinion formation is inherently a network process, with user opinions in a social network being driven to a certain average opinion. One simple and intuitive incarnation of this opinion attractor is the average of user opinions 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 of disabling such opinion control attempts via strategically altering the network's users' eigencentralities 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 networks.

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.

Modeling and predicting people's opinions plays an important role in today's life. For viral marketing and political strategy design, it is particularly important to be able to analyze competing 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 "behaved"' abnormally? Furthermore, can we predict how the opinions of individual users will change in the future? To answer such questions, it is insufficient to study individual user behavior, since opinions spread beyond users' ego-networks. Instead, we need to consider the opinion dynamics of all users simultaneously. 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 opinion dynamics model. SND has a rich semantics of a transportation problem, yet, is computable in pseudo-linear time, thereby, being applicable to large-scale social networks analysis. We demonstrate the effectiveness of SND in experiments with Twitter data.