Coarse-graining of Complex Systems  (CCS) Session 1

Abstract: To better understand the flows of ideas or information through social and biological systems, researchers develop maps that reveal important patterns in network flows. In practice, network flow models have implied memoryless first-order Markov chains, but recently researchers have introduced higher-order Markov chain models with memory to capture patterns in multi-step pathways. Higher-order models are particularly important for effectively revealing actual, overlapping community structure, but higher-order Markov chain models suffer from the curse of dimensionality: their vast parameter spaces require exponentially increasing data to avoid overfitting and therefore make mapping inefficient already for moderate-sized systems. To overcome this problem, we introduce an efficient cross-validated mapping approach based on network flows modeled by sparse Markov chains. To illustrate our approach, we present a map of citation flows in science with research fields that overlap in multidisciplinary journals. Compared with currently used categories in science of science studies, the research fields form better units of analysis because the map more effectively captures how ideas flow through science. Close

Abstract: A challenging problem in the study of complex systems is that of resolving, without prior information, the emergent, mesoscopic organization determined by groups of units whose dynamical activity is more strongly correlated internally than with the rest of the system. The existing techniques to filter correlations are not explicitly oriented towards identifying such modules and can suffer from an unavoidable information loss. A promising alternative is that of employing community detection techniques developed in network theory. Unfortunately, this approach has focused predominantly on replacing network data with correlation matrices, a procedure that we show to be intrinsically biased because of its inconsistency with the null hypotheses underlying the existing algorithms. Here, we introduce, via a consistent redefinition of null models based on random matrix theory, the appropriate correlation-based counterparts of the most popular community detection techniques. Our methods can filter out both unit-specific noise and system-wide dependencies, and the resulting communities are internally correlated and mutually anticorrelated. We also implement multiresolution and multifrequency approaches revealing hierarchically nested subcommunities with ?hard? cores and ?soft? peripheries. We apply our techniques to financial and brain time series and identify robust patterns providing nontrivial information about these systems. Ref: Mel MacMahon and Diego Garlaschelli, Phys. Rev. X 5, 021006 (2015). Close

Abstract: The identification and control of ties, which are transmitting information in complex networks can provide effective ways to hinder and postpone outbreaks of spreading phenomena. In this work we introduce a new method by using diffusion processes to define transmission centrality for links, which quantifies their importance in disseminating information in the network structure. We demonstrate that this measure can precisely identify weak ties in the network structure and furthermore estimates the betweenness centrality of each link in a computationally efficient way. By testing various link removal strategies in three human communication networks we show that the combined measure of transmission centrality and link overlap provides the best way to identify links keeping the global structure connected. We also explored their role in control of spreading processes through SIR model simulations. This method allows us to select the optimal but minimal set of links to gain maximum control on spreading processes. Close

Abstract: We understand multiplex networks as a non-linear superposition of complex networks, where components, being them social actors, genes, devices, or physical locations, interacts through a variety of different relationships and communication channels, which we conceptualize as different layers of the multiplex network. Because of the structure of a multiplex network, it is natural to try to aggregate the interaction pattern of each layer in a single network somehow. An operation that we call dimensionality reduction, whereas the result of such operation leads to what we call an aggregate network. Several candidates for the aggregate network have been proposed in the literature. We claim that the natural definition of an aggregate network is given by the notion of quotient network. In addiction, in the quotient network framework, we are able to introduce in a symmetric way another reduced network, the network of layers, that encodes the connectivity pattern between layers. We give the relations between the Laplacian and the adjacency spectra of the original multiplex network and that of its coarse-grained representations, and we show that a number of the structural and dynamical properties of the original multiplex are inherited by the coarse-grained representations. Finally, we show the relation between some walk-based structural metrics (e.g. the clustering coefficient) calculated on the original multiplex and the same metric calculated on the aggregate network. Close

Abstract: Patterns are widespread in nature and appear in large plethora of different conformations.From chemistry to biology,passing through physics,ecology,social systems or engineered ones, just to name few.Beautiful spatially extended motifs are found which spontaneously emerge from an ensemble made of interacting microscopic actors. The proto-typical approach to patterns formation in reaction-diffusion processes dates back to Turing?s seminal paper on morphogenesis[1].Under specific conditions,diffusion drives an instability by perturbing a homogeneous stable fixed point, via an activator-inhibitor mechanism.As the perturbation grows,nonlinear reactions balance the diffusion terms,yielding the asymptotic, spatially inhomogeneous, steady state. Reaction diffusion models are often defined on a regular lattice, either continuous or discrete.In many cases of interest, it is however more natural to schematize the system as a complex network.Building on the pioneering work of Othmer and Scriven[2], Nakao and Mikhailov developed[3] the theory of Turing patterns on random static undirected network, highlighting the peculiarities that stem from the embedding graph structure.The dispersion relation, from which the instability conditions ultimately descend, is related to the spectrum of the discrete Laplacian associated to the embedding network.Laplacian eigenvalues determine hence the spatial characteristics of the emerging patterns. Evidence suggests that in many applications networks evolve in time,new nodes can enter or other can leave the system,new links can emerge or disappear[4-6].Linear processes such as diffusion have been studied on temporal networks[7-8].The goal of this paper is to propose a first study of a generic non-linear process running on top of a complex temporal network and determine the conditions for the onset of Turing patterns.We will provide examples where patterns emerge in the temporal network while they cannot develop in each time-snapshot network, namely for any fixed time. [1]A.M.Turing,PTR.Soc.London,Ser.B 237,37(1952) [2]H.G.Othmer,L.E.J.Scriven,Theor.Biol. 32,507(1971);43,83(1974) [3]H.Nakao,A.S.Mikhailov, NatPhys 6,544(2010) [4]V. Kostakos,PhysicaA 388,1007(2009) [5]P. Holme,J.Saram?ki,PhysRep 519,97(2012) [6]P.Holme,EPJB 88, 234(2015) [7]J.-C.Delvenne,R.Lambiotte,L.E.C.Rocha,NatComm 6,7366(2015) [8]R. Lambiotte,L.Tabourier,J.-C.Delvenne,EPJB 86,320(2013) Close

Abstract: Usual coarse-graining techniques require a full-knowledge of the network and its dynamics. This assumption is increasingly irrealistic as we consider larger and larger networks, due to both incomplete data and lack computational resources. We propose a theory of local coarse graining where a set of nodes is reduced to a single node without knowledge of the rest of the network, and with limited impact on the resulting dynamics. This allows us to identify interesting structures in a network, including, but not limited to, local communities. The methodology is illustrated on social, biological and power networks. Joint work with YW Yu, S Yaliraki, M Barahona Close