Constrained randomization of weighted networks

Time-series-analysis-based detection of critical transitions in real-world non-autonomous systems

Real-world non-autonomous systems are open, out-of-equilibrium systems that evolve in and are driven by temporally varying environments. Such systems can show multiple timescale and transient dynamics together with transitions to very different and, at times, even disastrous dynamical regimes. Since such critical transitions disrupt the systems' intended or desired functionality, it is crucial to understand the underlying mechanisms, to identify precursors of such transitions, and to reliably detect them in time series of suitable system observables to enable forecasts. This review critically assesses the various steps of investigation involved in time-series-analysis-based detection of critical transitions in real-world non-autonomous systems: from the data recording to evaluating the reliability of offline and online detections. It will highlight pros and cons to stimulate further developments, which would be necessary to advance understanding and forecasting nonlinear behavior such as critical transitions in complex systems.

The time-evolving epileptic brain network: concepts, definitions, accomplishments, perspectives

Epilepsy is now considered a network disease that affects the brain across multiple levels of spatial and temporal scales. The paradigm shift from an epileptic focus-a discrete cortical area from which seizures originate-to a widespread epileptic network-spanning lobes and hemispheres-considerably advanced our understanding of epilepsy and continues to influence both research and clinical treatment of this multi-faceted high-impact neurological disorder. The epileptic network, however, is not static but evolves in time which requires novel approaches for an in-depth characterization. In this review, we discuss conceptual basics of network theory and critically examine state-of-the-art recording techniques and analysis tools used to assess and characterize a time-evolving human epileptic brain network. We give an account on current shortcomings and highlight potential developments towards an improved clinical management of epilepsy.

Community detection in multi-frequency EEG networks

Functional connectivity networks of the human brain are commonly studied using tools from complex network theory. Existing methods focus on functional connectivity within a single frequency band. However, it is well-known that higher order brain functions rely on the integration of information across oscillations at different frequencies. Therefore, there is a need to study these cross-frequency interactions. In this paper, we use multilayer networks to model functional connectivity across multiple frequencies, where each layer corresponds to a different frequency band. We then introduce the multilayer modularity metric to develop a multilayer community detection algorithm. The proposed approach is applied to electroencephalogram (EEG) data collected during a study of error monitoring in the human brain. The differences between the community structures within and across different frequency bands for two response types, i.e. error and correct, are studied. The results indicate that following an error response, the brain organizes itself to form communities across frequencies, in particular between theta and gamma bands while a similar cross-frequency community formation is not observed following the correct response.

Network structure from a characterization of interactions in complex systems

Many natural and man-made complex dynamical systems can be represented by networks with vertices representing system units and edges the coupling between vertices. If edges of such a structural network are inaccessible, a widely used approach is to identify them with interactions between vertices, thereby setting up a functional network. However, it is an unsolved issue if and to what extent important properties of a functional network on the global and the local scale match those of the corresponding structural network. We address this issue by deriving functional networks from characterizing interactions in paradigmatic oscillator networks with widely-used time-series-analysis techniques for various factors that alter the collective network dynamics. Surprisingly, we find that particularly key constituents of functional networks—as identified with betweenness and eigenvector centrality—coincide with ground truth to a high degree, while global topological and spectral properties—clustering coefficient, average shortest path length, assortativity, and synchronizability—clearly deviate. We obtain similar concurrences for an empirical network. Our findings are of relevance for various scientific fields and call for conceptual and methodological refinements to further our understanding of the relationship between structure and function of complex dynamical systems.

Patent citation network analysis: A perspective from descriptive statistics and ERGMs

