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

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

复杂网络牵制控制优化选点算法及节点组重要性排序

本文研究复杂网络动力学模型的无向网络牵制控制的优化选点及节点组重要性排序问题.根据牵制控制的同步准则,网络的牵制控制同步取决于网络的Laplacian删后矩阵的最小特征值.因此,通过合理选择受控节点集得到一个较大的Laplacian删后矩阵最小特征值,是牵制控制优化选点问题的核心所在.基于Laplacian删后矩阵最小特征值的图谱性质,本文提出了多个受控节点选取的递归迭代算法,该算法适用于任意类型的网络.通过BA无标度网络、NW小世界网络及一些实际网络中的仿真实验表明:该算法在控制节点数较少时,能有效找到最优受控节点集.最后讨论了在复杂网络牵制控制背景下节点组重要性排序问题,提出节点组的重要性排序与受控节点的数目有关.     

一种基于势博弈的无线传感器网络拓扑控制算法

在实际的应用中,无线传感器网络常常由大量电池资源有限的传感器节点组成.如何降低网络功耗,最大化网络生存时间,是传感器网络拓扑控制技术的重要研究目标.随着传感节点的运行,节点的能量分布可能越来越不均衡,需要在考虑该因素的情况下,动态地调整节点的网络负载以均衡节点的能耗,达到延长网络生存时间的目的.该文引入博弈理论和势博弈的概念,综合考虑节点的剩余能量和节点发射功率等因素,设计了一种基于势博弈的拓扑控制模型,并证明了该模型纳什均衡的存在性.通过构造兼顾节点连通性和能耗均衡性的收益函数,以确保降低节点功耗的同时维持网络的连通性.通过提高邻居节点的平均剩余能量值以实现将剩余能量多的节点选择作为自身的邻居节点,提高节点能耗的均衡性.在此基础上,提出了一种分布式的能耗均衡拓扑控制算法.理论分析证明了该算法能保持网络的连通性.与现有基于博弈理论的DIA算法和MLPT算法相比,本算法形成的拓扑负载较重、剩余能量较小的瓶颈节点数量较少,节点剩余能量的方差较小,网络生存时间更长.     

Ranking important nodes in complex networks by simulated annealing

In this paper, based on simulated annealing a new method to rank important nodes in complex networks is presented.First, the concept of an importance sequence(IS) to describe the relative importance of nodes in complex networks is defined. Then, a measure used to evaluate the reasonability of an IS is designed. By comparing an IS and the measure of its reasonability to a state of complex networks and the energy of the state, respectively, the method finds the ground state of complex networks by simulated annealing. In other words, the method can construct a most reasonable IS. The results of experiments on real and artificial networks show that this ranking method not only is effective but also can be applied to different kinds of complex networks.     

Network connectivity entropy and its application on network connectivity reliability

The network structure entropy has served as one of the index measuring network heterogeneity, but it gives no considerations to the impact of isolated nodes on the network structure. In addition, the all-terminal reliability is zero and is unable to compare it between disconnected networks. Therefore, the concept of network connectivity entropy is suggested to remove the current bottleneck and helps facilitate new index in terms of network connectivity reliability. This study fully proves the rules as follows: when the edges of network are diminishing, the newly-established network connectivity reliability will remain unchanged or become weaker; conversely, when the edges of network are increasing, the network connectivity reliability will remain unchanged or become stronger. Thus, the proposed index of network connectivity reliability is proved reasonable. Furthermore, the impaired metro network of Nanjing city is exemplified to demonstrate the validity and practicability of network connectivity reliability. The result shows that this new approach is in good position to compute network connectivity reliability quickly and effectively, and also to compare it between different networks.     

Optimization and scale-freeness for complex networks

Complex networks are mapped to a model of boxes and balls where the balls are distinguishable. It is shown that the scale-free size distribution of boxes maximizes the information associated with the boxes provided configurations including boxes containing a finite fraction of the total amount of balls are excluded. It is conjectured that for a connected network with only links between different nodes, the nodes with a finite fraction of links are effectively suppressed. It is hence suggested that for such networks the scale-free node-size distribution maximizes the information encoded on the nodes. The noise associated with the size distributions is also obtained from a maximum entropy principle. Finally, explicit predictions from our least bias approach are found to be borne out by metabolic networks.     

Hierarchical Characterization of Complex Networks

