## tabs

In the spirit of past CCEGN workshops (CCEGN-2018, CCEGN-2017, CCEGN-2016), the workshop "Critical and Collective Effects in Graphs and Networks - 2019" (CCEGN-2019) continues to explore the topics at the interface between network science, statistical physics, and random graphs. The CCEGN-2019 will bring together top researchers working in these areas. The workshop aims at facilitating the transfer of ideas, insights and interdisciplinary approaches to tackle new and exciting problems in random graphs and real networks. Topics include:

**Spreading phenomena and other dynamical process on networks, Griffiths phases and spectral methods****Metric structure of random graphs, and spatially embedded random graphs****Random graphs with quenched disorder, microcanonical and canonical ensembles of random graphs, phase transitions, belief propagation and related questions****Statistical methods in interdisciplinary applications: social and ecological networks, genomic networks, neuroscience**

There are two traditional features of the CCEGN workshops that the past attendees mostly enjoyed: (i) the relaxed schedule of talks to allocate a plenty of time for scientific discussions and exchange of ideas, and (ii) the high quality of the presentations -- all talks are invited and are given by top experts in their fields, and each talk is 1 hour including questions. Discussion panels on various topics may be formed by the organizers if there is a substantial interest among the attendees.

The list of speakers:

**Ginestra Bianconi**(Queen Mary University, London, UK)**Zdzislaw Burda**(AGH University of Science and Technology, Kraków, Poland)**Sergey Dorogovtsev**(Aveiro University, Portugal, and A.F. Ioffe Institute, St. Petersburg, Russia)**Alex Fornito**(Monash University, Melbourne, Australia)**Laetitia Gauvin**(ISI Foundation, Torino, Italy)**James Gleeson**(University of Limerick, Ireland)**Joaquín Goñi**(Purdue University, West Lafayette, IN, USA)**Clara Granell**(University of Barcelona, Spain)**Roger Guimerà**(Universitat Rovira i Virgili, Tarragona, Spain)**Byungnam Kahng**(Seoul National University, Seoul, Korea)**Pavel Krapivsky**(University of Boston, Boston, USA)**Vito Latora**(Queen Mary University, London, UK)**Sergei Maslov**(University of Illinois at Urbana-Champaign, USA)**Adilson Motter**(Northwestern University, Evanston, IL, USA)**Fragkiskos Papadopoulos**(Cyprus University of Technology, Limassol, Cyprus)**Tiago Peixoto**(University of Bath, UK, and ISI Foundation, Turin, Italy)**M. Ángeles Serrano****Zoltan Toroczkai**(University of Notre Dame, Notre Dame, IN, USA)

The overview yet in-depth format of talks provides an excellent opportunity for researchers at early stages of their carriers to learn about recent cutting-edge developments in network science and adjacent areas, so that PhD students, postdocs and young researchers working in these areas are encouraged to attend the workshop. The workshop attendees are encouraged to submit posters on their research as the workshop will feature poster sessions with lightning presentations. A limited number of travel grants will be available on a competitive basis. To submit a poster and/or to apply for a travel grant, please contact the workshop organizing committee at **ccegn2019-oc@googlegroups.com**.

The workshop will take place during 6 - 10 of May, 2019 at Les Houches Physics School located in the Chamonix valley of French Alps.

**Schedule of the CCEGN 2019 Workshop**

Ecole de Physique des Houches (May, 6-10, 2019)

**Schedule of each day:**

7-45 – 8-45: Breakfast

**9-30 – 10-30: Talk #1**

10-30 – 11-00: Break

**11-00 – 12-00: Talk #2**

12-30 – 14-30: Lunch

**14-30 – 15-30: Talk #3**

15-30 – 16-00: Break

**16-00 – 17-00: Talk #4**

17-00 – 17-30: Break

**17-30 – 18-30: Talk #5**

19-30: Dinner

**We invite participants with posters to post their posters on the first day before the lunch. **The poster discussions can take any time during the workshop.

In the section **LINKS & DOWNLOADS** at the bottom of this page please find:

