In this paper, we develop a formal framework for what a good community should look like and how strong a community is (community strength). One of the key innovations is to incorporate the concept of relative centrality into structural analysis of networks. In our framework, relative centrality is a measure that measures how important a set of nodes in a network is with respect to another set of nodes, and it is a generalization of centrality. Building on top of relative centrality, the community strength for a set of nodes is measured by the difference between its relative centrality with respect to itself and its centrality. A community is then a set of nodes with a nonnegative community strength. We show that our community strength is related to conductance that is commonly used for measuring the strength of a small community. We define the modularity for a partition of a network as the average community strength for a randomly selected node. Such a definition generalizes the original Newman's modularity and recovers the stability in as special cases. For the local community detection problem, we also develop efficient agglomerative algorithms that guarantee the community strength of the detected local community.

The first two research articles in this issue of Network Science have a common theme—they use workplace contact patterns, in addition to other data, to model infectious disease spread.

The special issue of “Networks in space and in time: methods and applications” contributes to the debate on contextual analysis in network science. It includes seven research papers that shed light on the analysis of network phenomena studied within geographic space and across temporal dimensions. In these papers, methodological issues as well as specific applications are described from different fields. We take the seven papers, study their citations and texts, and relate them to the broader literature. By exploiting the bibliographic information and the textual data of these seven documents, citation analysis and lexical correspondence analysis allow us to evaluate the connections among the papers included in this issue.

The clustering coefficient is typically used as a measure of the prevalence of node clusters in a network. Various definitions for this measure have been proposed for the cases of networks having weighted edges which may or not be directed. However, these techniques consistently assume that only a subset of all possible edges is present in the network, whereas there are weighted networks of interest in which all possible edges are present, that is, complete weighted networks. For this situation, the concept of clustering is redefined, and computational techniques are presented for computing an associated clustering coefficient for complete weighted undirected or directed networks. The performance of this new definition is compared with that of current clustering definitions when extended to complete weighted networks.

Most social networks present complex structures. They can be both multi-modal and multi-relational. In addition, each relationship can be observed across time occasions. Relational data observed in such conditions can be organized into multidimensional arrays and statistical methods from the theory of multiway data analysis may be exploited to reveal the underlying data structure. In this paper, we adopt an exploratory data analysis point of view, and we present a procedure based on multiple factor analysis and multiple correspondence analysis to deal with time-varying two-mode networks. This procedure allows us to create static displays in order to explore network evolutions and to visually analyze the degree of similarity of actor/event network profiles over time while preserving the different statuses of the two modes.

Inspired by socio-political scenarios, like dictatorships, in which a minority of people exercise control over a majority of weakly interconnected individuals, we propose vulnerability and power measures defined on groups of actors of networks. We establish an unexpected connection between network vulnerability and graph regularizability. We use the Shapley value of coalition games to introduce fresh notions of vulnerability and power at node level defined in terms of the corresponding measures at group level. We investigate the computational complexity of computing the defined measures, both at group and node levels, and provide effective methods to quantify them. Finally we test vulnerability and power on both artificial and real networks.

Triadic closure has been conceptualized and measured in a variety of ways, most famously the clustering coefficient. Existing extensions to affiliation networks, however, are sensitive to repeat group attendance, which does not reflect common interpersonal interpretations of triadic closure. This paper proposes a measure of triadic closure in affiliation networks designed to control for this factor, which manifests in bipartite models as biclique proliferation. To avoid arbitrariness, the paper introduces a triadic framework for affiliation networks, within which a range of measures can be defined; it then presents a set of basic axioms that suffice to narrow this range to the one measure. An instrumental assessment compares the proposed and two existing measures for reliability, validity, redundancy, and practicality. All three measures then take part in an investigation of three empirical social networks, which illustrates their differences.

Face-to-face social contacts are potentially important transmission routes for acute respiratory infections, and understanding the contact network can improve our ability to predict, contain, and control epidemics. Although workplaces are important settings for infectious disease transmission, few studies have collected workplace contact data and estimated workplace contact networks. We use contact diaries, architectural distance measures, and institutional structures to estimate social contact networks within a Swiss research institute. Some contact reports were inconsistent, indicating reporting errors. We adjust for this with a latent variable model, jointly estimating the true (unobserved) network of contacts and duration-specific reporting probabilities. We find that contact probability decreases with distance, and that research group membership, role, and shared projects are strongly predictive of contact patterns. Estimated reporting probabilities were low only for 0–5 min contacts. Adjusting for reporting error changed the estimate of the duration distribution, but did not change the estimates of covariate effects and had little effect on epidemic predictions. Our epidemic simulation study indicates that inclusion of network structure based on architectural and organizational structure data can improve the accuracy of epidemic forecasting models.

