ABSTRACT. Understanding the mechanisms governing neural communication in large-scale brain networks remains a major goal in neuroscience \cite{avena:2017,seguin:2018}. Many network communication measures adopted in the systems neuroscience literature are intrinsically asymmetric. This means that the communication efficiency from node $i$ to node $j$ may be different to the communication efficiency from $j$ to node $i$, even when all connections in the network can be traversed bidirectionally (Fig. \ref{fig}a). To date, this asymmetric behaviour of communication models has not been explored.

White matter tractography applied to diffusion MRI data from 200 healthy participants of the Human Connectome Project \cite{van-essen:2013} was used to map connectomes at several spatial resolutions ($N=256,360,512$). Effective connectivity between cortical subsystems \cite{yeo:2011,glasser:2016} was computed using spectral dynamic causal modeling (DCM) \cite{friston:2014} applied to resting-state functional data from the same individuals.

We developed a measure to test for statistically significant communication asymmetries and applied it to three asymmetric communication measures: i) navigation efficiency \cite{seguin:2018}, ii) diffusion efficiency \cite{goni:2013}, and iii) search information \cite{goni:2014}. We refer to the obtained measures of asymmetry in send-receive efficiency simply as ``communication asymmetry'' or, in the case of navigation efficiency, ``navigation asymmetry''. We characterized cortical regions and subsystems as senders, receivers or neutral, based on the extent of asymmetry in the efficiency of information transfer in one direction relative to the other.

Several cortical regions and subsystems showed significant asymmetry in sending and receiving efficiency (Fig. \ref{fig}b). In particular, for the measure of navigation efficiency, primary sensory-motor regions tended to be senders (higher efficiency of efferent paths) and functionally heterogeneous multimodal regions were more likely to be receivers (higher efficiency of afferent paths). This gives rise to a sending-receiving cortical hierarchy (Fig. \ref{fig}b,c), which recapitulates established organizational gradients between sensory-motor and multimodal areas (Pearson correlation $r=-0.22$, $P=2\times10^{-5}$ between navigation asymmetry and a measure of cortical functional heterogeneity \cite{margulies:2016}). Crucially, we found that navigation asymmetries significantly predicted asymmetry in effective connectivity (Pearson correlation $r=$0.47--0.52, Fig. \ref{fig}d). This association was stronger than those found for ensembles of geometrically randomized, topologically randomized and cost-preserving topologically randomized null networks. These results provide cross-modal validation of the predominant directions of information flow that we infer from the geometry and topology of the structural connectomes.

We conclude that asymmetric measures of neural communication provide meaningful insight into patterns of human cortical information processing, revealing a hierarchy of cortical senders and receivers. Our work challenges the belief that \textit{in vivo} structural neuroimaging is unable to characterize directional interactions between neuronal elements.

ABSTRACT. Introduction: Mapping functional brain biomarkers to cognitive, behavioral, and demographic attributes is imperative to understanding the biological mechanisms underlying functional disorders. In Alzheimer’s Disease (AD), specifically, there is a need for development of theragnostic biomarkers that dynamically respond to potential treatments in addition to correlating with cognitive outcomes. Evidence suggests that functional connectivity (FC) biomarkers, derived from resting state fMRI, may be able to fill this gap. However, low disease signal and lack of generalizability of predictive models derived from FC biomarkers hamper clinical utility. Here, we introduce a framework that combines connectome predictive modeling (CPM) and differential identifiability based on group level principal component analysis (PCA). We demonstrate that this framework not only improves test-retest reliability but, importantly, also improves the stability, anatomical specificity, and generalizability of models developed to predict AD related cognitive changes from FC.

Methods: Resting State fMRI Scans of 82 individuals from the Alzheimer’s Disease Neuroimaging Initiative, spanning the AD spectrum, were used. All included cognitively impaired individuals were Amyloid Positive, so as to not confound with other pathologies. Subjects received a comprehensive battery of cognitive and clinical evaluations. Sensitive tests for each cognitive domain: visuospatial (Clock Score), memory (Learning/Immediate Recall, Delayed Recall 30min), executive function (Learning/Immediate Recall, Trails B), and language (Animal Fluency) were chosen and the Montreal Cognitive Assessment (MOCA) was chosen as a representative clinical measure. Following pre-processing of fMRI data, whole-brain FC matrices were estimated as Pearson correlation coefficients between node time-series using a 286-region parcellation. Processed fMRI time series were split into halves, representing “Mode1” and “Mode2” sessions (i.e. Test and Retest), therefore two whole-brain FCs were estimated for each subject. FCs were decomposed and subsequently reconstructed using group level PCA (164 PCs) to maximize test-retest correspondence (as measured by Differential Identifiability). CPM was used to model the association between FC reconstructed using various ranges of PCs and z-scored neurocognitive scores, clinical scores, and age. (1) Edge Selection: For each measure of interest, bootstrapped random sampling of the whole cohort (200 samples) was used to generate distributions of edge-wise Pearson correlations between each variable of interest and a randomly selected FC (Mode1) from each subject. The bootstrap mean at each edge was used as the representative correlation estimate. Significantly associated edges were defined as those outside the 95% CI across all edges, creating a positive and a negative mask of edges. This process was repeated using the remaining FC data (Mode2). The stability of this step across ranges of PCs was evaluated in two ways. First, the divergence between Mode1 and Mode2 correlation matrices was quantified by their Frobenius norm (Fig.1A). Second, the stability between Mode1 and Mode2 masks was quantified by their overlap of significant edges (Fig.1B). Anatomical specificity was evaluated by comparing the similarity between the battery measures to the similarity between their corresponding edge masks (Fig.1C). We hypothesized that masks from highly similar measures would exhibit greater spatial overlap. (2) Model Fitting: Mode1 FCs were used to estimate the coefficients. FC strength within each mask was calculated for all subjects. A linear model was used to fit the relationship between FC strength, and each battery measure. A leave one out procedure was used, hence fitting 82 instances of this model. (3) Generalizability: Mean squared error (MSE) was used to evaluate generalizability of the associations. We first evaluated MSE after imposing the model from Mode1 on Mode2 FCs of the same subjects. The we evaluated MSE after imposing the model from Mode1 on Mode2 FCs from left out (validation) subjects.

Results: Differential identifiability was optimized at 82 PCs (Fig.1A). At this level of FC reconstruction, the stability of correlations (Fig.1A) and masks (Fig.1C) was optimal. Additionally, overlap between masks generated from different battery measures reflected the correlation between the measures themselves (Fig.1C). Finally, MSE on validation subjects was minimized at 82 PCs.

Conclusions: Maximizing differential identifiability of FC data not only improves test-retest reliability of whole-brain functional connectomes, but importantly, also improves the stability, anatomical specificity, accuracy, and generalizability of prediction of AD related outcomes from FC. Our framework integrating CPM and differential identifiability represents an important step in improving the clinical utility of FC biomarkers.

ABSTRACT. Consciousness is the product of interaction between multiple brain structures and depends on the brain’s ability to integrate different complex patterns of internal communication. Although several studies demonstrated that the fronto-parietal and default mode networks play a key role in in conscious processes, it is still not clear whether the brain network organization is altered at the global level in patients with disorders of consciousness (DOC). Herein, we investigated the functional connectivity of unresponsive wakefulness syndrome (UWS) and minimally conscious state (MCS) patients, from a network perspective by using resting state EEG recording. Network-based statistical analysis revealed a subnetwork of decreased functional connectivity in UWS compared to the MCS patients, mainly involving the interhemispheric fronto-parietal connectivity patterns (Figure 1). Global network topological analysis identified increased values of Local Community Paradigm-correlation (LCP-corr), as well as of high clustering coefficient (CC) and modularity in UWS patients compared to MCS patients. This is the first time that LCP-corr is measured in the EEG connectome of patients with DoC. At the nodal level, the UWS patients showed altered topology in several limbic and temporo-parieto-occipital regions. Our results suggest that in altered states of consciousness the local community organization of the network is preserved (LCP-corr > 0.8). However, the network tends towards a more local community-oriented organization in patients with UWS (higher values of LCP-corr), pointing out a gradual and cumulative enrichment of neural connections inside the same local community. It can be reasonable to assume that the higher tendency towards a local community-oriented topological organization in UWS may represent an epiphenomenon of diffusely emergent (possibly) dysfunctional connections, resulting in aberrant self-reinforcing loops. A strong correlation with the Coma Recovery Scale-Revised scoring was also found when pooling together the LCP-corr and CC (Z=65, p<0.001). Notably, two patients with UWS behaved as outliers, suggesting the clinical potential of our method for identifying patients with UWS who may be aware at covert level. Taken together, our results highlight i) the involvement of the interhemispheric fronto-parietal network in the pathophysiology of consciousness disorders and ii) an aberrant network organization both at the global and at the nodal level in UWS compared to the MCS patients.

ABSTRACT. It has been well established that individuals have a unique fingerprint in their Functional Connectomes (FCs), obtained from neuroimaging data, which can be used to identify them from a population of FCs[12]. Although identification accuracy is high using resting-state FCs, other tasks have moderate to low values[12]. In addition, individual fingerprinting is not task independent, i.e. FCs from one task cannot be used to identify individuals from a database of FCs of another task. Here we propose a multidimensional framework based on group-level Principal Component Analysis (PCA) decomposition of FCs, which not only increases the identification accuracy significantly, but also makes the fingerprinting process potentially task independent. We use neuroimaging data for resting-state and seven different task sessions from the Human Connectome Project (HCP) dataset to obtain FCs. By applying the PCA-space (PCS) framework on each task separately, we show that identification accuracy increases significantly for each task, including resting-state. Furthermore, by using multiple task FCs in the database of our framework, we show that an individual can be identified with extremely high accuracy (97-100%), even if the FC being identified belongs to a task not included in the database. Additionally, we found that FCs from two tasks for each individual are sufficient to create a database that enables the identification of an individual FC under any task with extremely high accuracy. Interestingly, for this to succeed, one of those two tasks must be resting-state, but any other task can be used as the second one, with relational task producing the best results within this dataset. In other words, resting-state and a non-resting-state task seem to cover the entire cognitive space for individual FC fingerprinting. This framework provides a task-independent method to identify an individual with extremely high accuracy, which can be used to quantify the change in an individual’s FC fingerprint resulting from a brain trauma or a neurological disease, e.g. Alzheimer’s or Schizophrenia.

ABSTRACT. Task-specific focal dystonia selectively affects the motor control during skilled and highly learned behaviors. Recent data suggest the role of neural network abnormalities in the development of the pathophysiological dystonic cascade. We used resting-state functional MRI and analytic techniques rooted in network science and graph theory to examine the formation of abnormal subnetwork of highly influential brain regions, the functional network kernel, and its influence on aberrant dystonic connectivity specific to affected body region and skilled motor behavior. We found abnormal embedding of sensorimotor cortex and prefrontal thalamus in dystonic network kernel as a hallmark of task-specific focal dystonia. Dependent on the affected body region, aberrant functional specialization of the network kernel included regions of motor control management in focal hand dystonia (writer's cramp, musician's focal hand dystonia) and sensorimotor processing in laryngeal dystonia (spasmodic dysphonia, singer's laryngeal dystonia). Dependent on skilled motor behavior, the network kernel featured altered connectivity between sensory and motor execution circuits in musician's dystonia (musician's focal hand dystonia, singer's laryngeal dystonia) and abnormal integration of sensory feedback into motor planning and executive circuits in non-musician's dystonia (writer's cramp, spasmodic dysphonia). Our study identified specific traits in disorganization of large-scale neural connectivity that underlie the common pathophysiology of task-specific focal dystonia while reflecting distinct symptomatology of its different forms. Identification of specialized regions of information transfer that influence dystonic network activity is an important step for future delineation of targets for neuromodulation as a potential therapeutic option of task-specific focal dystonia.