- The PDF version of the program
- The list of all participants
- The booklet of posters (titles and abstracts)
- The practical information about the facilities during the workshop

### Geometric renormalization unravels self-similarity of the multiscale human connectome

The renormalization group allows a systematic investigation of physical systems at different resolutions. However, the small-world property of complex networks complicates renormalization by introducing correlations between coexisting length scales. A geometric description of networks offers now a powerful framework where distances in a hidden metric space can be defined and used to formulate a geometric renormalization (GR) transformation. The application of GR to real networks unfolds them into a multilayer shell that shows geometric scaling and statistical self-similarity, and enables multiscale navigation and the production of high-fidelity downscaled network replicas. Interestingly, self-similarity of the GR multiscale shell also holds for human brain connectomes, in agreement with the self-similarity observed when the resolution length is progressively decreased by hierarchical coarse-graining of anatomical regions. Our results suggest that the same principles organize connectivity between brain regions at different length scales. The implications are varied and can affect fundamental debates, like whether the brain is working near a critical point, and lead to applications including advanced tools to simplify the digital reconstruction and simulation of the brain.

### Brain network hubs: maps, molecules, and models

The complex topology of nervous systems is thought to result from competitive selection pressures to minimize wiring costs and promote complex, adaptive function. Indeed, while most connections in the brain are short-range, a smaller subset of metabolically costly projections extend over long distances to connect disparate anatomical areas. These long-range connections support integrated brain function and are concentrated between the most highly connected network elements; the hubs of the brain. Hub connectivity thus plays a vital role in determining how a given nervous system negotiates the trade-off between cost and value, and natural selection may favour connections that provide high functional benefit for low cost. Consistent with this view, I will present evidence that hub connectivity of the brain is under strong genetic control. Specifically, I will show that the strength of connectivity between hubs in the human brain is more heritable than connectivity between other nodes, and that the genetic variants driving individual variability in hub connectivity overlap with those implicated in mental illness and intelligence. Hub connections also display a distinct gene expression signature, characterized by elevated transcriptional coupling of genes regulating energy metabolism. This signature is highly conserved, being evident in the human, mouse, and C. elegans nervous systems. Finally, I will discuss some progress and challenges associated with developing generative models that evaluate the role of different cost-value trade-offs in driving complex brain topology.

### What’s love got to do with it? Stable marriage and networks in microbial ecosystems.

Microbial communities routinely have several alternative stable states observed for the same environmental parameters. A possibility of sudden and irreversible transitions between these states (regime shifts) complicates the external manipulation of these systems. Can we predict which specific perturbations may induce such regime shifts and which would have only a transient effect? Here I will describe several new conceptual models that exhibit these emergent phenomena. Two of our models [2,3] were inspired by a decades-old economics work: the stable marriage or stable allocation problem, developed by Gale and Shapley in the 1960s and awarded the Nobel prize in economics in 2012. Using only the ranked tables of competitive abilities of microbes and their nutrient preferences, we determine all stable states of the ecosystem. Each stable state is characterized by a range of environmental parameters (nutrient influxes) in which it is feasible, that is to say, the abundances of all species are non-negative. Finally, we identify the specific environmental perturbations shifting the system from one stable state to another, and analyze a complex interconnected network of transitions between these states.

[1] Goyal A, Maslov S. Diversity, stability, and reproducibility in stochastically assembled microbial ecosystems. Phys. Rev. Lett., 120, 158102. https://doi.org/10.1103/PhysRevLett.120.158102

[2] Goyal A, Dubinkina V, Maslov S (2018) Microbial community structure predicted by the stable marriage problem. ISME Journal 12: 2823–2834. https://doi.org/10.1038/s41396-018-0222-x

[3] Dubinkina V, Fridman Y, Pandey PP, Maslov S (2018) Alternative stable states in a model of microbial community limited by multiple essential nutrients. BioRxiv 439547 [Preprint]. October 11, 2018. Available from: https://doi.org/10.1101/439547

### Microscopic Markov Chain model for epidemics on networks: from multiplex networks to bipartite metapopulations

