Improving robustness of complex networks via the effective graph resistance

Improving robustness of complex networks is a challenge in several application domains, such as power grids and water management networks. In such networks, high robustness can be achieved by optimizing graph metrics such as the effective graph resistance, which is the focus of this paper. An important challenge lies in improving the robustness of complex networks under dynamic topological network changes, such as link addition and removal. This paper contributes theoretical and experimental findings about the robustness of complex networks under two scenarios: (i) selecting a link whose addition maximally decreases the effective graph resistance; (ii) protecting a link whose removal maximally increases the effective graph resistance. Upper and lower bounds of the effective graph resistance under these topological changes are derived. Four strategies that select single links for addition or removal, based on topological and spectral metrics, are evaluated on various synthetic and real-world networks. Furthermore, this paper illustrates a novel comparison method by considering the distance between the added or removed links, optimized according to the effective graph resistance and the algebraic connectivity. The optimal links are different in most cases but in close proximity.     

Entropy-Based Graph Clustering of PPI Networks for Predicting Overlapping Functional Modules of Proteins

Functional modules can be predicted using genome-wide protein–protein interactions (PPIs) from a systematic perspective. Various graph clustering algorithms have been applied to PPI networks for this task. In particular, the detection of overlapping clusters is necessary because a protein is involved in multiple functions under different conditions. graph entropy (GE) is a novel metric to assess the quality of clusters in a large, complex network. In this study, the unweighted and weighted GE algorithm is evaluated to prove the validity of predicting function modules. To measure clustering accuracy, the clustering results are compared to protein complexes and Gene Ontology (GO) annotations as references. We demonstrate that the GE algorithm is more accurate in overlapping clusters than the other competitive methods. Moreover, we confirm the biological feasibility of the proteins that occur most frequently in the set of identified clusters. Finally, novel proteins for the additional annotation of GO terms are revealed.     

复杂网络中节点重要性排序的研究进展

如何用定量分析的方法识别超大规模网络中哪些节点最重要, 或者评价某个节点相对于其他一个或多个节点的重要程度, 这是复杂网络研究中亟待解决的重要问题之一. 本文分别从网络结构和传播动力学的角度, 对现有的复杂网络中节点重要性排序方法进行了系统的回顾,总结了节点重要性排序方法的最新研究进展, 并对不同的节点重要性排序指标的优缺点以及适用环境进行了分析, 最后指出了这一领域中几个有待解决的问题及可能的发展方向. 关键词： 复杂网络 节点重要性 网络结构 传播动力学     

TOLOMEO,a Novel Machine Learning Algorithm to Measure Information and Order in Correlated Networks and Predict Their State

We present ToloMEo (TOpoLogical netwOrk Maximum Entropy Optimization), a program implemented in C and Python that exploits a maximum entropy algorithm to evaluate network topological information. ToloMEo can study any system defined on a connected network where nodes can assume N discrete values by approximating the system probability distribution with a Pottz Hamiltonian on a graph. The software computes entropy through a thermodynamic integration from the mean-field solution to the final distribution. The nature of the algorithm guarantees that the evaluated entropy is variational (i.e., it always provides an upper bound to the exact entropy). The program also performs machine learning, inferring the system’s behavior providing the probability of unknown states of the network. These features make our method very general and applicable to a broad class of problems. Here, we focus on three different cases of study: (i) an agent-based model of a minimal ecosystem defined on a square lattice, where we show how topological entropy captures a crossover between hunting behaviors; (ii) an example of image processing, where starting from discretized pictures of cell populations we extract information about the ordering and interactions between cell types and reconstruct the most likely positions of cells when data are missing; and (iii) an application to recurrent neural networks, in which we measure the information stored in different realizations of the Hopfield model, extending our method to describe dynamical out-of-equilibrium processes.     

Dynamic Topology Reconfiguration of Boltzmann Machines on Quantum Annealers