ABSTRACT. Brains are networks of interconnected regions whose connectivity patterns support complex cognitive processes. Disruptions to normative patterns of connectivity can result in psychiatric disorders. Nonetheless, how differences in network structure lead to distinct disorders remains unclear. In this study, we used a freely available diffusion weighted imaging (DWI) dataset [Poldrack, R. A. et al.] and processed them on brainlife.io. We examined differences in the global and local properties of the structural brain networks in the healthy control subjects and patients with psychiatric disorder (schizophrenia, bipolar, and attention deficit hyperactivity disorders). Next, we leveraged a machine learning framework to classify patients and control groups based on information obtained from this initial analysis of structural networks.

To this end, we generated structural connectivity matrices for each subject using a fiber density measure estimated between all pairs of n=373 brain regions [Glasser et al., 2016]. We then compared subjects on the basis of the global network measures. First, we characterized the capacity for efficient information flow across the whole brain by calculating the weighted shortest path length (SPL) and the number of steps required to reach node j from node i. Next, we identified rich clubs consisting of high degree brain regions that are also highly connected to one another using the normalized rich club coefficient. We then compared the control and patients’ groups in terms of the calculated network measures and assessed statistical significance using the Kolmogorov–Smirnov test. Finally, we classified psychiatric conditions using local network measures including participation coefficient, degree, closeness, and betweenness centrality as features in a decision tree-based machine learning framework.

We find that weighted SPL and the average number of steps required to go from one brain region to another were higher in patients compared to the control group (p < 0.001; Fig. 1A). In addition, for nodes with degrees higher than a specific range of threshold, the normalized rich club coefficient value was lower in patients meaning that they are less connected to one another compared to the control group. (p<0.05; Fig. 1B). Lastly, the classification results showed that the local network properties of a small subset of brain regions were disproportionately useful in distinguishing psychiatric conditions from the control group (Fig. 1C). Overall our findings suggest that the difference in the global and local properties of the structural brain networks in patients with psychiatric disorders and control group can be used to distinguish and classify them effectively.

ABSTRACT. Epidemic containment is a major concern when confronting large-scale infections in complex networks. Many works have been devoted to analytically understand how to restructure the network to minimize the impact of major outbreaks. In many cases, the strategies consist in the isolation of certain nodes, while less attention has been paid to the intervention on links. In epidemic spreading, links inform about the probability of carrying the contagion of the disease from infected to susceptible individuals. 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 contention of epidemics, based on deactivating the most important links in transmitting the disease, while, at the same time, it preserves the connectivity of the network, hence, its functionality.

ABSTRACT. The rise of Emergent Infectious Diseases (EIDs) is one of the primary modern stresses causing devastation to biological systems today. The widespread decline of bumble bees (Bombus Spp.), concurrent with the detection of several new pathogens, indicates the presence of EIDs may be one of the factors leading to the decline of this biologically and economically important genus. One such pathogen recently found in bumble bees is Deformed wing virus (DWV). There is mounting experimental evidence that there is a spillover of DWV from commercial honey bees (Apis mellifera) to neighboring bumble bee populations [3], and that a primary route of transmission between these groups is through flowers [2].

We model the spread of DWV between honey and bumble bees through flowers using a tripartite network, with edges connecting bees to flowers within their foraging range, and analyze disease spread for two cases of such networks. First we consider a fully-connected tripartite network, which corresponds to the classical mean-field Ross-Macdonald model with an additional vector population, and derive the steady states and reproductive number using a simple branching argument (see Figure 1). Next, to incorporate spatially-explicit dynamics we construct the tripartite network using satellite images with the open-source software BEESCOUT [1], and compare our model’s outbreak dynamics to observed infection densities. Together, these approaches demonstrate how a shared transmission route can lead to a major outbreak between two groups, even when either group may not appear at risk when studied in isolation.

ABSTRACT. Directionality in contact networks has often been disregarded, either because of the lack of data or in order to simplify the theoretical approaches. Specifically, in the context of epidemic spreading, networks are usually considered undirected in both theoretical and applied studies. However, there are studies in which directionality has been found to be very important such as in the case of meerkats in which transmission varies between groomers and groomees [1]. Similarly, when one wants to address the problem of diseases that can be transmitted between different species, it is important to account for the fact that they might be able to spread from one type of host to the other, but not the other way around. This type of problems can be tackled using multilayer networks, in which the network of each species is represented in one layer and the possible interactions between the species are encoded in the links connecting the layers. For example, bubonic plague can be endemic in rodent populations and spread to humans and other animals under certain conditions. If it evolves to the pneumonic form, it may then spread from human to human [2]. Similar scenarios can be found in the interface between wildlife and livestock, with diseases being endemic in one of them and then being transmitted unidirectionaly to the other [3]. %Even more, the recent introduction of high resolution data of face-to-face interactions has renewed the interest in using directed network. Indeed, this data can be used to build temporal multilayer networks in which the connections between layers, i.e. different time frames, have to be necessarily directed in order to preserve the causality induced by time ordering [4].

In this work, we aim to characterize the spreading of epidemics in directed multilayer networks. We focus on investigating how the epidemic threshold is influenced by the directionality of links, both interlayer and intralayer links. To do so, we use generating functions to analytically derive the epidemic threshold for directed multilayer networks. In particular, we consider multilayer networks composed by two layers with heterogeneous degree distributions. Besides, we analyze all possible combinations of directionality: (i) directed layers and undirected interlinks (DUD); (ii) directed layers and directed interlinks (DDD); (iii) undirected layers and directed interlinks (UDU); and (iv) undirected layers and undirected interlinks (UUU). We then implement a susceptible-infected-susceptible (SIS) model on these networks and compare the results with the analytically derived epidemic threshold, finding a perfect agreement. Our findings show that the directionality in the links across layers is much more important than in the links within layers. Thus, as precisely in the examples cited previously directionality is mainly in the links connecting different layers, we can conclude that more emphasis should be put in studying the role it can play in the spreading of epidemics.

[1] J. A. Drewe; Proc. R. Soc. B (2010) 277, 633-642. [2] J. L. Kool and R. A. Weinstein; Clinical Infectious Diseases, 40 (8), 1166-1172. [3] R.G. Bengis, R.A Kock and J. Fischer; Rev. sci. tech. Off. int. Epiz., 21 (1), 53-65.

ABSTRACT. The challenges of modeling disease spreading are not only related to the disease itself and its dynamics, as it is also crucial to correctly account for the medium where it spreads, whether it is people, animals or plants. The introduction of multilayer networks, as an extension of classical or monolayer networks, has proved to be particularly useful in the study of interacting diseases, with each disease, or strain, circulating in one layer of the system [1]. The extension of classical epidemiological models such as the susceptible-infected-recovered (SIR) model to these networks is straightforward. Indeed, the spreading of a given disease, or strain, would be the same as in monolayer networks and then the interaction would be encoded in the links connecting the layers. This way, an individual could be recovered from one disease (recovered in one layer) and not from the other one (susceptible in the other), which is the approach mostly found in the literature [2]. However, it is also possible to use multilayer networks to capture the distinct connectivity patterns characteristics of human societies. Hence, it is possible to define one layer as the set of interactions that take place in a particular setting, like schools, another layer for the ones taking place in households, etc. If we were to use a direct extension of the current SIR model to these systems, we would be incurring in an obvious mistake as a person could be recovered in one place and susceptible in another. For this reason, in this work we explore an extension of the SIR model to multilayer networks in which the recovered state is coupled in all the layers so that when an individual heals in one layer, the healing would be automatically applied in all the layers.

We firstly test this approach on synthetic multilayer networks composed by two layers and find that the final amount of recovered individuals is higher with this model than with the standard formulation. Then, we show that this behavior can be captured by a pairwise quenched mean-field approximation. Lastly, we apply this model to a synthetic multiplex network resembling the social structure of the population in The Netherlands. This network is composed by four layers: school, household, workplace and community layers. Furthermore, we introduce the average number of contacts an individual can have in each layer into the adjacency matrix describing the network to account for the possible differences in the spreading in each layer. This highly detailed network allows us to study our SIR model in a very realistic scenario, even if the model itself is rather simple from the mathematical point of view. In particular, we are able to fit the parameters of our model to resemble a typical influenza epidemic. Even more, we are able to capture the temporal evolution of the reproduction number that has been observed in agent based models [3] and obtain some insights about the effect that different self-protection measures can have on the spreading of an epidemic.

[1] J. Sanz, C. Xia, S. Meloni and Y. Moreno. Phys. Rev. X, 4(4) 041005. [2] M. Dickison, S. Havlin and H. E. Stanley. Phys. Rev. E, 85(6):066109 [3] Q. Liu et al. Proc. Natl. Acad. Sci. U.S.A., 2018 115 (50) 12680-12685.

ABSTRACT. We study a general epidemic model with arbitrary recovery rate distributions. This simple deviation from the standard setup is sufficient to prove that heterogeneity in the dynamical parameters can be as important as the more studied structural heterogeneity. Our analytical solution is able to predict the shift in the critical properties induced by heterogeneous recovery rates. Additionally, we show that the critical value of infectivity tends to be smaller than the one predicted by quenched mean-field approaches in the homogeneous case and that it can be linked to the variance of the recovery rates. We then illustrate the role of dynamical--structural correlations, which allow for a complete change in the critical behavior. We show that it is possible for a power-law network topology to behave similarly to an homogeneous structure by an appropriate tuning of its recovery rates, and vice versa. Finally, we show how heterogeneity in recovery rates affects the network localization properties of the spreading process.

Please, see the complete abstract submission in the attached pdf file.

ABSTRACT. Many real-world networked systems that involve humans are characterized by a temporal evolution of the network structure, besides the evolution of the characteristics of individuals. These two dynamics are typically intertwined through a self-excitement mechanisms. The more an individual is socially active in generating connections with peers, the more he/she is motivated to further increase his/her social activity, yielding bursty phenomena.

While the temporal evolution of the network of interactions has been successfully modeled using the paradigm of activity-driven networks (ADNs), attempts to include memory and self-excitement mechanisms have been sporadic and mostly based on numerical simulations. To the best of our knowledge, this work is the first endeavor to design an analytically treatable model to shed light on these phenomena. We generalize ADNs to encapsulate self-excitement dynamics, toward ADNs where activity rates are time-varying. Such a time-variability is modeled through Hawkes processes, often used in other social systems applications to model self-excitement.

