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.

Online social networking services involve communication activities between large number of individuals over the public Internet and their crawled records are often regarded as proxies of real (i.e., offline) interaction structure. However, structure observed in these records might differ from real counterparts because individuals may behave differently online and non-human accounts may even participate. To understand the difference between online and real social networks, we investigate an empirical communication network between users on Twitter, which is perhaps one of the largest social networking services. We define a network of user pairs that send reciprocal messages. Based on the correlation between degree of adjacent nodes observed in this network, we hypothesize that this network differs from conventional understandings in the sense that there is a small number of distinctive users that we call outsiders. Outsiders do not belong to any user groups but they are connected with different groups, while not being well connected with each other. We identify outsiders by maximizing the degree assortativity coefficient of the network via node removal, thereby confirming that local structural properties of outsiders identified are consistent with our hypothesis. Our findings suggest that the existence of outsiders should be considered when using Twitter communication networks for social network analysis.

Assuming a society of conditional cooperators (or moody conditional cooperators), this computational study proposes a new perspective on the structural advantage of social network clustering. Previous work focused on how clustered structure might encourage initial outbreaks of cooperation or defend against invasion by a few defectors. Instead, we explore the ability of a societal structure to retain cooperative norms in the face of widespread disturbances. Such disturbances may abstractly describe hardships like famine and economic recession, or the random spatial placement of a substantial numbers of pure defectors (or round-1 defectors) among a spatially structured population of players in a laboratory game, etc.

As links in tightly clustered societies are reallocated to distant contacts, we observe that a society becomes increasingly susceptible to catastrophic cascades of defection: mutually-beneficial cooperative norms can be destroyed completely by modest shocks of defection. In contrast, networks with higher clustering coefficients can withstand larger shocks of defection before being forced to catastrophically low levels of cooperation. We observe a remarkably linear protective effect of clustering coefficient that becomes active above a critical level of clustering. Notably, both the critical level and the slope of this dependence is higher for decision-rule parameterizations that correspond to higher costs of cooperation. Our modeling framework provides a simple way to reinterpret the counter-intuitive and widely cited human experiments of Suri and Watts (2011) while also affirming the classical intuition that network clustering and higher levels of cooperation should be positively associated.

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.

Using the direct current power flow model, we study cascading failures and their spatial and temporal properties in the U.S. Western Interconnection (USWI) power grid. We show that yield (the fraction of demand satisfied after the cascade) has a bimodal distribution typical of a first-order transition. The single line failure leads either to an insignificant power loss or to a cascade which causes a major blackout with yield less than 0.8. The former occurs with high probability if line tolerance α (the ratio of the maximal load a line can carry to its initial load) is greater than 2, while a major blackout occurs with high probability in a broad range of 1 < α < 2. We also show that major blackouts begin with a latent period (with duration proportional to α) during which few lines overload and yield remains high. The existence of the latent period suggests that intervention during early stages of a cascade can significantly reduce the risk of a major blackout. Finally, we introduce the preferential Degree And Distance Attachment model to generate random networks with similar degree, resistance, and flow distributions to the USWI. Moreover, we show that the Degree And Distance Attachment model behaves similarly to the USWI against failures.

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.

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.

This paper investigates how we infer the status of others from their social relationships. In a series of experimental studies, we test the effects of a social relationship's type and direction on the status judgments of others. We demonstrate empirically, possibly for the first time, a widely-assumed connection between network structure and perceptions of status; that is, that observers do infer the status positions of group members from their relationships. Moreover, we find that observers' status judgments vary with the direction and type of social relationship. We theorize that underlying this variance in status judgments are two relational schemas which differentially influence the processing of the observed social ties. Our finding that only the linear-ordering schema leads to status inferences provides an important scope condition to prior research on network cognition, and specifically on the perceptions of social status.

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.

With origins in post-war development thinking, the core–periphery concept has spread across the social and, increasingly, the natural sciences. Initially reflecting divergent socioeconomic properties of geographical regions, its relational connotations rapidly led to more topological interpretations. In today's network science, the standard core–periphery model consists of a cohesive set of core actors and a peripheral set of internally disconnected actors. Exploring the classical core–periphery literature, this paper finds conceptual support for the characteristic intra-categorical density differential. However, this literature also lends support to the notions of peripheral dependency and core dominance, power-relational aspects that existing approaches do not capture. To capture such power-relations, this paper suggests extensions to the correlation-based core–periphery metric of Borgatti and Everett (2000). Capturing peripheral dependency and, optionally, core dominance, these extensions allow for either measuring the degree of such power-relational features in given core–periphery partitions, or as part of a criteria function to search for power-relational core–periphery structures. Applied to the binary and valued citation data in Borgatti and Everett (2000), the proposed extensions seemingly capture dependency and dominance features of core–periphery structures. This is particularly evident when, circling back to the original domains of the concept, examining the network of European commodity trade in 2010.