Boltzmann machines have useful roles in deep learning applications, such as generative data modeling, initializing weights for other types of networks, or extracting efficient representations from high-dimensional data. Most Boltzmann machines use restricted topologies that exclude looping connectivity, as such connectivity creates complex distributions that are difficult to sample. We have used an open-system quantum annealer to sample from complex distributions and implement Boltzmann machines with looping connectivity. Further, we have created policies mapping Boltzmann machine variables to the quantum bits of an annealer. These policies, based on correlation and entropy metrics, dynamically reconfigure the topology of Boltzmann machines during training and improve performance.     

Robustness measurement of scale-free networks based on motif entropy

As a classical complex network model, scale-free network is widely used and studied. And motifs, as a high-order subgraph structure, frequently appear in scale-free networks, and have a great influence on the structural integrity, functional integrity and dynamics of the networks. In order to overcome the shortcomings in the existing work on the robustness of complex networks, only nodes or edges are considered, while the defects of high-order structure in the network are ignored. From the perspective of network motif, we propose an entropy of node degree distribution based on motif to measure the robustness of scale-free networks under random attacks. The effectiveness and superiority of our method are verified and analyzed in the BA scale-free networks.     

Entropy-based link prediction in weighted networks

Information entropy has been proved to be an effective tool to quantify the structural importance of complex networks.In a previous work [Xu et al. Physica A, 456 294(2016)], we measure the contribution of a path in link prediction with information entropy. In this paper, we further quantify the contribution of a path with both path entropy and path weight,and propose a weighted prediction index based on the contributions of paths, namely weighted path entropy(WPE), to improve the prediction accuracy in weighted networks. Empirical experiments on six weighted real-world networks show that WPE achieves higher prediction accuracy than three other typical weighted indices.     

基于通信序列熵的复杂网络传输容量

网络的传输性能在一定程度上依赖于网络的拓扑结构.本文从结构信息的角度分析复杂网络的传输动力学行为,寻找影响网络传输容量的信息结构测度指标.通信序列熵可以有效地量化网络的整体结构信息,为了表征网络整体传输能力,把通信序列熵引入到复杂网络传输动力学分析中,研究网络的通信序列熵与传输性能之间的关联特性,分析这种相关性存在的内在机理.分别在BA无标度和WS小世界网络模型上进行仿真,结果显示:网络的通信序列熵与其传输容量存在密切关联性,随着通信序列熵的增加,网络拓扑结构的均匀性随之增强,传输容量明显增加.网络的传输容量是通信序列熵的单调递增函数,与通信序列熵成正关联关系.通信序列熵可有效评估网络的传输容量,本结论可为设计高传输容量网络提供理论依据.     

基于K-阶结构熵的网络异构性研究

结构熵可以考察复杂网络的异构性.为了弥补传统结构熵在综合刻画网络全局以及局部特性能力上的不足,本文依据网络节点在K步内可达的节点总数定义了K-阶结构熵,可从结构熵随K值的变化规律、最大K值下的结构熵以及网络能够达到的最小结构熵三个方面来评价网络的异构性.利用K-阶结构熵对规则网络、随机网络、Watts-Strogatz小世界网络、Barabási_-Albert无标度网络以及星型网络进行了理论研究与仿真实验,结果表明上述网络的异构性依次增强.其中K-阶结构熵能够较好地依据小世界属性来刻画小世界网络的异构性,且对星型网络异构性随其规模演化规律的解释也更为合理.此外, K-阶结构熵认为在规则结构外新增孤立节点的网络的异构性弱于未添加孤立节点的规则结构,但强于同节点数的规则网络.本文利用美国西部电网进一步论证了K-阶结构熵的有效性.     

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.     

Structural Entropy of the Stochastic Block Models

