Impact of origin-destination information in epidemic spreading
Sergio Gómez, Alberto Fernández, Sandro Meloni and Alex Arenas
Scientific Reports 9 (2019) 2315
(pdf) (doi) (Springer-Nature open access)
The networked structure of contacts shapes the spreading of epidemic processes. Recent advances on network theory have improved our understanding of the epidemic processes at large scale. The relevance of several considerations still needs to be evaluated in the study of epidemic spreading. One of them is that of accounting for the influence of origin and destination patterns in the flow of the carriers of an epidemic. Here we compute origin-destination patterns compatible with empirical data of coarse grained flows in the air transportation network. We study the incidence of epidemic processes in a metapopulation approach considering different alternatives to the flows prior knowledge. The data-driven scenario where the estimation of origin and destination flows is considered turns out to be relevant to assess the impact of the epidemics at a microscopic level (in our scenario, which populations are infected). However, this information is irrelevant to assess its macroscopic incidence (fraction of infected populations). These results are of interest to implement even better computational platforms to forecast epidemic incidence.
Shortest paths are representative of discrete geodesic distances in graphs, and many descriptors of networks depend on their counting. In multiplex networks, this counting is radically important to quantify the switch between layers and it has crucial implications in the transportation efficiency and congestion processes. Here we present a mathematical approach to the computation of the joint distribution of distance and multiplicity (degeneration) of shortest paths in multiplex networks, and exploit its relation to congestion processes. The results allow to approximate semi-analytically the onset of congestion in multiplex networks as a function of the congestion of its layers.
Endemicity and prevalence of multipartite viruses under heterogeneous between-host transmission
Eugenio Valdano, Susanna Manrubia, Sergio Gómez and Alex Arenas
PLOS Computational Biology (2019) in press
Multipartite viruses replicate through a puzzling evolutionary strategy. Their genome is segmented into two or more parts, and encapsidated in separate particles that appear to propagate independently. Completing the replication cycle, however, requires the full genome, so that a persistent infection of a host requires the concurrent presence of several particles. This represents an apparent evolutionary drawback of multipartitism, while its advantages remain unclear. A transition from monopartite to multipartite viral forms has been described in vitro under conditions of high multiplicity of infection, suggesting that cooperation between defective mutants is a plausible evolutionary pathway towards multipartitism. However, it is unknown how the putative advantages that multipartitism might enjoy at the microscopic level affect its epidemiology, or if an explicit advantange is needed to explain its ecological persistence. In order to disentangle which mechanisms might contribute to the rise and fixation of multipartitism, we here investigate the interaction between viral spreading dynamics and host population structure. We set up a compartmental model of the spread of a virus in its different forms and explore its epidemiology using both analytical and numerical techniques. We uncover that the impact of host contact structure on spreading dynamics entails a rich phenomenology of ecological relationships that includes cooperation, competition, and commensality. Furthermore, we find out that multipartitism might rise to fixation even in the absence of explicit microscopic advantages. Multipartitism allows the virus to colonize environments that could not be invaded by the monopartite form, while homogeneous contacts between hosts facilitate its spread. We conjecture that there might have been an increase in the diversity and prevalence of multipartite viral forms concomitantly with the expansion of agricultural practices.
Identification of modules in molecular networks is at the core of many current analysis methods in biomedical research. However, how well different approaches identify disease-relevant modules in different types of networks remains poorly understood. We launched the "Disease Module Identification DREAM Challenge", an open competition to comprehensively assess module identification methods across diverse gene, protein and signaling networks. Predicted network modules were tested for association with complex traits and diseases using a unique collection of 180 genome-wide association studies (GWAS). While a number of approaches were successful in terms of discovering complementary trait-associated modules, consensus predictions derived from the challenge submissions performed best. We find that most of these modules correspond to core disease-relevant pathways, which often comprise therapeutic targets and correctly prioritize candidate disease genes. This community challenge establishes benchmarks, tools and guidelines for molecular network analysis to study human disease biology (https://synapse.org/modulechallenge).
Effective approach to epidemic containment using link equations in complex networks
Joan T. Matamalas, Alex Arenas and Sergio Gómez
Science Advances 4 (2018) eaau4212
(pdf + suppl) (doi) (AAAS open access)
Epidemic containment is a major concern when confronting large-scale infections in complex networks. Many studies have been devoted to analytically understand how to restructure the network to minimize the impact of major outbreaks of infections at large scale. In many cases, the strategies are based on isolating certain nodes, while less attention has been paid to interventions on the links. In epidemic spreading, links inform about the probability of carrying the contagion of the disease from infected to susceptible individuals. Note that these states depend on the full structure of the network, and its determination is not straightforward from the knowledge of nodes’ states. Here, we confront this challenge and propose a set of discrete-time governing equations that can be closed and analyzed, assessing the contribution of links to spreading processes in complex networks. Our approach allows a scheme for the containment of epidemics based on deactivating the most important links in transmitting the disease. The model is validated in synthetic and real networks, yielding an accurate determination of epidemic incidence and critical thresholds. Epidemic containment based on link deactivation promises to be an effective tool to maintain functionality of networks while controlling the spread of diseases, such as disease spread through air transportation networks.
The rapid growth of population in urban areas is jeopardizing the mobility and air quality worldwide. One of the most notable problems arising is that of traffic congestion which in turn affects air pollution. With the advent of technologies able to sense real-time data about cities, and its public distribution for analysis, we are in place to forecast scenarios valuable to ameliorate and control congestion. Here, we analyze a local congestion pricing scheme, hotspot pricing, that surcharges vehicles traversing congested junctions. The proposed tax is computed from the estimation of the evolution of congestion at local level, and the expected response of users to the tax (elasticity). Results on cities’ road networks, considering real-traffic data, show that the proposed hotspot pricing scheme would be more effective than current mechanisms to decongest urban areas, and paves the way towards sustainable congestion in urban areas.
Revealing cause-effect relations in comorbidities analysis using process mining and tensor network decomposition
Joan T. Matamalas, Alex Arenas, Antoni Martínez-Ballest\'e, Agustí Solanas, Carlos Alonso-Villaverde and Sergio Gómez
Proceedings of 2018 9th International Conference on Information, Intelligence, Systems and Applications (IISA), IEEE (2018) 329-333
(pdf) (doi) (IEEE)
The existence of certain comorbidities, the co-occurrence of different diseases in the same individual, is well-known in the medical community. However, finding temporal cause-effect relations between those diseases constitutes a big challenge. Clinical records can be used to extract the required information, but their analysis is elusive due to the vast and heterogeneous amount of data. We propose a new methodology for time-preserving tensor networks decomposition to be applied in the analysis of big data problems where the temporal dimension of the key factual fields must not be modified. This methodology will also allow the creation of a new process mining modeling which can capture the cause-effect relations as low-order tensors associated to the transitions of the mined processes, and whose structure takes the form of a multilayer complex network. All these theoretical and methodological advances will allow their application to real biomedical data to analyze comorbidities.
La vida urbana está caracterizada por una gran movilidad, y está fuertemente atada al uso de vehículos. Entre los problemas que se generan existe uno predominante: la congestión del tráfico en zonas urbanas. La gran cantidad de horas perdidas en atascos (entre 15 y 50 horas en ciudades europeas) tiene consecuencias económicas, medioambientales y de salud pública muy negativas. Una de las estrategias más controvertidas es la aplicación de tarifas a la congestión (p. ej. Londres o Milán). Este tipo de estrategias consiste en gravar económicamente el acceso dentro del área perimetral de la ciudad, durante ciertos periodos de tiempo, para equilibrar oferta (carreteras existentes) y demanda (cantidad de coches que quieren viajar). Sin embargo, este tipo de estrategias no son demasiado eficaces debido a la complejidad en las decisiones de los conductores y sus interacciones en las redes de carreteras. Nuestro enfoque consiste en aplicar ideas de la física de sistemas complejos, y en particular de la teoría de redes, para proponer mejores estrategias en este sentido.
The understanding and prediction of information diffusion processes on networks is a major challenge in network theory with many implications in social sciences. Many theoretical advances occurred due to stochastic spreading models. Nevertheless, these stochastic models overlooked the influence of rational decisions on the outcome of the process. For instance, different levels of trust in acquaintances do play a role in information spreading, and actors may change their spreading decisions during the information diffusion process accordingly. Here, we study an information-spreading model in which the decision to transmit or not is based on trust. We explore the interplay between the propagation of information and the trust dynamics happening on a two-layer multiplex network. Actors' trustable or untrustable states are defined as accumulated cooperation or defection behaviors, respectively, in a Prisoner's Dilemma set up, and they are controlled by a memory span. The propagation of information is abstracted as a threshold model on the information-spreading layer, where the threshold depends on the trustability of agents. The analysis of the model is performed using a tree approximation and validated on homogeneous and heterogeneous networks. The results show that the memory of previous actions has a significant effect on the spreading of information. For example, the less memory that is considered, the higher is the diffusion. Information is highly promoted by the emergence of trustable acquaintances. These results provide insight into the effect of plausible biases on spreading dynamics in a multilevel networked system.
Disease module identification by adjusting resolution in community detection algorithms
Sergio Gómez, Manlio De Domenico and Alex Arenas
Disease Module Identification DREAM Challenge (2016) Synapse ID: syn7352969
Second place in sub-challenge 1 (challenge)
Community detection methods for complex networks usually ignore the finding of the correct scale of resolution. This is crucial in this Disease Module Identification challenge, since communities must contain no more than 100 genes. Therefore, we have used the Multiresolution technique in (Arenas, Fernández and Gómez, 2008) to choose an appropriate scale for two different methods: modularity optimization in subchallenge 1, and a multiscale Multimap approach (the extension of Infomap to multilayer networks, De Domenico et al., 2015) in subchallenge 2.
Multiplex networks are representations of multilayer interconnected complex networks where the nodes are the same at every layer. They turn out to be good abstractions of the intricate connectivity of multimodal transportation networks, among other types of complex systems. One of the most important critical phenomena arising in such networks is the emergence of congestion in transportation flows. Here, we prove analytically that the structure of multiplex networks can induce congestion for flows that otherwise would be decongested if the individual layers were not interconnected. We provide explicit equations for the onset of congestion and approximations that allow us to compute this onset from individual descriptors of the individual layers. The observed cooperative phenomenon is reminiscent of Braess' paradox in which adding extra capacity to a network when the moving entities selfishly choose their route can in some cases reduce overall performance. Similarly, in the multiplex structure, the efficiency in transportation can unbalance the transportation loads resulting in unexpected congestion.
We present an analytical approach for bond percolation on multiplex networks and use it to determine the expected size of the giant connected component and the value of the critical bond occupation probability in these networks. We advocate the relevance of these tools to the modeling of multilayer robustness and contribute to the debate on whether any benefit is to be yielded from studying a full multiplex structure as opposed to its monoplex projection, especially in the seemingly irrelevant case of a bond occupation probability that does not depend on the layer. Although we find that in many cases the predictions of our theory for multiplex networks coincide with previously derived results for monoplex networks, we also uncover the remarkable result that for a certain class of multiplex networks, well described by our theory, new critical phenomena occur as multiple percolation phase transitions are present. We provide an instance of this phenomenon in a multiplex network constructed from London rail and European air transportation data sets.
A model to identify urban traffic congestion hotspots in complex networks
Albert Solé-Ribalta, Sergio Gómez and Alex Arenas
Royal Society Open Science 3 (2016) 160098
(pdf + suppl) (doi) (Royal Society open access)
Data (Dryad) (doi)
The rapid growth of population in urban areas is jeopardizing the mobility and air quality worldwide. One of the most notable problems arising is that of traffic congestion. With the advent of technologies able to sense real-time data about cities, and its public distribution for analysis, we are in place to forecast scenarios valuable for improvement and control. Here, we propose an idealized model, based on the critical phenomena arising in complex networks, that allows to analytically predict congestion hotspots in urban environments. Results on real cities’ road networks, considering, in some experiments, real traffic data, show that the proposed model is capable of identifying susceptible junctions that might become hotspots if mobility demand increases.
Detection of timescales in evolving complex systems
Richard K. Darst, Clara Granell, Alex Arenas, Sergio Gómez, Jari Saramäki and Santo Fortunato
Scientific Reports 6 (2016) 39713
(pdf + suppl) (doi) (Springer-Nature open access)
Most complex systems are intrinsically dynamic in nature. The evolution of a dynamic complex system is typically represented as a sequence of snapshots, where each snapshot describes the configuration of the system at a particular instant of time. This is often done by using constant intervals but a better approach would be to define dynamic intervals that match the evolution of the system’s configuration. To this end, we propose a method that aims at detecting evolutionary changes in the configuration of a complex system, and generates intervals accordingly. We show that evolutionary timescales can be identified by looking for peaks in the similarity between the sets of events on consecutive time intervals of data. Tests on simple toy models reveal that the technique is able to detect evolutionary timescales of time-varying data both when the evolution is smooth as well as when it changes sharply. This is further corroborated by analyses of several real datasets. Our method is scalable to extremely large datasets and is computationally efficient. This allows a quick, parameter-free detection of multiple timescales in the evolution of a complex system.
Random walk centrality in interconnected multilayer networks
Albert Solé-Ribalta, Manlio De Domenico, Sergio Gómez and Alex Arenas
Physica D: Nonlinear Phenomena 323-324 (2016) 73-79
(pdf) (doi) (Elsevier)
Real-world complex systems exhibit multiple levels of relationships. In many cases they require to be modeled as interconnected multilayer networks, characterizing interactions of several types simultaneously. It is of crucial importance in many fields, from economics to biology and from urban planning to social sciences, to identify the most (or the less) influential nodes in a network using centrality measures. However, defining the centrality of actors in interconnected complex networks is not trivial. In this paper, we rely on the tensorial formalism recently proposed to characterize and investigate this kind of complex topologies, and extend two well known random walk centrality measures, the random walk betweenness and closeness centrality, to interconnected multilayer networks. For each of the measures we provide analytical expressions that completely agree with numerically results.
Layer-layer competition in multiplex complex networks
Jesús Gómez-Gardeñes, Manlio De Domenico, Gerardo Gutiérrez, Alex Arenas and Sergio Gómez
Philosophical Transactions of the Royal Society A 373 (2015) 20150117
(pdf) (doi) (Royal Society open access)
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. This novel approach has unveiled that the multiplex nature of complex systems has strong influence in the emergence of collective states and their critical properties. 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 layer 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.
The study of complex networks that account for different types of interactions has become a subject of interest in the last few years, specially because its representational power in the description of users interactions in diverse online social platforms (Facebook, Twitter, Instagram, etc.). The mathematical description of these interacting networks has been coined under the name of multilayer networks, where each layer accounts for a type of interaction. It has been shown that diffusive processes on top of these networks present a phenomenology that cannot be explained by the naive superposition of single layer diffusive phenomena but require the whole structure of interconnected layers. Nevertheless, the description of diffusive phenomena on multilayer networks has obviated the fact that social networks have strong mesoscopic structure represented by different communities of individuals driven by common interests, or any other social aspect. In this work, we study the transfer of information in multilayer networks with community structure. The final goal is to understand and quantify, if the existence of well-defined community structure at the level of individual layers, together with the multilayer structure of the whole network, enhances or deteriorates the diffusion of packets of information.
Benchmark model to assess community structure in evolving networks
Clara Granell, Richard K. Darst, Alex Arenas, Santo Fortunato and Sergio Gómez
Physical Review E 92 (2015) 012805
(pdf + suppl) (doi) (APS)
Detecting the time evolution of the community structure of networks is crucial to identify major changes in the internal organization of many complex systems, which may undergo important endogenous or exogenous events. This analysis can be done in two ways: considering each snapshot as an independent community detection problem or taking into account the whole evolution of the network. In the first case, one can apply static methods on the temporal snapshots, which correspond to configurations of the system in short time windows, and match afterwards the communities across layers. Alternatively, one can develop dedicated dynamic procedures, so that multiple snapshots are simultaneously taken into account while detecting communities, which allows to keep memory of the flow. To check how well a method of any kind could capture the evolution of communities, suitable benchmarks are needed. Here we propose a model for generating simple dynamic benchmark graphs, based on stochastic block models. In them, the time evolution consists of a periodic oscillation of the system's structure between configurations with built-in community structure. We also propose the extension of quality comparison indices to the dynamic scenario. Additionally, we perform several tests on various algorithms which show, unsurprisingly, that dynamic techniques are more suitable than static ones to describe community evolution.
Structure of triadic relations in multiplex networks
Emanuele Cozzo, Mikko Kivelä, Manlio De Domenico, Albert Solé-Ribalta, Alex Arenas, Sergio Gómez, Mason A. Porter and Yamir Moreno
New Journal of Physics 17 (2015) 073029
(pdf) (doi) (IOP open access)
Recent advances in the study of networked systems have highlighted that our interconnected world is composed of networks that are coupled to each other through different 'layers' that each represent one of many possible subsystems or types of interactions. Nevertheless, it is traditional to aggregate multilayer networks into a single weighted network in order to take advantage of existing tools. This is admittedly convenient, but it is also extremely problematic, as important information can be lost as a result. It is therefore important to develop multilayer generalizations of network concepts. In this paper, we analyze triadic relations and generalize the idea of transitivity to multiplex networks. By focusing on triadic relations, which yield the simplest type of transitivity, we generalize the concept and computation of clustering coefficients to multiplex networks. We show how the layered structure of such networks introduces a new degree of freedom that has a fundamental effect on transitivity. We compute multiplex clustering coefficients for several real multiplex networks and illustrate why one must take great care when generalizing standard network concepts to multiplex networks. We also derive analytical expressions for our clustering coefficients for ensemble averages of networks in a family of random multiplex networks. Our analysis illustrates that social networks have a strong tendency to promote redundancy by closing triads at every layer and that they thereby have a different type of multiplex transitivity from transportation networks, which do not exhibit such a tendency. These insights are invisible if one only studies aggregated networks.
Ranking in interconnected multilayer networks reveals versatile nodes
Manlio De Domenico, Albert Solé-Ribalta, Elisa Omodei, Sergio Gómez and Alex Arenas
Nature Communications 6 (2015) 6868
(pdf + suppl) (doi) (Springer-Nature)
The determination of the most central agents in complex networks is important because they are responsible for a faster propagation of information, epidemics, failures and congestion, among others. A challenging problem is to identify them in networked systems characterized by different types of interactions, forming interconnected multilayer networks. Here we describe a mathematical framework that allows us to calculate centrality in such networks and rank nodes accordingly, finding the ones that play the most central roles in the cohesion of the whole structure, bridging together different types of relations. These nodes are the most versatile in the multilayer network. We investigate empirical interconnected multilayer networks and show that the approaches based on aggregating—or neglecting—the multilayer structure lead to a wrong identification of the most versatile nodes, overestimating the importance of more marginal agents and demonstrating the power of versatility in predicting their role in diffusive and congestion processes.
Strategical incoherence regulates cooperation in social dilemmas on multiplex networks
Joan T. Matamalas, Julia Poncela-Casasnovas, Sergio Gómez and Alex Arenas
Scientific Reports 5 (2015) 9519
(pdf + suppl) (doi) (Springer-Nature open access)
Cooperation is a very common, yet not fully-understood phenomenon in natural and human systems. The introduction of a network within the population is known to affect the outcome of cooperative dynamics, allowing for the survival of cooperation in adverse scenarios. Recently, the introduction of multiplex networks has yet again modified the expectations for the outcome of the Prisoner's Dilemma game, compared to the monoplex case. However, much remains unstudied regarding other social dilemmas on multiplex, as well as the unexplored microscopic underpinnings of it. In this paper, we systematically study the evolution of cooperation in all four games in the T-S plane on multiplex. More importantly, we find some remarkable and previously unknown features in the microscopic organization of the strategies, that are responsible for the important differences between cooperative dynamics in monoplex and multiplex. Specifically, we find that in the stationary state, there are individuals that play the same strategy in all layers (coherent), and others that don't (incoherent). This second group of players is responsible for the surprising fact of a non full-cooperation in the Harmony Game on multiplex, never observed before, as well as a higher-than-expected cooperation rates in some regions of the other three social dilemmas.
Quantifying sudden changes in dynamical systems using symbolic networks
Cristina Masoller, Yanhua Hong, Sarah Ayad, Francois Gustave, Stephane Barland, Antonio J. Pons, Sergio Gómez and Alex Arenas
New Journal of Physics 17 (2015) 023068
(pdf) (doi) (IOP open access)
We characterise the evolution of a dynamical system by combining two well-known complex systems' tools, namely, symbolic ordinal analysis and networks. From the ordinal representation of a time-series we construct a network in which every node weights represents the probability of an ordinal patterns (OP) to appear in the symbolic sequence and each edges weight represents the probability of transitions between two consecutive OPs. Several network-based diagnostics are then proposed to characterize the dynamics of different systems: logistic, tent and circle maps. We show that these diagnostics are able to capture changes produced in the dynamics as a control parameter is varied. We also apply our new measures to empirical data from semiconductor lasers and show that they are able to anticipate the polarization switchings, thus providing early warning signals of abrupt transitions.
Emergence of assortative mixing between clusters of cultured neurons
Sara Teller, Clara Granell, Manlio De Domenico, Jordi Soriano, Sergio Gómez and Alex Arenas
PLOS Computational Biology 10(9) (2014) e1003796
(pdf + suppl) (doi) (PLOS open access)
The analysis of the activity of neuronal cultures is considered to be a good proxy of the functional connectivity of in vivo neuronal tissues. Thus, the functional complex network inferred from activity patterns is a promising way to unravel the interplay between structure and functionality of neuronal systems. Here, we monitor the spontaneous self-sustained dynamics in neuronal cultures formed by interconnected aggregates of neurons (clusters). Dynamics is characterized by the fast activation of groups of clusters in sequences termed bursts. The analysis of the time delays between clusters' activations within the bursts allows the reconstruction of the directed functional connectivity of the network. We propose a method to statistically infer this connectivity and analyze the resulting properties of the associated complex networks. Surprisingly enough, in contrast to what has been reported for many biological networks, the clustered neuronal cultures present assortative mixing connectivity values, as well as a rich-club core, meaning that there is a preference for clusters to link to other clusters that share similar functional connectivity, which shapes a 'connectivity backbone' in the network. These results point out that the grouping of neurons and the assortative connectivity between clusters are intrinsic survival mechanisms of the culture.
Navigability of interconnected networks under random failures
Manlio De Domenico, Albert Solé-Ribalta, Sergio Gómez and Alex Arenas
Proceedings of the National Academy of Sciences USA 111 (2014) 8351-8356
(pdf + suppl) (doi) (PNAS open access)
Assessing the navigability of interconnected networks (transporting information, people, or goods) under eventual random failures is of utmost importance to design and protect critical infrastructures. Random walks are a good proxy to determine this navigability, specifically the coverage time of random walks, which is a measure of the dynamical functionality of the network. Here, we introduce the theoretical tools required to describe random walks in interconnected networks accounting for structure and dynamics inherent to real systems. We develop an analytical approach for the covering time of random walks in interconnected networks and compare it with extensive Monte Carlo simulations. Generally speaking, interconnected networks are more resilient to random failures than their individual layers per se, and we are able to quantify this effect. As an application --which we illustrate by considering the public transport of London-- we show how the efficiency in exploring the multiplex critically depends on layers' topology, interconnection strengths, and walk strategy. Our findings are corroborated by data-driven simulations, where the empirical distribution of check-ins and checks-out is considered and passengers travel along fastest paths in a network affected by real disruptions. These findings are fundamental for further development of searching and navigability strategies in real interconnected systems.
Epidemiclike spreading processes on top of multilayered interconnected complex networks reveal a rich phase diagram of intertwined competition effects. A recent study by the authors [C. Granell et al., Phys. Rev. Lett. 111, 128701 (2013).] presented an analysis of the interrelation between two processes accounting for the spreading of an epidemic, and the spreading of information awareness to prevent infection, on top of multiplex networks. The results in the case in which awareness implies total immunization to the disease revealed the existence of a metacritical point at which the critical onset of the epidemics starts, depending on completion of the awareness process. Here we present a full analysis of these critical properties in the more general scenario where the awareness spreading does not imply total immunization, and where infection does not imply immediate awareness of it. We find the critical relation between the two competing processes for a wide spectrum of parameters representing the interaction between them. We also analyze the consequences of a massive broadcast of awareness (mass media) on the final outcome of the epidemic incidence. Importantly enough, the mass media make the metacritical point disappear. The results reveal that the main finding, i.e., existence of a metacritical point, is rooted in the competition principle and holds for a large set of scenarios.
Centrality rankings in multiplex networks
Albert Solé-Ribalta, Manlio De Domenico, Sergio Gómez and Alex Arenas
Proceedings of the 2014 ACM conference on Web science, published by ACM, New York (2014) 149-155
(pdf) (doi) (ACM)
The vertiginous increase of e-platforms for social communication has boosted the ways people use to interact each other. Micro-blogging and decentralized posts are used indistinctly for social interaction, usually by the same individuals acting simultaneously in the different platforms. Multiplex networks are the natural abstraction representation of such "layered" relationships and others, like co-authorship. Here, we re-define the betweenness centrality measure to account for the inherent structure of multiplex networks and propose an algorithm to compute it in an effcient way. To show the necessity and the advantage of the proposed definition, we analyze the obtained centralities for two real multiplex networks, a social multiplex of two layers obtained from Twitter and Instagram and a co-authorship network of four layers obtained from arXiv. Results show that the proposed definition provides more accurate results than the current approach of evaluating the classical betweenness centrality on the aggregated network, in particular for the middle ranked nodes. We also analyze the computational cost of the presented algorithm.
¿Qué es una epidemia?. Cuando se habla de epidemias, generalmente la idea que nos viene a la cabeza es la propagación de enfermedades, pensamos en la existencia de un virus o bacteria que se difunde por una población más o menos extensa. Ejemplos de ello son la gripe estacional, que cada invierno es noticia en los telediarios; la gripe A, que llegó a tener un alcance a nivel global, o, a más pequena escala, la propagación de los piojos en una clase de preescolares.
Lo que quizás no es tan obvio es que existen otros sucesos que no tienen nada que ver con las enfermedades y que en cambio también pueden ser descritos como procesos epidémicos.
Complex systems are usually represented as an intricate set of relations between their components forming a complex graph or network. The understanding of their functioning and emergent properties are strongly related to their structural properties. The finding of structural patterns is of utmost importance to reduce the problem of understanding the structure-function relationships. Here we propose the analysis of similarity measures between nodes using hierarchical clustering methods. The discrete nature of the networks usually leads to a small set of different similarity values, making standard hierarchical clustering algorithms ambiguous. We propose the use of multidendrograms, an algorithm that computes agglomerative hierarchical clusterings implementing a variable-group technique that solves the non-uniqueness problem found in the standard pair-group algorithm. This problem arises when there are more than two clusters separated by the same maximum similarity (or minimum distance) during the agglomerative process. Forcing binary trees in this case means breaking ties in some way, thus giving rise to different output clusterings depending on the criterion used. Multidendrograms solves this problem by grouping more than two clusters at the same time when ties occur.
Mathematical formulation of multilayer networks
Manlio De Domenico, Albert Solé-Ribalta, Emanuele Cozzo, Mikko Kivelä, Yamir Moreno, Mason A. Porter, Sergio Gómez and Alex Arenas
Physical Review X 3 (2013) 041022
(pdf) (doi) (APS open access)
A network representation is useful for describing the structure of a large variety of complex systems. However, most real and engineered systems have multiple subsystems and layers of connectivity, and the data produced by such systems are very rich. Achieving a deep understanding of such systems necessitates generalizing “traditional” network theory, and the newfound deluge of data now makes it possible to test increasingly general frameworks for the study of networks. In particular, although adjacency matrices are useful to describe traditional single-layer networks, such a representation is insufficient for the analysis and description of multiplex and time-dependent networks. One must therefore develop a more general mathematical framework to cope with the challenges posed by multilayer complex systems. In this paper, we introduce a tensorial framework to study multilayer networks, and we discuss the generalization of several important network descriptors and dynamical processes --including degree centrality, clustering coefficients, eigenvector centrality, modularity, von Neumann entropy, and diffusion-- for this framework. We examine the impact of different choices in constructing these generalizations, and we illustrate how to obtain known results for the special cases of single-layer and multiplex networks. Our tensorial approach will be helpful for tackling pressing problems in multilayer complex systems, such as inferring who is influencing whom (and by which media) in multichannel social networks and developing routing techniques for multimodal transportation systems.
Centrality in interconnected multilayer networks
Manlio De Domenico, Albert Solé-Ribalta, Elisa Omodei, Sergio Gómez and Alex Arenas
Part of Ranking in interconnected multilayer networks reveals versatile nodes appeared in Nature Communications 6 (2015) 6868
(pdf + suppl) (doi) (Springer-Nature) (arXiv)
Real-world complex systems exhibit multiple levels of relationships. In many cases, they require to be modeled by interconnected multilayer networks, characterizing interactions on several levels simultaneously. It is of crucial importance in many fields, from economics to biology, from urban planning to social sciences, to identify the most (or the less) influent nodes in a network. However, defining the centrality of actors in an interconnected structure is not trivial.
In this paper, we capitalize on the tensorial formalism, recently proposed to characterize and investigate this kind of complex topologies, to show how several centrality measures -- well-known in the case of standard ("monoplex") networks -- can be extended naturally to the realm of interconnected multiplexes. We consider diagnostics widely used in different fields, e.g., computer science, biology, communication and social sciences, to cite only some of them. We show, both theoretically and numerically, that using the weighted monoplex obtained by aggregating the multilayer network leads, in general, to relevant differences in ranking the nodes by their importance.
We present the analysis of the interrelation between two processes accounting for the spreading of an epidemics, and the information awareness to prevent its infection, on top of multiplex networks. This scenario is representative of an epidemic process spreading on a network of persistent real contacts, and a cyclic information awareness process diffusing in the network of virtual social contacts between the same individuals. The topology corresponds to a multiplex network where two diffusive processes are interacting affecting each other. The analysis using a Microscopic Markov Chain Approach (MMCA) reveals the phase diagram of the incidence of the epidemics and allows to capture the evolution of the epidemic threshold depending on the topological structure of the multiplex and the interrelation with the awareness process. Interestingly, the critical point for the onset of the epidemics has a critical value (meta-critical point) defined by the awareness dynamics and the topology of the virtual network, from which the onset increases and the epidemics incidence decreases.
Spectral properties of the Laplacian of multiplex networks
Albert Solé-Ribalta, Manlio De Domenico, Nikos E. Kouvaris, Albert Díaz-Guilera, Sergio Gómez and Alex Arenas
Physical Review E 88 (2013) 032807
(pdf + suppl) (doi) (APS)
One of the more challenging tasks in the understanding of dynamical properties of models on top of complex networks is to capture the precise role of multiplex topologies. In a recent paper, Gómez et al. [Phys. Rev. Lett. 101, 028701 (2013)] proposed a framework for the study of diffusion processes in such networks. Here, we extend the previous framework to deal with general configurations in several layers of networks, and analyze the behavior of the spectrum of the Laplacian of the full multiplex. We derive an interesting decoupling of the problem that allow us to unravel the role played by the interconnections of the multiplex in the dynamical processes on top of them. Capitalizing on this decoupling we perform an asymptotic analysis that allow us to derive analytical expressions for the full spectrum of eigenvalues. This spectrum is used to gain insight into physical phenomena on top of multiplex, specifically, diffusion processes and synchronizability.
Random walks on multiplex networks
Manlio De Domenico, Albert Solé-Ribalta, Sergio Gómez and Alex Arenas
Supplementary Information of Navigability of interconnected networks under random failures appeared in PNAS 111 (2014) 8351-8356
(pdf + suppl) (doi) (PNAS open access) (arXiv)
Multiplex networks are receiving increasing interests because they allow to model relationships between networked agents on several layers simultaneously. In this letter, we extend well-known random walks to multiplexes and we introduce a new type of walk that can exist only in multiplexes. We derive exact expressions for vertex occupation time and the coverage. Finally, we show how the effciency in exploring the multiplex critically depends on the underlying topology of layers, the weight of their inter-connections and the strategy adopted to walk.
Diffusion dynamics on multiplex networks
Sergio Gómez, Albert Díaz-Guilera, Jesús Gómez-Gardeñes, Conrad J. Pérez-Vicente, Yamir Moreno and Alex Arenas
Physical Review Letters 110 (2013) 028701
(pdf + suppl) (doi) (APS)
We study the time scales associated with diffusion processes that take place on multiplex networks, i.e., on a set of networks linked through interconnected layers. To this end, we propose the construction of a supra-Laplacian matrix, which consists of a dimensional lifting of the Laplacian matrix of each layer of the multiplex network. We use perturbative analysis to reveal analytically the structure of eigenvectors and eigenvalues of the complete network in terms of the spectral properties of the individual layers. The spectrum of the supra-Laplacian allows us to understand the physics of diffusionlike processes on top of multiplex networks.
On the routability of the Internet
Pau Erola, Sergio Gómez and Alex Arenas
Dynamics On and Of Complex Networks, Volume 2, A. Mukherjee, M. Choudhury, F. Peruani, N. Ganguly and B. Mitra (eds.), Modeling and Simulation in Science, Engineering and Technology (2013) 41-54
(pdf) (doi) (Springer)
The third chapter delves into the detail of presenting methodologies based on complex network theory to construct navigable maps of the scale-free Internet. This chapter is motivated by the studies which have concluded that in the presence of topology dynamics, a better scaling on Internet-like topologies is fundamentally impossible: while routing tables can be greatly reduced, the amount of messages per topology change cannot grow slower than linearly.
Local-based semantic navigation on a networked representation of information
José A. Capitán, Javier Borge-Holthoefer, Sergio Gómez, Juan Martínez-Romo, Lourdes Araujo, José A. Cuesta and Alex Arenas
PLOS ONE 7(8) (2012) e43694
(pdf) (doi) (PLOS open access)
The size and complexity of actual networked systems hinders the access to a global knowledge of their structure. This fact pushes the problem of navigation to suboptimal solutions, one of them being the extraction of a coherent map of the topology on which navigation takes place. In this paper, we present a Markov chain based algorithm to tag networked terms according only to their topological features. The resulting tagging is used to compute similarity between terms, providing a map of the networked information. This map supports local-based navigation techniques driven by similarity. We compare the efficiency of the resulting paths according to their length compared to that of the shortest path. Additionally we claim that the path steps towards the destination are semantically coherent. To illustrate the algorithm performance we provide some results from the Simple English Wikipedia, which amounts to several thousand of pages. The simplest greedy strategy yields over an 80% of average success rate. Furthermore, the resulting content-coherent paths most often have a cost between one- and threefold compared to shortest-path lengths.
Explosive first-order transition to synchrony in networked chaotic oscillators
I. Leyva, R. Sevilla-Escoboza, J. M. Buldú, I. Sendiña-Nadal, J. Gómez-Gardeñes, A. Arenas, Y. Moreno, S. Gómez, R. Jaimes-Reátegui and S. Boccaletti
Physical Review Letters 108 (2012) 168702
(pdf) (doi) (APS)
Critical phenomena in complex networks, and the emergence of dynamical abrupt transitions in the macroscopic state of the system are currently a subject of the outmost interest. We report evidence of an explosive phase synchronization in networks of chaotic units. Namely, by means of both extensive simulations of networks made up of chaotic units, and validation with an experiment of electronic circuits in a star configuration, we demonstrate the existence of a first-order transition towards synchronization of the phases of the networked units. Our findings constitute the first prove of this kind of synchronization in practice, thus opening the path to its use in real-world applications.
Modeling epidemic spreading in complex networks: Concurrency and traffic
Sandro Meloni, Alex Arenas, Sergio Gómez, Javier Borge-Holthoefer and Yamir Moreno
Handbook of Optimization in Complex Networks, My T. Thai and Panos M. Pardalos (eds.), Springer Optimization and Its Applications 57 (2012) 435-462
(pdf) (doi) (Springer)
The study of complex networks sheds light on the relation between the structure and function of complex systems. One remarkable result is the absence of an epidemic threshold in infinite-size scale-free networks, which implies that any infection will perpetually propagate regardless of the spreading rate. However, real-world networks are finite and experience indicates that infections do have a finite lifetime. In this chapter, we will provide with two new approaches to cope with the problem of concurrency and traffic in the spread of epidemics. We show that the epidemic incidence is shaped by contact flow or traffic conditions. Contrary to the classical assumption that infections are transmitted as a diffusive process from nodes to all neighbors, we instead consider the scenario in which epidemic pathways are defined and driven by flows. Extensive numerical simulations and theoretical predictions show that whether a threshold exists or not depends directly on contact flow conditions. Two extreme cases are identified. In the case of low traffic, an epidemic threshold shows up, while for very intense flow, no epidemic threshold appears. In this way, the classical mean-field theory for epidemic spreading in scale free networks is recovered as a particular case of the proposed approach. Our results explain why some infections persist with low prevalence in scale-free networks, and provide a novel conceptual framework to understand dynamical processes on complex networks.
Trade is a fundamental pillar of economy and a form of social organization. Its empirical characterization at the worldwide scale is represented by the World Trade Web (WTW), the network built upon the trade relationships between the different countries. Several scientific studies have focused on the structural characterization of this network, as well as its dynamical properties, since we have registry of the structure of the network at different times in history. In this paper we study an abstract scenario for the development of global crises on top of the structure of connections of the WTW. Assuming a cyclic dynamics of national economies and the interaction of different countries according to the import-export balances, we are able to investigate, using a simple model of pulse-coupled oscillators, the synchronization phenomenon of crises at the worldwide scale. We focus on the level of synchronization measured by an order parameter at two different scales, one for the global system and another one for the mesoscales defined through the topology. We use the WTW network structure to simulate a network of Integrate-and-Fire oscillators for six different snapshots between years 1950 and 2000. The results reinforce the idea that globalization accelerates the global synchronization process, and the analysis at a mesoscopic level shows that this synchronization is different before and after globalization periods: after globalization, the effect of communities is almost inexistent.
Hierarchical multiresolution method to overcome the resolution limit in complex networks
Clara Granell, Sergio Gómez and Alex Arenas
International Journal of Bifurcation and Chaos 22 (2012) 1250171
(pdf) (doi) (World Scientific)
The analysis of the modular structure of networks is a major challenge in complex networks theory. The validity of the modular structure obtained is essential to confront the problem of the topology-functionality relationship. Recently, several authors have worked on the limit of resolution that different community detection algorithms have, making impossible the detection of natural modules when very different topological scales coexist in the network. Existing multiresolution methods are not the panacea for solving the problem in extreme situations, and also fail. Here, we present a new hierarchical multiresolution scheme that works even when the network decomposition is very close to the resolution limit. The idea is to split the multiresolution method for optimal subgraphs of the network, focusing the analysis on each part independently. We also propose a new algorithm to speed up the computational cost of screening the mesoscale looking for the resolution parameter that best splits every subgraph. The hierarchical algorithm is able to solve a difficult benchmark proposed by [Lancichinetti & Fortunato, 2011], encouraging the further analysis of hierarchical methods based on the modularity quality function.
Reliability of optimal linear projection of growing scale-free networks
Pau Erola, Javier Borge-Holthoefer, Sergio Gómez and Alex Arenas
International Journal of Bifurcation and Chaos 22 (2012) 1250159
(pdf) (doi) (World Scientific)
Singular Value Decomposition (SVD) is a technique based on linear projection theory, which has been frequently used for data analysis. It constitutes an optimal (in the sense of least squares) decomposition of a matrix in the most relevant directions of the data variance. Usually, this information is used to reduce the dimensionality of the data set in a few principal projection directions, this is called Truncated Singular Value Decomposition (TSVD). In situations where the data is continuously changing the projection might become obsolete. Since the change rate of data can be fast, it is an interesting question whether the TSVD projection of the initial data is reliable. In the case of complex networks, this scenario is particularly important when considering network growth. Here we study the reliability of the TSVD projection of growing scale free networks, monitoring its evolution at global and local scales.
Unsupervised clustering analysis: a multiscale complex networks approach
Clara Granell, Sergio Gómez and Alex Arenas
International Journal of Bifurcation and Chaos 22 (2012) 1230023
(pdf) (doi) (World Scientific)
Unsupervised clustering, also known as natural clustering, stands for the classification of data according to their similarities. Here we study this problem from the perspective of complex networks. Mapping the description of data similarities to graphs, we propose to extend two multiresolution modularity based algorithms to the finding of modules (clusters) in general data sets producing a multiscales' solution. We show the performance of these reported algorithms to the classification of a standard benchmark of data clustering and compare their performance.
MultiDendrograms is a Java-written application that computes agglomerative hierarchical clusterings of data. Starting from a distances (or weights) matrix, MultiDendrograms is able to calculate its dendrograms using the most common agglomerative hierarchical clustering methods. The application implements a variable-group algorithm that solves the non-uniqueness problem found in the standard pair-group algorithm. This problem arises when two or more minimum distances between different clusters are equal during the agglomerative process, because then different output clusterings are possible depending on the criterion used to break ties between distances. MultiDendrograms solves this problem implementing a variable-group algorithm that groups more than two clusters at the same time when ties occur.
An Internet local routing approach based on network structural connectivity
Pau Erola, Sergio Gómez and Alex Arenas
Proceedings of the GLOBECOM Workshops (GC Wkshps) 2011 IEEE, IEEE Conference Publications (2011) 95-99
(pdf) (doi) (IEEE)
Internet is one of the largest synthetic complex system ever built. It consists in a collection of more than 30,000 networks each one known as an Autonomous System. In the last few years, Internet is experiencing an explosive growth that is compromising its navigation scalability due to its dependence on the Border Gateway Protocol (BGP). The BGP routing protocol requires to maintain an updated partial view of the network topology, involving a huge amount of data exchange and significant convergence times. The scale-free topology of Internet makes complex network theory the natural framework to analyze its problems and propose solutions. Here, we present a local alternative to BGP based on complex networks. Our approach uses the linear projection of the modular structure of the network to construct a navigable map of the Internet. This map guarantees a high reliability over time on the actual evolving network, in the sense that projection changes are negligible. The simulation results show that we are in high percentage close to optimal paths.
Modeling human mobility responses to the large-scale spreading of infectious diseases
Sandro Meloni, Nicola Perra, Alex Arenas, Sergio Gómez, Yamir Moreno and Alessandro Vespignani
Scientific Reports 1 (2011) 62
(pdf + suppl) (doi) (Springer-Nature open access)
Current modeling of infectious diseases allows for the study of realistic scenarios that include population heterogeneity, social structures, and mobility processes down to the individual level. The advances in the realism of epidemic description call for the explicit modeling of individual behavioral responses to the presence of disease within modeling frameworks. Here we formulate and analyze a metapopulation model that incorporates several scenarios of self-initiated behavioral changes into the mobility patterns of individuals. We find that prevalence-based travel limitations do not alter the epidemic invasion threshold. Strikingly, we observe in both synthetic and data-driven numerical simulations that when travelers decide to avoid locations with high levels of prevalence, this self-initiated behavioral change may enhance disease spreading. Our results point out that the real-time availability of information on the disease and the ensuing behavioral changes in the population may produce a negative impact on disease containment and mitigation.
Nonperturbative heterogeneous mean-field approach to epidemic spreading in complex networks
Sergio Gómez, Jesús Gómez-Gardeñes, Yamir Moreno and Alex Arenas
Physical Review E 84 (2011) 036105
(pdf) (doi) (APS)
Since roughly a decade ago, network science has focused among others on the problem of how the spreading of diseases depends on structural patterns. Here, we contribute to further advance our understanding of epidemic spreading processes by proposing a nonperturbative formulation of the heterogeneous mean-field approach that has been commonly used in the physics literature to deal with this kind of spreading phenomena. The nonperturbative equations we propose have no assumption about the proximity of the system to the epidemic threshold, nor any linear approximation of the dynamics. In particular, we first develop a probabilistic description at the node level of the epidemic propagation for the so-called susceptible-infected-susceptible family of models, and after we derive the corresponding heterogeneous mean-field approach. We propose to use the full extension of the approach instead of pruning the expansion to first order, which leads to a nonperturbative formulation that can be solved by fixed-point iteration, and used with reliability far away from the epidemic threshold to assess the prevalence of the epidemics. Our results are in close agreement with Monte Carlo simulations, thus enhancing the predictive power of the classical heterogeneous mean-field approach, while providing a more effective framework in terms of computational time.
Explosive collective phenomena have attracted much attention since the discovery of an explosive percolation transition. In this Letter, we demonstrate how an explosive transition shows up in the synchronization of scale-free networks by incorporating a microscopic correlation between the structural and the dynamical properties of the system. The characteristics of the explosive transition are analytically studied in a star graph reproducing the results obtained in synthetic networks. Our findings represent the first abrupt synchronization transition in complex networks and provide a deeper understanding of the microscopic roots of explosive critical phenomena.
Trade synchronization in the World Trade Web
Pau Erola, Albert Díaz-Guilera, Sergio Gómez and Alex Arenas
International Journal of Complex Systems in Science 1 (2011) 202--208
(pdf) (IJCSS open access)
In March 2008, the bankruptcy of Lehman Brothers marked for many the beginning of the global crisis. In an increasingly globalized world, the financial crisis spread relentlessly. Recent theories of financial fragility link globalization with economic cycles, i.e. when local crises coincide with bad credit regulation and failures in international monetary arrangements. The globalization process in recent years has been accelerated due to to the increase of international trade. Here we analyze how economic cycles can spread worldwide over the global trade network (WTW). We use the WTW network structure to simulate a network of Integrate-and-Fire oscillators for two different years, 1980 and 2000. The results reinforce the idea that globalization accelerates the global synchronization process.
We investigate the adaptation and performance of modularity-based algorithms, designed in the scope of complex networks, to analyze the mesoscopic structure of correlation matrices. Using a multiresolution analysis, we are able to describe the structure of the data in terms of clusters at different topological levels. We demonstrate the applicability of our findings in two different scenarios: to analyze the neural connectivity of the nematode Caenorhabditis elegans and to automatically classify a typical benchmark of unsupervised clustering, the Iris dataset, with considerable success.
Probabilistic framework for epidemic spreading in complex networks
Sergio Gómez, Alex Arenas, Javier Borge-Holthoefer, Sandro Meloni and Yamir Moreno
International Journal of Complex Systems in Science 1 (2011) 47-54
(pdf) (IJCSS open access)
The discovery of the important role played by the complex connectivity structure between individuals has lead to an increasing interest in the analysis of epidemic spreading in complex networks. Here we propose a discrete-time formulation of the problem of contact-based epidemic spreading, within the context of susceptible-infected-susceptible epidemic models. The proposed equations establish the relations between the probabilities of infection of individual nodes. They can be easily solved by iteration, showing an almost perfect agreement with Monte Carlo experiments throughout the whole phase diagram. This framework also allows the determination of the epidemic threshold and, unlike heterogeneous mean-field approaches, it is valid for any finite-size and weighted network.
The famous Milgram's small-world experiment revealed that there is something special in the structure of natural and man-made complex systems: without a global view of the network, a message can be routed efficiently between any pair of nodes. Our initial hypothesis is that the community structure, that provides meaningful insights on the structure and function of complex networks, is an important actor in these routing properties. To exploit the modular structure of networks we need to analyze the contribution of each node to the modules. Unfortunately, this analysis involves a huge amount of data. To reduce this problem we propose to build a map using the linear projection theory as a basis of a guided routing. First we project the matrix of contributions of each node of a given network to its modules in a plane using the Truncated Singular Value Decomposition. This two-dimensional plane reveals the structure of modules and their boundaries and we will use it as the map for navigating through the network. Considering that each node only has knowledge about its neighbors, we define a simple greedy routing algorithm to guide the communication among them. We apply our framework to the Internet Autonomous Systems (ASs) network achieving, in high percentage, close to optimal paths.
One of the most important problems in science is that of inferring knowledge from data. The most challenging issue is the unsupervised classification of patterns (observations, measurements, or feature vectors) into groups (clusters) according to their similarity. The quantification of similarity is usually performed in terms of distances or correlations between pairs. The resulting similarity matrix is a weighted complete graph. In this work we investigate the adaptation and performance of modularity-based algorithms to analyze the structure of the similarity matrix. Modularity is a quality function that allows comparing different partitions of a given graph, rewarding those partitions that are more internally cohesive than externally. In our problem cohesiveness is the representation of the similarity between members of the same group. The modularity criterion, however, has a drawback, the impossibility to find clusters below a certain size, known as the resolution limit, which depends on the topology of the graph. This is overcome by applying multi-resolution analysis. Using the multi-resolution approach for modularity-based algorithms we automatically classify typical benchmarks of unsupervised clustering with considerable success. These results open the door to the applicability of community detection algorithms in complex networks to the classification of real data sets.
The study of the sub-structure of complex networks is of major importance to relate topology and functionality. Many efforts have been devoted to the analysis of the modular structure of networks using the quality function known as modularity. However, generally speaking, the relation between topological modules and functional groups is still unknown, and depends on the semantic of the links. Sometimes, we know in advance that many connections are transitive and, as a consequence, triangles have a specific meaning. Here we propose the study of the modular structure of networks considering triangles as the building blocks of modules. The method generalizes the standard modularity and uses spectral optimization to find its maximum. We compare the partitions obtained with those resulting from the optimization of the standard modularity in several real networks. The results show that the information reported by the analysis of modules of triangles complements the information of the classical modularity analysis.
Improved prognostic classification of breast cancer defined by antagonistic activation patterns of immune response pathway modules
Andrew E. Teschendorff, Sergio Gómez, Alex Arenas, Dorraya El-Ashry, Marcus Schmidt, Mathias Gehrmann and Carlos Caldas
BMC Cancer 10 (2010) 604
(pdf) (doi) (BMC open access, Highly accessed)
Elucidating the activation pattern of molecular pathways across a given tumour type is a key challenge necessary for understanding the heterogeneity in clinical response and for developing novel more effective therapies. Gene expression signatures of molecular pathway activation derived from perturbation experiments in model systems as well as structural models of molecular interactions (''model signatures'') constitute an important resource for estimating corresponding activation levels in tumours. However, relatively few strategies for estimating pathway activity from such model signatures exist and only few studies have used activation patterns of pathways to refine molecular classifications of cancer.
Here we propose a novel network-based method for estimating pathway activation in tumours from model signatures. We find that although the pathway networks inferred from cancer expression data are highly consistent with the prior information contained in the model signatures, that they also exhibit a highly modular structure and that estimation of pathway activity is dependent on this modular structure. We apply our methodology to a panel of 438 estrogen receptor negative (ER-) and 785 estrogen receptor positive (ER+) breast cancers to infer activation patterns of important cancer related molecular pathways.
We show that in ER negative basal and HER2+ breast cancer, gene expression modules reflecting T-cell helper-1 (Th1) and T-cell helper-2 (Th2) mediated immune responses play antagonistic roles as major risk factors for distant metastasis. Using Boolean interaction Cox-regression models to identify non-linear pathway combinations associated with clinical outcome, we show that simultaneous high activation of Th1 and low activation of a TGF-beta pathway module defines a subtype of particularly good prognosis and that this classification provides a better prognostic model than those based on the individual pathways. In ER+ breast cancer, we find that simultaneous high MYC and RAS activity confers significantly worse prognosis than either high MYC or high RAS activity alone. We further validate these novel prognostic classifications in independent sets of 173 ER- and 567 ER+ breast cancers.
We have proposed a novel method for pathway activity estimation in tumours and have shown that pathway modules antagonize or synergize to delineate novel prognostic subtypes. Specifically, our results suggest that simultaneous modulation of T-helper differentiation and TGF-beta pathways may improve clinical outcome of hormone insensitive breast cancers over treatments that target only one of these pathways.
Optimal map of the modular structure of complex networks
Alex Arenas, Javier Borge-Holthoefer, Sergio Gómez and Gorka Zamora-López
New Journal of Physics 12 (2010) 053009
(pdf) (doi) (IOP open access)
Modular structure is pervasive in many complex networks of interactions observed in natural, social and technological sciences. Its study sheds light on the relation between the structure and function of complex systems. Generally speaking, modules are islands of highly connected nodes separated by a relatively small number of links. Every module can have contributions of links from any node in the network. The challenge is to disentangle these contributions to understand how the modular structure is built. The main problem is that the analysis of a certain partition into modules involves, in principle, as many data as number of modules times number of nodes. To confront this challenge, here we first define the contribution matrix, the mathematical object containing all the information about the partition of interest, and after, we use a Truncated Singular Value Decomposition to extract the best representation of this matrix in a plane. The analysis of this projection allow us to scrutinize the architecture of the modular structure, revealing the structure of individual modules and their interrelations.
Discrete-time Markov chain approach to contact-based disease spreading in complex networks
Sergio Gómez, Alex Arenas, Javier Borge-Holthoefer, Sandro Meloni and Yamir Moreno
Europhysics Letters 89 (2010) 38009
(pdf) (doi) (IOP)
Many epidemic processes in networks spread by stochastic contacts among their connected vertices. There are two limiting cases widely analyzed in the physics literature, the so-called contact process (CP) where the contagion is expanded at a certain rate from an infected vertex to one neighbor at a time, and the reactive process (RP) in which an infected individual effectively contacts all its neighbors to expand the epidemics. However, a more realistic scenario is obtained from the interpolation between these two cases, considering a certain number of stochastic contacts per unit time. Here we propose a discrete-time formulation of the problem of contact-based epidemic spreading. We resolve a family of models, parameterized by the number of stochastic contact trials per unit time, that range from the CP to the RP. In contrast to the common heterogeneous mean-field approach, we focus on the probability of infection of individual nodes. Using this formulation, we can construct the whole phase diagram of the different infection models and determine their critical properties.
Communities in complex networks: Identification at different levels
Alex Arenas, Jordi Duch, Sergio Gómez, Leon Danon and Albert Díaz-Guilera
Complex Networks, G. Caldarelli (ed.)
Encyclopedia of Life Support Systems (2010) 197-219
We present here and compare the most common approaches to community structure identification in terms of sensitivity and computational cost. The work is intended as an introduction as well as a proposal for a standard benchmark test of community detection methods.
We present a reformulation of modularity that allows the analysis of the community structure in networks of correlated data. The modularity preserves the probabilistic semantics of the original definition even when the network is directed, weighted, signed, and has self-loops. This is the most general condition one can find in the study of any network, in particular those defined from correlated data. We apply our results to a real network of correlated data between stores in the city of Lyon (France).
An optimization approach to the structure of the neuronal layout of C. elegans
Alex Arenas, Alberto Fernández and Sergio Gómez
Handbook on Biological Networks, S. Boccaletti, V. Latora and Y. Moreno (eds.), World Scientific Lecture Notes in Complex Systems 10 (2009) 243-256
(pdf) (World Scientific)
In this chapter we will review a recent optimization approach to the wiring connectivity in C. elegans, discussing the possible outcomes of the optimization process, its dependence on the optimization parameters, and its validation with the actual neuronal layout data. We will follow the main procedure described in the work by Chen et al. [2-4]. The results show that the current approach to optimization of neuronal layouts is still not conclusive, and then the "wiring economy principle" remains unproved.
The worldwide computing grid is essential to the LHC experiments in analysing the data collected by the detectors. Within LHCb, the computing model aims to simulate data at Tier-2 grid sites as well as non-grid resources. The reconstruction, stripping and analysis of the produced LHCb data will pimarily place at the Tier-1 centres. The computing data challenge DC06 started in May 2006 with the primary aims being to exercise the LHCb computing mod and to produce events which will be used for analyses in the forthcoming LHCb physics book. This paper gives an overview of the LHCb computing model and addresses the challenges and experiences during DC06. The management of the production of Monte Carlo data on the LCG was done using the DIRAC worklad management system which in turn uses the WLCG infrastructure and middleware. We shall report on the amount of data simulated during DC06, including the performance of the sites used. The paper will also summarise the experience gained during DC06, in particular he distribution of data to the Ter-1 sits and the access to this data.
The DIRAC system was developed in order to provide a complete solution for using the distributed computing resources of the LHCb experiment at CERN for data production and analysis. It allows a concurrent use of over 10K CPUs and 10M file replicas distributed over many tens of sites. The sites can be part of a Computing Grid such as WLCG or standalone computing clusters all integrated in a single management structure. DIRAC is a generic system with the LHCb specific functionality incorporated through a number of plug-in modules. It can be easily adapted to the needs of other communities. Special attention is paid to the resilience of the DIRAC components to allow an efficient use of non-reliable resources. The DIRAC production management components provide a framework for building highly automated data production systems including data distribution and data driven workload scheduling. In this paper we give an overview of the DIRAC system architecture and design choices. We show how different components are put together to compose an integrated data processing system including all the aspects of the LHCb experiment - from the MC production and raw data reconstruction to the final user analysis.
A complex network approach to the determination of functional groups in the neural system of C. elegans
Alex Arenas, Alberto Fernández and Sergio Gómez
Bio-Inspired Computing and Communication, P. Liò, E. Yoneki, J. Crowcroft, D.C. Verma (eds.), BIOWIRE 2007
Lecture Notes in Computer Science 5151 (2008) 9-18
(pdf) (doi) (Springer)
The structure of real complex networks is often modular, with sets of nodes more connected between them than to the rest of the network. These communities are usually reflecting a topology-functionality interplay, whose discovery is basic for the understanding of the operation of the networks. Thus, much attention has been driven to the determination of the modular structure of complex networks. Recently it has been shown that this modular organization appears at several scales of description, which may be found by a synchronization process on top of these networks. Here we make use of it for a tentative uncovering of functional groups in the neural system of the nematode C. elegans.
In agglomerative hierarchical clustering, pair-group methods suffer from a problem of non-uniqueness when two or more distances between different clusters coincide during the amalgamation process. The traditional approach for solving this drawback has been to take any arbitrary criterion in order to break ties between distances, which results in different hierarchical classifications depending on the criterion followed. In this article we propose a variable-group algorithm that consists in grouping more than two clusters at the same time when ties occur. We give a tree representation for the results of the algorithm, which we call a multidendrogram, as well as a generalization of the Lance and Williams' formula which enables the implementation of the algorithm in a recursive way.
Modular structure is ubiquitous in real-world complex networks, and its detection is important because it gives insights into the structure-functionality relationship. The standard approach is based on the optimization of a quality function, modularity, which is a relative quality measure for the partition of a network into modules. Recently, some authors (Fortunato and Barthélemy 2007 Proc. Natl Acad. Sci. USA 104 36 and Kumpula et al 2007 Eur. Phys. J. B 56 41) have pointed out that the optimization of modularity has a fundamental drawback: the existence of a resolution limit beyond which no modular structure can be detected even though these modules might have their own entity. The reason is that several topological descriptions of the network coexist at different scales, which is, in general, a fingerprint of complex systems. Here, we propose a method that allows for multiple resolution screening of the modular structure. The method has been validated using synthetic networks, discovering the predefined structures at all scales. Its application to two real social networks allows us to find the exact splits reported in the literature, as well as the substructure beyond the actual split.
Community definitions usually focus on edges, inside and between the communities. However, the high density of edges within a community determines correlations between nodes going beyond nearest neighbors, and which are indicated by the presence of motifs. We show how motifs can be used to define general classes of nodes, including communities, by extending the mathematical expression of Newman-Girvan modularity. We construct then a general framework and apply it to some synthetic and real networks.
The ubiquity of modular structure in real-world complex networks is the focus of attention in many trials to understand the interplay between network topology and functionality. The best approaches to the identification of modular structure are based on the optimization of a quality function known as modularity. However this optimization is a hard task provided that the computational complexity of the problem is in the non-deterministic polynomial-time hard (NP-hard) class. Here we propose an exact method for reducing the size of weighted (directed and undirected) complex networks while maintaining their modularity. This size reduction allows use of heuristic algorithms that optimize modularity for a better exploration of the modularity landscape. We compare the modularity obtained in several real complex-networks by using the extremal optimization algorithm, before and after the size reduction, showing the improvement obtained. We speculate that the proposed analytical size reduction could be extended to an exact coarse graining of the network in the scope of real-space renormalization.
In this paper we apply a heuristic method based on artificial neural networks (NN) in order to trace out the efficient frontier associated to the portfolio selection problem. We consider a generalization of the standard Markowitz mean-variance model which includes cardinality and bounding constraints. These constraints ensure the investment in a given number of different assets and limit the amount of capital to be invested in each asset. We present some experimental results obtained with the NN heuristic and we compare them to those obtained with three previous heuristic methods.
Feature selection and outliers detection with genetic algorithms and neural networks
A. Solanas, E. Romero, S. Gómez, J. M. Sopena, R. Alquézar and J. Domingo-Ferrer
Artificial Intelligence Research and Development, B. López, J. Meléndez, P. Radeva, J. Vitrià (eds),
IOS Press (Frontiers in Artificial Intelligence and Applications), Amsterdam 131 (2005) 41-48
(pdf) (IOS Press)
This paper presents a new feature selection method and an outliers detection algorithm. The presented method is based on using a genetic algorithm combined with a problem-specific-designed neural network. The dimensional reduction and the outliers detection makes the resulting dataset more suitable for training neural networks. A comparative analysis between different kind of proposed criteria to select the features is reported. A number of experimental results have been carried out to demonstrate the usefulness of the presented technique.
HI content, 3D structure and dynamics of the Virgo cluster region
T. Sanchis, E. Salvador-Solé, J.M. Solanes and S. Gómez
Highlights of Spanish Astrophysics III, J. Gallego, J. Zamorano and N. Cardiel (eds), Kluwer Academic Publishers, Dordrecht (2003) 163-166
The HI content and Tully-Fisher distances of 161 spiral galaxies in the region of Virgo cluster are used to gain insight into the complicated structure of this galaxy system and to constrain the role played by interactions with the hot intracluster medium on the exhaustion of the interstellar HI. We confirm previous findings that the spiral distribution is substantially more elongated toward the line-of-sight than in the plane of the sky. The filamentary structure is also reproduced in the HI deficiency distribution, which shows a central enhancement suggestive of bearing the Virgo cluster proper, extending from around 16 to 22 Mpc in radial distance, but also important enhancements in the cluster front and in a group of background galaxies. The fact that some of the spirals on the Virgo outskirts exhibit gas deficiencies as strong as those of the inner galaxies has led us to explore, by means of a dynamical model, the possibility that some peripheral objects are not newcomers. We conclude that it is not unfeasible that some of the galaxies far from the cluster, including the HI-deficient background group, have already plunged in the past into the Virgo cluster.
HI content and dynamical history of the Virgo cluster
T. Sanchis, J.M. Solanes, E. Salvador-Solé, A. Manrique and S. Gómez
Revista Mexicana de Astronomía y Astrofísica (Serie de Conferencias) 17 (2003) 193-193
(pdf) (RevMexAA(SC) open access)
We conduct an investigation into the nature of and conditions within the 3D structure of the Virgo region, by adding to the analysis the HI content of its spiral population.
LHCb Calorimeters, Technical Design Report.
Scintillator Pad Detector front end electronics design
Sebastià Bota, Ángel Diéguez, Lluis Garrido, David Gascón, Sergio Gómez, Ramon Miquel, Daniel Peralta, Mar Roselló and Xavier Vilasís
The front electronics designed to read out the LHCb Scintillator Pad Detector (SPD) is described in this note. After defining the detector features and reporting the relevant characteristics of the signal, the architecture of the read out system is presented. Analog signal processing is done on an ASIC which has also a digital part for control and calibration. Finally, synchronization and front end controls questions are commented.
We address the problem of training and prediction with Neural Networks in those situations where the data to predict possess a natural hierarchical structure. We perform backpropagation with a specialized objective function that takes into account this structure and show that it betters the results of the non-hierarchical learning.
Non-linear dimensionality reduction with input distances preservation
Lluis Garrido, Sergio Gómez and Jaume Roca
Proceedings of the 9th International Conference on Artificial Neural Networks (ICANN'99), published by the Institution of Electrical Engineers 470 (1999) 922-927
(pdf) (doi) (IET) (IEEE)
A new error term for dimensionality reduction, which clearly improves the quality of NLPCA neural networks, is introduced, and some illustrative examples are given. The method tries to maintain the original data structure by preserving the distances between data points.
Improved multidimensional scaling analysis using neural networks with distance-error backpropagation
Lluis Garrido, Sergio Gómez and Jaume Roca
Neural Computation 11 (1999) 595-600
(pdf) (doi) (MIT Press)
We show that neural networks, with a suitable error function for backpropagation, can be successfully used for metric multidimensional scaling (MDS) (i.e., dimensional reduction while trying to preserve the original distances between patterns) and are in fact able to outdo the standard algebraic approach to MDS, known as classical scaling.
We show that Neural Networks, trained with a suitable error function for backpropagation, can be used for Metric Multidimensional Scaling (i.e. dimensional reduction while trying to preserve the original distances between patterns) and are able to outdo other standard methods mainly because of the ability to model non-linear maps.
Predicción de índices de futuros financieros mediante redes neuronales
Joan Bosch, Lluis Garrido and Sergio Gómez
Swaps & Productos Derivados 27 (1997) 19-21
En este artículo estudiamos la aplicación de Redes Neuronales Artificiales a la predicción, basada únicamente en datos históricos, del futuro financiero español Bono 10, teniendo en cuenta las comisiones y la dispersión de los precios.
Optimal projection to estimate the proportions of the different subsamples in a given mixtute sample
Lluis Garrido, Sergio Gómez, Aurelio Juste and Vicens Gaitán
Computer Physics Communications 104 (1997) 37-45
(pdf) (doi) (Elsevier)
Given a n-dimensional sample composed of a mixture of m subsamples with different probability density functions (p.d.f.), it is possible to build a (m-1)-dimensional distribution that carries all the information about the subsample proportions in the mixture sample. This projection can be estimated without an analytical knowlegde of the p.d.f.'s of the different subsamples with the aid, for instance, of neural networks. This way, if m-1 < n it is possible to estimate the proportions of the mixture sample in a lower (m-1)-dimensional space without losing sensitivity.
A regularization term to avoid the saturation of the sigmoids in multilayer neural networks
Lluis Garrido, Sergio Gómez, Vicens Gaitán and Miquel Serra-Ricart
International Journal of Neural Systems 7 (1996) 257-262
(pdf) (doi) (World Scientific)
In this paper we propose a new method to prevent the saturation of any set of hidden units of a multilayer neural network. This method is implemented by adding a regularization term to the standard quadratic error function, which is based on a repulsive action between pairs of patterns.
The minimization quadratic error criterion which gives rise to the backpropagation algorithm is studied using functional analysis techniques. With them, we recover easily the well-known statistical result which states that the searched global minimum is a function which assigns, to each input pattern, the expected value of its corresponding output patterns. Its application to classification tasks shows that only certain output class representations can be used to obtain the optimal Bayesian decision rule. Finally, our method permits the study of other error criterions, finding out, for instance, that absolute value errors lead to medians instead of mean values.
A new perceptron learning rule which works with multilayer neural networks made of multistate units is obtained, and the corresponding convergence theorem is proved. The definition of perceptron of maximal stability is enlarged in order to include these new multistate perceptrons, and a proof of existence and uniqueness of such optimal solutions is outlined.
The possibility of achieving optimal associative memory by means of multilayer neural networks is explored. Three original different solutions which guarantee maximal basins of attraction and storage capacity are found, and their main characteristics are outlined.
Methods for encoding in multilayer feed-forward neural networks
Emili Elizalde, Sergio Gómez and August Romeo
Artificial Neural Networks, A. Prieto (ed.), IWANN'91
Lecture Notes in Computer Science 540 (1991) 136-143
(pdf) (doi) (Springer)
Neural network techniques for encoding-decoding processes have been developed. The net we have devised can work like a memory retrieval system in the sense of Hopfield, Feinstein and Palmer. Its behaviour for 2^R (R in N) input units has some special interesting features. In particular, the accessibilities for each initial symbol may be explicitly computed. Although thermal noise may muddle the code, we show how it can statistically rid the result of unwanted sequences while maintaining the network accuracy within a given bound.
Neural networks capable of encoding sets of patterns are analysed. Solutions are found by theoretical treatment instead of by supervised learning. The behaviour for 2^R (R in N) input units is studied and its characteristic features are discussed. The accessibilities for non-spurious patterns are calculated by analytic methods. Although thermal noise may induce wrong encoding, we show how it can rid the output of spurious sequences. Further, we compute error bounds at finite temperature.
Multilayer neural networks: learning models and applications
Ph.D. Thesis (1994)
Several theoretical and practical aspects of multilayer neural networks are studied. The main results are the following:
- Three different multilayer solutions to the problem of associative memory have been constructed, all of them sharing unlimited storage capacity, perfect recall and the removal of spurious minima and unstable states. Their retrieval power is optimal in the sense that the network's answer is selected by the maximal overlap criterion. The original contribution of these solutions has been the realization of such designs without introducing types of units different from those currently used in most neural network architectures.
- Neural network techniques for encoding-decoding processes have been developed. We have proved that it is not possible to encode arbitrary patterns with the minimal architecture, thus other non-optimal set-ups have been studied. In the simplest case of unary patterns, the accessibilities of the outputs have been calculated in two different situations: with and without thermal noise.
- A new perceptron learning rule which can be used with perceptrons made of multi-state units has been derived, and its corresponding convergence theorem has been proved. The definition of a perceptron of maximal stability has been enlarged in order to include these new multi-state perceptrons, and a proof of the existence and uniqueness of such optimal solutions has been outlined.
- The importance of the first hidden layer when multilayer neural networks with discrete activation functions are considered has been explained. As a consequence, several enhancements to the tiling algorithm have been proposed so as to increase the generalization ability of the trained nets.
- The unconstrained global minimum of the squared error criterion used in the back-propagation algorithm has been found using functional derivatives. The role played by the representation of the output patterns has been studied, showing that only certain output representations allow the achievement of the optimal Bayesian decision in classification tasks. Moreover, other error criterions have been analyzed.
- A method for the reconstruction of images from noisy data has been introduced and applied to two aerial images, showing that the results have a very competitive quality.
- Several methods based on self-supervised back-propagation have been devised for the compression of images. The new strategies admit more general applications, specifically to the diminishing of the loss of information produced by the saturation of the sigmoids.
- The performances of multi-layer feed-forward and recurrent networks have been compared when applied to time series prediction, showing that the second ones give, if proper activation functions are chosen, better predictions.