基于回溯机制的互联网AS拓扑的Betweenness算法

Betweenness能够刻画节点或边在网络中的重要程度.在Internet中,Betweenness直接反应了特定网络拓扑结构下节点或链路可能承载的网络流量,能够对网络的动态行为进行预测.但传统的Be-tweenness计算复杂度较高,为O(n3),但这些算法是为加权网络设计的,而很多实际的网络模型并没有考虑权重.另一方面,目前的算法都没有考虑边的语义,而互联网AS(autonomoussystem)拓扑中的边具有语义.针对简单无权网络提出一种基于回溯的时间复杂度为O(nm)的Betweenness计算方法.在进一步考虑InternetAS拓扑的特殊性,即任意两个相连的AS都具有某种商业关系的基础上提出了互联网AS层拓扑的Betweenness计算方法.

基于流量加权Betweenness提高网络容量的方法

在节点的发包速率和转发包速率都和节点度相关的流量模型中,研究了在基于跳数的最短路径路由策略下网络的容量问题。将Betweenness的概念进行了扩展,提出流量加权Betweenness的概念,使之更准确地描述在每个节点的发包速率各不相同的情况下节点可能承载的流量。并据此推导出适合于该流量模型的网络容量计算公式,同时指出在基于BA算法构造的scale-free网络中,在流量加权Betweenness值处在前5%至10%和前10%至15%的节点间加边的方法能显著提高容量。最后,通过仿真实验验证了该公式的正确性和该方法的有效性。

Evolving networks: from topology to dynamics

A multi-local-world model is introduced to describe the evolving networks that have a localization property such as the Internet. Based on this model, we show that the traffic load defined by 'betweenness centrality' on the multi-local-world scale-free networks' model also follows a power law form. In this kind of network, a few vertices have heavier loads and so play more important roles than the others in the network.

Analysis of cascading failures of power cyber-physical systems considering false data injection attacks

This study considers the performance impacts of false data injection attacks on the cascading failures of a power cyber-physical system,and identifies vulnerable nodes.First,considering the monitoring and control functions of a cyber network and power flow characteristics of a power network,a power cyber-physical system model is established.Then,the influences of a false data attack on the decision-making and control processes of the cyber network communication processes are studied,and a cascading failure analysis process is proposed for the cyber-attack environment.In addition,a vulnerability evaluation index is defined from two perspectives,i.e.,the topology integrity and power network operation characteristics.Moreover,the effectiveness of a power flow betweenness assessment for vulnerable nodes in the cyberphysical environment is verified based on comparing the node power flow betweenness and vulnerability assessment index.Finally,an IEEE14-bus power network is selected for constructing a power cyber-physical system.Simulations show that both the uplink communication channel and downlink communication channel suffer from false data attacks,which affect the ability of the cyber network to suppress the propagation of cascading failures,and expand the scale of the cascading failures.The vulnerability evaluation index is calculated for each node,so as to verify the effectiveness of identifying vulnerable nodes based on the power flow betweenness.

Dynamical robustness of networks based on betweenness against multi-node attack

We explore the robustness of a network against failures of vertices or edges where a fraction of vertices is removed and an overload model based on betweenness is constructed.It is assumed that the load and capacity of vertex are correlated with its betweenness centrality B_(i)as B_(i)^(θ)and(1+α)B_(i)^(θ)(θis the strength parameter,αis the tolerance parameter).We model the cascading failures following a local load preferential sharing rule.It is found that there exists a minimal whenθis between 0 and 1,and its theoretical analysis is given.The minimalα_(c)characterizes the strongest robustness of a network against cascading failures triggered by removing a random fraction f of vertices.It is realized that the minimalα_(c)increases with the increase of the removal fraction f or the decrease of average degree.In addition,we compare the robustness of networks whose overload models are characterized by degree and betweenness,and find that the networks based on betweenness have stronger robustness against the random removal of a fraction f of vertices.

Two Novel Methods to Enhance Network Synchronizability

In this paper, we propose two methods to enhance the synchronizability of a class of complex networks which do not hold the positive correlation between betweenness centrality （BC） and degree of a node, and observe other topology characteristics of the network affected by the methods. Numerical simulations show that both methods can effectively enhance the synchronizability of this kind of networks. Furthermore, we show that the maximal BC of all edges is an important factor to affect the network synchronizability, although it is not the unique factor.

Sewage flow optimization algorithm for large-scale urban sewer networks based on network community division

By considering the flow control of urban sewer networks to minimize the electricity consumption of pumping stations, a decomposition-coordination strategy for energy savings based on network community division is developed in this paper. A mathematical model characterizing the steady-state flow of urban sewer networks is first constructed, consisting of a set of algebraic equations with the structure transportation capacities captured as constraints. Since the sewer networks have no apparent natural hierarchical structure in general, it is very difficult to identify the clustered groups. A fast network division approach through calculating the betweenness of each edge is successfully applied to identify the groups and a sewer network with arbitrary configuration could be then decomposed into subnetworks. By integrating the coupling constraints of the subnetworks, the original problem is separated into N optimization subproblems in accordance with the network decomposition. Each subproblem is solved locally and the solutions to the subproblems are coordinated to form an appropriate global solution. Finally, an application to a specified large-scale sewer network is also investigated to demonstrate the validity of the proposed algorithm.