Complex networks have recently attracted much interest due to their prevalence in nature and our daily lives (Vespignani, 2009; Newman, 2010). A critical property of a network is its resilience to random breakdown and failure (Albert et al., 2000; Cohen et al., 2000; Callaway et al., 2000; Cohen et al., 2001), typically studied as a percolation problem (Stauffer & Aharony, 1994; Achlioptas et al., 2009; Chen & D'Souza, 2011) or by modeling cascading failures (Motter, 2004; Buldyrev et al., 2010; Brummitt, et al. 2012). Many complex systems, from power grids and the Internet to the brain and society (Colizza et al., 2007; Vespignani, 2011; Balcan & Vespignani, 2011), can be modeled using modular networks comprised of small, densely connected groups of nodes (Girvan & Newman, 2002). These modules often overlap, with network elements belonging to multiple modules (Palla et al. 2005; Ahn et al. 2010). Yet existing work on robustness has not considered the role of overlapping, modular structure. Here we study the robustness of these systems to the failure of elements. We show analytically and empirically that it is possible for the modules themselves to become uncoupled or non-overlapping well before the network disintegrates. If overlapping modular organization plays a role in overall functionality, networks may be far more vulnerable than predicted by conventional percolation theory.

Dynamic network models describe many important scientific processes, from cell biology and epidemiology to sociology and finance. Estimating dynamic networks from noisy time series data is a difficult task since the number of components involved in the system is very large. As a result, the number of parameters to be estimated is typically larger than the number of observations. However, a characteristic of many real life networks is that they are sparse. For example, the molecular structure of genes make interactions with other components a highly-structured and, therefore, a sparse process. Until now, the literature has focused on static networks, which lack specific temporal interpretations.

We propose a flexible collection of ANOVA-like dynamic network models, where the user can select specific time dynamics, known presence or absence of links, and a particular autoregressive structure. We use undirected graphical models with block equality constraints on the parameters. This reduces the number of parameters, increases the accuracy of the estimates and makes interpretation of the results more relevant. We illustrate the flexibility of the method on both synthetic and real data.

Empirical data on contacts between individuals in social contexts play an important role in providing information for models describing human behavior and how epidemics spread in populations. Here, we analyze data on face-to-face contacts collected in an office building. The statistical properties of contacts are similar to other social situations, but important differences are observed in the contact network structure. In particular, the contact network is strongly shaped by the organization of the offices in departments, which has consequences in the design of accurate agent-based models of epidemic spread. We consider the contact network as a potential substrate for infectious disease spread and show that its sparsity tends to prevent outbreaks of rapidly spreading epidemics. Moreover, we define three typical behaviors according to the fraction f of links each individual shares outside its own department: residents, wanderers, and linkers. Linkers (f ~ 50%) act as bridges in the network and have large betweenness centralities. Thus, a vaccination strategy targeting linkers efficiently prevents large outbreaks. As such a behavior may be spotted a priori in the offices' organization or from surveys, without the full knowledge of the time-resolved contact network, this result may help the design of efficient, low-cost vaccination or social-distancing strategies.

To expand the toolbox available to network science, we study the isomorphism between distance and Fuzzy (proximity or strength) graphs. Distinct transitive closures in Fuzzy graphs lead to closures of their isomorphic distance graphs with widely different structural properties. For instance, the All Pairs Shortest Paths (APSP) problem, based on the Dijkstra algorithm, is equivalent to a metric closure, which is only one of the possible ways to calculate shortest paths in weighted graphs. We show that different closures lead to different distortions of the original topology of weighted graphs. Therefore, complex network analyses that depend on the calculation of shortest paths on weighted graphs should take into account the closure choice and associated topological distortion. We characterize the isomorphism using the max-min and Dombi disjunction/conjunction pairs. This allows us to: (1) study alternative distance closures, such as those based on diffusion, metric, and ultra-metric distances; (2) identify the operators closest to the metric closure of distance graphs (the APSP), but which are logically consistent; and (3) propose a simple method to compute alternative path length measures and corresponding distance closures using existing algorithms for the APSP. In particular, we show that a specific diffusion distance is promising for community detection in complex networks, and is based on desirable axioms for logical inference or approximate reasoning on networks; it also provides a simple algebraic means to compute diffusion processes on networks. Based on these results, we argue that choosing different distance closures can lead to different conclusions about indirect associations on network data, as well as the structure of complex networks, and are thus important to consider.

Over the past years, network science has proven invaluable as a means to better understand many of the processes taking place in the brain. Recently, interareal connectivity data of the macaque cortex was made available with great richness of detail. We explore new aspects of this dataset, such as a correlation between connection weights and cortical hierarchy. We also look at the link-community structure that emerges from the data to uncover the major communication pathways in the network, and moreover investigate its reciprocal connections, showing that they share similar properties. A question arising from these analyses is that of determining the role of weak connections in the unfolding of cortical processes. Though we leave this question largely unanswered, we have found that weak connections pervade the entire cortex while giving rise to no community-like structure. We conjecture that whatever function they come to be found to perform will likely involve some form of cortex-wide communication or control.

In dynamic networks, the presence of ties are subject both to endogenous network dependencies and spatial dependencies. Current statistical models for change over time are typically defined relative to some initial condition, thus skirting the issue of where the first network came from. Additionally, while these longitudinal network models may explain the dynamics of change in the network over time, they do not explain the change in those dynamics. We propose an extension to the longitudinal exponential random graph model that allows for simultaneous inference of the changes over time and the initial conditions, as well as relaxing assumptions of time-homogeneity. Estimation draws on recent Bayesian approaches for cross-sectional exponential random graph models and Bayesian hierarchical models. This is developed in the context of foreign direct investment relations in the global electricity industry in 1995–2003. International investment relations are known to be affected by factors related to: (i) the initial conditions determined by the geographical locations; (ii) time-dependent fluctuations in the global intensity of investment flows; and (iii) endogenous network dependencies. We rely on the well-known gravity model used in research on international trade to represent how spatial embedding and endogenous network dependencies jointly shape the dynamics of investment relations.

Asymmetric ties make up a significant proportion of ties in friendship networks. But little is known about their origins. Prior research has suggested treating them either as “accidental” (e.g., resulting from constraints in name generators) or “aspirational” (i.e., the attempts of individuals to pursue relationships with higher status peers). In this paper, we show that self-perception can also explain the occurrence of asymmetric ties. We argue that under the general norm of reciprocity, actors with high self-perceived centrality will more likely send out ties to others than their counterparts. Supposing that outgoing ties are similarly reciprocated by peers, then actors with high self-perceived centrality will also entail more asymmetric ties. We test this idea along with the competing arguments using exponential random graph models (ERGMs) on network data collected from over 4,000 students in China. Consistent with previous findings, we find that asymmetric ties reflect status differences, but probably more strongly so for difference in individual status characteristics than difference in social positional status. More importantly, we find that students with high self-perceived centrality are about twice as likely to send asymmetric ties as their peers. Last, we examine the implications of our findings for future network research.

Modularity maximization has been one of the most widely used approaches in the last decade for discovering community structure in networks of practical interest in biology, computing, social science, statistical mechanics, and more. Modularity is a quality function that measures the difference between the number of edges found within clusters minus the number of edges one would statistically expect to find based on some equivalent random graph model. We explore a natural generalization of modularity based on the difference between the actual and expected number of walks within clusters, which we refer to as walk-modularity. Walk-modularity can be expressed in matrix form, and community detection can be performed by finding the leading eigenvector of the walk-modularity matrix. We demonstrate community detection on both synthetic and real-world networks and find that walk-modularity maximization returns significantly improved results compared to traditional modularity maximization.

We study the interplay between the diffusion of a harmful state in a network of contacts and the possibility of individual agents to undertake costly investment to protect themselves against infection. We characterize how equilibrium diffusion outcomes, such as the immunization rate, total prevalence and welfare, respond to changes in the architecture of the network, and show that these responses depend on the details of the diffusion process.

We compare and contrast the network formation of interest groups across industry and issue area. We focus on membership interest groups, which by virtue of representing the interests of voluntary members face particular organizational and maintenance constraints. To reveal their cooperative behavior we build a network dataset based on cosigner status to United States Supreme Court amicus curiae briefs and analyze it with exponential random graph models and multidimensional scaling. Our methodological approach culminates in a clear and compact spatial representation of network similarities and differences. We find that while many of the same factors shape membership networks, religious, labor, and political organizations do not share the same structure as each other or as the business, civic and professional groups.

Writers for popular media frequently draw on insights known about social networks in developing their plotlines and character biographies (whether in books, television, movies, etc.). Perhaps most known to network analysts in this respect, Freeman (2000) presents a collection of network concepts represented in comic strips. These depictions often are consistent with the patterns network analysts observe in real-world empirical examples. For example, the long-running sitcom Friends exhibited strong homophily (McPherson et al., 2001) or assortative mixing on race and socioeconomic status among the main characters. Other times the violation of these typical patterns can serve to generate dramatic tension or a source of comedy. For example transitivity—or the tendency of one's friends to also become friends (Holland & Leinhardt, 1972)—is absent in the movie Hush where Jessica Lange's character plots to kill the daughter-in-law she does not like. P-O-X social balance (Heider, 1948) describes the tendency for friends to share common interests, which was violated to comedic effect in the Seinfeld episode where Jerry's character simply cannot accept his date's refusal to try a taste of the pie he finds delicious, bothering him for days and ultimately leading to his ending the relationship.