Two main results have been achieved, elucidating the effect of self-excitement on the network structure and on the inception of epidemic spreading. First, we characterize the dynamics of the distribution of the nodes' activity rates. Second, we include a Susceptible--Infected--Susceptible (SIS) epidemic model, and we analytically compute its epidemic threshold, in the presence of self-excitement and behavioral changes due to the individual health state (caused by the disease itself, or by containment strategies such as quarantine). Through a comparison with the corresponding model in the absence of self-excitement, we observe a decreased epidemic threshold, yielding an increased propensity toward the inception of epidemics. We observe that neglecting the effect of self-excitement phenomena may lead to a harmful underestimation of the risk of an epidemic outbreak. Further numerical simulations are performed to deepen our understanding of the effect of self-excitement. For instance, we investigate the long-run behavior of the epidemic model, the effect of latency periods, when individuals are still unaware of being infected, and the presence of permanent immunization in the Susceptible--Infected--Recovered model.

ABSTRACT. Motivated by networks in critical infrastructures (e.g., communication and power networks), we analyze optimal robustness of a class of flow networks against cascading failures triggered by removal of a portion of lines. Our network model consists of N lines with initial flows L1,...,LN. The capacity of line i is set to be Ci = Li + Si, where Si quantifies the free-space or redundancy available to line i. Redundancy Si and load Li obey the joint distribution P[L ≤ x,S ≤ y]. A line failure occurs either initially due to attack or later due to overloading, i.e., the flow on a line exceeding its capacity. We are interested in the following important practical problem: Given a total available amount of redundant space, how should we allocate S1,...,SN so that the resulting network has maximum possible robustness?. Our result gives a surprising answer to this question: Under various cascading failure models including i) global redistribution; ii) fully local redistribution based on network topology; and iii) partially local, partially global redistribution, and under both a) random and b) targeted attacks, we show analytically that allocating every line the same redundant space maximizes the robustness of the system, under some regulatory assumptions. We quantify robustness of the network as the expected fraction of surviving lines when the attack size p (i.e., the fraction of the lines initially failed) follows a uniform distribution between zero and one. This shows that the setting Ci = (1 + K)Li , with K denoting the tolerance factor used for all lines, that is widely adopted in the literature does not lead to optimal robustness. Numerical results confirm the optimality of equally allocating redundancy among the lines under several attack and flow redistribution models.

ABSTRACT. Despite extensive studies on diffusion of innovations, our knowledge about the reverse process—how innovations are abandoned—remains limited. Here, we analyze two large-scale datasets, each capturing detailed temporal and social patterns that trace the entire lifecycle of innovations. By analyzing 29 M scholars researching more than scientific 2000 fields and 3.6 M individuals using more than 9000 mobile handsets, we find that, in contrast to the poissonian dynamics commonly assumed in the abandoning please of the lifecycle, the abandoning probability increases with the number of past abandonments, demonstrating a bandwagon effect characterizing how innovations are abandoned (Fig. A-B). We constructed the social networks underneath the two systems through co-authorships and mobile communication records, finding that a preferential abandonment mechanism at a network level is responsible for generating the observed effect (Fig. C-D). Most importantly, we show analytically that the presence of preferential abandonment induces a structural collapse in the topology of the system (Fig. E), where networked systems that were thought to be robust undergo a novel phase transition (Fig. F-G). We test the theoretical predictions systematically in our datasets, obtaining broadly consistent empirical support. Together these results demonstrate that the collapse of real systems follow reproducible but fundamentally different dynamics than what traditional theoretical frameworks predicted. Our findings suggest that preferential abandonment and the structural collapse it induces may be a generic property that prevails the declining phase of the innovation lifecycle.

ABSTRACT. How big is the risk that a few initial failures of nodes in a network amplify to large cascades that span a substantial share of all nodes? The answer (and its policy implications) are usually based on estimates of the average cascade size as proxy for systemic risk. In the past decade, substantial progress has been made to calculate it efficiently by (Heterogeneous) Mean Field Analysis and Belief Propagation. Yet, in finite networks, this average does not need to be a likely event [1,2]. Instead, we find broad and even bimodal cascade size distributions - also far away from phase transitions and in large systems [1]. Furthermore, we are most interestedin the risk of extreme events, e.g. very large or small cascades. Ideally, we have information about the full cascade size probability distribution. To obtain this, I derive a novel Message Passing Algorithm for a large class of cascade models that is exact on trees [2,3]. An approximate variant applies to any fixed and finite network topology, yet, the approximation quality is excellent mostly for locally tree-like networks. This approach, termed Tree Distribution Approximation, has several advantages: 1) It is efficient and parallelizable. 2) It applies to any network topology. To increase accuracy, the main principle can be combined with Monte Carlo simulations on subnetworks. 3) It enables the computation of additional information, like the failure probability of nodes conditional on the final cascade size as visualized in Fig. 1B (bottom). Interestingly, we find that those are not monotoneously increasing for increasing cascade size and node rankings can change accordingly. These insights correct common expectations about the role of hubs. 4) Explicit cascade size distribution information paves the way for Bayesian learning approaches, for instance to estimate model parameters based on cascade size observations or to detect the cascade source.

[1] R. Burkholz, H. J. Herrmann, F. Schweitzer (2018). Explicit size distributions of failure cascades redefine systemic risk on finite networks. Scientific Reports 8 (1), 6878. [2] R. Burkholz (2018). Efficient message passing for cascade size distributions on finite trees. arXiv:1811.06872. [3] R. Burkholz (2018). Tree distribution approximation for the independent cascade model. Working Paper.

ABSTRACT. Biodegradation of network polymers is emerging as an important future industry. Researches to solve environmental problems by biodegradation of plastic and decomposition of lignin, a component of wood's cell wall, as an alternative resource for petroleum are active. The important thing in the biodegradation are enzymes, and enzymes have substrate specificity. We approach the substrate specificity of enzymes from the percolation perspective and develop a new percolation model.

Our new percolation model, called the $K$-selective percolation, has the following rules. First, to model the network polymer, we remove each node of the underlying network randomly with probability of $(1-p)$ (like thermodegradation). Second, the $K$-selective percolation rule is applied as follows: We iteratively remove a randomly-chosen node among those having degree exactly $K$ (like enzymatic degradation), until there are no nodes having degree $K$ left in the network. This is a simplification of a specific substrate that enzyme reacts into the node with specific degree ($K$). A schematic example for $3$-selective percolation is shown in Figure.~\ref{fig}(a).

We apply the $K$-selective percolation model to the diluted random regular (RR) networks and the Erd\H{o}s-R\'enyi (ER) networks which corresponds to network polymer. We derived analytical solutions using generating function method and verified them by extensive Monte Carlo Simulation. We obtain, among others, the optimal $K_{\mathrm{opt}}$ with which the network is decomposed most effectively depending on the initial structure of network polymer [Figure.~\ref{fig}(b)].

Three phases are identified in the $K$-selective percolation process [Figure. \ref{fig}(c)]. In phase I (non-percolating phase) there is no giant cluster, but in phase II and III a giant cluster exists. In phase II (sparse phase) a giant cluster mostly composed of nodes with degree less than $K$, on the contrary in phase III(dense phase) a giant cluster dominantly composed of nodes with degree more than $K$. In most cases double phase transitions are observed, the first phase transitions (between phase I and II) are continuous and the second phase transitions (between phase II and III) are hybrid. Mostly continuous phase transitions have same universality with ordinary percolation, and hybrid phase transitions have same universality with k-core percolation.

We anticipate this work to initiate the percolation-based endeavors of studying network polymers in the network science perspective as well as to help understand fundamental physics regarding the multiple phase transitions in the theoretical perspective.

ABSTRACT. About a half century ago, Thouless showed that 1/r^2-type long-range interactions in the one-dimensional Ising model change the phase transition type from second order to first order. Since then, long-range interactions in diverse equilibrium and non-equilibrium systems have received considerable attention. Similar to this long-range interaction effect, it was suggested that global suppression effect can change the percolation transition type in complex networks. Here, we investigate how a percolation transition is changed by the global suppression effect in growing networks. It is known that the percolation transition in growing networks is of infinite order, following the Berezinskii-Kosteritz-Thouless (BKT) transition. Examples are ubiquitous. We show that under the global suppression effect, the BKT transition breaks down, but the features of infinite-order, second-order, and first-order transitions all emerge in a single framework. The critical region below the BKT transition point is extended and the power-law behavior of the cluster size distribution reaches the state with the exponent tau=2, suggesting that the system has the maximum diversity of cluster sizes. We also analyze the underlying mechanism and show that the features are universal. The evolution rule of our network model starts from a single node and then a new node is added every time step t. To choose two nodes to be linked, we select one node randomly from all nodes and select randomly the other node from a subset consisting of a portion g of all nodes that belong to the smallest clusters. Figure 1 shows the phase diagram in the plane of (p,g). We present a simpler model to explain the underlying mechanisms of these abnormal transition behaviors.

ABSTRACT. Percolation transition is widely observed in networks ranging from biology to engineering. While much attention has been paid to network topologies, studies rarely focus on critical percolation phenomena driven by network dynamics. Using extensive real data, we study the critical percolation properties in city traffic dynamics. Our results suggest that two modes of different critical percolation behaviors are switching in the same network topology under different traffic dynamics. One mode of city traffic (during nonrush hours or days off) has similar critical percolation characteristics as small world networks, while the other mode (during rush hours on working days) tends to behave as a 2D lattice. This switching behavior can be understood by the fact that the high-speed urban roads during nonrush hours or days off (that are congested during rush hours) represent effective long-range connections, like in small world networks. Our results might be useful for understanding and improving traffic resilience.

ABSTRACT. Acts of sexual violence often go unreported because of the stigmatization surrounding disclosure. Although nearly 1 in every 3 women in the United States will experience an act of sexual violence in her lifetime, almost half of those women will never disclose that incident to anyone. Consequently, the pervasive social and public health problem of violence against women has been relegated to a “whisper network” outside of public conversations. More recently, many survivors of sexual violence have sought community and support online, where they can anonymously connect with one another via anonymous and private message boards. Research has emphasized the importance of anonymity and privacy in these communities. It is therefore unexpected that women would publicly and identifiably broadcast sexual violence disclosures on non-anonymous social media platforms. However, on October 15th, 2017, thousands of women publicly did exactly that, disclosing their stories of sexual violence after actress Alyssa Milano called on women to share the phrase “me too” if they have ever been sexually harassed or assaulted. The resulting cascade of disclosures that followed Milano’s tweet came to be known as the #MeToo movement. We argue that the uncharacteristically public #MeToo disclosures can be explained by the concept of network-level reciprocal disclosures, in which women disclose in response to the reduction in stigma as other women disclose. At a macro level, the #MeToo disclosures activated an online network that brought the typically-marginalized experiences of sexual assault survivors to the mainstream, bringing attention to the systemic issue of violence against women and reducing stigma against further disclosures.

Through a mixed-methods analysis of 1.4 million #MeToo tweets and replies to those tweets posted during the first two weeks of the movement, we disentangle the dynamics of network-level reciprocal disclosure and measure the feedback dynamics between disclosures, stigma reduction, and collective action. We first hand-code 2,500 tweets for disclosures of sexual violence, allowing us to train a machine learning model capable of accurately identifying disclosures in #MeToo tweets. The model allows us to map the disclosure landscape of the network that emerged around the hashtag. Finally, through the alignment of the #MeToo network with the underlying follower-following network, we are able to provide estimates of both the effect of previous disclosures within an individual’s social network on a later disclosure and the effects of reciprocal support and positive replies on continued engagement with the #MeToo movement. By bridging the theories of network-level reciprocal disclosure and networked feminist counterpublics through quantitative and qualitative analyses of the #MeToo movement, we are able to clarify the micro mechanisms that govern the disclosures of stigmatized experiences on public social media platforms and the macro mechanisms that govern the emergence of the #MeToo movement and other feminist hashtag campaigns such as #YesAllWomen, #NotOkay, and #WhyIStayed.

