Clustering a graph, i.e., assigning its nodes to groups, is an important operation whose best known application is the discovery of communities in social networks. Graph clustering and community detection have traditionally focused on graphs without attributes, with the notable exception of edge weights. However, these models only provide a partial representation of real social systems, that are thus often described using node attributes, representing features of the actors, and edge attributes, representing different kinds of relationships among them. We refer to these models as attributed graphs. Consequently, existing graph clustering methods have been recently extended to deal with node and edge attributes. This article is a literature survey on this topic, organizing, and presenting recent research results in a uniform way, characterizing the main existing clustering methods and highlighting their conceptual differences. We also cover the important topic of clustering evaluation and identify current open problems.

This is the beginning of Network Science. The journal has been created because network science is exploding. As is typical for a field in formation, the discussions about its scope, contents, and foundations are intense. On these first few pages of the first issue of our new journal, we would like to share our own vision of the emerging science of networks.

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.

We introduce NetworKit, an open-source software package for analyzing the structure of large complex networks. Appropriate algorithmic solutions are required to handle increasingly common large graph data sets containing up to billions of connections. We describe the methodology applied to develop scalable solutions to network analysis problems, including techniques like parallelization, heuristics for computationally expensive problems, efficient data structures, and modular software architecture. Our goal for the software is to package results of our algorithm engineering efforts and put them into the hands of domain experts. NetworKit is implemented as a hybrid combining the kernels written in C++ with a Python frontend, enabling integration into the Python ecosystem of tested tools for data analysis and scientific computing. The package provides a wide range of functionality (including common and novel analytics algorithms and graph generators) and does so via a convenient interface. In an experimental comparison with related software, NetworKit shows the best performance on a range of typical analysis tasks.

Homophily—the tendency for individuals to associate with similar others—is one of the most persistent findings in social network analysis. Its importance is established along the lines of a multitude of sociologically relevant dimensions, e.g. sex, ethnicity and social class. Existing research, however, mostly focuses on one dimension at a time. But people are inherently multidimensional, have many attributes and are members of multiple groups. In this article, we explore such multidimensionality further in the context of network dynamics. Are friendship ties increasingly likely to emerge and persist when individuals have an increasing number of attributes in common? We analyze eleven friendship networks of adolescents, draw on stochastic actor-oriented network models and focus on the interaction of established homophily effects. Our results indicate that main effects for homophily on various dimensions are positive. At the same time, the interaction of these homophily effects is negative. There seems to be a diminishing effect for having more than one attribute in common. We conclude that studies of homophily and friendship formation need to address such multidimensionality further.

We use data on a real, large-scale social network of 27 million individuals interacting daily, together with the day-by-day adoption of a new mobile service product, to inform, build, and analyze data-driven simulations of the effectiveness of seeding (network targeting) strategies under different social conditions. Three main results emerge from our simulations. First, failure to consider homophily creates significant overestimation of the effectiveness of seeding strategies, casting doubt on conclusions drawn by simulation studies that do not model homophily. Second, seeding is constrained by the small fraction of potential influencers that exist in the network. We find that seeding more than 0.2% of the population is wasteful because the gain from their adoption is lower than the gain from their natural adoption (without seeding). Third, seeding is more effective in the presence of greater social influence. Stronger peer influence creates a greater than additive effect when combined with seeding. Our findings call into question some conventional wisdom about these strategies and suggest that their overall effectiveness may be overestimated.

Time plays an essential role in the diffusion of information, influence, and disease over networks. In many cases we can only observe when a node is activated by a contagion—when a node learns about a piece of information, makes a decision, adopts a new behavior, or becomes infected with a disease. However, the underlying network connectivity and transmission rates between nodes are unknown. Inferring the underlying diffusion dynamics is important because it leads to new insights and enables forecasting, as well as influencing or containing information propagation. In this paper we model diffusion as a continuous temporal process occurring at different rates over a latent, unobserved network that may change over time. Given information diffusion data, we infer the edges and dynamics of the underlying network. Our model naturally imposes sparse solutions and requires no parameter tuning. We develop an efficient inference algorithm that uses stochastic convex optimization to compute online estimates of the edges and transmission rates. We evaluate our method by tracking information diffusion among 3.3 million mainstream media sites and blogs, and experiment with more than 179 million different instances of information spreading over the network in a one-year period. We apply our network inference algorithm to the top 5,000 media sites and blogs and report several interesting observations. First, information pathways for general recurrent topics are more stable across time than for on-going news events. Second, clusters of news media sites and blogs often emerge and vanish in a matter of days for on-going news events. Finally, major events, for example, large scale civil unrest as in the Libyan civil war or Syrian uprising, increase the number of information pathways among blogs, and also increase the network centrality of blogs and social media sites.

