Schedule

Communication asymmetry in the human connectome: A cortical hierarchy of senders

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.

Stability, Specificity, and Generalizability of Connectome Predictive Modeling

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.

Functional brain network topology discriminates between patients with minimally conscious state and unresponsive wakefulness syndrome

Consciousness arises from the functional interaction of multiple brain structures and their ability to integrate different complex patterns of internal communication. Although several studies demonstrated that the fronto-parietal and default mode functional networks play a key role in conscious processes, it is still not clear which topological network measures (that quantifies different features of whole-brain functional network organization) are altered in patients with disorders of consciousness (DOC). Herein, we investigate the functional connectivity of unresponsive wakefulness syndrome (UWS) and minimally conscious state (MCS) patients from a topological network perspective, by using resting state EEG recording. Network-based statistical analysis reveals a subnetwork of decreased functional connectivity in UWS compared to the MCS patients, mainly involving the interhemispheric fronto-parietal connectivity patterns. Network topological analysis reveals increased values of Local-Community-Paradigm correlation, as well as higher clustering coefficient and local efficiency in UWS patients compared to MCS patients. This is the first time that LCP-corr is measured in patients with DoC. At the nodal level, the UWS patients showed altered functional 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 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 community-oriented topological organization in UWS may represent an epiphenomenon of diffusely emergent (possibly) dysfunctional connections, resulting in aberrant self-reinforcing loops. Taken together, our results highlight i) the involvement of the interhemispheric fronto-parietal functional connectivity in the pathophysiology of consciousness disorders and ii) an aberrant connectome organization both at the network topology and at the nodal level in UWS compared to the MCS patients.

Multidimensional framework based on functional connectivity traits for task independent individual fingerprinting

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.

Task specificity is shaped by a diversity of functional network kernel: Implications for neurological movement disorders

Classification of Individuals with Psychiatric Disorders Based on Structural Brain Network Properties

Epidemic containment driven by link importance

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.

Modelling Disease Spillover Using Multipartite Networks

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.

Disease spreading on directed multilayer networks

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.

Realistic modeling of disease spreading in multiplex networks

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.

Impact of the distribution of recovery rates on disease spreading in complex networks

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.

How Self-Excitement Dynamics Affects Epidemic Spreading in Time-Varying Networks

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.

Uniform redundancy allocation maximizes the robustness of flow networks under random and targeted attacks

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.

Preferential Abandonment induces Structural Collapse in Robust Networks: Evidence from Scientific Fields and Technology Products

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.

Tree distribution approximation for finite networks

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 Analysi

s 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.

Selective percolation: Modeling enzymatic degradation of network polymers

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.

Switch between critical percolation modes in city traffic dynamics

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.

Comparing methods for reconstructing networks from time series data by comparing methods for measuring network similarity

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).

GLEE: Geometric Laplacian Eigenmap Embedding

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.

Anomaly detection in temporal networks

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.