With the rapid expansion of graphs and networks and the growing magnitude of data from all areas of science, effective treatment and compression schemes of context-dependent data is extremely desirable. A particularly interesting direction is to compress the data while keeping the “structural information” only and ignoring the concrete labelings. Under this direction, Choi and Szpankowski introduced the structures (unlabeled graphs) which allowed them to compute the structural entropy of the Erdős–Rényi random graph model. Moreover, they also provided an asymptotically optimal compression algorithm that (asymptotically) achieves this entropy limit and runs in expectation in linear time. In this paper, we consider the stochastic block models with an arbitrary number of parts. Indeed, we define a partitioned structural entropy for stochastic block models, which generalizes the structural entropy for unlabeled graphs and encodes the partition information as well. We then compute the partitioned structural entropy of the stochastic block models, and provide a compression scheme that asymptotically achieves this entropy limit.     

A Two-Parameter Fractional Tsallis Decision Tree

Decision trees are decision support data mining tools that create, as the name suggests, a tree-like model. The classical C4.5 decision tree, based on the Shannon entropy, is a simple algorithm to calculate the gain ratio and then split the attributes based on this entropy measure. Tsallis and Renyi entropies (instead of Shannon) can be employed to generate a decision tree with better results. In practice, the entropic index parameter of these entropies is tuned to outperform the classical decision trees. However, this process is carried out by testing a range of values for a given database, which is time-consuming and unfeasible for massive data. This paper introduces a decision tree based on a two-parameter fractional Tsallis entropy. We propose a constructionist approach to the representation of databases as complex networks that enable us an efficient computation of the parameters of this entropy using the box-covering algorithm and renormalization of the complex network. The experimental results support the conclusion that the two-parameter fractional Tsallis entropy is a more sensitive measure than parametric Renyi, Tsallis, and Gini index precedents for a decision tree classifier.     

Extractive summarization using complex networks and syntactic dependency

The realization that statistical physics methods can be applied to analyze written texts represented as complex networks has led to several developments in natural language processing, including automatic summarization and evaluation of machine translation. Most importantly, so far only a few metrics of complex networks have been used and therefore there is ample opportunity to enhance the statistics-based methods as new measures of network topology and dynamics are created. In this paper, we employ for the first time the metrics betweenness, vulnerability and diversity to analyze written texts in Brazilian Portuguese. Using strategies based on diversity metrics, a better performance in automatic summarization is achieved in comparison to previous work employing complex networks. With an optimized method the Rouge score (an automatic evaluation method used in summarization) was 0.5089, which is the best value ever achieved for an extractive summarizer with statistical methods based on complex networks for Brazilian Portuguese. Furthermore, the diversity metric can detect keywords with high precision, which is why we believe it is suitable to produce good summaries. It is also shown that incorporating linguistic knowledge through a syntactic parser does enhance the performance of the automatic summarizers, as expected, but the increase in the Rouge score is only minor. These results reinforce the suitability of complex network methods for improving automatic summarizers in particular, and treating text in general.     

Dynamics of load entropy during cascading failure propagation in scale-free networks

In this Letter, we introduce the concept of load entropy, which can be an average measure of a network's heterogeneity in the load distribution. Then we investigate the dynamics of load entropy during failure propagation using a new cascading failures load model, which can represent the node removal mechanism in many real-life complex systems. Simulation results show that in the early stage of failure propagation the load entropy for a larger cascading failure increases more sharply than that for a smaller one, and consequently the cascading failure with a larger damage can be identified at the early stage of failure propagation according to the load entropy. Particularly, load entropy can be used as an index to be optimized in cascading failures control and defense in many real-life complex networks.     

A Generalized Measure of Cumulative Residual Entropy

In this work, we introduce a generalized measure of cumulative residual entropy and study its properties. We show that several existing measures of entropy, such as cumulative residual entropy, weighted cumulative residual entropy and cumulative residual Tsallis entropy, are all special cases of this generalized cumulative residual entropy. We also propose a measure of generalized cumulative entropy, which includes cumulative entropy, weighted cumulative entropy and cumulative Tsallis entropy as special cases. We discuss a generating function approach, using which we derive different entropy measures. We provide residual and cumulative versions of Sharma–Taneja–Mittal entropy and obtain them as special cases this generalized measure of entropy. Finally, using the newly introduced entropy measures, we establish some relationships between entropy and extropy measures.     