ABSTRACT. Online social interactions are increasingly used to study different aspects of human behavior such as information exchange between groups, social mobilization or political polarization. However, making direct links from online to offline social behavior proves a challenge and it remains unclear to what extent online social interactions inform offline social interactions. In other words, the external validity of research done using online behavior data does not necessarily translate into offline behavior. In this paper we examine whether online political support is mirrored in offline political support.

We overlay two data sets, both containing data on political support among Swiss politicians. The first data set stems from an online Swiss political debate and networking platform called Politnetz. On Politnetz, politicians, as well as citizens can debate political issues and establish support-relations with each other similar to ‘friendship’-links on other social media sites. The second dataset captures offline political support via legislative cosponsorship signatures among Swiss members of parliament (MP). One of the key tasks of MPs is to draft new legislative proposals, propose them to parliament, where they are discussed and voted on. In order to improve the chance of their proposal passing a vote, MPs actively ask other MPs to support their proposal by adding their cosponsorship signature to it.

We present a network inference model for multi-edge networks to assess whether online political support is reflected in cosponsorship support. Our results show that direct online support has no explanatory power in cosponsorship support among MPs. However, when using aggregated similarities in online behavior our model explains 15% of the variance of offline legislative support (pseudo-R2). Our results show that online behavioral traces do have some explanatory power for offline interactions if handled with care. However, the results also show that generalizations based on social media data are limited.

ABSTRACT. Quantifying insurgent organizations’ capabilities for destruction, one focus of the science of human conflict, is a problem escalating with the proliferation of terror attacks. Yet, quantifying and predicting an organization’s potential for lethality has proven elusive because data on a terror organization’s destructive capabilities and resources is typically concealed to avoid measurement. Here we present a statistical model for estimating a terror group’s future lethality using latent variable modeling techniques to infer a group’s intrinsic capabilities and resources for inflicting harm. The analysis has three salient findings: (1) The analysis introduces two explanatory variables that measure a terror group’s underlying capabilities and resources. These variables together explain 52% of the variation in lethality in terror group behavior and when combined with existing models raise the overall explained variance. When adding hand-curated network-based information about a group’s alliances, these two variables remain statistically significant. (2) The model identifies a dynamic turning point in the severity of lethality. Before the turning point, changes in levels of destructive resources have little relationship to lethality (Fig. A). After the turning point, groups are increasingly lethal, with each unit increase past the turning point predicting a 67% rise in casualties. (3) The model generates an early warning signal of an individual group’s future lethality. Based on a few first attacks, the model accurately estimates a group’s lifetime lethality, a critical factor in designing security and resource-allocating system (Fig. B&C). The model’s robustness is evaluated with out-of-sample testing and simulations (Fig. D&E&F). The findings’ theoretical and pragmatic implications for the science of human conflict are discussed.

ABSTRACT. Governments in modern societies undertake an array of complex functions that shape politics and economics, individual and group behavior, and the natural, social, and built environment. How are governments structured to execute these diverse responsibilities? How do those structures vary, and what explains the differences?

To examine these longstanding questions, we develop a technique for mapping Internet "footprint" of government with network science methods. We use this approach to describe and analyze the diversity in functional scale and structure among the 50 state governments reflected in the webpages and links they have created online: 32.5 million webpages and 110 hyperlinks among 47,631 agencies. Each agency becomes a node in our network and agencies are connected if there is a significant number of hyperlinks between the two websites.

We first verify that this extensive online footprint systematically reflects known characteristics: 50 hierarchically-organized networks of state agencies that scale with population and are specialized around easily identifiable functions in accordance with legal mandates. Our analysis of the network hierarchy emphatically shows beyond doubt that such organization exists. It also aligns with our expectation, and with the de jure organization of the government.

We validate our network by manually reconstructing the government network of Massachusetts, since the state's constitution mandates public agencies interactions in its articles. The agreement between the de facto network as obtained by our Internet crawl and the de jure structure from the constitution is high. Interestingly, the most significant differences are in the additional information that the Internet network allows to explore but that are not coded in the constitution. This includes significant public activities such as education.

We also find that the footprint reflects extensive diversity among these state functional hierarchies in terms of number of agencies per function performed, average agency complexity, and the interconnectedness between agencies performing the same function -- are they all in the same connected component or are there significant isolated communities? We hypothesize that this variation should reflect, among other factors, citizens' income, economic structure, ideology, and where they live. We find that government structures are most strongly associated with state economic structures, with geography and income playing more limited roles. Voters' recent ideological preferences about the proper roles and extent of government are not significantly associated with the scale and structure of their state governments as reflected online.

We conclude that the online footprint of governments offers a broad and comprehensive window on how they are structured and can help deepen understanding of those structures.

ABSTRACT. Individuals' perceptions about the prevalence of attributes in their social networks are commonly biased by the limited information available to them: False consensus indicates the tendency to consider one’s own attributes---including personal characteristics, beliefs, and behaviors---as more common than they really are. A contrasting bias is false uniqueness, the tendency to think that one's own attributes are less frequent than they really are. Here we show how both perception biases can be explained within a single theoretical framework that includes effects of symmetrical and asymmetrical homophily and the size of the minority group. Using a generative network model with tunable homophily and minority-group size, we demonstrate analytically and numerically under what conditions and to what extent the two perception biases emerge. We also show that this model is supported by results from a cross-cultural survey study and calculate the potential for perception biases in six real-world networks. Given the results, we could understand that the network structure constructed by homophily (or heterophily) could give us parsimony explanation for the perception biases without having more complicated explanations. Our results show that (i) homophily explains perception biases in social networks, (ii) these biases are related to the asymmetrical nature of homophily in networks, and (iii) the size of the minority relative to the majority group can enlarge perception biases. It would extend our understanding about the perception biases and suggest a principal forming our biases in the point of the social networks we are surrounded by. Finally, we explore whether individuals can reduce their perception biases by relying on perceptions of their neighbors. We find that increasing diversity could reduce the perception biases for the minority and majority in the symmetric homophily condition. However, when the homophily is more asymmetric, increasing diversity in social networks shows more non-trivial behaviors. To sum up, this study advances our understanding of the impact of network structure on perception biases and offers a quantitative approach for addressing related issues in society.

ABSTRACT. The friendship paradox states that ``your friends are more popular than you'', or that the average excess degree is greater than the average node degree. A recent generalisation found when introducing a notion of ``closeness'' of friendships via ranking alters by contact volume, that in fact the strength of the friendship paradox increases with rank (Fig.~1B, top panel), meaning ``your best friends are no more popular than you''.

In this paper we build upon this work by asking: when ranking alters by contact volume, where do the alter-alter ties tend to point? (Fig.~1A.) Do highly-ranked alters tend to have ties with other alters, and if so, which ones? Do ties tend to point ``upwards'', towards closer-ranked alters or ``downwards'', to more distant ones?

By analysing two datasets (one mobile phone, one Twitter) we find that alter-alter ties are more likely to exist for highly-ranked alters (Fig.~1B, lower panels). Interestingly, the direction of these ties tend to point ``upwards'' towards closer-ranked alters (Fig.~1C), suggesting that the structure of these social networks acts to propagate information effectively towards egos from distant (and more popular) alters, rather than the other way around. By introducing a null model of social ties in the presence of contact strength we show that this effect is significantly stronger than that expected by chance alone. Furthermore, by examining activity on these alter-alter ties, we find that ego-alter-alter triangles are much more active than expected by triadic closure alone; we introduce another null model for activity on social ties to show this.

Our results shed new light onto the friendship paradox as observed in real social networks, and suggest surprising new results about the information-carrying capacity of these networks for individuals. Whereas the classic friendship paradox suggests that social networks are highly clustered and that typical individuals are relatively well-separated from popular ``infuentials'', our results suggests that real social networks nonetheless have the ability to propagate information between social strata effectively.

ABSTRACT. Across many disciplines, we analyze networks that have been reconstructed or inferred from time series data (e.g., changes in brain activity in neuroscience, shifting stock prices in economics, population dynamics in ecology). These networks can be reconstructed using a variety of techniques, but because different algorithms can output different networks, practitioners are often uncertain about whether their approach is suitable for describing the system in question. Similar to other tools in network science, it appears that no single technique is universally optimal for inferring network structure from time series data, as was recently shown in the case of community detection (Peel, Larremore, & Clauset, 2017). The absence of a "best" technique is likely due to several factors, from the quality or amount of time series data collected, to the nature of the system or dynamics being modeled, to the types of interactions between entities in the system (causal, correlational, weighted, etc.). In this work, we review dozens of network reconstruction techniques in order to characterize the extent to which different techniques will output networks that are similar to one another. The goal of this review is not to provide estimates of the "best" network reconstruction technique but rather to identify approaches that are more likely to infer similar network structures given the same time series data. In doing so, we also systematically compare a number of techniques for measuring network similarity (also known as graph distance).

ABSTRACT. Graph embedding is a fundamental task in machine learning that seeks to build a low-dimensional representation of a graph G. This embedding can then be used for downstream machine learning tasks (such as graph reconstruction, node classification, and link prediction). The intuition behind many popular embedding techniques is that the embedding of a graph must respect node similarity; that is, similar nodes must have representations which are a short distance away from each other. One popular approach that makes such an assumption is the Laplacian Eigenmaps (LE) technique, which constructs a graph embedding based on the spectral properties of the Laplacian matrix of G. Here, we introduce the Geometric Laplacian Eigenmap Embedding (GLEE) by removing the node-distance minimization assumption. Instead, we use the Laplacian matrix to find an embedding that encodes graph structure in a way that is geometric in nature, as opposed to metric (e.g., distance-minimizing) or spectral (as in LE). We compare GLEE to other embedding methods with preliminary results showing that it outperforms LE in the task of graph reconstruction across data sets. Our contributions are two-fold: (1) we propose a new technique that depends solely on the basic properties of the Laplacian matrix and outperforms the well-known and widely used LE; and (2) we break with previous works on graph embedding by focusing on the geometry of the embedding space.

