We examine a model of network formation in single-layer and multiplex networks in which individuals have positive incentives for social ties, closed triangles, and spillover edges. In particular, we investigate the influence of shocks to the network in which the cost of social ties changes after an initial equilibrium. We highlight the emergence of structural entrenchment: the retention of structural features, such as closed triangles and spillover edges, which are formed under historically different conditions from those currently driving network evolution. This work has broad implications for understanding path dependence in the structure and dynamics of single-layer and multiplex networks.

While logistic regression models are easily accessible to researchers, when applied to network data there are unrealistic assumptions made about the dependence structure of the data. For temporal networks measured in discrete time, recent work has made good advances (Almquist & Butts, 2014), but there is still the assumption that the dyads are conditionally independent given the edge histories. This assumption can be quite strong and is sometimes difficult to justify. If time steps are rather large, one would typically expect not only the existence of temporal dependencies among the dyads across observed time points but also the existence of simultaneous dependencies affecting how the dyads of the network co-evolve. We propose a general observation-driven model for dynamic networks that overcomes this problem by modeling both the mean and the covariance structures as functions of the edge histories using a flexible autoregressive approach. This approach can be shown to fit into a generalized linear mixed model framework. We propose a visualization method that provides evidence concerning the existence of simultaneous dependence. We describe a simulation study to determine the method's performance in the presence and absence of simultaneous dependence, and we analyze both a proximity network from conference attendees and a world trade network. We also use this last data set to illustrate how simultaneous dependencies become more prominent as the time intervals become coarser.

Metric graph properties lie in the heart of the analysis of complex networks, while in this paper we study their convexity through mathematical definition of a convex subgraph. A subgraph is convex if every geodesic path between the nodes of the subgraph lies entirely within the subgraph. According to our perception of convexity, convex network is such in which every connected subset of nodes induces a convex subgraph. We show that convexity is an inherent property of many networks that is not present in a random graph. Most convex are spatial infrastructure networks and social collaboration graphs due to their tree-like or clique-like structure, whereas the food web is the only network studied that is truly non-convex. Core–periphery networks are regionally convex as they can be divided into a non-convex core surrounded by a convex periphery. Random graphs, however, are only locally convex meaning that any connected subgraph of size smaller than the average geodesic distance between the nodes is almost certainly convex. We present different measures of network convexity and discuss its applications in the study of networks.

The degree distribution of the neighbors of nodes in a network is a theoretically important tool that is invoked in diverse studies in network science, such as epidemics, network resilience, network search and observability, network synchronization, random walks, opinion dynamics, and other dynamical systems on networks. Many real networks grow, and their properties pertaining to the said phenomena evolve. There is a paucity of theoretical research on how the evolution of these properties depend upon time and upon the structure of the initial network. This paper addresses this problem by providing the first theoretical study of the temporal evolution of the nearest-neighbor degree distribution for arbitrary networks (with any size) in arbitrary times. The posited results enable the analysis of the structural properties of growing networks in the short-time and intermediary time regimes, which are typically ignored in favor of the steady state. We corroborate the solutions via Monte Carlo simulations on various topologies. As a byproduct of the obtained solutions, we also demonstrate that the existing result in the literature on the asymptotic behavior of the Pearson coefficient of growing networks under the preferential attachment mechanism is incorrect, and we present the correct solution.

Random multigraphs with fixed degrees are obtained by the configuration model or by so called random stub matching. New combinatorial results are given for the global probability distribution of edge multiplicities and its marginal local distributions of loops and edges. The number of multigraphs on triads is determined for arbitrary degrees, and aggregated triads are shown to be useful for analyzing regular and almost regular multigraphs. Relationships between entropy and complexity are given and numerically illustrated for multigraphs with different number of vertices and specified average and variance for the degrees.

Detecting communities in large-scale social networks is a challenging task where each vertex may belong to multiple communities. Such behavior of vertices and the implied strong overlaps among communities render many detection algorithms invalid. We develop a Partial Community Merger Algorithm (PCMA) for detecting communities with significant overlaps as well as slightly overlapping and disjoint ones. It is a bottom-up approach based on properly reassembling partial information of communities revealed in ego networks of vertices to reconstruct complete communities. We propose a novel similarity measure of communities and an efficient merger process to address the two key issues—noise control and merger order—in implementing this approach. PCMA is tested against two benchmarks and overall it outperforms all compared algorithms in both accuracy and efficiency. It is applied to two huge online social networks, Friendster and Sina Weibo. Millions of communities are detected and they are of higher qualities than the corresponding metadata groups. We find that the latter should not be regarded as the ground-truth of structural communities. The significant overlapping pattern found in the detected communities confirms the need of new algorithms, such as PCMA, to handle multiple memberships of vertices in social networks.

Today's economy, production activity, and our life are sustained by social and technological network infrastructures, while new threats of network attacks by destructing loops have been found recently in network science. We inversely take into account the weakness, and propose a new design principle for incrementally growing robust networks. The networks are self-organized by enhancing interwoven long loops. In particular, we consider the range-limited approximation of linking by intermediations in a few hops, and show the strong robustness in the growth without degrading efficiency of paths. Moreover, we demonstrate that the tolerance of connectivity is reformable even from extremely vulnerable real networks according to our proposed growing process with some investment. These results may indicate a prospective direction to the future growth of our network infrastructures.