The modeling of epidemics is one of the most crucial topics in the present day, given the globalized and accelerated travel patterns of individuals among different regions in the world. In the last years, we have witnessed an increased awareness of the risks of epidemics, ranging from seasonal influenza, to vector-borne diseases like Dengue or Chikungunya.

To address this, we need spreading models that are able to account for the particularities of each type of epidemic spreading setup, while still being generalistic enough to lead to robust, meaningful insights.

Along the many models available for modeling epidemics, there is one method that aims at calculating the individual (microscopic) probabilities of nodes for any given network. This model, commonly referred to as the Microscopic Markov Chain Approach (MMCA), has been shown to be very useful when applied to spreading processes on single layered networks. It has been shown that it provides accurate results when compared to MonteCarlo simulations, displaying a better agreement than other mean-field approaches while still being analytically treatable. The simplicity and accuracy of this method makes it suitable to extensions that account for more realistic scenarios. In this talk I will present several extensions of this model, ranging from modeling the interplay between awareness and epidemic spreading on a multiplex networks, to modeling epidemics in localized environments with specific recurrent mobility patterns.

### Network structure and dynamics: when and how multiplex really matters?

After almost ten years of research on characterising the properties of real-world networks with many layers, describing mathematically the structure of multiplex networks, and modelling different types of dynamical processes occurring over them, it is now time to draw the first conclusions and try to answer a fundamental question: does multiplex really matter? Focusing here both on the structure and on dynamics of multiplex networks, we discuss some cases where multiplexity gives rise to the emergence of novel behaviours, otherwise unobserved in single-layer networks.

### Using graphs to build a Bayesian machine scientist

Since the scientific revolution, interpretable closed-form mathematical models have been instrumental for advancing our understanding of the world. Think, for example, of Newton’s law of gravitation, and how it has enabled us to predict astronomical phenomena with great accuracy and to gain deep insights about seemingly unrelated physical phenomena. With the data revolution, we may now be in a position to uncover new mathematical models for many systems, from physics and chemistry to the social sciences. However, to deal with increasing amounts of data, we need approaches that are able to extract these models automatically, without supervision, and with guarantees of asymptotically finding the correct model. In this talk I will review standard machine learning approaches and discuss their limitations in terms of getting interpretable models. Then, I will present a Bayesian "machine scientist" that deals rigorously with model plausibilities and also explores systematically the space of models, using the analogy between Bayesian inference, information theory, and statistical mechanics. The machine scientist is able to obtain closed-form mathematical models from data, and to make out-of-sample predictions that are more accurate than those of standard machine learning approaches.

### Network reconstruction and community detection from dynamics

The observed functional behavior of a wide variety large-scale systems is often the result of a network of pairwise interactions. However, in many cases these interactions are hidden from us, either because they are impossible to be measured directly, or because their measurement can be done only at significant experimental cost. In such situations, we are required to infer the network of interactions from the observed functional behavior.

In this talk, we present a scalable nonparametric Bayesian method to perform network reconstruction from observed functional behavior, that at the same time infers the communities present in the network. We show that the joint reconstruction with community detection has a synergistic effect, where the edge correlations used to inform the existence of communities are inherently also used to improve the accuracy of the reconstruction, which in turn can better inform the uncovering of communities. We illustrate the use of our method with observations arising from epidemic models and the Ising model, both on synthetic and empirical networks, as well as on data containing only functional information.

### Converse Symmetry Breaking: The Emergent Role of Heterogeneity in Network Dynamics

Symmetry breaking--the phenomenon in which the symmetry of a system is not inherited by its stable states--underlies pattern formation, superconductivity, and numerous other effects. In this talk, I will report on the recently established possibility of converse symmetry breaking, an emergent network phenomenon in which the stable states are symmetric only when the system itself is not. In particular, I will present an experimental demonstration of this phenomenon as well as concrete applications to network optimization and control. The presentation will also discuss how converse symmetry breaking challenges the fundamental and widely held assumption that identical agents are necessarily more likely to exhibit similar behavior. I will show that it can, in fact, give rise to beneficial effects of heterogeneity in numerous complex systems in which interacting entities are required to exhibit coordinated behavior. Through this presentation, I hope to convey that our research in network science is now not only benefiting from statistical and nonlinear physics, but also fostering foundational discoveries in these areas.

