Chaos synchronization in networks of coupled maps with time-varying topologies

Complexity of dynamical networks can arise not only from the complexity of the topological structure but also from the time evolution of the topology. In this paper, we study the synchronous motion of coupled maps in time-varying complex networks both analytically and numerically. The temporal variation is rather general and formalized as being driven by a metric dynamical system. Four network models are discussed in detail in which the interconnections between vertices vary through time randomly. These models are: 1) i.i.d. sequences of random graphs with fixed wiring probability, 2) groups of graphs with random switches between the individual graphs, 3) graphs with temporary random failures of nodes, and 4) the meet-for-dinner model where the vertices are randomly grouped. We show that the temporal variation and randomness of the connection topology can enhance synchronizability in many cases; however, there are also instances where they reduce synchronizability. In analytical terms, the Hajnal diameter of the coupling matrix sequence is presented as a measure for the synchronizability of the graph topology. In topological terms, the decisive criterion for synchronization of coupled chaotic maps is that the union of the time-varying graphs contains a spanning tree.     

Stability and dynamical properties of material flow systems on random networks

The theory of complex networks and of disordered systems is used to study the stability and dynamical properties of a simple model of material flow networks defined on random graphs. In particular we address instabilities that are characteristic of flow networks in economic, ecological and biological systems. Based on results from random matrix theory, we work out the phase diagram of such systems defined on extensively connected random graphs, and study in detail how the choice of control policies and the network structure affects stability. We also present results for more complex topologies of the underlying graph, focussing on finitely connected Erdös-Réyni graphs, Small-World Networks and Barabási-Albert scale-free networks. Results indicate that variability of input-output matrix elements, and random structures of the underlying graph tend to make the system less stable, while fast price dynamics or strong responsiveness to stock accumulation promote stability.     

Clustering and community detection in directed networks: A survey

Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed — in the sense that there is directionality on the edges, making the semantics of the edges nonsymmetric as the source node transmits some property to the target one but not vice versa. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of relevant application domains. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs — with clustering being the primary method sought and the primary tool for community detection and evaluation. The goal of this paper is to offer an in-depth comparative review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions.     

Random graph models for dynamic networks

Recent theoretical work on the modeling of network structure has focused primarily on networks that are static and unchanging, but many real-world networks change their structure over time. There exist natural generalizations to the dynamic case of many static network models, including the classic random graph, the configuration model, and the stochastic block model, where one assumes that the appearance and disappearance of edges are governed by continuous-time Markov processes with rate parameters that can depend on properties of the nodes. Here we give an introduction to this class of models, showing for instance how one can compute their equilibrium properties. We also demonstrate their use in data analysis and statistical inference, giving efficient algorithms for fitting them to observed network data using the method of maximum likelihood. This allows us, for example, to estimate the time constants of network evolution or infer community structure from temporal network data using cues embedded both in the probabilities over time that node pairs are connected by edges and in the characteristic dynamics of edge appearance and disappearance. We illustrate these methods with a selection of applications, both to computer-generated test networks and real-world examples.     

Rewiring dynamical networks with prescribed degree distribution for enhancing synchronizability

In this paper, we present an algorithm for enhancing synchronizability of dynamical networks with prescribed degree distribution. The algorithm takes an unweighted and undirected network as input and outputs a network with the same node-degree distribution and enhanced synchronization properties. The rewirings are based on the properties of the Laplacian of the connection graph, i.e., the eigenvectors corresponding to the second smallest and the largest eigenvalues of the Laplacian. A term proportional to the eigenvectors is adopted to choose potential edges for rewiring, provided that the node-degree distribution is preserved. The algorithm can be implemented on networks of any sizes as long as their eigenvalues and eigenvectors can be calculated with standard algorithms. The effectiveness of the proposed algorithm in enhancing the network synchronizability is revealed by numerical simulation on a number of sample networks including scale-free, Watts-Strogatz, and Erdo?s-Re?nyi graphs. Furthermore, a number of network's structural parameters such as node betweenness centrality, edge betweenness centrality, average path length, clustering coefficient, and degree assortativity are tracked as a function of optimization steps.     