Latent stochastic blockmodels are flexible statistical models that are widely used in social network analysis. In recent years, efforts have been made to extend these models to temporal dynamic networks, whereby the connections between nodes are observed at a number of different times. In this paper, we propose a new Bayesian framework to characterize the construction of connections. We rely on a Markovian property to describe the evolution of nodes' cluster memberships over time. We recast the problem of clustering the nodes of the network into a model-based context, showing that the integrated completed likelihood can be evaluated analytically for a number of likelihood models. Then, we propose a scalable greedy algorithm to maximize this quantity, thereby estimating both the optimal partition and the ideal number of groups in a single inferential framework. Finally, we propose applications of our methodology to both real and artificial datasets.

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.

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.

In this introduction to the special section on globalization, regionalization, and multi-polarity, we review network analysis applications to the study of globalization as a complex and multi-dimensional phenomenon and we explore the frontiers of our knowledge about the network properties of global systems. We focus on the global economic (trade and investment), political, and migration systems.

We examined social mechanisms that account for similarity in the social context of school-sponsored extracurricular sports activities among friends. We distinguish two social mechanisms: “shared sports activities that lead to friendship,” whereby friendship formation and maintenance are conditioned by joint sports participation, and “friendship that leads to shared sports activities,” a form of social influence whereby adolescents join or maintain certain sports activities based on their friends' choices. Using a longitudinal sample of 1,776 10th graders at five high schools in Southern California, we employed a stochastic actor-oriented multivariate dynamic model to model the dynamic interplay between the two-mode affiliation network of adolescents' participation in sports activities and the one-mode friendship network. As a corresponding descriptive method, we propose a quantitative measure for the relative strength of the two-mentioned mechanisms as explanations of the association between the one-mode and the two-mode network. Further, we introduce two specifications that represent homophily effects in the two-mode network and apply them to test gender homophily in sports participation. The results provide strong evidence for both mechanisms, with friendship leading to shared sport activities as stronger than shared sports activities leading to friendships in explaining adolescents' friendships with co-participants.

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.

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.

Prisoner's Dilemma (PD) games have become a well-established paradigm for studying the mechanisms by which cooperative behavior may evolve in societies consisting of selfish individuals. Recent research has focused on the effect of spatial and connectivity structure in promoting the emergence of cooperation in scenarios where individuals play games with their neighbors, using simple “memoryless” rules to decide their choice of strategy in repeated games. While heterogeneity and structural features such as clustering have been seen to lead to reasonable levels of cooperation in very restricted settings, no conditions on network structure have been established, which robustly ensure the emergence of cooperation in a manner that is not overly sensitive to parameters such as network size, average degree, or the initial proportion of cooperating individuals. Here, we consider a natural random network model, with parameters that allow us to vary the level of “community” structure in the network, as well as the number of high degree hub nodes. We investigate the effect of varying these structural features and show that, for appropriate choices of these parameters, cooperative behavior does now emerge in a truly robust fashion and to a previously unprecedented degree. The implication is that cooperation (as modelled here by PD games) can become the social norm in societal structures divided into smaller communities, and in which hub nodes provide the majority of inter-community connections.

In this paper, we study how the topology of the International Trade Network (ITN) changes in geographical space, and along time. We employ geographical distance between countries in the world to filter the links in the ITN, building a sequence of subnetworks, each one featuring trade links occurring at similar distance. We then test if the assortativity and clustering of ITN subnetworks changes as distance increases, and we find that this is indeed the case: distance strongly impacts, in a non-linear way, the topology of the ITN. We show that the ITN is disassortative at long distances, while it is assortative at short ones. Similarly, the main determinant of the overall high-ITN clustering level are triangular trade triples between geographically close countries. This means that trade partnership choices and trade patterns are highly differentiated over different distance ranges, even after controlling for the economic size and income per capita of trading partners, and it is persistent over time. This evidence has relevant implications for the non-linear evolution of globalization.

Social influence is frequently measured through an ego's direct ties. Although influence may also stem from an ego's indirect ties, reference group, and casual contacts, it is difficult to capture their impact using existing network methods. We identify and trace the influence stemming from an ego's “familiar others,” consisting of those socially similar individuals with whom the ego comes in contact at school, but does not necessarily share a relationship. To evaluate the role of familiar others, we investigate unhealthy weight behaviors in adolescence using data from the National Longitudinal Study of Adolescent to Adult Health. Our results demonstrate that familiar others' unhealthy weight-related behaviors are strong predictors of the ego's own weight behaviors, net of immediate alters' behaviors, and individual-level characteristics. Further, we find that this relationship is stronger and more robust than that between egos and their direct ties. These results suggest that familiar others constitute a key source of social influence that is distinct from the influence of network alters.