ABSTRACT. Temporal networks are being used to describe numerous social, biological, economic and other real-world phenomena, including urban mobility and the, social interactions of economic transactions. Early -detection of anomalous developments in such networks, e.g. indicating major disruptions in urban function or even potential threats to public safety, is a challenge of a critical importance. While anomaly detection in time-series of certain parameters changing over time is a well-known problem with many state-of-the art approaches, tracking the dynamics of temporal networks is challenged by the complexity of the subject and often also by the noisiness of individual edge weights changing over time. Some recent works address anomaly detection in specific types of networks, like ICT [Ahmed, M. et al. Journal of Network and Computer Applications, 60 (2016)] and social networks [Savage, D., et al. Social Networks 39 (2014)]. In the present work we address the problem of anomaly detection in generic temporal networks, describing various aspects of human or biological activity, by building a network representation framework which consists of three phases: (i) A network pre-processing phase for dimensionality reduction, performing topological aggregation of each slice of the temporal network according to the discovered community structure of the network, (ii) learning the representative feature space through further dimensionality reduction, and (iii) anomaly detection over the final feature space through expectation maximization clustering. The first phase is currently implemented using a COMBO algorithm [Sobolevsky, S., et al. Physical Review E 90.1 (2014): 012811.] which allows for an increase in signal stability and enhanced spatial delineation of impacts. For the second phase we evaluate standard linear dimensionality reduction methods such as principal component analysis and non-linear deep representation learning approaches. The third phase allows to adequately address repeatable temporal patterns in the data. Three major advantages of the proposed network representation approach are: i) Smothering of noise through preliminary network aggregation, ii) ability to learn a limited number of complex features to best reflect the relevant network properties related to the anomalies of interest, iii) ability to largely exclude the weekly and/or seasonal effects by focusing on trend-independent features and/or clustering comparable periods of observation. The approach is successfully evaluated over synthetic data (anomaly recognition accuracy over 80%) as well as available spatio-temporal big data records of human activity, such as taxi and subway trips, social media and mobile app activity. The approach consistently recognizes over 70% of known urban events (such as holidays, protests and weather events) in New York City and Washington DC as well as all 100% of public holidays in Taipei (Taiwan), while having the overall frequency of days detected as anomalous (sensitivity of the approach) of around 25%. The network representation approach also provides a noticeable improvement compared to a baseline anomaly detection through straightforward time-series analysis of the total activity and local network centrality measures, which is only able to recognize 47% of the known events in Washington DC at a comparable sensitivity level. The results demonstrate scalability of the proposed approach across datasets and geographies. Once evaluated, the approach could be applicable for other types of temporal networks, e.g. representing dynamics of financial markets, epidemic outbreaks or brain activity.

ABSTRACT. Predicting missing links in networks is both a common network analysis task and a quantitative means for comparing representations or models of network structure. Past work has shown that both community detection algorithms [1] and structural features [2] exhibit wide variations in their accuracy on link prediction tasks. This diversity of performances suggests that it may be possible to combine different link prediction methods to make predictions that are strictly more accurate than any individual method. In this work, we use model stacking techniques [3] to construct a nearly optimal method for link prediction, which learns how to combine features of three classes of methods: community detection algorithms, structural features, and network embedding algorithms. We evaluate these methods individually, and in stacked combination on synthetic data with known structure, for which we analytically calculate the optimal link prediction performance, and on a large corpus of 572 real-world networks drawn from social, biological, technological, information, economic, and transportation domains. Across settings, the stacking approach, which uses supervised learning to combine features from all three methods classes, is nearly always the best. On synthetic data, stacking can achieve nearly-optimal link prediction scores, suggesting that its observed accuracy on empirical data is likely close to optimal. On real-world networks, we find that link prediction appears to be fundamentally easier in social networks than in other domains, with technological networks being the most difficult. These results shed new light on the limits of predictability of missing links in complex networks, across domains, and demonstrate the utility of learning to combine multiple methods by training on large corpora of real-world networks in order to make nearly-optimal predictions.

ABSTRACT. Contagion phenomena, whether information flow, cascading power grid failures or disease epidemics, are inherently linked to the network structure on which they propagate. Understanding this complex connection is fundamental in promoting or preventing propagation, such as in marketing products or halting an epidemic.

We often observe dynamics without knowledge of the underlying network structure, and reconstruction of the network from these observations becomes crucial for understanding and controlling the diffusion process. Bayesian inference has seen increasing success in a wide variety of contexts and has great potential in network inference to recover distributions over the network space. This empowers us to perform uncertainty quantification and to gain new insights including dominant and secondary influence pathways or understanding ``shadow" networks of unobserved relationships between actors.

We use the well known independent cascade model of information propagation and develop a Bayesian inference method based on Markov Chain Monte Carlo to infer links between individuals. The method samples from the distribution of networks $P(G)$ conditioned on the observation of a set of infections $C$. There are many benefits to this type of network inference. By quantifying the uncertainty, estimates can be obtained with small amounts of data, and known information about edges can be easily incorporated. The method infers the distribution of the underlying network structure, from which a point estimate can be obtained, using cascade data on moderately sized networks, and shows the benefits of understanding the distribution of networks over which the cascade is observed.

ABSTRACT. One promising application of the hyperbolic geometry framework is the prediction of missing links in a network. According to the hyperbolic geometry approach, network nodes are points in the hyperbolic space, and connections are established between points with independent probabilities, which are decreasing functions of distances between the nodes. To predict missing links in a network of interest one first needs to infer node coordinates in the hyperbolic space. Then, link prediction is reduced to the ranking of unconnected node pairs based on the hyperbolic distance between them: the closer the two unlinked nodes are the higher is the probability of a missing link. In our paper we conduct a systematic analysis of the utility of hyperbolic geometry in the link prediction problem. We show that the performance of hyperbolic link prediction is highly sensitive to the accuracy of hyperbolic geometry inference: even a relatively small coordinate inference error may decrease the link prediction accuracy by an order of amplitude. Hence, to achieve accurate link prediction results we developed a novel hyperbolic geometry inference algorithm that outperforms popular link prediction methods on synthetic networks and offers competitive performance on real networks characterized by strong clustering coefficient. The accuracy of the algorithm comes at the price of its scalability. The running time complexity of the algorithm scales quadratically with the network size and, thus, limits its scope to networks of small to moderate size.

ABSTRACT. Perturbations in gene regulatory programs in breast cancer lead to altered gene expression patterns. Different clinical manifestations of breast cancer may exhibit different perturbation profiles, a source for pathological heterogeneity, and the basis for the classification of breast cancer into molecular subtypes. The role of Micro-RNA (miR) regulation in the emergence and maintenance of cancer is a current area of interest for the biomedical community. This phenomenon may be studied using network models. In previous work, our group has modeled the regulatory role of miRs in breast cancer using a bipartite network formalism in which miR – gene regulatory interactions are derived from co-expression measured using mutual information. We have shown the existence of few highly connected, non-redundant miRs, named “commodore miRs” (cdre-miRs), which mostly regulate gene sets involved in specific biological functions deregulated in cancer. A major question is whether all molecular subtypes of breast cancer share the same set of cdre-miRs, or if there are differences either the miRs and/or the functions regulated by them. In this work, we systematically search for cdre-miRs in the context of the four most common molecular subtypes of breast cancer: luminal (A and B), basal, and HER2-enriched. We infer miR – gene bipartite co-expression networks from transcriptomic data retrieved from the Cancer Genome Atlas (TCGA) project for each molecular subtypes. We identify cdre-miRs in each molecular subtype. We compare and contrast the cdre-miRs existing in each breast cancer molecular subtype network, as well as the functions associated to each cdre-miR, providing novel insights on the contribution of miR (de)regulation to the different manifestations of breast cancer.

ABSTRACT. Electrically coupled excitable and passive cells are ubiquitous in biological tissues. In addition to the soma and dendrites of neurons, which are typically excitable and passive, respectively, cells of this nature are found in the heart and uterus, and include myocytes which are excitable in nature, as well as fibroblasts and interstitial Cajal-like cells which are electrically passive. Although these two cell types are quiescent in the absence of an external stimulus, they can exhibit dynamical self-oscillatory activity upon being coupled via gap junctions [1]. The spatiotemporal profiles of the dynamical activity of these cells vary widely. In order to unravel the complexity of the emergent collective behaviour observed in such systems, we systematically investigate, in increasing order of complexity, the dynamics of simple structural motifs in systems consisting of these two cell types. These individual motifs are simple in topology and hence act as building blocks of networks of more complicated connection topologies that are found in biological tissues. We consider different connection topologies formed by these motifs, exploring an array of possible combinations of series and parallel connections between excitable and passive cells. Neuronal connections are an example where such motifs can be seen. We try to answer the open question that whether the complex activity observed in spatially extended systems of coupled excitable and passive cells [2] can be understood by examining the dynamical activity of a small network of these cells. These simple network structures show a wide range of spatiotemporal phenomena ranging from oscillation death to chaos. This includes the surprising coexistence of chaotic and regular activity in different segments of the same network. This investigation may help provide an understanding of the emergence of complex dynamics in electrically coupled heterogenous cell types. This study also demonstrates that much of the observed dynamical complexity of these biological systems may have a simple structural origin.

REFERENCES

[1] V. Jacquemet, Phys. Rev. E 74, 011908 (2006). [2] R. Singh, J. Xu, N. G. Garnier, A. Pumir, and S. Sinha, Phys. Rev. Lett. 108, 068102 (2012).

ABSTRACT. Biological cells and their behaviors are governed by complex gene and chemical reaction networks that process information and guide cellular responses. Interestingly, cells are almost exclusively observed in a relatively small number of states, consistent with the idea that stable “differentiation” states are defined as attractors of an underlying multi-stable gene regulatory network. This provides a powerful framework to predict perturbations that will reprogram cells toward desirable states, by driving gene circuits toward desirable modes, with broad applications in engineering cellular systems and medicine. Nevertheless, precise quantitative details of cellular regulatory networks are generally hard or impossible to obtain. To work around this issue, most research has adopted one of two extremes: (1) impose constraints into the dynamics that are not well-founded by any data, or (2) make predictions based purely on network structure. Here, we propose a probabilistic logic-modeling based approach that strongly constrains the dynamics only in regions of the phase space for which constraining data exists, while remaining unconstrained elsewhere. We define master regulators as genes whose activation destabilizes a given attractor across many models consistent with the data. We likewise define master destabilizers as genes whose activation destabilizes a given attractor. We demonstrate the application of this method to two networks: a previously published differentiation-pluripotency network, and a new drug-resistance network inferred in small-cell lung cancer. Our results reveal that this is a promising technique for identifying key perturbations that can drive cells in desired directions.

ABSTRACT. A promising avenue toward understanding system-level biology is network-based dynamical modeling. In such networks, nodes are biological entities such as proteins or metabolites, edges are interactions or regulations, and the nodes are characterized by state variables that change due to the interactions. Biological phenotypes are interpreted as long-term system-level behaviors (attractors) of the network model. We integrated a published network model [1] with our newly identified protein-protein interactions to understand the crosstalk between two external signals in determining biological phenotypes. Specifically, we focused on the integrated effects of ABA (abscisic acid, a plant hormone) and high CO2 in inducing closure of microscopic pores called stomata. The regulation of stomatal aperture is vital to plants’ response to environmental cues (e.g. light, drought or change of CO2 concentration). Our model recapitulates known experimental results in ABA-induced stomatal closure, and also in the less-understood CO2 or external Ca2+ induced stomatal closure networks. We determined the dynamic repertoire of the network model using our recently-developed general algorithm to identify all attractors of a discrete dynamic model [2]. It is based on an expanded representation integrating the network topology and the regulatory functions that govern the node state variables. Then one can identify self-sustaining motifs (stable or oscillating motifs, respectively) in this network that serve as dynamical cores (similar to points of no return) of the dynamic model. The algorithm finds not only fixed-point attractors but also complex (oscillatory) attractors. We applied the method to the ABA-CO2 crosstalk model to show the motifs and core nodes that drive the system’s behavior. We identified two overlapping and dynamically equivalent stable motifs, both leading to stomatal closure. Each of these motifs depends on a different G-protein alpha subunit: the canonical subunit GPA1 or the noncanonical XLGs (extra-large G-proteins), respectively. The model predicts that XLGs regulate several components in the signal transduction network, making them a key mediator of CO2 or external Ca2+-induced stomatal closure. The model predictions will be assessed experimentally by our collaborative team.