### Branching processes as models of cascade dynamics on networks

Network models may be applied to describe many complex systems, and in the era of online social networks the study of dynamics on networks is an important branch of computational social science. Cascade dynamics can occur when the state of a node is affected by the states of its neighbours in the network, for example when a Twitter user is inspired to retweet a message that she received from a user she follows, with one event (the retweet) potentially causing further events (retweets by followers of followers) in a chain reaction. In this talk I will review some mathematical models that can help us understand how social contagion (the spread of cultural fads and the viral diffusion of information) depends upon the structure of the social network and on the dynamics of human behaviour. Although the models are simple enough to allow for mathematical analysis, I will show examples where they can also provide good matches to empirical observations of cascades on social networks.

### Universality of local statistics of Lyapunov exponents

Systems where time evolution follows a multiplicative process are ubiquitous in physics. We study a toy model for such systems where each time step is given by multiplication with an independent random NxN matrix with complex Gaussian elements, the complex Ginibre ensemble. This model allows to explicitly compute the Lyapunov exponents and local correlations amongst them, when the number of factors M becomes large. While the smallest eigenvalues always remain deterministic, which is also the case for many chaotic quantum systems, we identify a critical double scaling limit N~M for the rest of the spectrum. It interpolates between the known deterministic behavior of the Lyapunov exponents for M>>N (or N fixed) and universal random matrix statistics for M<<N (or M fixed), characterizing chaotic behavior. After unfolding this agrees with Dyson's Brownian Motion starting from equidistant positions in the bulk and at the soft edge of the spectrum. This universality statement is further corroborated by numerical experiments, multiplying different kinds of random matrices. It leads us to conjecture a much wider applicability in complex systems, that display a transition from deterministic to chaotic behavior.

### Degree Preserving Network Growth

We define a family of network growth models in which a newly arriving vertex attaches to the existing network without changing the degrees of the older vertices, by a process of cutting and joining edges. We discuss some of the properties of the graphs generated by such processes as

function of the evolution of the graph's matching number. We show that when the incoming degree is twice the matching number of the existing graph, the limit graph is a near split graph, with density 1/2. We show that this process can be used to build networks with power-law degree distribution without involving preferential attachment processes. We also present a generative model for growing random regular graphs, which, to our best knowledge, is the first model of this kind. We present an application to prime gap sequences.

### Hubs, Modularity and Densification in Networks

Hubs and modularity are among the key properties of many sparse networks. We show that these features naturally arise in basic models of growing networks. Hubs can be numerous and greatly vary from realization to realization, while in other models the emergence of the hub resembles a peculiar phase transition that looks like a classical continuous transition, yet shares some properties with an infinite-order phase transition. We also argue that a rather extreme version of modularity when the core of the network---the set of nodes with degree greater than one---grows sub-linearly with the total number of nodes and thus constitutes a vanishingly small fraction of network arises in astonishingly simple models. Densification transitions will be also discussed.

### Complex distributions emerging in filtering and compression

In filtering and compression, and many other problems, each output is produced by a certain number of different inputs. We explore the statistics of this degeneracy in an explicitly treatable filtering problem in which filtering performs the maximal compression of relevant information contained in inputs. The filter patterns in this problem conveniently allow a microscopic, combinatorial consideration. We observe that the resulting degeneracy distribution of outputs decays markedly faster than a power law and describe its functional form. Importantly, this distribution essentially depends on the size of the input data set, appearing to be closer to a power-law dependence for small data set sizes than for large ones. We demonstrate that for sufficiently small input data set sizes typical for empirical studies, this distribution could be easily perceived as a power law. Finally, we describe a mean-field theory for this kind of problems.

### Tensor-based methods for temporal networks

In this talk I will describe machine learning techniques based on tensor factorization to study temporal networks such as contact networks. Considering the temporal dimension of networks allows us to understand better and predict complex phenomena, by taking into account both the fact that the network edges are not continuously active and the potential relation between the spatial and temporal dimensions. A fundamental challenge in this area is the definition of mathematical models and tools apt to capture topological and dynamical characteristics and to reproduce properties observed on the real dynamics of networks.