While the majority of approaches to the characterization of complex networks has relied on measurements considering only the immediate neighborhood of each network node, valuable information about the network topological properties can be obtained by considering further neighborhoods. The current work considers the concept of virtual hierarchies established around each node and the respectively defined hierarchical node degree and clustering coefficient (introduced in cond-mat/0408076), complemented by new hierarchical measurements, in order to obtain a powerful set of topological features of complex networks. The interpretation of such measurements is discussed, including an analytical study of the hierarchical node degree for random networks, and the potential of the suggested measurements for the characterization of complex networks is illustrated with respect to simulations of random, scale-free and regular network models as well as real data (airports, proteins and word associations). The enhanced characterization of the connectivity provided by the set of hierarchical measurements also allows the use of agglomerative clustering methods in order to obtain taxonomies of relationships between nodes in a network, a possibility which is also illustrated in the current article.     

面向结构洞的复杂网络关键节点排序

复杂网络中的结构洞节点对于信息传播具有重要作用, 现有关键节点排序方法多数没有兼顾结构洞节点和其他类型的关键节点进行排序. 本文根据结构洞理论与关键节点排序相关研究选取了网络约束系数、介数中心性、等级度、效率、网络规模、PageRank值以及聚类系数7个度量指标, 将基于ListNet的排序学习方法引入到复杂网络的关键节点排序问题中, 融合7个度量指标, 构建了一个能够综合评价面向结构洞节点的关键节点排序方法. 采用模拟网络和实际复杂网络进行了大量实验, 人工标准试验结果表明本文排序方法能够综合考虑结构洞节点和核心节点, 关键节点排序与人工排序结果具有较高的一致性. SIR传播模型评估实验结果表明由本文选择TOP-K节点发起的传播能够在较短的传播时间内达到最大的传播范围.     

The structural role of weak and strong links in a financial market network

We investigate the properties of correlation based networks originating from economic complex systems, such as the network of stocks traded at the New York Stock Exchange (NYSE). The weaker links (low correlation) of the system are found to contribute to the overall connectivity of the network significantly more than the strong links (high correlation). We find that nodes connected through strong links form well defined communities. These communities are clustered together in more complex ways compared to the widely used classification according to the economic activity. We find that some companies, such as General Electric (GE), Coca Cola (KO), and others, can be involved in different communities. The communities are found to be quite stable over time. Similar results were obtained by investigating markets completely different in size and properties, such as the Athens Stock Exchange (ASE). The present method may be also useful for other networks generated through correlations.     

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

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

Controlling a complex dynamical network to attain an inhomogeneous equilibrium

Many networks are made up of a few groups, with nodes in the same group having the same kind of function. In this work, the problem of controlling a complex dynamical network to attain an inhomogeneous equilibrium point is investigated, which means that nodes in the same group achieve the same equilibrium point as an isolated node, while different groups correspond to different equilibrium points. An open-loop constant control approach is first proposed to obtain the inhomogeneous equilibrium point of the network. Then, the feedback pinning control approach is applied to make the inhomogeneous equilibrium point asymptotically stable.     

Cost and effect of pinning control for network synchronization

The problem of pinning control for the synchronization of complex dynamical networks is discussed in this paper. A cost function of the controlled network is defined by the feedback gain and the coupling strength of the network. An interesting result is that a lower cost is achieved by using the control scheme of pinning nodes with smaller degrees. Some strict mathematical analyses are presented for achieving a lower cost in the synchronization of different star-shaped networks. Numerical simulations on some non-regular complex networks generated by the Barabási--Albert model and various star-shaped networks are performed for verification and illustration.     

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.     

Stochastic thermodynamics: principles and perspectives

Stochastic thermodynamics provides a framework for describing small systems like colloids or biomolecules driven out of equilibrium but still in contact with a heat bath. Both, a first-law like energy balance involving exchanged heat and entropy production entering refinements of the second law can consistently be defined along single stochastic trajectories. Various exact relations involving the distribution of such quantities like integral and detailed fluctuation theorems for total entropy production and the Jarzynski relation follow from such an approach based on Langevin dynamics. Analogues of these relations can be proven for any system obeying a stochastic master equation like, in particular, (bio)chemically driven enzyms or whole reaction networks. The perspective of investigating such relations for stochastic field equations like the Kardar-Parisi-Zhang equation is sketched as well.     