The network analysis of urban streets: A dual approach

The application of the network approach to the urban case poses several questions in terms of how to deal with metric distances, what kind of graph representation to use, what kind of measures to investigate, how to deepen the correlation between measures of the structure of the network and measures of the dynamics on the network, what are the possible contributions from the GIS community. In this paper, the author considers six cases of urban street networks characterized by different patterns and historical roots. The authors propose a representation of the street networks based firstly on a primal graph, where intersections are turned into nodes and streets into edges. In a second step, a dual graph, where streets are nodes and intersections are edges, is constructed by means of a generalization model named Intersection Continuity Negotiation, which allows to acknowledge the continuity of streets over a plurality of edges. Finally, the authors address a comparative study of some structural properties of the dual graphs, seeking significant similarities among clusters of cases. A wide set of network analysis techniques are implemented over the dual graph: in particular the authors show that the absence of any clue of assortativity differentiates urban street networks from other non-geographic systems and that most of the considered networks have a broad degree distribution typical of scale-free networks and exhibit small-world properties as well.     

Consensus on de Bruijn graphs

We study the consensus dynamics with or without time-delays on directed and undirected de Bruijn graphs. Our results show that consensus on an undirected de Bruijn graph has a lower converging speed and larger time-delay tolerance in comparison with that on an undirected scale-free network. Although there is not much difference between the eigenvalue ratios of the two undirected networks, we found that their dynamical properties are remarkably different; consequently, it is seemingly more informative to consider the second smallest and the largest eigenvalues separately rather than considering their ratio in the study of synchronization of a coupled oscillators network. Moreover, our study on directed de Bruijn graphs reveals that properly setting directions on edges can improve the converging speed and time-delay tolerance simultaneously.     

Planar unclustered scale-free graphs as models for technological and biological networks

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases — usually associated with topological restrictions — their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular several families of technological and biological networks, and in the design of new practical communication algorithms in relation to their dynamical processes. They can also help understanding the underlying mechanisms that have produced their particular structure.     

Components in time-varying graphs

Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, today it is possible to produce and analyze social and biological networks with detailed information on the time of occurrence and duration of each link. However, standard graph metrics introduced so far in complex network theory are mainly suited for static graphs, i.e., graphs in which the links do not change over time, or graphs built from time-varying systems by aggregating all the links as if they were concurrent in time. In this paper, we extend the notion of connectedness, and the definitions of node and graph components, to the case of time-varying graphs, which are represented as time-ordered sequences of graphs defined over a fixed set of nodes. We show that the problem of finding strongly connected components in a time-varying graph can be mapped into the problem of discovering the maximal-cliques in an opportunely constructed static graph, which we name the affine graph. It is, therefore, an NP-complete problem. As a practical example, we have performed a temporal component analysis of time-varying graphs constructed from three data sets of human interactions. The results show that taking time into account in the definition of graph components allows to capture important features of real systems. In particular, we observe a large variability in the size of node temporal in- and out-components. This is due to intrinsic fluctuations in the activity patterns of individuals, which cannot be detected by static graph analysis.     

Weighted complex network analysis of travel routes on the Singapore public transportation system

The structure and properties of public transportation networks have great implications for urban planning, public policies and infectious disease control. We contribute a complex weighted network analysis of travel routes on the Singapore rail and bus transportation systems. We study the two networks using both topological and dynamical analyses. Our results provide additional evidence that a dynamical study adds to the information gained by traditional topological analysis, providing a richer view of complex weighted networks. For example, while initial topological measures showed that the rail network is almost fully connected, dynamical measures highlighted hub nodes that experience disproportionately large traffic. The dynamical assortativity of the bus networks also differed from its topological counterpart. In addition, inspection of the weighted eigenvector centralities highlighted a significant difference in traffic flows for both networks during weekdays and weekends, suggesting the importance of adding a temporal perspective missing from many previous studies.     

Are networks with more edges easier to synchronize,or not？