I will here present techniques we have developed based on tensor factorization, that detect groups of links in networks that have correlated activities. I will first focus on the analysis of the topological structures that characterize time-varying networks, such as network communities (densely connected group of nodes). In particular, I will show how we can use tensor factorization to detect anomalies in temporal networks. I will then present a study on the interplay between the structures of time-varying networks and the dynamic processes unfolding over them, using the specific case of disease spreading. I will finally extend the framework of standard tensor factorization to infer missing data from a partial dataset and show how it enables us to reproduce the output of a dynamical process on the full temporal network.

### Challenges in percolation: from the large deviation of percolation to percolation in hyperbolic manifolds

In this talk I will present recent advances on percolation theory including progress on the large deviation of percolation and percolation on hyperbolic manifolds. The common theme that we will address is the investigation of when discontinuous percolation transitions can be observed.

The theory of large deviation of percolation [1-3] aims at characterizing the uncertain response of finite networks to perturbations. Therefore, this theory addresses important challenges posed by the study of the robustness of networks far from the thermodynamic limit such as ecosystems, power-grids and infrastructures. In this context we will show that when aggravating configuration of the initial damage are considered the percolation becomes discontinuous.

In is known that for the Farey graph, constituting a special type of hyperbolic manifold formed by simplicial complexes, percolation can be discontinuous. Here we investigate how robust this result is with respect to the extension to higher dimensional percolation, i.e. topological percolation to hyperbolic manifolds formed by simplicial complexes of dimension d=3 [4].

[1] Bianconi, G., 2018. Rare events and discontinuous percolation transitions. Physical Review E, 97(2), p.022314.

[2] Bianconi, G., 2019. Large deviation theory of percolation on multiplex networks. Journal of Statistical Mechanics: Theory and Experiment, 2019(2), p.023405.

[3] Coghi, F., Radicchi, F. and Bianconi, G., 2018. Controlling the uncertain response of real multiplex networks to random damage. Physical Review E, 98(6), p.062317.

[4] Bianconi, G. and Ziff, R.M., 2018. Topological percolation on hyperbolic simplicial complexes. Physical Review E, 98(5), p.052308.

### Hybrid percolation transitions in dichotomous cluster merging processes: a new type of self-organization process

Recently hybrid phase transitions, exhibiting first-order and second-order phase transitions at the same transition point, receive considerable attention as unconventional phase transitions. Particularly, hybrid percolation transitions (HPTs) were observed in diverse models and phenomena in complex systems such as k-core percolation, contagion processes, and cascade-failure model on interdependent networks. Such HPTs are induced by cascade failure dynamics in pruning process. However, HPTs induced by cluster merging process (CMP) still remain challenges theoretically and experimentally. Here using the so-called restricted ER random graph model, we find that dichotomous cluster merging processes can serve as a key underlying mechanism for such a type of HPTs. A system is decomposed into two sets A and B, which contains a portion of the smallest clusters and the remaining large clusters, respectively. Small clusters are allowed to grow fast in the set A and the grown clusters move to the set B. On the other hand, large clusters in the set B grow slowly and are moved to the set A. The inter-set crossing events occur in a self-organized way. Even though this self-organization process differs from that of the conventional the Bak-Tang-Wiesenfeld dynamics, the inter-event time distribution exhibits power-law decay with the exponent one and thus its power spectrum shows the 1/f noise pattern. Through this self-organized process, the system accumulates a so-called powder keg containing a large number of medium-size clusters. As dynamics proceeds further, the powder keg explodes and the giant cluster is formed in a short time period. We present analytic solutions for the inter-event time distribution and anomalous features of the HPT.

### Latent geometry of face-to-face interaction networks: emergence of heavy-tailed contact dynamics and recurrent components from similarity

