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. [Slides]
The dynamics of networks of neuronal cultures has been recently shown to be strongly dependent on the network geometry and in particular on their dimensionality. However, this phenomenon has been so far mostly unexplored from the theoretical point of view. Here we reveal the rich interplay between network geometry and synchronization of coupled oscillators in the context of a simplicial complex model of manifolds called Complex Network Manifold. The networks generated by this model combine small world properties (infinite Hausdorff dimension) and a high modular structure with finite and tunable spectral dimension. We show that the networks display frustrated synchronization for a wide range of the coupling strength of the oscillators, and that the synchronization properties are directly affected by the spectral dimension of the network. [Slides]
In this talk, I'll show that the community structure of a network can be used as a coarse version of its embedding in a hidden space with hyperbolic geometry. The finding emerges from a systematic analysis of several real-world and synthetic networks. I'll take advantage of the analogy for reinterpreting results originally obtained through network hyperbolic embedding in terms of community structure only. First, I'll show that the robustness of a multiplex network can be controlled by tuning the correlation between the community structures across different layers. Second, I'll deploy an efficient greedy protocol for network navigability that makes use of routing tables based on community structure. [Slides]
The coexistence of multiple types of interactions within social, technological and biological networks has moved the focus of the physics of complex systems towards a multiplex description of the interactions between their constituents. Here we address an important issue that is intrinsic to the coexistence of multiple means of interactions within a network: their competition. To this aim, we study a two-layer multiplex in which the activity of users can be localized in each of the layers or shared between them, favoring that neighboring nodes within a layer focus their activity on the same layer. This framework mimics the coexistence and competition of multiple communication channels, in a way that the prevalence of a particular communication platform emerges as a result of the localization of users activity in one single interaction layer. Our results indicate that there is a transition from localization (use of a preferred layer) to delocalization (combined usage of both layers) and that the prevalence of a particular layer (in the localized state) depends on their structural properties. To obtain these results, advanced optimization techniques are needed since standard methods fail to capture the ground state. In particular, we have selected Particle Swarm Optimization, one of the outstanding Swarm Intelligence methodologies. [Slides]
Deep generative models have been praised for their ability to learn smooth latent representation of images, text, and audio, which can then be used to generate new, plausible data. However, current generative models are unable to work with graphs due to their unique characteristics—their underlying structure is not Euclidean or grid-like, they remain isomor- phic under permutation of the nodes labels, and they come with a different number of nodes and edges. In this paper, we propose NeVAE, a novel variational autoencoder for graphs, whose encoder and decoder are specially designed to account for the above properties by means of several technical innovations. In addition, by using masking, the decoder is able to guarantee a set of local structural and functional properties in the generated graphs. Experiments reveal that our model is able to learn and mimic the generative process of several well- known random graph models and can be used to discover new molecules more effectively than several state of the art methods. Moreover, by utilizing Bayesian optimization over the continuous latent representation of molecules our model finds, we can also identify molecules that maximize certain desirable properties more effectively than alternatives.
Networks are often modelled using global connection rules where the presence of edges is prescribed at the network level (e.g. Erdős–Rényi networks) however these models can potentially neglect more complex interactions between nodes in the formation of the network. In this talk we study the behaviour of collections of nodes by considering a topological and temporal decomposition of temporal network. Characterizing the behaviour of these collectives using both temporal and static features to create an feature-space embedding we show that the temporal network is comprised of many distinct behaviours whose prevalence also varies over time. This suggests that to model certain systems we may need to consider all of individual, local, and global interactions in unison. Switching our focus to dynamics on networks, we further we show that the same methods can be used to characterise dynamical processes (such as the spread of infection) on an underlying network. [Slides]
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 with 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 factors involved in the formation of links and contagion processes in complex networks. It is common practice to measure the level of assortativity according to the assortativity coefficient, or modularity in the case of discrete-valued 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 localise 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. [Slides]
In the era of big data, graph sampling is indispensable in many settings. Existing sampling methods are mostly designed for static graphs, and aim to preserve basic structural properties of the original graph (such as degree distribution, clustering coefficient etc.) in the sample. We argue that for any sampling method it is impossible to produce an universal representative sample which can preserve all the properties of the original graph; rather sampling should be application specific (such as preserving hubs - needed for information diffusion). Here we consider community detection as an application scenario. We propose ComPAS, a novel sampling strategy that unlike previous methods, is not only designed for streaming graphs (which is a more realistic representation of a real-world scenario) but also preserves the community structure of the original graph in the sample. Empirical results on both synthetic and different real-world graphs show that ComPAS is the best to preserve the underlying community structure. [Slides]
Multilayer networks allow one to represent diverse and dependent connectivity patterns &emdash; e.g., time-dependence, multiple subsystems, or both &emdash; that arise in many applications and which are difficult or awkward to incorporate into standard network representations. In the study of multilayer networks, it is important to investigate mesoscale (i.e., intermediate-scale) structures, such as dense sets of nodes known as communities, to discover network features that are not apparent at the microscale or the macroscale. In this paper, we introduce a generative model for mesoscale structure in multilayer networks. Our model is very general &emdash; and can thus admit many features of empirical multilayer networks &emdash; and explicitly incorporates a user-specified dependency structure between layers. Our results provide a standardized set of null models, together with an associated set of principles from which they are derived, for studies of mesoscale structures in multilayer networks. We discuss the parameters and properties of our generative model, and we illustrate examples of its use as a benchmark model for community-detection methods and algorithms in multilayer networks.
Human decision-making is influenced by a multitude of factors, including social, psychological, neurological, normative, and learning factors, as well as individual traits like age and education level. Social/cognitive computational models that incorporate these factors are increasingly being used to study human decision-making. A result is that agent models, within agent-based modeling (ABM), are becoming more heavyweight, i.e., are more computationally demanding, making scalability and at-scale simulations all the more difficult to achieve. To address these challenges, we have developed Matrix: an ABM simulation framework, that uses bulk synchronous parallel design that makes it easy for authors of complex agents to develop data-intensive simulations at-scale. To demonstrate the effectiveness of our platform we also describe system requirements and design of a simulation of the GitHub platform. We simulate the interactions of 5 million users (each as an individual agent) with 45 million repositories, leading to 797 million user-repository interactions. Our simulations predict user interactions with GitHub repositories, which to our knowledge are the first simulations of this kind. Our simulations demonstrate a 3-order of magnitude increase in the number of cognitive agents simultaneously interacting, compared to previous state-of-the-art.