We study the diffusion of an idea, a product, a disease, a cultural fad, or a technology among agents in a social network that exhibits segregation or homophily (the tendency of agents to associate with others similar to themselves). Individuals are distinguished by their types—e.g., race, gender, age, wealth, religion, profession—which, together with biased interaction patterns, induce heterogeneous rates of adoption or infection. We identify the conditions under which a behavior or disease diffuses and becomes persistent in the population. These conditions relate to the level of homophily in a society and the underlying proclivities of various types for adoption or infection. In particular, we show that homophily can facilitate diffusion from a small initial seed of adopters.

The human connectome has been widely studied over the past decade. A principal finding is that it can be decomposed into communities of densely interconnected brain regions. Past studies have often used single-scale modularity measures in order to infer the connectome's community structure, possibly overlooking interesting structure at other organizational scales. In this report, we used the partition stability framework, which defines communities in terms of a Markov process (random walk), to infer the connectome's multi-scale community structure. Comparing the community structure to observed resting-state functional connectivity revealed communities across a broad range of scales that were closely related to functional connectivity. This result suggests a mapping between communities in structural networks, models of influence-spreading and diffusion, and brain function. It further suggests that the spread of influence among brain regions may not be limited to a single characteristic scale.

The gravity model, long the empirical workhorse for modeling international trade, ignores network dependencies in bilateral trade data, instead assuming that dyadic trade is independent, conditional on a hierarchy of covariates over country, time, and dyad. We argue that there are theoretical as well as empirical reasons to expect network dependencies in international trade. Consequently, standard gravity models are empirically inadequate. We combine a gravity model specification with “latent space” networks to develop a dynamic mixture model for real-valued directed graphs. The model simultaneously incorporates network dependencies in both trade incidence and trade volumes. We estimate this model using bilateral trade data from 1990 to 2008. The model substantially outperforms standard accounts in terms of both in- and out-of-sample predictive heuristics. We illustrate the model's usefulness by tracking trading propensities between the USA and China.

In empirical studies of friendship networks, participants are typically asked, in interviews or questionnaires, to identify some or all of their close friends, resulting in a directed network in which friendships can, and often do, run in only one direction between a pair of individuals. Here we analyze a large collection of such networks representing friendships among students at US high and junior-high schools and show that the pattern of unreciprocated friendships is far from random. In every network, without exception, we find that there exists a ranking of participants, from low to high, such that almost all unreciprocated friendships consist of a lower ranked individual claiming friendship with a higher ranked one. We present a maximum-likelihood method for deducing such rankings from observed network data and conjecture that the rankings produced reflect a measure of social status. We note in particular that reciprocated and unreciprocated friendships obey different statistics, suggesting different formation processes, and that rankings are correlated with other characteristics of the participants that are traditionally associated with status, such as age and overall popularity as measured by total number of friends.

To find out, we measure co-voting similarity networks in the US Senate and trace individual careers over time. Standard network visualization tools fail on dense highly clustered networks, so we used two aggregation strategies to clarify positional mobility over time. First, clusters of Senators who often vote the same way capture coalitions, and allow us to measure polarization quantitatively through modularity (Newman, 2006; Waugh et al., 2009; Poole, 2012). Second, we use role-based blockmodels (White et al., 1976) to identify role positions, identifying sets of Senators with highly similar tie patterns. Our partitioning threshold for roles is stringent, generating many roles occupied by single Senators. This combination allows us to identify movement between positions over time (specifically, we used the Kernighan–Lin improvement of a Louvain method greedy partitioning algorithm for modularity [Blondel et al., 2008], and CONCOR with an internal similarity threshold for roles; see Supplementary materials for details).

In network models for real-world domains, often network adaptation has to be addressed by incorporating certain network adaptation principles. In some cases, also higher order adaptation occurs: the adaptation principles themselves also change over time. To model such multilevel adaptation processes, it is useful to have some generic architecture. Such an architecture should describe and distinguish the dynamics within the network (base level), but also the dynamics of the network itself by certain adaptation principles (first-order adaptation level), and also the adaptation of these adaptation principles (second-order adaptation level), and may be still more levels of higher order adaptation. This paper introduces a multilevel network architecture for this, based on the notion network reification. Reification of a network occurs when a base network is extended by adding explicit states representing the characteristics of the structure of the base network. It will be shown how this construction can be used to explicitly represent network adaptation principles within a network. When the reified network is itself also reified, also second-order adaptation principles can be explicitly represented. The multilevel network reification construction introduced here is illustrated for an adaptive adaptation principle from social science for bonding based on homophily and one for metaplasticity in Cognitive Neuroscience.