Face-to-face interaction networks portray social interactions in closed settings such as schools, hospitals, offices, university campuses, etc. A typical representation consists of a series of network snapshots. The agents (nodes) in each snapshot are individuals and an edge between any two agents represents a direct face-to-face interaction. Analyses of such networks have uncovered universal properties, such as the heavy-tailed distributions of the interaction duration and time between consecutive interactions. In the first part of this talk, we will show that these universal properties along with the formation of connected components that appear recurrently in such systems, find a natural explanation in the assumption that the agents of the temporal network reside in a hidden similarity space. Distances between the agents in this space act as similarity forces directing their motion towards other agents in the physical space and determining the duration of their interactions. The modeling approach we consider bears similarities to N-body simulations and Langevin dynamics, while the resulting probability that two agents interact as a function of their similarity distance is reminiscent of a Fermi-Dirac distribution. Based on this observation, in the second part of the talk we will establish a connection to the Newtonian/Hyperbolic latent-space model of traditional complex networks. Our findings are also applicable to human proximity networks where interactions are not exactly face-to-face, and could potentially be applicable to other types of time-varying networks.

### The identifiability matrix: uses and interpretations for assessing fingerprints on brain connectivity networks

In the 17th century, physician Marcello Malpighi observed the existence of patterns of ridges and sweat glands on fingertips. This was a major breakthrough and originated a long and continuing quest for ways to uniquely identify individuals based on fingerprints. In the modern era, the concept of fingerprinting has expanded to other sources of data, such us voice recognition and retinal scans. It is only in the last few years that technologies and methodologies have achieved high-quality data for individual human brain imaging, and the subsequent estimation of structural and functional connectivity. In this context, the next challenge for human identifiability is posed on brain data, particularly on brain networks, both structural and functional.

Here I will introduce a mathematical object, the identifiability matrix, and its possible uses and interpretations to assess and measure individual fingerprints within the brain connectivity domain. A collection of measurements derived from the Identifiability matrix and related to fingerprinting scores will be presented. Different null models set at the connectivity level as well as on the identifiability matrix will be also discussed. Results presented includes data from the Human Connectome Project and from a local cohort at Purdue University.

**The registration is now closed**

For any questions please do not hesitate to contact the organizers at

**General Information**

Les Houches is a village located in Chamonix valley, in the French Alps. Established in 1951, the Physics School is situated at 1150 m above sea level in natural surroundings, with breathtaking views on the Mont-Blanc mountain range.

Les Houches Physics School is UMS 2002 run by Université Grenoble Alpes (UGA). The 5 school partners of are UGA, the Centre National de la Recherche Scientifique (CNRS), the Commissariat à l'Energie Atomique (CEA), the Institut National Polytechnique (Grenoble-INP), and the Ecole Normale Supérieure de Lyon (ENS Lyon).

**Address**

Ecole de Physique des Houches

149 Chemin de la Cote,

F-74310 Les Houches, France.

**How to get there**

The instructions how to get to the school are available at the school website, https://www.houches-school-physics.com/practical-information/access/. Some additional important information about staying at the school can be found here: https://www.houches-school-physics.com/practical-information/your-stay/, as well as in the **LINKS & DOWNLOADS** section at the bottom of this page.

**Logistics and checking-in/out**

The school is at a relatively isolated location, far above the Les Houches village in terms of elevation, and about 3km from its center, where the closest shops, restaurants, etc., are located. The hike down takes about 20 minutes, the hike back up is about 40 minutes.

The school will be locked, and there will be no one around until **Sunday, May 5, 3pm**. Check-in is possible only after this time. The latest room check-out time is **10am on Friday, May 10**. The talks, meetings, and discussions can continue until noon on that day, when the last lunch will be served, but all the participants must abandon the school premises by **Friday, May 10, 3pm** latest.

**The practical information during the workshop**

Some practical information about the facilities during the workshop can be found in the file at the bottom of this page in the section **LINKS & DOWNLOADS**

## Deadlines

## Organizers

## Contacts

**Alex Arenas**

alexandre.arenas@urv.cat**Alexander Gorsky**

shuragor@mail.ru**Dima Krioukov**

dima@northeastern.edu**Sergei Nechaev**

sergei.nechaev@gmail.com