ABSTRACT. We will discuss the concept of an expanded network, which represents causal links between variables in a dynamical system [1,2]. The nodes of such a network are regions of the dynamical state space, and a directed link between two regions indicates that system trajectories in the intersection must exit one region before the other. By constructing and analyzing an expanded network, we can uncover control-robust trap spaces in the state-space of the dynamical system, which we call stable modules. Trap spaces constrain the values of certain variables, and represent decision points in the system’s dynamical repertoire. A stable module is a trap space that is control-robust in the sense that constraints on variables can only be broken by direct external manipulation, as opposed to by control strategies that influence constrained variables via intermediary system variables. Stable modules manifest in the expanded network as source-free subgraphs satisfying certain consistency criteria.

The principal difficulty in applying these methods lies in the selection of regions of interest to consider as nodes in an expanded network. This difficulty is avoided in discrete models, in which we may consider all regions defined by a constraint on a single variable and thereby attain a nearly complete picture of the dynamics.

In other types of models, notably ODEs, a more specialized approach is required. We illustrate a method for constructing expanded networks that makes use of assumptions that are frequently satisfied in ODE models of biomolecular systems. This specialized method exploits monotonicity of regulatory functions to identify parameterized candidate stable modules. We use these candidates to construct a “worst-case” subsystem whose steady states determine state-space regions of interest for inclusion in an expanded network.

[1] Rozum JC, Albert R (2018) J Theo Biol 459 pp 36-44 [2] Rozum JC, Albert R (2018) PLoS Comput Biol 14(12): e1006630.

ABSTRACT. The nature and universality of the biological processes underlying aging in cells and tissues are still unclear. A long-standing paradigm holds that somatic cells accumulate stochastic genetic and epigenetic damages that eventually lead to impaired tissue function or aging related diseases [López-Otín, 2013, Booth, 2016]. The central mechanism by which these molecular damages cause degeneration of tissue functions is by randomly disrupting the proper transcription, leading to malfunctioned group activity of many cells in the tissue [Gems, 2013]. Indeed, in some cell types these age-related changes are manifested as increased cell-to-cell transcriptional variability [Bahar, 2006, Martinez, 2017, Enge, 2017], however, other cell types seem to lack this effect [Warren, 2007]. Thus, despite the generality of this paradigm as a fundamental aging process, we still do not understand its downstream transcriptional outcome in all cell types. Here, we suggest that the main result of the accumulated molecular damages is disturbing the regular coordination between functionally related genes. We develop a new computational method to evaluate the genome-wide level of gene-to-gene transcriptional coordination, without assuming any a priori knowledge of the regulatory network’s structure and its specific interaction type. We apply it to systematically analyze age-related datasets of single-cell transcriptomes from five independent studies, including different organisms: mouse and fruit-fly, and different cell types: long-term (LT) and multipotent progenitor (MPP) hematopoietic stem cells (HSCs), neurons and Glia cells, unstimulated and stimulated naïve and effector memory CD4+ T cells. We find across all tissues and cell types a significant loss of gene-to-gene coordination level during aging. The strength of this aging effect, though, is found to be cell-type-dependent. The coordination levels within and between several functionally related gene-sets (pathways) are profoundly higher compared with random ones, nevertheless, the coordination decrease is largely pathway-independent. These results broadly indicate that loss of gene-to-gene coordination is a key component of the accumulated random damage paradigm, suggesting a possible mechanism for decaying tissue function, and provide a common measure for its effect in different cell types .

ABSTRACT. Heterogeneity is commonly incorporated into epidemiological models by dividing the population into multiple interacting subpopulations. This partitioning captures a variety of characteristics of the whole population; the subpopulations may represent: geographically separated locations, high- and low-risk groups, age structure or multiple species. The strength of interaction, or 'coupling', between two populations can be captured by a single phenomenological parameter; however, a limitation of this approach is how to infer this coupling parameter. Between-population interactions are complex and high quality data on relevant interactions are rarely available; how such data translates into a single coupling parameter is also unclear. We present a method that circumvents this problem by estimating the coupling using more widely-available data on disease incidence. We begin with a stochastic SIR model in P identical interacting subpopulations, where the force of infection in each subpopulation depends on a mixture of within-population and between-population transmission. By making a moment closure approximation we derive an analytic approximation for the correlation between the number of infected individuals in a given pair of subpopulations as a function of the coupling between them. We show that our result holds for a range of parameter values and is supported by stochastic simulations -- considering a measles-like disease as a specific example. We can also reverse this process: the correlation between the number of infected individuals in two populations can be calculated from data on disease incidence and then used in conjunction with our result to estimate the coupling parameter. Crucially, this allows us to estimate the coupling between subpopulations even in the absence of data on human mobility. As heterogeneity is widely-acknowledged to promote to disease persistence, so accurate estimation of coupling parameters could be invaluable to disease eradication research.

ABSTRACT. In the context of spreading processes on networks, an epidemic is localized if the infected (or affected) nodes mostly belong to a certain subgraph (the localization set). A better grasp of this phenomenon for realistic network structures contributes to a sound understanding of spreading processes, for it has important applications, e.g. targeted immunization strategies are very sensitive to the localization regime [1].

Using spectral analysis [1] or compartmental formalism on random networks [2], it is possible to distinguish the different localization regimes. The former approach suggests that the localization set for real networks often corresponds either to the star subgraph associated with the maximal degree node, or to the maximum K-core in a K-core decomposition. However, as far as we know, the role of ubiquitous mesoscopic structures--such as clusters of densely connected communities--remains virtually unexplored, theoretically or otherwise, with regards to localization.

We revisit the SIS model on random networks with heterogeneous cluster sizes [3] and leverage the analytical tractability of the compartmental formalism to identify a dichotomy for the localization, dependent only on the structural properties. In the delocalized regime, all clusters participate to the epidemic, leading to a clean phase transition; in the mesoscopic localization regime, the phase transition is smeared, with the epidemic mostly localized in the largest clusters at the critical point.

Our work establishes the concept of mesoscopic localization in a coherent mathematical formalism and paves the way for the investigation of this phenomenon under various conditions, e.g. non-Markovian and complex contagions. It further suggests that mesoscopic localizations (and the associated localization sets) could be identified in real systems and exploited in targeted immunization strategies.

[1] R. Pastor-Satorras and C. Castellano, J. Stat. Phys. 173, 1110-1123 (2018) [2] G. St-Onge et al., Phys. Rev. E 97, 022305 (2018) [3] L. Hébert-Dufresne et al., Phys. Rev. E 82, 036115 (2010)

ABSTRACT. Networks have been extensively used to describe the connectivity patterns of complex systems of various nature. In particular, they have been used to represent the social structure on which dynamical processes, such as the spreading of diseases or the formation of opinions, occur in a population. However, recent empirical results have shown that the dynamics of social contagion may significantly differ from the those describing the spreading of biological diseases. In fact, the transmission of a biological virus happens through pairwise interactions between the individuals of a population, so it can be well modelled as a spreading process over the links of the underlying network. Contrarily, pairwise interactions are often not enough to characterize the mechanisms behind social contagion processes such as, for instance, the diffusion of opinions or the adoption of norms, where more complex dynamics of peer influence and social reinforcement take place. Here, we introduce the Simplicial Contagion Model (SCM), a novel higher-order modelling framework of social contagion. In the SCM, the structure of a social system is represented as a simplicial complex, and different channels of infections, with different transmission rates, are considered depending on the fact that a contagion can occur on a link (two-body interaction) or is due to a group interaction. Differently from standard networks, simplicial complexes are indeed able to describe in a unified manner not only pairwise but also group interactions of higher-order, by extending the network concept of links between two units to the one of simplices, encoding relations between any number of units. By taking into account these high order interactions between individuals, our model extends the idea of complex contagion by considering not only multiple but also collective exposures. In the SCM, we start from the standard SIS compartmental model in which the population of N individuals is divided into two classes of susceptible (S) and infected (I), and each individual corresponds to a vertex of the simplicial complex representing the social structure. The model of order D, with D ∈ [1, N − 1], is governed by a set of D control parameters B = {β1, β2, . . . , βD}, whose elements represent the probability per unit time for a susceptible node i that participates to a simplex σ of dimension D to get the infection from each one of the subfaces composing σ. With this notation, β1 corresponds to the standard probability of infection β that an infected node i passes the infection to a susceptible one j through the link (i,j), while β2 = β∆ corresponds to the probability that node i receives the infection from the closed triangle (2-simplex) (i,j,k). Finally, the recovery dynamics is controlled by the standard recovery probability μ. After defining a new model for random simplicial complexes that generates simplices of different dimensions, we find that the inclusion of the lowest higer-order interactions is already enough to change the nature of the spreading process from continuous to discontinuous. Through extensive numerical simulations we identify the regions of the parameter space where we observe bistability in the asymptotic density of infectious, with a co-existence of an healthy and an endemic state. We further investigate this phenomena by deriving a mean field (MF) equation for the evolution of density of infected nodes, showing that the steady-state dynamics, the position, and the nature of the transition can be predicted analytically.

ABSTRACT. Going beyond exact representations of temporal networks, there has been a recent surge in the development of methods to create embedding for networks that preserve important properties of the original structure, while representing it in a lower dimensional space. DeepWalk (Perozzi et al., 2014) and node2vec (Grover et al. 2016) are recent network embedding frameworks that were inspired by word embedding used in Natural Language Processing. While they were proved to be useful for anomaly detection or prediction of links in networks, they cannot be used directly for temporal networks. Some other frameworks were also developed specifically for link prediction, (Rahman, et al. 2018) yet any of these methods enable to estimate the outcome of a dynamical process on the original network. This question is relevant to tackle in order to understand what topological and structural structures are keys for dynamical processes. Here we propose a pipeline for temporal network representation learning to estimate epidemic sizes for each event seen as a seed of the spreading process (see Fig. 1). Exploiting similarities between neighbouring events of events in a directed acyclic graph representation of the network (Kivelä et al., 2018) -- to build the embedding -- we are able to estimate the epidemic sizes of some temporal networks with high accuracy. To get a better picture of features we are able to capture with the embedding, we test our approach on various randomized models of real temporal networks. While the method still needs to be refined for some temporal structures, this work is a first step to provide compact representation of networks while possibly highlighting new relevant features for spreading processes on temporal networks.

ABSTRACT. Random walks represent an important tool in the network science community for researchers to better understand structural and dynamical properties of complex networks on both local and nonlocal scales. In this work we introduce and study a family of nonlinear random walks on complex networks, where transition probabilities depend on the current state of the system, thereby changing in time. These systems provide a tool for better modeling more complicated transport across networks that cannot be captured by traditional random walks and yield a rich array of new dynamics.