GLOBALink, a large online network of tobacco control professionals, was active in the promotion of the World Health Organization's Framework Convention on Tobacco Control treaty, an international treaty aimed at reducing the global burden of tobacco-related death and disease. We examined and compared the roles that different countries served in the GLOBALink community during FCTC negotiation and ratification. Previous studies of FCTC ratification found the process adhered to a diffusion of innovation model (Valente et al., 2015). We followed that work by conducting content analyses of discussion messages posted by GLOBALink members representing different countries. Based on the time when they ratified the FCTC, each country was labeled by one of the four adoption stages of the diffusion model and we investigated the amount of shared word use between the different stages. A goodness-of-fit chi-squared test indicated that content was not shared in an expected manner between stages (χ2 = 11,856.45, N = 51,447, p < 0.001). A deeper look at the specific words shared between countries within and between adoption stages provided insight into how interactions between certain countries might have served to support the ratification process.

Social network data are prone to errors regardless their source. This paper focuses on missing data due to actor non-response in valued networks. If actors refuse to provide information, all values for outgoing ties are missing. Partially observed incoming ties to non-respondents and all other patterns for ties between members of the network can be used to impute missing outgoing ties. Many centrality measures are used to determine the most prominent actors inside the network. Using treatments for actor non-response enables us to estimate better the centrality scores of all actors regarding their popularity or prominence. Simulations using initial known blockmodel structures based on three most frequently occurring macro-network structures: cohesive subgroups, core-periphery models, and hierarchical structures were used to evaluate the relative merits of the treatments for non-response. The results indicate that the amount of non-respondents, the type of underlying macro-structure, and the employed treatment have an impact on centrality scores. Regardless of the underlying network structure, the median of the 3-nearest neighbors based on incoming ties performs the best. The adequacy (or not) of the other non-response treatments is contingent on the network macro-structure.

Understanding how person-to-person contagious processes spread through a population requires accurate information on connections between population members. However, such connectivity data, when collected via interview, is often incomplete due to partial recall, respondent fatigue, or study design, e.g. fixed choice designs (FCD) truncate out-degree by limiting the number of contacts each respondent can report. Research has shown how FCD affects network properties, but its implications for predicted speed and size of spreading processes remain largely unexplored. To study the impact of degree truncation on predictions of spreading process outcomes, we generated collections of synthetic networks containing specific properties (degree distribution, degree-assortativity, clustering), and used empirical social network data from 75 villages in Karnataka, India. We simulated FCD using various truncation thresholds and ran a susceptible-infectious-recovered (SIR) process on each network. We found that spreading processes on truncated networks resulted in slower and smaller epidemics, with a sudden decrease in prediction accuracy at a level of truncation that varied by network type. Our results have implications beyond FCD to truncation due to any limited sampling from a larger network. We conclude that knowledge of network structure is important for understanding the accuracy of predictions of process spread on degree truncated networks.

Many hierarchically modular systems are structured in a way that resembles an hourglass. This “hourglass effect” means that the system generates many outputs from many inputs through a relatively small number of intermediate modules that are critical for the operation of the entire system, referred to as the waist of the hourglass. We investigate the hourglass effect in general, not necessarily layered, hierarchical dependency networks. Our analysis focuses on the number of source-to-target dependency paths that traverse each vertex, and it identifies the core of a dependency network as the smallest set of vertices that collectively cover almost all dependency paths. We then examine if a given network exhibits the hourglass property or not, comparing its core size with a “flat” (i.e., non-hierarchical) network that preserves the source dependencies of each target in the original network. As a possible explanation for the hourglass effect, we propose the Reuse Preference model that captures the bias of new modules to reuse intermediate modules of similar complexity instead of connecting directly to sources or low complexity modules. We have applied the proposed framework in a diverse set of dependency networks from technological, natural, and information systems, showing that all these networks exhibit the general hourglass property but to a varying degree and with different waist characteristics.

Historically, health has played an important role in network research, and vice versa (Valente, 2010). This intersection has contributed to how we understand human health as well as the development of network concepts, theory, and methods. Throughout, dynamics have featured prominently. Even when limited to static methods, the emphasis in each of these fields on providing causal explanations has led researchers to draw upon theories that are dynamic, often explicitly. Here, we elaborate a variety of ways to conceptualize the relationship between health and network dynamics, show how these possibilities are reflected in the existing literature, highlight how the articles within this special issue expand that understanding, and finally, identify paths for future research to push this intersection forward.

Social ties are strongly related to well-being. But what characterizes this relationship? This study investigates social mechanisms explaining how social ties affect well-being through social integration and social influence, and how well-being affects social ties through social selection. We hypothesize that highly integrated individuals–those with more extensive and dense friendship networks–report higher emotional well-being than others. Moreover, emotional well-being should be influenced by the well-being of close friends. Finally, well-being should affect friendship selection when individuals prefer others with higher levels of well-being, and others whose well-being is similar to theirs. We test our hypotheses using longitudinal social network and well-being data of 117 individuals living in a graduate housing community. The application of a novel extension of Stochastic Actor-Oriented Models for ordered networks (ordered SAOMs) allows us to detail and test our hypotheses for weak- and strong-tied friendship networks simultaneously. Results do not support our social integration and social influence hypotheses but provide evidence for selection: individuals with higher emotional well-being tend to have more strong-tied friends, and there are homophily processes regarding emotional well-being in strong-tied networks. Our study highlights the two-directional relationship between social ties and well-being, and demonstrates the importance of considering different tie strengths for various social processes.

A measure of centrality is rank monotone if after adding an arc x → y, all nodes with a score smaller than (or equal to) y have still a score smaller than (or equal to) y. If, in particular, all nodes with a score smaller than or equal to y get a score smaller than y (i.e., all ties with y are broken in favor of y), the measure is called strictly rank monotone. We prove that harmonic centrality is strictly rank monotone, whereas closeness is just rank monotone on strongly connected graphs, and that some other measures, including betweenness, are not rank monotone at all (sometimes not even on strongly connected graphs). Among spectral measures, damped scores such as Katz's index and PageRank are strictly rank monotone on all graphs, whereas the dominant eigenvector is strictly monotone on strongly connected graphs only.