Identifying Important Nodes in Complex Networks Based on Node Propagation Entropy

In recent years, the identification of the essential nodes in complex networks has attracted significant attention because of their theoretical and practical significance in many applications, such as preventing and controlling epidemic diseases and discovering essential proteins. Several importance measures have been proposed from diverse perspectives to identify crucial nodes more accurately. In this paper, we propose a novel importance metric called node propagation entropy, which uses a combination of the clustering coefficients of nodes and the influence of the first- and second-order neighbor numbers on node importance to identify essential nodes from an entropy perspective while considering the local and global information of the network. Furthermore, the susceptible–infected–removed and susceptible–infected–removed–susceptible epidemic models along with the Kendall coefficient are used to reveal the relevant correlations among the various importance measures. The results of experiments conducted on several real networks from different domains show that the proposed metric is more accurate and stable in identifying significant nodes than many existing techniques, including degree centrality, betweenness centrality, closeness centrality, eigenvector centrality, and H-index.     

Concentric characterization and classification of complex network nodes: Application to an institutional collaboration network

Differently from theoretical scale-free networks, most real networks present multi-scale behavior, with nodes structured in different types of functional groups and communities. While the majority of approaches for classification of nodes in a complex network has relied on local measurements of the topology/connectivity around each node, valuable information about node functionality can be obtained by concentric (or hierarchical) measurements. This paper extends previous methodologies based on concentric measurements, by studying the possibility of using agglomerative clustering methods, in order to obtain a set of functional groups of nodes, considering particular institutional collaboration network nodes, including various known communities (departments of the University of São Paulo). Among the interesting obtained findings, we emphasize the scale-free nature of the network obtained, as well as identification of different patterns of authorship emerging from different areas (e.g. human and exact sciences). Another interesting result concerns the relatively uniform distribution of hubs along concentric levels, contrariwise to the non-uniform pattern found in theoretical scale-free networks such as the BA model.     

Information Dimension of Stochastic Processes on Networks: Relating Entropy Production to Spectral Properties

We consider discrete stochastic processes, modeled by classical master equations, on networks. The temporal growth of the lack of information about the system is captured by its non-equilibrium entropy, defined via the transition probabilities between different nodes of the network. We derive a relation between the entropy and the spectrum of the master equation’s transfer matrix. Our findings indicate that the temporal growth of the entropy is proportional to the logarithm of time if the spectral density shows scaling. In analogy to chaos theory, the proportionality factor is called (stochastic) information dimension and gives a global characterization of the dynamics on the network. These general results are corroborated by examples of regular and of fractal networks.     

Rethinking failure and attack tolerance assessment in complex networks

Studies have revealed that real complex networks are inherently vulnerable to the loss of high centrality nodes. These nodes are crucial to maintaining the network connectivity and are identified by classical measures, such as degree and betweenness centralities. Despite its significance, an assessment based solely on this vulnerability premise is misleading for the interpretation of the real state of the network concerning connectivity. As a matter of fact, some networks may be in a state of imminent fragmentation before such a condition is fully characterized by an analysis targeted solely on the centrally positioned nodes. This work aims at showing that, in fact, it is basically the global network configuration that is responsible for network fragmentation, as it may allow many other lower centrality nodes to seriously damage the network connectivity.     

Communication on the structure of biological networks

Networks are widely used to represent interaction pattern among the components in complex systems. Structures of real networks from different domains may vary quite significantly. As there is an interplay between network architecture and dynamics, structure plays an important role in communication and spreading of information in a network. Here we investigate the underlying undirected topology of different biological networks which support faster spreading of information and are better in communication. We analyse the good expansion property by using the spectral gap and communicability between nodes. Different epidemic models are also used to study the transmission of information in terms of spreading of disease through individuals (nodes) in those networks. Moreover, we explore the structural conformation and properties which may be responsible for better communication. Among all biological networks studied here, the undirected structure of neuronal networks not only possesses the small-world property but the same is also expressed remarkably to a higher degree compared to any randomly generated network which possesses the same degree sequence. A relatively high percentage of nodes, in neuronal networks, form a higher core in their structure. Our study shows that the underlying undirected topology in neuronal networks, in a significant way, is qualitatively different from the same in other biological networks and that they may have evolved in such a way that they inherit a (undirected) structure which is excellent and robust in communication.