This article considers the link removal problem in a strongly connected directed network with the goal of minimizing the dominant eigenvalue of the network’s adjacency matrix while maintaining its strong connectivity. Due to the complexity of the problem, this article focuses on computing a suboptimal solution. Furthermore, it is assumed that the knowledge of the overall network topology is not available. This calls for distributed algorithms which rely solely on the local information available to each individual node and information exchange between each node and its neighbors. Two different strategies based on matrix perturbation analysis are presented, namely simultaneous and iterative link removal strategies. Key ingredients in implementing both strategies include novel distributed algorithms for estimating the dominant eigenvectors of an adjacency matrix and for verifying strong connectivity of a directed network under link removal. It is shown via numerical simulations on different type of networks that in general the iterative link removal strategy yields a better suboptimal solution. However, it comes at a price of higher communication cost in comparison to the simultaneous link removal strategy.

We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm.

Researchers have found that although external attacks, exogenous shocks, and node knockouts can disrupt networked systems, they rarely lead to the system’s collapse. Although these processes are widely understood, most studies of how exogenous shocks affect networks rely on simulated or observational data. Thus, little is known about how groups of real individuals respond to external attacks. In this article, we employ an experimental design in which exogenous shocks, in the form of the unexpected removal of a teammate, are imposed on small teams of people who know each other. This allows us to causally identify the removed individual’s contribution to the team structure, the effect that an individual had on those they were connected, and the effect of the node knockout on the team. At the team level, we find that node knockouts decrease overall internal team communication. At the individual level, we find that node knockouts cause the remaining influential players to become more influential, while the remaining peripheral players become more isolated within their team. In addition, we also find that node knockouts may have a nominal influence on team performance. These findings shed light on how teams respond and adapt to node knockouts.

While we know that adolescents tend to befriend peers who share their race and gender, it is unclear whether patterns of homophily vary according to the strength, intimacy, or connectedness of these relationships. By applying valued exponential random graph models to a sample of 153 adolescent friendship networks, I test whether tendencies towards same-race and same-gender friendships differ for strong versus weak relational ties. In nondiverse, primarily white networks, weak ties are more likely to connect same-race peers, while racial homophily is not associated with the formation of stronger friendships. As racial diversity increases, however, strong ties become more likely to connect same-race peers, while weaker bonds are less apt to be defined by racial homophily. Gender homophily defines the patterns of all friendship ties, but these tendencies are more pronounced for weaker connections. My results highlight the empirical value of considering tie strength when examining social processes in adolescent networks.

Dense networks with weighted connections often exhibit a community-like structure, where although most nodes are connected to each other, different patterns of edge weights may emerge depending on each node’s community membership. We propose a new framework for generating and estimating dense weighted networks with potentially different connectivity patterns across different communities. The proposed model relies on a particular class of functions which map individual node characteristics to the edges connecting those nodes, allowing for flexibility while requiring a small number of parameters relative to the number of edges. By leveraging the estimation techniques, we also develop a bootstrap methodology for generating new networks on the same set of vertices, which may be useful in circumstances where multiple data sets cannot be collected. Performance of these methods is analyzed in theory, simulations, and real data.