Investigation of road network features and safety performance

The analysis of road network designs can provide useful information to transportation planners as they seek to improve the safety of road networks. The objectives of this study were to compare and define the effective road network indices and to analyze the relationship between road network structure and traffic safety at the level of the Traffic Analysis Zone (TAZ). One problem in comparing different road networks is establishing criteria that can be used to scale networks in terms of their structures. Based on data from Orange and Hillsborough Counties in Florida, road network structural properties within TAZs were scaled using 3 indices: Closeness Centrality, Betweenness Centrality, and Meshedness Coefficient. The Meshedness Coefficient performed best in capturing the structural features of the road network. Bayesian Conditional Autoregressive (CAR) models were developed to assess the safety of various network configurations as measured by total crashes, crashes on state roads, and crashes on local roads. The models’ results showed that crash frequencies on local roads were closely related to factors within the TAZs (e.g., zonal network structure, TAZ population), while crash frequencies on state roads were closely related to the road and traffic features of state roads. For the safety effects of different networks, the Grid type was associated with the highest frequency of crashes, followed by the Mixed type, the Loops & Lollipops type, and the Sparse type. This study shows that it is possible to develop a quantitative scale for structural properties of a road network, and to use that scale to calculate the relationships between network structural properties and safety.     

Structural vulnerability of power systems: A topological approach

Vulnerability analysis of power systems is a key issue in modern society and many efforts have contributed to the analysis. Complex network metrics for the assessment of the vulnerability of networked systems have been recently applied to power systems. Complex network theory may come in handy for vulnerability analysis of power systems due to a close link between the topological structure and physical properties of power systems. However, a pure topological approach fails to capture the engineering features of power systems. So an extended topological method has been proposed by incorporating several of specific features of power systems such as electrical distance, power transfer distribution factors and line flow limits. This paper defines, starting from the extended metric for efficiency named as net-ability, an extended betweenness and proposes a joint method of extended betweenness and net-ability to rank the most critical lines and buses in an electrical power grid. The method is illustrated in the IEEE-118-bus, IEEE-300-bus test systems as well as the Italian power grid.     

Robust network planning in nonuniform traffic scenarios

Robustness to the environmental variations is an important feature of any reliable communication network. This paper reports on a network theory approach to the design of such networks where the environmental changes are traffic fluctuations, topology modifications, and changes in the source of external traffic. Motivated by the definition of betweenness centrality in network science, we introduce the notion of traffic-aware betweenness (TAB) for data networks, where usually an explicit (or implicit) traffic matrix governs the distribution of external traffic into the network. We use the average normalized traffic-aware betweenness, which is referred to as traffic-aware network criticality (TANC), as our main metric to quantify the robustness of a network. We show that TANC is directly related to some important network performance metrics, such as average network utilization and average network cost. We prove that TANC is a linear function of end-to-end effective resistances of the graph. As a result, TANC is a convex function of link weights and can be minimized using convex optimization techniques. We use semi-definite programming method to study the properties of the optimization problem and derive useful results to be employed for robust network planning purposes.     

Betweenness parameterized above tight lower bound

We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the Betweenness problem parameterized above its tight lower bound, which is stated as follows. For a set V of variables and set C of constraints “vi is between vj and vk”, decide whether there is a bijection from V to the set {1,…,|V|} satisfying at least |C|/3+κ of the constraints in C. Our result solves an open problem attributed to Benny Chor in Niedermeier's monograph “Invitation to Fixed-Parameter Algorithms”. The betweenness problem is of interest in molecular biology. An approach developed in this paper can be used to determine parameterized complexity of a number of other optimization problems on permutations parameterized above or below tight bounds.     

基于复杂网络理论的无线传感器网络特征度量分析

通过研究复杂网络的理论,介绍了复杂网络的几种主要特征度量,并以此分析了无线传感器网络的特性。列举了无线传感器网络的节点度分布、集聚系数、平均路径长度、网络联通性等特性。研究了节点数、通讯半径、连通率间的关系,由仿真的数据得出,增加节点不能完全保证网络的联通,只能增加联通的概率,而增加通讯半径则可以迅速地使网络联通。因此,在条件允许的情况下,选择通讯半径大的传感器比增加撒布节点更能保证网络的联通。最后给出了适合于无线传感器网络的介数的评价方法。     

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)...     

基于FPGA的稀疏网络关键节点计算的硬件加速方法研究

随着互联网、生物医学及社交网络等复杂网络研究的深入,如何寻找其等效图中关键节点越来越重要。中介中心度作为衡量图中节点重要性的主要指标,其单点的计算复杂度高达O(N3),因而成为关键节点计算问题的难点。该文在对传统的中介中心度快速算法进行分析之后,提出了一种适用于硬件设计的改进算法。同时,基于算法中各点独立、以及相邻计算间无数据依赖的特点,该文利用改进算法实现了一个流水线结构的8计算单元并行计算系统,并在FPGA上完成了硬件系统的设计和验证。通过对比8核CPU软件系统的计算时间,该文的硬件计算系统实现了4.31倍的加速比。     

基于中介中心性提高复杂网络容量的方法

对于像互联网这样具有无标度特征的网络,节点的重要程度差别很大,少数中枢节点成为制约网络容量的瓶颈.引入中介中心性对网络拓扑进行优化和拥塞预测,通过理论分析和仿真实验,考察了网络中节点的介数的和、标准差,两点间最短路径长度,最短路径通过的中枢节点的个数等参数与网络容量的关系.最终提出在具有无标度特征的复杂网络中,依据网络中节点的介数以及介数的标准差增加一些捷径路径的方法.该方法简单易行,能有效平衡中枢节点的负载,缓解拥塞状况,提高网络容量.     

复杂网络算法中K—shell与介数中心性算法的实现

复杂网络中实现节点的中心性有许多算法,这些算法可以让人们快速识别出各种社交环境中的核心人物与话题。常用的中心性指标有度中心性．介数中心性、紧密中心性、特征向量中心性和K—shell分解方法。但是现有的理论中,仅仅提及算法的概念,并且实现的复杂性过高,算法的提及更多是用于分析阶段。为了解决这个问题,主要提出介数中心性指标和K—shell分解方法的程序实现。以便更好地应用于各种场合。