In this paper, the relationship between network synchronizability and the edge-addition of its associated graph is investigated. First, it is shown that adding one edge to a cycle definitely decreases the network synchronizability. Then, since sometimes the synchronizability can be enhanced by changing the network structure, the question of whether the networks with more edges are easier to synchronize is addressed. Based on a subgraph and complementary graph method, it is shown by examples that the answer is negative even if the network structure is arbitrarily optimized. This reveals that generally there are redundant edges in a network, which not only make no contributions to synchronization but actually may reduce the synchronizability. Moreover, a simple example shows that the node betweenness centrality is not always a good indicator for the network synchronizability. Finally, some more examples are presented to illustrate how the network synchronizability varies following the addition of edges, where all the examples show that the network synchronizability globally increases but locally fluctuates as the number of added edges increases.     

基于多路可视图的健康与心梗患者心电图信号复杂网络识别

可视图(visibility graph, VG)算法已被证明是将时间序列转换为复杂网络的简单且高效的方法,其构成的复杂网络在拓扑结构中继承了原始时间序列的动力学特性.目前,单维时间序列的可视图分析已趋于成熟,但应用于复杂系统时,单变量往往无法描述系统的全局特征.本文提出一种新的多元时间序列分析方法,将心梗和健康人的12导联心电图(electrocardiograph, ECG)信号转换为多路可视图,以每个导联为一个节点,两个导联构成可视图的层间互信息为连边权重,将其映射到复杂网络.由于不同人群的全连通网络表现为完全相同的拓扑结构,无法唯一表征不同个体的动力学特征,根据层间互信息大小重构网络,提取权重度和加权聚类系数,实现对不同人群12导联ECG信号的识别.为判断序列长度对识别效果的影响,引入多尺度权重度分布熵.由于健康受试者拥有更高的平均权重度和平均加权聚类系数,其映射网络表现为更加规则的结构、更高的复杂性和连接性,可以与心梗患者进行区分,两个参数的识别准确率均达到93.3%.     

Ricci Curvature-Based Semi-Supervised Learning on an Attributed Network

In recent years, on the basis of drawing lessons from traditional neural network models, people have been paying more and more attention to the design of neural network architectures for processing graph structure data, which are called graph neural networks (GNN). GCN, namely, graph convolution networks, are neural network models in GNN. GCN extends the convolution operation from traditional data (such as images) to graph data, and it is essentially a feature extractor, which aggregates the features of neighborhood nodes into those of target nodes. In the process of aggregating features, GCN uses the Laplacian matrix to assign different importance to the nodes in the neighborhood of the target nodes. Since graph-structured data are inherently non-Euclidean, we seek to use a non-Euclidean mathematical tool, namely, Riemannian geometry, to analyze graphs (networks). In this paper, we present a novel model for semi-supervised learning called the Ricci curvature-based graph convolutional neural network, i.e., RCGCN. The aggregation pattern of RCGCN is inspired by that of GCN. We regard the network as a discrete manifold, and then use Ricci curvature to assign different importance to the nodes within the neighborhood of the target nodes. Ricci curvature is related to the optimal transport distance, which can well reflect the geometric structure of the underlying space of the network. The node importance given by Ricci curvature can better reflect the relationships between the target node and the nodes in the neighborhood. The proposed model scales linearly with the number of edges in the network. Experiments demonstrated that RCGCN achieves a significant performance gain over baseline methods on benchmark datasets.     

Offdiagonal complexity: A computationally quick complexity measure for graphs and networks

A vast variety of biological, social, and economical networks shows topologies drastically differing from random graphs; yet the quantitative characterization remains unsatisfactory from a conceptual point of view. Motivated from the discussion of small scale-free networks, a biased link distribution entropy is defined, which takes an extremum for a power-law distribution. This approach is extended to the node–node link cross-distribution, whose nondiagonal elements characterize the graph structure beyond link distribution, cluster coefficient and average path length. From here a simple (and computationally cheap) complexity measure can be defined. This offdiagonal complexity (OdC) is proposed as a novel measure to characterize the complexity of an undirected graph, or network. While both for regular lattices and fully connected networks OdC is zero, it takes a moderately low value for a random graph and shows high values for apparently complex structures as scale-free networks and hierarchical trees. The OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates.     

Networks of strong ties