ABSTRACT. Information-communication technology provides an increasingly accurate picture of human interactions, allowing a detailed mapping of the underlying network structures that mediate contagion processes. In social contagion, characteristic for spreading of innovations, rumours or systemic risk, transmission is a collective phenomenon where all social ties of an individual may be involved. Consequently, degrees (number of links) of nodes are critical to the final dynamical outcome of the spreading process. This behaviour is well captured by threshold models of social contagion on single-layer networks, which predict large-scale cascades of adoption only for relatively sparse networks. Empirical social networks, however, indicate that individuals can maintain hundreds of ties with strength of interaction varying across a range of social contexts. These systems constitute dense and strongly heterogeneous networks that nonetheless exhibit frequent system-wide cascades of social contagion.

We address this issue by incorporating some of the most relevant features of empirical social networks into a conventional threshold model. First, we consider that network ties are heterogeneous and can be characterised by edge “types’’ modelled by multiplex structures. In social networks, due to finite cognitive and time resources, individuals actively maintain limited number of relationships, and organise them into hierarchical intimacy circles that increase in size as they decrease in importance, a phenomenon which can be arguably explained by an entropy maximisation process.

Here we study threshold driven contagion over such heterogeneous multiplex networks organised in weighted layers with hierarchical density. By means of analytical and numerical tools, we show that multiplexity can lead to global cascades in networks with average degree in the hundreds or thousands, perturbed only by a single initial adoption. As a novel observation, we also show that in a multiplex network with increasing link density a sequence of phase transitions occur, resulting in alternating phases of stability and instability to global cascades.

ABSTRACT. Since 2010, research on interdependent networks and networks of networks has been driven by the observation that there can exist more than one type of link in a complex system. For interdependent networks of networks, this is manifest in connectivity links within each network and dependency links between the networks. Nodes function only when they are connected within their network, and the node which they depend on in another network is also connected. This defines a new percolation-based concept of robustness and gives rise to distinctive phenomena including cascading failures and abrupt discontinuous transitions.

However, this approach is limited to cases where connectivity can be taken as a proxy for functionality. In general, functionality of a node is determined by a particular dynamic process. Here, we present new research on interacting network dynamics with multiple link types exhibiting a wide range of new phenomena which are observed in the real-world but absent in previous models. By extending the concept of connectivity and dependency links to dynamical processes, we are able to shed light on real-world complex systems from social networks to the brain.

We begin with a standard Kuramoto model of oscillators on a network but introduce an interaction term between networks, whereby the level of local synchronization around a node in one network either increases or decreases the coupling strength around a corresponding node in another network. When it increases the coupling strength, we have an interdependent interaction. When it decreases the coupling strength we have a competitive interaction. In this way, we can model a rich spectrum of interactions between oscillator networks. We further extend the new framework to interacting diseases, where we find hysteretic transitions and finite basins of stability around the non-endemic phase. This new framework provides a key missing link in the modeling of real-world multilayer networks. The talk is based on our recent manuscript.

ABSTRACT. Complex networks are ubiquitous. Many dynamical processes on networks, including spreading processes such as SIR and SIS, are generally weakly non-linear and the core of the process consists of a diffusion process. However, while the diffusion may have a trivial fixed point where the probability distributions over all nodes becomes uniform or proportional to their degree, the nonlinearity generally results in the trivial fixed point becoming unstable, yielding non-trivial outcomes. As a result, the system relaxes into finite-energy low-energy states. Characterizing the stable low-energy solutions and their multiplicity, thus, allows us to understand the fate of the dynamical process on the network. In real networks with modular and other internal structures, characterizing these outcomes requires numerical simulations.

Here we report discovering a deep connection between these solutions and symmetry groups. In particular, we consider a multi-dimensional weakly non-linear dynamical process on a network and show that it is equivalent to a force-directed layout (FDL) problem. We then show how the topology of the embedding space and its symmetry group can be used to characterize the low-energy solutions to the dynamical process. Many such solutions turn out to be topological in nature.

Mapping such dynamical systems problems on network to one about topology of the embedding affords us with a new set of tools to tackle problems of state counting and stability of dynamical processes on networks.

ABSTRACT. We study rings of experimental nanoelectromechanical (NEMS) oscillators with nearest-neighbor coupling. The dynamical model of these devices incorporates a nonlinear frequency dependence and is readily generalized to include Ginzburg-Landau and other amplitude-phase oscillators. The system is symmetric to rotations and reflections of the ring network, as well as to uniform phase shifts of the oscillators. When the number of oscillators is an integer multiple of four, these symmetries induce dynamically decoupled synchronization: trajectories in which uncoupled next-nearest neighbors are anti-phase locked, yet the phase difference between directly coupled neighbors is arbitrary. All oscillator amplitudes go to unity. The state was recently observed in an experimentally realized ring of eight NEMS oscillators.

We show that the phase configurations of this invariant 2-torus, while also invariant in the first-order reduced phase model, requires the amplitude degrees of freedom for linear stability. The state cannot be linearly stable in phase-only oscillators with pairwise coupling. The symmetry subgroup that predicts the phenomenon also allows for block-diagonalization of the Jacobian, identifying non-interacting four-dimensional subspaces of perturbations. We thus present stability results in closed-form for this phenomenon of dynamically decoupled synchronization on arbitrary size ring networks of amplitude-phase oscillators.

ABSTRACT. In recent years the development of the field of complex systems has been unavoidably bound to that of complex networks [1]. In this context, a network materializes the backbone of the complex interactions between the interacting entities of large systems and consequently the dynamics of such systems is dependent on the topology of the interacting network. Recently, it has been shown that strong non-normality of such complex structures appears to be a universal property of most families of real networks arising from a wide spectrum of fields from biology (neuronal, genetic, proteins) to sociology (communication, citations, social media) passing by ecology (food webs) or transportation (airports) networks [2]. The particular interest in non-normal networks follows from their peculiar dynamical behavior: a linear deterministic process evolving on top of a non-normal network, while being stable, exhibits initially a strong transient amplification before exponentially relaxing to its stable state. It can be proved that this transient instability translates to the possibility of a nonlinear system to converge to a different state from that predicted from the linear stability analysis making the comprehension of the dynamical properties impossible to be captured by the classical spectral methods [3]. In this case more advanced techniques such as the pseudo-spectrum are needed to understand such behaviors [2]. In the realistic scenario, however, a pure deterministic behavior is never possible due to some amount of external noise always present in the surrounding environment or due to endogenous noise stemming from the finite size of the involved system. Based on the Langevin formalism that captures both scenarios, we study the (semi-)Markovian stochastic dynamics of non-normal networked system. At odds with the deterministic description, in the stochastic case the linear system never relaxes to the expected steady state, but at contrary quasi-cyclic behavior is manifested, leading to a “levitation phenomenon”. From the thermodynamical point of view, this means that the mean-field description is unable to predict the lack of relaxation in the thermodynamic limit. For illustrative purpose, we show that a logistic equation on top of a non-normal network manifests a quasi-oscillatory behavior. This result has a huge impact in the understanding of the behavior of real complex systems, in particular, biological ones where oscillatory dynamics are omnipresent.

ABSTRACT. Majority-vote model is a much-studied model for social opinion dynamics of two competing opinions. With the recent appreciation that our social network comprises a variety of different ``layers'' forming a multiplex network, a natural question arises on how such multiplex interactions affect the dynamics of social opinion and consensus formation. Here, generalizing an archetypical model of nonlinear collective social opinion dynamics, the majority-vote model, in multiplex setting, multiplex majority-vote processes are studied on multiplex networks to understand the effect of multiplexity on opinion dynamics [1].

In the original majority-vote model, a node choose its state according to the majority-rule by looking up its neighbors, with additional randomness encoded by the noise parameter. We generalize the original majority-vote model into multiplex networks by introducing two layer-wise decision rules how to incorporate the neighbors' states in different layers. We focus on how global consensus is reached by three different types of voters---what we call the AND- and OR-rule voters---and what different microscopic origins are working in these different types.

Primary findings from the study include that the AND-model tends to reach the greatest consensus below the critical noise level $q_c$. It needs, however, much longer time to reach consensus than other models and the consensus collapses abruptly in the vicinity of the transition point. The OR-model has smaller level of consensus than the AND-rule but it reaches the consensus more quickly thanks to weak endurances. The OR-model exhibits more active dynamics with more opinion flips as well as more disagreements than the AND-model, which render its consensus transition continuous at the critical point. These and other aspects of the two multiplex majority-vote processes will be compared and discussed in detail. The numerical simulation results are supported analytically using approximate master equations.

References [1] J. Choi and K.-I. Goh, ``Majority-vote dynamics on multiplex networks.'' arXiv:1812.03488.

ABSTRACT. Traffic demand is an important component of city traffic, whose variation and fluctuation can have a great influence on the operating state (such as jams) of the traffic system. Many studies that pay much attention to point-to-point traffic demand focus on traffic demand estimation or prediction based on OD (origin-destination) matrix. However, traffic demand in different regions of a city may be coupled and have interaction with others as a flow network from the perspective of network science. Using extensive traffic trajectory data, we study the properties of city’s flow network in certain time period. Our results suggest that the degree distribution, the link weight distribution and the node strength distribution of the flow network follow power-law distribution with different exponents. The Zipf plot curves of flow proportion of various nodes collapse into a single curve, suggesting that the universal driving mechanism behind different locations in a city. We propose method to trace the hierarchical flow formation of congestion regions, to assess the traffic reliability effects of the critical regions. Our results might provide a novel insight in city traffic demand and could be useful in city planning and traffic management.

ABSTRACT. Despite the world becoming highly connected, societies seem to be increasingly polarized and fragmented. All over the globe, nationalist currents and regionalisms gain strength and threaten to radically transform the composition of countries and States as we know them. The basis of this phenomenon is in the complex structure and dynamics of social systems. Far from homogeneously mixing with each other, we self-organize into groups that can span across multiple scales, from families or friends up to cities and cultures. We study the modular structure of society using mobility and communication data obtained from social media. We see that societies are organized in geographical patches where people meet and interact both offline and online, revealing the geometry of the social tissue. The smaller patches can span across neighborhoods while the largest can span across states and countries. Given the challenges that we face as a global society, it is imperative that we learn the way societies are actually structured. The emergence of the structure we observe in the data can be explained with a network growth model that combines the preferential attachment mechanism, the human mobility gravity model and a spatial growth process based on nearest neighbors. In our model, we consider a regular lattice representing a map of geographical locations, simulating the way people travel. Three exponents, , and , control the effects of mechanisms. Model reveals that as highly connected places, cities act like gravity centers attracting human displacements from surrounding areas and creating spatial patches where people inhabit and interact with each other. The model is able to reproduce the heterogeneous spatial patterns of the degree distribution as well as the geographical modular structure of the resulting network.