The temporal exponential random graph model (TERGM) and the stochastic actor-oriented model (SAOM, e.g., SIENA) are popular models for longitudinal network analysis. We compare these models theoretically, via simulation, and through a real-data example in order to assess their relative strengths and weaknesses. Though we do not aim to make a general claim about either being superior to the other across all specifications, we highlight several theoretical differences the analyst might consider and find that with some specifications, the two models behave very similarly, while each model out-predicts the other one the more the specific assumptions of the respective model are met.

The analysis of multilayer networks is among the most active areas of network science, and there are several methods to detect dense “communities” of nodes in multilayer networks. One way to define a community is as a set of nodes that trap a diffusion-like dynamical process (usually a random walk) for a long time. In this view, communities are sets of nodes that create bottlenecks to the spreading of a dynamical process on a network. We analyze the local behavior of different random walks on multiplex networks (which are multilayer networks in which different layers correspond to different types of edges) and show that they have very different bottlenecks, which correspond to rather different notions of what it means for a set of nodes to be a good community. This has direct implications for the behavior of community-detection methods that are based on these random walks.

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.

The analysis of complex networks has so far revolved mainly around the role of nodes and communities of nodes. However, the dynamics of interconnected systems is often focalized on edge processes, and a dual edge-centric perspective can often prove more natural. Here we present graph-theoretical measures to quantify edge-to-edge relations inspired by the notion of flow redistribution induced by edge failures. Our measures, which are related to the pseudo-inverse of the Laplacian of the network, are global and reveal the dynamical interplay between the edges of a network, including potentially non-local interactions. Our framework also allows us to define the embeddedness of an edge, a measure of how strongly an edge features in the weighted cuts of the network. We showcase the general applicability of our edge-centric framework through analyses of the Iberian power grid, traffic flow in road networks, and the C. elegans neuronal network.

Many studies have attempted to determine whether an observed network exhibits a so-called “small-world structure.” Such determinations have often relied on a conceptual definition of small worldliness proposed by Watts and Strogatz in their seminal 1998 paper, but recently several quantitative indices of network small worldliness have emerged. This paper reviews and compares three such indices—the small-world quotient (Q), a small-world metric (ω), and the small-world index(SWI)—in the canonical Watts–Strogatz re-wiring model and in four real-world networks. These analyses suggest that researchers should avoid Q, and identify considerations that should guide the choice between ω and SWI.

Discovering community structure in complex networks is a mature field since a tremendous number of community detection methods have been introduced in the literature. Nevertheless, it is still very challenging for practitioners to determine which method would be suitable to get insights into the structural information of the networks they study. Many recent efforts have been devoted to investigating various quality scores of the community structure, but the problem of distinguishing between different types of communities is still open. In this paper, we propose a comparative, extensive, and empirical study to investigate what types of communities many state-of-the-art and well-known community detection methods are producing. Specifically, we provide comprehensive analyses on computation time, community size distribution, a comparative evaluation of methods according to their optimization schemes as well as a comparison of their partitioning strategy through validation metrics. We process our analyses on a very large corpus of hundreds of networks from five different network categories and propose ways to classify community detection methods, helping a potential user to navigate the complex landscape of community detection.

We consider the specification of effects of numerical actor attributes, having an interval level of measurement, in statistical models for directed social networks. A fundamental mechanism is homophily or assortativity, where actors have a higher likelihood to be tied with others having similar values of the variable under study. But there are other mechanisms that may also play a role in how the attribute values of two actors influence the likelihood of a tie between them. We discuss three additional mechanisms: aspiration, the tendency to send more ties to others having high values; attachment conformity, sending more ties to others whose values are close to the “social norm”; and sociability, where those having higher values will tend to send more ties generally. These mechanisms may operate jointly, and then their effects will be confounded. We present a specification representing these effects simultaneously by a four-parameter quadratic function of the values of sender and receiver. Flexibility can be increased by a five-parameter extension. We argue that for numerical actor attributes having important effects on directed networks, these specifications may provide an improvement. An illustration is given of dependence of advice ties on academic grades, analyzed by the Stochastic Actor-oriented Model.