Social networks transmitting covert or sensitive information cannot use all ties for this purpose. Rather, they can only use a subset of ties that are strong enough to be “trusted”. This paper addresses whether it is still possible, under this restriction, for information to be transmitted widely and rapidly in social networks. We use transitivity as evidence of strong ties, requiring one or more shared contacts in order to count an edge as strong. We examine the effect of removing all non-transitive ties in two real social network data sets, imposing varying thresholds in the number of shared contacts. We observe that transitive ties occupy a large portion of the network and that removing all other ties, while causing some individuals to become disconnected, preserves the majority of the giant connected component. Furthermore, the average shortest path, important for the rapid diffusion of information, increases only slightly relative to the original network. We also evaluate the cost of forming transitive ties by modeling a random graph composed entirely of closed triads and comparing its connectivity and average shortest path with the equivalent Erdös–Renyi random graph. Both the empirical study and random model point to a robustness of strong ties with respect to the connectivity and small world property of social networks.     

Modelling epidemics on networks

Infectious disease remains, despite centuries of work to control and mitigate its effects, a major problem facing humanity. This paper reviews the mathematical modelling of infectious disease epidemics on networks, starting from the simplest Erdös–Rényi random graphs, and building up structure in the form of correlations, heterogeneity and preference, paying particular attention to the links between random graph theory, percolation and dynamical systems representing transmission. Finally, the problems posed by networks with a large number of short closed loops are discussed.     

Enhancing the network synchronizability

The structural and dynamical properties, particularly the small-world effect and scale-free feature, of complex networks have attracted tremendous interest and attention in recent years. This article offers a brief review of one focal issue concerning the structural and dynamical behaviors of complex network synchronization. In the presentation, the notions of synchronization of dynamical systems on networks, stability of dynamical networks, and relationships between network structure and synchronizability, will be first introduced. Then, various technical methods for enhancing the network synchronizability will be discussed, which are roughly divided into two classes: Structural Modification and Coupling-Pattern Regulation, where the former includes three typical methods—dividing hub nodes, shortening average distances, and deleting overload edges, while the latter mainly is a method of strengthening the hub-nodes’ influence on the network.      

Synchronization in power-law networks

We consider realistic power-law graphs, for which the power-law holds only for a certain range of degrees. We show that synchronizability of such networks depends on the expected average and expected maximum degree. In particular, we find that networks with realistic power-law graphs are less synchronizable than classical random networks. Finally, we consider hybrid graphs, which consist of two parts: a global graph and a local graph. We show that hybrid networks, for which the number of global edges is proportional to the number of total edges, almost surely synchronize.     

TLP-CCC: Temporal Link Prediction Based on Collective Community and Centrality Feature Fusion

In the domain of network science, the future link between nodes is a significant problem in social network analysis. Recently, temporal network link prediction has attracted many researchers due to its valuable real-world applications. However, the methods based on network structure similarity are generally limited to static networks, and the methods based on deep neural networks often have high computational costs. This paper fully mines the network structure information and time-domain attenuation information, and proposes a novel temporal link prediction method. Firstly, the network collective influence (CI) method is used to calculate the weights of nodes and edges. Then, the graph is divided into several community subgraphs by removing the weak link. Moreover, the biased random walk method is proposed, and the embedded representation vector is obtained by the modified Skip-gram model. Finally, this paper proposes a novel temporal link prediction method named TLP-CCC, which integrates collective influence, the community walk features, and the centrality features. Experimental results on nine real dynamic network data sets show that the proposed method performs better for area under curve (AUC) evaluation compared with the classical link prediction methods.     

Synchronization in asymmetrically coupled networks with node balance

We study global stability of synchronization in asymmetrically connected networks of limit-cycle or chaotic oscillators. We extend the connection graph stability method to directed graphs with node balance, the property that all nodes in the network have equal input and output weight sums. We obtain the same upper bound for synchronization in asymmetrically connected networks as in the network with a symmetrized matrix, provided that the condition of node balance is satisfied. In terms of graphs, the symmetrization operation amounts to replacing each directed edge by an undirected edge of half the coupling strength. It should be stressed that without node balance this property in general does not hold.