Patent Citation Analysis has been gaining considerable traction over the past few decades. In this paper, we collect extensive information on patents and citations and provide a perspective of citation network analysis of patents from a statistical viewpoint. We identify and analyze the most cited patents, the most innovative and the highly cited companies along with the structural properties of the network by providing in-depth descriptive analysis. Furthermore, we employ Exponential Random Graph Models (ERGMs) to analyze the citation networks. ERGMs enables understanding the social perspectives of a patent citation network which has not been studied earlier. We demonstrate that social properties such as homophily (the inclination to cite patents from the same country or in the same language) and transitivity (the inclination to cite references' references) together with the technicalities of the patents (e.g., language, categories), has a significant effect on citations. We also provide an in-depth analysis of citations for sectors in patents and how it is affected by the size of the same. Overall, our paper delves into European patents with the aim of providing new insights and serves as an account for fitting ERGMs on large networks and analyzing them. ERGMs help us model network mechanisms directly, instead of acting as a proxy for unspecified dependence and relationships among the observations.

Randomization algorithms for large sparse networks

In many domains it is necessary to generate surrogate networks, e.g., for hypothesis testing of different properties of a network. Generating surrogate networks typically requires that different properties of the network are preserved, e.g., edges may not be added or deleted and edge weights may be restricted to certain intervals. In this paper we present an efficient property-preserving Markov chain Monte Carlo method termed CycleSampler for generating surrogate networks in which (1) edge weights are constrained to intervals and vertex strengths are preserved exactly, and (2) edge and vertex strengths are both constrained to intervals. These two types of constraints cover a wide variety of practical use cases. The method is applicable to both undirected and directed graphs. We empirically demonstrate the efficiency of the CycleSampler method on real-world data sets. We provide an implementation of CycleSampler in R, with parts implemented in C.

Surrogate-assisted identification of influences of network construction on evolving weighted functional networks

We aim at identifying factors that may affect the characteristics of evolving weighted networks derived from empirical observations. To this end, we employ various chains of analysis that are often used in field studies for a data-driven derivation and characterization of such networks. As an example, we consider fully connected, weighted functional brain networks before, during, and after epileptic seizures that we derive from multichannel electroencephalographic data recorded from epilepsy patients. For these evolving networks, we estimate clustering coefficient and average shortest path length in a time-resolved manner. Lastly, we make use of surrogate concepts that we apply at various levels of the chain of analysis to assess to what extent network characteristics are dominated by properties of the electroencephalographic recordings and/or the evolving weighted networks, which may be accessible more easily. We observe that characteristics are differently affected by the unavoidable referencing of the electroencephalographic recording, by the time-series-analysis technique used to derive the properties of network links, and whether or not networks were normalized. Importantly, for the majority of analysis settings, we observe temporal evolutions of network characteristics to merely reflect the temporal evolutions of mean interaction strengths. Such a property of the data may be accessible more easily, which would render the weighted network approach-as used here-as an overly complicated description of simple aspects of the data.

Surrogate-assisted network analysis of nonlinear time series

The performance of recurrence networks and symbolic networks to detect weak nonlinearities in time series is compared to the nonlinear prediction error. For the synthetic data of the Lorenz system, the network measures show a comparable performance. In the case of relatively short and noisy real-world data from active galactic nuclei, the nonlinear prediction error yields more robust results than the network measures. The tests are based on surrogate data sets. The correlations in the Fourier phases of data sets from some surrogate generating algorithms are also examined. The phase correlations are shown to have an impact on the performance of the tests for nonlinearity.

Spatial network surrogates for disentangling complex system structure from spatial embedding of nodes

Networks with nodes embedded in a metric space have gained increasing interest in recent years. The effects of spatial embedding on the networks' structural characteristics, however, are rarely taken into account when studying their macroscopic properties. Here, we propose a hierarchy of null models to generate random surrogates from a given spatially embedded network that can preserve certain global and local statistics associated with the nodes' embedding in a metric space. Comparing the original network's and the resulting surrogates' global characteristics allows one to quantify to what extent these characteristics are already predetermined by the spatial embedding of the nodes and links. We apply our framework to various real-world spatial networks and show that the proposed models capture macroscopic properties of the networks under study much better than standard random network models that do not account for the nodes' spatial embedding. Depending on the actual performance of the proposed null models, the networks are categorized into different classes. Since many real-world complex networks are in fact spatial networks, the proposed approach is relevant for disentangling the underlying complex system structure from spatial embedding of nodes in many fields, ranging from social systems over infrastructure and neurophysiology to climatology.

Reconstructing the world trade multiplex: the role of intensive and extensive biases

In economic and financial networks, the strength of each node has always an important economic meaning, such as the size of supply and demand, import and export, or financial exposure. Constructing null models of networks matching the observed strengths of all nodes is crucial in order to either detect interesting deviations of an empirical network from economically meaningful benchmarks or reconstruct the most likely structure of an economic network when the latter is unknown. However, several studies have proved that real economic networks and multiplexes topologically differ from configurations inferred only from node strengths. Here we provide a detailed analysis of the world trade multiplex by comparing it to an enhanced null model that simultaneously reproduces the strength and the degree of each node. We study several temporal snapshots and almost 100 layers (commodity classes) of the multiplex and find that the observed properties are systematically well reproduced by our model. Our formalism allows us to introduce the (static) concept of extensive and intensive bias, defined as a measurable tendency of the network to prefer either the formation of extra links or the reinforcement of link weights, with respect to a reference case where only strengths are enforced. Our findings complement the existing economic literature on (dynamic) intensive and extensive trade margins. More generally, they show that real-world multiplexes can be strongly shaped by layer-specific local constraints.

Node accessibility in cortical networks during motor tasks

Recent findings suggest that the preparation and execution of voluntary self-paced movements are accompanied by the coordination of the oscillatory activities of distributed brain regions. Here, we use electroencephalographic source imaging methods to estimate the cortical movement-related oscillatory activity during finger extension movements. Then, we apply network theory to investigate changes (expressed as differences from the baseline) in the connectivity structure of cortical networks related to the preparation and execution of the movement. We compute the topological accessibility of different cortical areas, measuring how well an area can be reached by the rest of the network. Analysis of cortical networks reveals specific agglomerates of cortical sources that become less accessible during the preparation and the execution of the finger movements. The observed changes neither could be explained by other measures based on geodesics or on multiple paths, nor by power changes in the cortical oscillations.

Incidental and intentional learning of verbal episodic material differentially modifies functional brain networks

Learning- and memory-related processes are thought to result from dynamic interactions in large-scale brain networks that include lateral and mesial structures of the temporal lobes. We investigate the impact of incidental and intentional learning of verbal episodic material on functional brain networks that we derive from scalp-EEG recorded continuously from 33 subjects during a neuropsychological test schedule. Analyzing the networks' global statistical properties we observe that intentional but not incidental learning leads to a significantly increased clustering coefficient, and the average shortest path length remains unaffected. Moreover, network modifications correlate with subsequent recall performance: the more pronounced the modifications of the clustering coefficient, the higher the recall performance. Our findings provide novel insights into the relationship between topological aspects of functional brain networks and higher cognitive functions.

Multivariate recurrence network analysis for characterizing horizontal oil-water two-phase flow

Characterizing complex patterns arising from horizontal oil-water two-phase flows is a contemporary and challenging problem of paramount importance. We design a new multisector conductance sensor and systematically carry out horizontal oil-water two-phase flow experiments for measuring multivariate signals of different flow patterns. We then infer multivariate recurrence networks from these experimental data and investigate local cross-network properties for each constructed network. Our results demonstrate that a cross-clustering coefficient from a multivariate recurrence network is very sensitive to transitions among different flow patterns and recovers quantitative insights into the flow behavior underlying horizontal oil-water flows. These properties render multivariate recurrence networks particularly powerful for investigating a horizontal oil-water two-phase flow system and its complex interacting components from a network perspective.

Robust detection of dynamic community structure in networks

We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations ("optimization variance") and over randomizations of network structure ("randomization variance"). Because the modularity quality function typically has a large number of nearly degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.

Identifying important nodes in weighted functional brain networks: a comparison of different centrality approaches

We compare different centrality metrics which aim at an identification of important nodes in complex networks. We investigate weighted functional brain networks derived from multichannel electroencephalograms recorded from 23 healthy subject under resting-state eyes-open or eyes-closed conditions. Although we observe the metrics strength, closeness, and betweenness centrality to be related to each other, they capture different spatial and temporal aspects of important nodes in these networks associated with behavioral changes. Identifying and characterizing of these nodes thus benefits from the application of several centrality metrics.

Unbiased degree-preserving randomization of directed binary networks

Randomizing networks using a naive "accept-all" edge-swap algorithm is generally biased. Building on recent results for nondirected graphs, we construct an ergodic detailed balance Markov chain with nontrivial acceptance probabilities for directed graphs, which converges to a strictly uniform measure and is based on edge swaps that conserve all in and out degrees. The acceptance probabilities can also be generalized to define Markov chains that target any alternative desired measure on the space of directed graphs in order to generate graphs with more sophisticated topological features. This is demonstrated by defining a process tailored to the production of directed graphs with specified degree-degree correlation functions. The theory is implemented numerically and tested on synthetic and biological network examples.