Complex Networks: Traffic Dynamics, Network Performance, and Network Structure

This paper explores traffic dynamics and performance of complex networks. Complex networks of various structures are studied. We use node betweenness centrality, network polarization, and average path length to capture the structural characteristics of a network. Network throughput, delay, and packet loss are used as network performance measures. We investigate how internal traffic, through put, delay, and packet loss change as a function of packet generation rate, network structure, queue type, and queuing discipline through simulation. Three network states are classified. Further, our work reveals that the parameters chosen to reflect network structure, including node betweenness centrality, network polarization, and average path length, play important roles in different states of the underlying networks.

An Energy-Based Centrality for Electrical Networks

We present an energy-based method to estimate centrality in electrical networks. Here the energy between a pair of vertices denotes by the effective resistance between them. If there is only one generation and one load, then the centrality of an edge in our method is the difference between the energy of network after deleting the edge and that of the original network. Compared with the local current-flow betweenness on the IEEE 14-bus system, we have an interesting discovery that our proposed centrality is closely related to it in the sense of that the significance of edges under the two measures are very similar.

Confidence Intervals for Assessing Sizes of Social Network Centralities

This research uses random networks as benchmarks for inferential tests of network structures. Specifically, we develop formulas for expected values and confidence intervals for four frequently employed social network centrality indices. The first study begins with analyses of stylized networks, which are then perturbed with increasing levels of random noise. When the indices achieve their values for fully random networks, the indices reveal systematic relationships that generalize across network forms. The second study then delves into the relationships between numbers of actors in a network and the density of a network for each of the centrality indices. In doing so, expected values are easily calculated, which in turn enable chi-square tests of network structure. Furthermore, confidence intervals are developed to facilitate a network analyst’s understanding as to which patterns in the data are merely random, versus which are structurally significantly distinct.

Research on LFS Algorithm in Software Network

Betweenness centrality helps researcher to master the changes of the system from the overall perspective in software network. The existing betweenness centrality algorithm has high time complexity but low accuracy. Therefore, Layer First Searching (LFS) algorithm is proposed that is low in time complexity and high in accuracy. LFS algorithm searches the nodes with the shortest to the designated node, then travels all paths and calculates the nodes on the paths, at last get the times of each node being traveled which is betweenness centrality. The time complexity of LFS algorithm is O(V2).

Planning for selective amygdalohippocampectomy involving less neuronal fiber damage based on brain connectivity using tractography

Temporal lobe resection is an important treatment option for epilepsy that involves removal of potentially essential brain regions. Selective amygdalohippocampectomy is a widely performed temporal lobe surgery. We suggest starting the incision for selective amygdalohippocampectomy at the inferior temporal gyrus based on diffusion magnetic resonance imaging（MRI） tractography. Diffusion MRI data from 20 normal participants were obtained from Parkinson＇s Progression Markers Initiative（PPMI） database（www.ppmi-info.org）. A tractography algorithm was applied to extract neuronal fiber information for the temporal lobe, hippocampus, and amygdala. Fiber information was analyzed in terms of the number of fibers and betweenness centrality. Distances between starting incisions and surgical target regions were also considered to explore the length of the surgical path. Middle temporal and superior temporal gyrus regions have higher connectivity values than the inferior temporal gyrus and thus are not good candidates for starting the incision. The distances between inferior temporal gyrus and surgical target regions were shorter than those between middle temporal gyrus and target regions. Thus, the inferior temporal gyrus is a good candidate for starting the incision. Starting the incision from the inferior temporal gyrus would spare the important（in terms of betweenness centrality values） middle region and shorten the distance to the target regions of the hippocampus and amygdala.

Virtual network embedding based on real-time topological attributes

As a great challenge of network virtualization, virtual network embedding/mapping is increasingly important. It aims to successfully and efficiently assign the nodes and links of a virtual network （VN） onto a shared substrate network. The problem has been proved to be NP-hard and some heuristic algorithms have been proposed. However, most of the algorithms use only the local information of a node, such as CPU capacity and bandwidth, to determine how to map a VN, without considering the top- ological attributes which may pose significant impact on the performance of the embedding. In this paper, a new embedding algorithm is proposed based on real-time topological attributes. The concept ofbetweenness centrality in graph theory is borrowed to sort the nodes of VNs, and the nodes of the substrate network are sorted according to the correlation properties between the former selected and unselected nodes. In this way, node mapping and link mapping can be well coupled. A simulator is built to evaluate the performance of the proposed virtual network embedding （VNE） algorithm. The results show that the new algorithm significantly increases the revenue/cost （R/C） ratio and acceptance ratio as well as reduces the runtime.

Control of cascading failures in coupled map lattices based on adaptive predictive pinning control

An adaptive predictive pinning control is proposed to suppress the cascade in coupled map lattices (CMLs).Two monitoring strategies are applied:(1) A specific fraction of nodes with the highest degree or betweenness are chosen to constitute the set of monitored nodes;(2) During the cascade,an adaptive pinning control is implemented,in which only the nodes in the monitored set whose current state is normal but whose predictive state is abnormal,are pinned with the predictive controller.Simulations show that for the scale-free (SF) CML the degree-based monitoring strategy is advantageous over the betweenness-based strategy,while for the small-world (SW) CML the situation is the opposite.With the adaptive predictive pinning control,the fewer local controllers can effectively suppress the cascade throughout the whole network.