Hierarchical community structure in networks.

Modular and hierarchical community structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions. (1) How should we define a hierarchy of communities? (2) How do we determine if there is sufficient evidence of a hierarchical structure in a network? (3) How can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.

Statistical inference links data and theory in network science.

The number of network science applications across many different fields has been rapidly increasing. Surprisingly, the development of theory and domain-specific applications often occur in isolation, risking an effective disconnect between theoretical and methodological advances and the way network science is employed in practice. Here we address this risk constructively, discussing good practices to guarantee more successful applications and reproducible results. We endorse designing statistically grounded methodologies to address challenges in network science. This approach allows one to explain observational data in terms of generative models, naturally deal with intrinsic uncertainties, and strengthen the link between theory and applications.

Community detection in networks without observing edges.

We develop a Bayesian hierarchical model to identify communities of time series. Fitting the model provides an end-to-end community detection algorithm that does not extract information as a sequence of point estimates but propagates uncertainties from the raw data to the community labels. Our approach naturally supports multiscale community detection and the selection of an optimal scale using model comparison. We study the properties of the algorithm using synthetic data and apply it to daily returns of constituents of the S&P100 index and climate data from U.S. cities.

Network constraints on the mixing patterns of binary node metadata.

We consider the network constraints on the bounds of the assortativity coefficient, which aims to quantify the tendency of nodes with the same attribute values to be connected. The assortativity coefficient can be considered as the Pearson's correlation coefficient of node metadata values across network edges and lies in the interval [-1,1]. However, properties of the network, such as degree distribution and the distribution of node metadata values, place constraints upon the attainable values of the assortativity coefficient. This is important as a particular value of assortativity may say as much about the network topology as about how the metadata are distributed over the network-a fact often overlooked in literature where the interpretation tends to focus simply on the propensity of similar nodes to link to each other, without any regard on the constraints posed by the topology. In this paper we quantify the effect that the topology has on the assortativity coefficient in the case of binary node metadata. Specifically, we look at the effect that the degree distribution, or the full topology, and the proportion of each metadata value has on the extremal values of the assortativity coefficient. We provide the means for obtaining bounds on the extremal values of assortativity for different settings and demonstrate that under certain conditions the maximum and minimum values of assortativity are severely limited, which may present issues in interpretation when these bounds are not considered.

Individual perception dynamics in drunk games.

We study the effects of individual perceptions of payoffs in two-player games. In particular we consider the setting in which individuals' perceptions of the game are influenced by their previous experiences and outcomes. Accordingly, we introduce a framework based on evolutionary games where individuals have the capacity to perceive their interactions in different ways. Starting from the narrative of social behaviors in a pub as an illustration, we first study the combination of the Prisoner's Dilemma and Harmony Game as two alternative perceptions of the same situation. Considering a selection of game pairs, our results show that the interplay between perception dynamics and game payoffs gives rise to nonlinear phenomena unexpected in each of the games separately, such as catastrophic phase transitions in the cooperation basin of attraction, Hopf bifurcations and cycles of cooperation and defection. Combining analytical techniques with multiagent simulations, we also show how introducing individual perceptions can cause nontrivial dynamical behaviors to emerge, which cannot be obtained by analyzing the system at a macroscopic level. Specifically, initial perception heterogeneities at the microscopic level can yield a polarization effect that is unpredictable at the macroscopic level. This framework opens the door to the exploration of new ways of understanding the link between the emergence of cooperation and individual preferences and perceptions, with potential applications beyond social interactions.

Multiscale mixing patterns in networks.

Assortative mixing in networks is the tendency for nodes with the same attributes, or metadata, to link to each other. It is a property often found in social networks, manifesting as a higher tendency of links occurring between people of the same age, race, or political belief. Quantifying the level of assortativity or disassortativity (the preference of linking to nodes with different attributes) can shed light on the organization of complex networks. It is common practice to measure the level of assortativity according to the assortativity coefficient, or modularity in the case of categorical metadata. This global value is the average level of assortativity across the network and may not be a representative statistic when mixing patterns are heterogeneous. For example, a social network spanning the globe may exhibit local differences in mixing patterns as a consequence of differences in cultural norms. Here, we introduce an approach to localize this global measure so that we can describe the assortativity, across multiple scales, at the node level. Consequently, we are able to capture and qualitatively evaluate the distribution of mixing patterns in the network. We find that, for many real-world networks, the distribution of assortativity is skewed, overdispersed, and multimodal. Our method provides a clearer lens through which we can more closely examine mixing patterns in networks.

The architecture of an empirical genotype-phenotype map.

Recent advances in high-throughput technologies are bringing the study of empirical genotype-phenotype (GP) maps to the fore. Here, we use data from protein-binding microarrays to study an empirical GP map of transcription factor (TF) -binding preferences. In this map, each genotype is a DNA sequence. The phenotype of this DNA sequence is its ability to bind one or more TFs. We study this GP map using genotype networks, in which nodes represent genotypes with the same phenotype, and edges connect nodes if their genotypes differ by a single small mutation. We describe the structure and arrangement of genotype networks within the space of all possible binding sites for 525 TFs from three eukaryotic species encompassing three kingdoms of life (animal, plant, and fungi). We thus provide a high-resolution depiction of the architecture of an empirical GP map. Among a number of findings, we show that these genotype networks are "small-world" and assortative, and that they ubiquitously overlap and interface with one another. We also use polymorphism data from Arabidopsis thaliana to show how genotype network structure influences the evolution of TF-binding sites in vivo. We discuss our findings in the context of regulatory evolution.

The ground truth about metadata and community detection in networks.

Across many scientific domains, there is a common need to automatically extract a simplified view or coarse-graining of how a complex system's components interact. This general task is called community detection in networks and is analogous to searching for clusters in independent vector data. It is common to evaluate the performance of community detection algorithms by their ability to find so-called ground truth communities. This works well in synthetic networks with planted communities because these networks' links are formed explicitly based on those known communities. However, there are no planted communities in real-world networks. Instead, it is standard practice to treat some observed discrete-valued node attributes, or metadata, as ground truth. We show that metadata are not the same as ground truth and that treating them as such induces severe theoretical and practical problems. We prove that no algorithm can uniquely solve community detection, and we prove a general No Free Lunch theorem for community detection, which implies that there can be no algorithm that is optimal for all possible community detection tasks. However, community detection remains a powerful tool and node metadata still have value, so a careful exploration of their relationship with network structure can yield insights of genuine worth. We illustrate this point by introducing two statistical techniques that can quantify the relationship between metadata and community structure for a broad class of models. We demonstrate these techniques using both synthetic and real-world networks, and for multiple types of metadata and community structures.