Entropy Production in Exactly Solvable Systems

The rate of entropy production by a stochastic process quantifies how far it is from thermodynamic equilibrium. Equivalently, entropy production captures the degree to which global detailed balance and time-reversal symmetry are broken. Despite abundant references to entropy production in the literature and its many applications in the study of non-equilibrium stochastic particle systems, a comprehensive list of typical examples illustrating the fundamentals of entropy production is lacking. Here, we present a brief, self-contained review of entropy production and calculate it from first principles in a catalogue of exactly solvable setups, encompassing both discrete- and continuous-state Markov processes, as well as single- and multiple-particle systems. The examples covered in this work provide a stepping stone for further studies on entropy production of more complex systems, such as many-particle active matter, as well as a benchmark for the development of alternative mathematical formalisms.     

A Quantitative Comparison between Shannon and Tsallis–Havrda–Charvat Entropies Applied to Cancer Outcome Prediction

In this paper, we propose to quantitatively compare loss functions based on parameterized Tsallis–Havrda–Charvat entropy and classical Shannon entropy for the training of a deep network in the case of small datasets which are usually encountered in medical applications. Shannon cross-entropy is widely used as a loss function for most neural networks applied to the segmentation, classification and detection of images. Shannon entropy is a particular case of Tsallis–Havrda–Charvat entropy. In this work, we compare these two entropies through a medical application for predicting recurrence in patients with head–neck and lung cancers after treatment. Based on both CT images and patient information, a multitask deep neural network is proposed to perform a recurrence prediction task using cross-entropy as a loss function and an image reconstruction task. Tsallis–Havrda–Charvat cross-entropy is a parameterized cross-entropy with the parameter α . Shannon entropy is a particular case of Tsallis–Havrda–Charvat entropy for α=1 . The influence of this parameter on the final prediction results is studied. In this paper, the experiments are conducted on two datasets including in total 580 patients, of whom 434 suffered from head–neck cancers and 146 from lung cancers. The results show that Tsallis–Havrda–Charvat entropy can achieve better performance in terms of prediction accuracy with some values of α .     

Quantifying information loss on chaotic attractors through recurrence networks

We propose an entropy measure for the analysis of chaotic attractors through recurrence networks which are un-weighted and un-directed complex networks constructed from time series of dynamical systems using specific criteria. We show that the proposed measure converges to a constant value with increase in the number of data points on the attractor (or the number of nodes on the network) and the embedding dimension used for the construction of the network, and clearly distinguishes between the recurrence network from chaotic time series and white noise. Since the measure is characteristic to the network topology, it can be used to quantify the information loss associated with the structural change of a chaotic attractor in terms of the difference in the link density of the corresponding recurrence networks. We also indicate some practical applications of the proposed measure in the recurrence analysis of chaotic attractors as well as the relevance of the proposed measure in the context of the general theory of complex networks.     

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.     

基于脑电图的大脑功能性网络分析

利用脑电图数据建立了大脑功能性网络.分析了该网络的复杂网络统计特征，发现它的聚类系数远大于相应随机网络，明显具有小世界网络的特征，其度分布也接近于无标度网络.进一步验证了大脑功能性网络的复杂网络特性，发现患者的各项复杂网络特征指数与正常人相比有明显不同.定义了大脑神经网络信息熵及神经网络标准信息熵的概念，发现脑病患者的大脑神经网络信息熵明显小于正常人.从一个全新的角度量度了大脑的复杂网络特征，并提示了临床脑病诊疗的判断依据. 关键词： 脑电图 大脑功能性网络 复杂网络统计特征 信息熵