ABSTRACT. Anecdotally, social connections made in college have life- long impact. Yet knowledge about the actual social networks in college and how they vary across schools remains episodic, due in large part to the difficulty and expense involved in collecting a suitable dataset for comprehensive analysis. To ad- vance and systematize insight into college social networks, we describe a dataset of the largest online social network platform used by college students in the United States. We combine de-identified and aggregated Facebook data with College Scorecard data, campus-level information provided by U.S. Department of Education, to produce a dataset covering the 2008-2014 entry year cohorts for 1,163 U.S. colleges and universities. We find a highly heterogeneous population of networks with consistent structural features across school types. For example, students at private schools have larger networks that are more clustered and with a higher homophily by year. To compare the networks of different sizes, we com- pute features over sampled ego-graphs, train binary classifiers for every pair of graphs, and operationalize distance between graphs as predictive accuracy. Social networks of different year cohorts at the same school are structurally more sim- ilar to one another than to cohorts at other schools. Social networks from similar schools have similar structures, with the public/private and graduation rate dimensions being the most distinguishable. Differences in student populations and in college environments lead to discernible difference in net- work structure.

ABSTRACT. Although many factors are known to determine students’ choices when entering Higher Education, it is still unclear how individual choices relate to organizing principles of Higher Education systems. Here, we contribute to addressing this gap by introducing the Higher Education Space (HES), a network that captures the interdependence structure between degree programs as perceived by applicants. Combining network science methods with the applicants’ revealed preferences in the Portuguese (2008-2015) and Chilean (2006-2017) higher education systems, we show the emergence of a structure characterized by a modular organization. We show the existence of positive assortments in the HES among degree program features, such as the gender balance, application scores, unemployment levels, demand/supply ratio, geographical mobility, and first-year drop-out rates. These assortments indicate that, for instance, if a degree program shows a high/low prevalence of female candidates, then the nearest degree programs in the HES also tend to exhibit a higher/lower prevalence than the average. These patterns extend up to two or three links of separation. A similar pattern in respect to time variations of features also occurs, but not to all. Finally, we provide causal evidence that information embedded in the HES is not accessible by merely considering the features of degree programs independently. Overall, our findings support the HES as a multi-dimensional framework that can effectively contribute to the governance of higher education systems, giving for the first time a glimpse of how applicants perceive the structure of higher education systems.

ABSTRACT. Rising economic inequality challenges today’s workers and policy makers to find new pathways to career suc- cess. However, descriptions of job polarization as a divide between low-skill and high-skill labor are vague. Rather, specific skill requirements determine a worker’s employability and mobility between labor markets. Advancing labor theory to empirical insights requires new methodology that embraces the complexity of workplace skills.

Here, we employ the O*NET skill database to go beyond the canonical cognitive/physical routine/non-routine labor categories [Acemoglu & Autor (2011)]. Using clustering techniques from network science, we construct a job network from shared skill requirements between occupation pairs that turns out to be highly polarized (see Fig. 1A). Our unsupervised methodology adds texture to descriptions of US job polarization by highlighting the specific low-skill and high-skill occupations that underpin the “hollowing of the middle class.”

This improved granularity into occupational skill requirements enables improved models for workers’ career mobility. For comparison, we consider a gravity-based model using national employment in combination with generic coarse labor categories. In support of skill matching’s crucial role in job matching theory [Mortensen & Pissarides (1994)], shared skills predict the flow of workers between job titles (see Fig. 1B). Therefore, the microscopic connections between occupations on the job network may inform policy makers seeking to combat the macroscopic job polarization captured by the overall network topology. For example, occupations that are “far away” on the job network, such as Truck Driver and Software Developer, may identify difficult targets for worker retraining programs (e.g. teaching drivers to program computers).

Anecdotal evidence and migration theory suggest that employment opportunities greatly influence a worker’s decision to relocate [World Migration Report (2015)]. Therefore, urban economies that support similar workers may experience greater spatial flows. To test this idea, we adapt a measure for “tightness” within urban labor mar- kets [Muneepeerakul et al (2013)] to instead measure the tightness of connections between urban labor markets. Combining employment distributions with the job network should identify separate economies with shared oppor- tunity for career mobility and, thereby, approximate inter-city spatial mobility. For comparison, we also consider the canonical gravity model and a simpler measure for the number of shared characteristic occupations between city pairs, which we call the city pair’s overlap. By projecting city’s shared characteristic occupations onto the job network, we find that city pairs with densely connected economies exhibit greater flows of enplaned passengers and census migration (see Fig. 1C). Combined, our results empirically connect occupations’ specific workplace requirements to the career and spatial mobility of US workers.

ABSTRACT. The idea of cities as complex systems lies at the core of seminal theories in different disciplines, from sociology to human geography, that have shaped how we understand and study urban settlements. The recent availability of transport infrastructure networks, thanks to OpenStreetMap (www.openstreetmap.org) along with network science approaches, has offered new insights on the network organization of cities and their transportation modes. In particular, multi-modal infrastructure, where each layer consists of a specific set of links (pedestrian, bicycle infrastructure, streets, and public transportation systems) and nodes represent intersections, can be naturally described by the mathematical framework of multiplex networks. Here we analyze the overlap and completeness of these layers in multiple cities around the world and show that similar patterns arise within distinct classes of cities, using network component analysis and multiplex measures such as a node overlap census. For example, Copenhagen and Amsterdam are distinct in their role of prioritizing cycling networks, while Los Angeles and Jakarta follow a car-centric model. Based on the insights from our network measures, we first introduce a greedy algorithm to detect the most critical missing links in the bicycle layer, showing that small but focused investments allow to significantly increase the efficiency of the bicycle network. We show how this computational approach outlines efficient pathways from car-centric towards sustainable cities by taking advantage of the yet largely untapped potential for multi-modal mobility.

ABSTRACT. Street networks may be planned according to clear organizing principles or they may evolve organically through accretion, but their configurations and orientations help define a city’s spatial logic and order. Measures of entropy help reveal a city’s streets’ order and disorder. Past studies have explored individual cases of orientation and entropy, but little is known about broader patterns and trends worldwide. This study examines street network orientation, configuration, and entropy in 100 cities around the world using OpenStreetMap data and OSMnx. It measures the entropy of street bearings in weighted and unweighted network models, along with each city’s typical street segment length, average circuity, average node degree, and the network’s proportions of four-way intersections and dead-ends. It also develops a new indicator of orientation-order that quantifies how a city’s street network follows the ordering logic of a single grid. It finds significant statistical relationships between a city’s orientation entropy and other indicators of spatial order, including street circuity and measures of connectedness. These indicators, taken in concert, help reveal the extent and nuance of the grid. On average, the US/Canada study sites are far more grid-like than those elsewhere, exhibiting less entropy and circuity. These methods demonstrate automatic, scalable, reproducible tools to empirically measure and visualize city spatial order, illustrating urban transportation system patterns and configurations around the world.

ABSTRACT. We study the inference of a model of dynamic networks in which both communities and links keep memory of previous network states. By considering maximum likelihood inference from single snapshot observations of the network, we show that link persistence makes the inference of communities harder, de- creasing the detectability threshold, while community persistence tends to make it easier. We analytically show that communities inferred from single network snapshot can share a maximum overlap with the underlying communities of a specific previous instant in time. This leads to time-lagged inference: the identification of past communities rather than present ones. Finally we compute the time lag and propose a corrected algorithm, the lagged snapshot dynamic (LSD) algorithm, for community detection in dynamic networks. We analyti- cally and numerically characterize the detectability transitions of such algorithm as a function of the memory parameters of the model and we make a comparison with a full dynamic inference.

ABSTRACT. Latent geometry has been recently shown to be relevant in applied fields of network science such as community detection and greedy routing. However, there have been no general investigations so far on the extent to which latent geometry inspired graph dissimilarities can boost the task of community detection regardless of the particular type of principle adopted in the graph partitioning algorithm (stochastic flow, message passing, modularity optimization, etc...). For instance, Affinity propagation (AP) and Markov Clustering (MCL) are among the most effective algorithms for data clustering in high-dimensional feature space. However the numerous attempts to test their performance for community detection in real complex networks have been attaining results very far from the state of the art methods such as Infomap and Louvain. Indeed, the crucial problem is to convert the network topology in a ‘smart-enough’ pre-weighted connectivity or dissimilarity matrix that is able to properly address the algorithmic procedure behind these clustering techniques. Here we discuss how to leverage network latent geometry notions in order to design weighted matrices for community detection. Our results demonstrate that the dissimilarity measures we designed can boost AP, MCL and also Louvain, not only on several original real networks, but also when their structure is corrupted by noise artificially induced by missing or spurious connectivity. On the other side, further investigations are needed for enhancing Infomap. Finally, the results obtained on real networks are also confirmed in tests performed on synthetic networks generated according to a hyperbolic latent geometry model that induces community structure.

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

ABSTRACT. Nodes in networks have many natural orders. Every centrality measure means we can say if one node has a higher centrality value than another. Many real world networks express an important constraint leading to a characteristic order; examples include publication dates of papers in a citation network, dependency of packages in computer software, and prey species in a food web. If edges respect this order, they exist only if they link a high value node to a lower value node, then edges are directed and there can be no cycles - a Directed Acyclic Graph (DAG).

So in a DAG a link between two nodes represents the order of the pair, not necessarily their similarity as links are often interpreted in standard network analysis. In order to better understand these common network topologies, we need to adapt our tools to make them respect the order implicit in a DAG.

In this work we explore a variation of a community detection algorithm which respects such an order and also finds similar nodes. We take inspiration from classic similarity measures of bibliometrics, used to assess how similar two publications are, based on their relative citation patters. The greater the overlap in the citations or bibliographies of two publications, the more similar they are, whether or not they cite each other. In most real-world cases, the most comparable nodes would be those that belong to the same hierarchical layer, as defined by the order, and which share many common neighbours. Nodes in the same hierarchical layer form an antichain so our algorithm finds antichains with a large neighbourhood overlap.

We do this by adapting the Quality function used in Modularity (Newman & Girvan, 2002) so that it respects the order and uses neighbour overlap to capture similarity. So in terms of adjacency matrix of the DAG A, we optimise the siblinarity S of a node partition defined as (equation not printed) The $\mathfrak{A}$ is a partition of nodes into antichains so each $\Acal$ is a set of disconnected nodes in the DAG.

We study the algorithm's performance and antichain properties in artificial models and in real networks, such as citation graphs and food webs. We show how well this partitioning algorithm distinguishes and groups together nodes of the same origin (in a citation network, the origin is a topic or a research field) as the figure illustrates. We make the comparison between our partitioning algorithm and standard hierarchical layering tools as well as community detection methods. We show that our algorithm outperforms the standard tools in finding similar, yet hierarchically equivalent sets of nodes.

ABSTRACT. In this talk, I’ll show that the community structure of a network can be used as a coarse version of its embedding in a hidden space with hyperbolic geometry. The finding emerges from a systematic analysis of several real-world and synthetic networks. I’ll take advantage of the analogy for reinterpreting results originally obtained through network hyperbolic embedding in terms of community structure only. First, I’ll show that the robustness of a multiplex network can be controlled by tuning the correlation between the community structures across different layers. Second, I’ll show that it is possible to deploy an efficient greedy protocol for network navigability that makes use of routing tables based on community structure.

ABSTRACT. The structure of complex networks is an important aspect in the study of the real network data. Quite often, it is desirable to know the division of the network into communities. A large number of community detection algorithms have been proposed to probe the community structure of complex networks. For a specific partition of a given network, we show that the distribution of modularity under a null hypothesis of free labeling is asymptotically normal when the size of the network gets large. The significance of the partition is defined based on this asymptotic distribution, which can help assess its goodness. A simulation study and a real data analysis are performed for illustration.