一种基于离散数据从局部到全局的网络重构算法

网络的结构和功能彼此相互影响,网络上的功能往往体现为网络上的动力学过程,网络上的动力学过程通过网络中的行为表象数据进行体现.因此,根据网络上可观测的相关数据对网络结构进行重构将成为可能.本文拟解决如何根据网络上可观测的离散数据还原网络拓扑结构的问题,提出了在网络局部利用每一条离散数据对应节点的相似程度来推测节点间发生连边的可能性,通过多条离散数据重构网络各个局部拓扑并将由多条数据得到的局部拓扑进行叠加,最终重构出整个网络的全局拓扑结构的算法.为了验证算法的可行性与准确性,在小世界、无标度和随机网络中进行了网络重构实验,通过在三种不同类型及不同规模的网络中进行网络重构实验可以看出,网络重构算法在不同类型网络中的表现也不同,且网络的平均度值也会影响网络重构算法对数据的要求.为了验证算法的适用性,对三个实际网络进行了网络重构实验,结果显示算法能够适用实际较大规模网络的重构.该算法具有很好的适用性和准确度,适合不同类型网络的拓扑结构重构场景.     

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.     

一种新的复杂网络影响力最大化发现方法

复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一, 其研究在理论和现实应用中都有重大的意义. 在给定s值的前提下, 如何寻找发现s个最大影响范围的节点集, 这是个组合优化问题, Kempe等已经证明该问题是NP-hard问题. 目前已有的随机算法时间复杂度低, 但是结果最差; 其他贪心算法时间复杂度很高, 不能适用于大型社会网络中, 并且这些典型贪心算法必须以了解网络的全局信息为前提, 而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的. 我们提出了一种新的影响力最大化算法模型RMDN, 及改进的模型算法RMDN++, 模型只需要知道随机选择的节点以及其邻居节点信息, 从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题, 算法的时间复杂度仅为O(s log(n)); 然后, 我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示, RMDN, RMDN++算法有着和现有典型算法相近的影响力传播效果, 且有时还略优, 同时在运行时间上则有显著的提高; 我们从理论上推导证明了方法的可行性. 本文所提出的模型算法适用性更广, 可操作性更强, 为这项具有挑战性研究提供了新的思路和方法.     

Routing and wavelength assignment in wavelength-routed all-optical WDM networks

In this paper, low-complexity mathematical model has been developed which is used for the calculation of the blocking probability of network and this model does not require any simulation statistics. The implementation of the model proposed has less complexity and the computation used in this model is quite efficient. The routing algorithm has also been proposed in this paper depending upon the proposed model, which is very efficient in calculation and minimization of the blocking probability. This algorithm suggests an optimum path as a solution to routing problem. The wavelength assignment technique has also been suggested in this paper to minimize the blocking probability. The proposed model and algorithms can be implemented on different network topologies. Furthermore, the model, routing algorithm and wavelength assignment technique is also used to evaluate the blocking performance of NSFNet and EUPAN Network topology and hence used to improve its performance on the basis of the blocking probability.     

一种无线传感器网络健壮性可调的能量均衡拓扑控制算法

无线传感器网络中, 应用环境的干扰导致节点间距不能被准确度量. 所以利用以节点间距作为权重的闭包图(EG)模型构建的拓扑没有考虑环境的干扰, 忽略了这部分干扰带来的能耗, 缩短了网络生存时间. 针对无线传感器网络拓扑能量不均的特点和EG模型的缺陷, 首先引入节点度调节因子, 建立通信度量模型和节点实际生存时间模型; 其次量化网络节点度, 从而获取满足能量均衡和网络生命期最大化需求的节点度的取值规律; 然后利用该取值规律和函数极值充分条件解析推导出网络最大能量消耗值和最长生存时间, 并获得最优节点度; 最后基于以上模型提出一种健壮性可调的能量均衡拓扑控制算法. 理论证明该拓扑连通且为双向连通. 仿真结果说明网络能利用最优节点度达到较高的健壮性, 保证信息可靠传输, 且算法能有效平衡节点能耗, 提高网络健壮性, 延长网络生命周期.     

确定度分布条件下可变同配系数的算法构造与影响分析

复杂网络是现实中大量节点和边的抽象拓扑, 如何揭示网络内部拓扑对网络连通性、脆弱性等特征的影响是当前研究的热点. 本文在确定度分布的条件下, 根据Newman提出的同配系数的定义分析其影响因素. 首先在可变同配系数下分别提出了基于度分布的确定算法和基于概率分布的不确定算法, 并分别在三种不同类型的网络(Erdös-Rényi网络, Barabási-Albert网络, Email真实网络)中验证. 实验结果表明: 当网络规模达到一定程度时, 确定算法优于贪婪算法. 以此为基础, 分析了同配系数改变时聚类系数的变化, 发现两者之间存在关联性, 并从网络的微观结构变化中揭示了聚类系数变化的原因.     

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

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

Detection of influential nodes with multi-scale information

The identification of influential nodes in complex networks is one of the most exciting topics in network science. The latest work successfully compares each node using local connectivity and weak tie theory from a new perspective. We study the structural properties of networks in depth and extend this successful node evaluation from single-scale to multi-scale. In particular, one novel position parameter based on node transmission efficiency is proposed, which mainly depends on the shortest distances from target nodes to high-degree nodes. In this regard, the novel multi-scale information importance (MSII) method is proposed to better identify the crucial nodes by combining the network's local connectivity and global position information. In simulation comparisons, five state-of-the-art algorithms, i.e. the neighbor nodes degree algorithm (NND), betweenness centrality, closeness centrality, Katz centrality and the k-shell decomposition method, are selected to compare with our MSII. The results demonstrate that our method obtains superior performance in terms of robustness and spreading propagation for both real-world and artificial networks.     

一种带物理约束的光网络业务量疏导方法

提出了基于最大收益的捆绑疏导算法(MRA)来解决光网络中具有多种物理约束的业务量疏导问题。MRA首先在物理拓扑上逐个放置业务, 随后捆绑细粒度业务、实现管道实例化。即考虑业务的路由情况, 将其在物理拓扑上的路由都视为单跳的细粒度管道, 然后使用基于深度优先搜索的方法来检查哪些业务能够捆绑到一起形成多跳粗粒度的潜在管道, 以节省中间节点的细粒度交换容量。再从这些粗粒度的潜在管道中, 使用最大收益的方法遴选出具有最大成本收益的无冲突集合, 并加以实例化。仿真结果显示, 在处理多个物理约束时, MRA在容量和实现成本上均优于现有的算法, 并且它能处理多达百个节点以上的大网络中的业务量疏导问题。     

虚拟机在舰艇编队一体化防御系统中的应用

面对信息化、远程精确打击的空袭作战,必须构建网络化、一体化的防空作战体系;主要针对舰艇编队一体化防御系统中无线网络的不可靠性,设计了基于嵌入式虚拟机的架构,提出了任务的动态分配和移植算法;首先根据作战环境中网络的拓扑条件,虚拟机动态的将控制任务分配到可靠的无线节点中,并实时监测网络状态,当网络结构发生变化时,将底层不可靠无线节点中的控制任务移植到可靠的无线节点中;通过这种方法可以解决作战环境恶劣和无线网络本身的不可靠引起的控制的不稳定性问题,确保防御任务的顺利进行;仿真结果表明,当编队一体化防御系统的链路发生故障时,此方法能够在不改变原有控制算法的基础上,迅速重建控制构架,不仅适用于舰艇编队一体化防御系统这种对时间要求和安全性要求高的系统,而且对基于无线网络的控制系统也有一定的借鉴意义。     

Overlapping Community Detection Based on Membership Degree Propagation

A community in a complex network refers to a group of nodes that are densely connected internally but with only sparse connections to the outside. Overlapping community structures are ubiquitous in real-world networks, where each node belongs to at least one community. Therefore, overlapping community detection is an important topic in complex network research. This paper proposes an overlapping community detection algorithm based on membership degree propagation that is driven by both global and local information of the node community. In the method, we introduce a concept of membership degree, which not only stores the label information, but also the degrees of the node belonging to the labels. Then the conventional label propagation process could be extended to membership degree propagation, with the results mapped directly to the overlapping community division. Therefore, it obtains the partition result and overlapping node identification simultaneously and greatly reduces the computational time. The proposed algorithm was applied to a synthetic Lancichinetti–Fortunato–Radicchi (LFR) dataset and nine real-world datasets and compared with other up-to-date algorithms. The experimental results show that our proposed algorithm is effective and outperforms the comparison methods on most datasets. Our proposed method significantly improved the accuracy and speed of the overlapping node prediction. It can also substantially alleviate the computational complexity of community structure detection in general.     

A fast and efficient heuristic algorithm for detecting community structures in complex networks

Community structure is an important property of complex networks. How to detect the communities is significant for understanding the network structure and to analyze the network properties. Many algorithms, such as K-L and GN, have been proposed to detect community structures in complex networks. According to daily experience, a community should have many nodes and connections. Based on these principles and existing researches, a fast and efficient algorithm for detecting community structures in complex networks is proposed in this paper. The key strategy of the algorithm is to mine a node with the closest relations with the community and assign it to this community. Four real-world networks are used to test the performance of the algorithm. Experimental results demonstrate that the algorithm proposed is rather efficient for detecting community structures in complex networks.     

Efficient Network Dismantling via Node Explosive Percolation

The network dismantling problem asks the minimum separate node set of a graph whose removal will break the graph into connected components with the size not larger than the one percentage of the original graph.This problem has attracted much attention recently and a lot of algorithms have been proposed. However, most of the network dismantling algorithms mainly focus on which nodes are included in the minimum separate set but overlook how to order them for removal, which will lead to low general efficiency during the dismantling process. In this paper,we reformulate the network dismantling problem by taking the order of nodes' removal into consideration. An efficient dismantling sequence will break the network quickly during the dismantling processes. We take the belief-propagation guided decimation(BPD) dismantling algorithm, a state-of-the-art algorithm, as an example, and employ the node explosive percolation(NEP) algorithm to reorder the early part of the dismantling sequence given by the BPD. The proposed method is denoted as the NEP-BPD algorithm(NBA) here. The numerical results on Erd¨os-R′enyi graphs,random-regular graphs, scale-free graphs, and some real networks show the high general efficiency of NBA during the entire dismantling process. In addition, numerical computations on random graph ensembles with the size from 2~(10) to2~(19) exhibit that the NBA is in the same complexity class with the BPD algorithm. It is clear that the NEP method we used to improve the general efficiency could also be applied to other dismantling algorithms, such as Min-Sum algorithm,equal graph partitioning algorithm and so on.     

Quantum connectivity optimization algorithms for entanglement source deployment in a quantum multi-hop network

At first, the entanglement source deployment problem is studied in a quantum multi-hop network, which has a significant influence on quantum connectivity. Two optimization algorithms are introduced with limited entanglement sources in this paper. A deployment algorithm based on node position (DNP) improves connectivity by guaranteeing that all overlapping areas of the distribution ranges of the entanglement sources contain nodes. In addition, a deployment algorithm based on an improved genetic algorithm (DIGA) is implemented by dividing the region into grids. From the simulation results, DNP and DIGA improve quantum connectivity by 213.73% and 248.83% compared to random deployment, respectively, and the latter performs better in terms of connectivity. However, DNP is more flexible and adaptive to change, as it stops running when all nodes are covered.     

Detecting overlapping communities of weighted networks via a local algorithm

Identification of communities is significant in understanding the structures and functions of networks. Since some nodes naturally belong to several communities, the study of overlapping communities has attracted increasing attention recently, and many algorithms have been designed to detect overlapping communities. In this paper, an overlapping communities detecting algorithm is proposed whose main strategies are finding an initial partial community from a node with maximal node strength and adding tight nodes to expand the partial community. Seven real-world complex networks and one synthetic network are used to evaluate the algorithm. Experimental results demonstrate that the algorithm proposed is efficient for detecting overlapping communities in weighted networks.     

基于电磁拓扑的多腔体屏蔽效能快速算法

提出基于电磁拓扑理论计算开孔多腔体屏蔽效能的快速方法.首先给出双腔体等效电路和电磁拓扑信号流图,并推导孔缝节点处的散射矩阵,给出拓扑网络的散射矩阵方程和传输矩阵方程,获得双腔体的广义Baum-Liu-Tesche(BLT)方程.在此基础上研究了开孔三腔体,包括串型级联三腔体和串并型混合级联三腔体的广义BLT方程.对于串型级联三腔体,其电磁拓扑网络和广义BLT方程在双腔体基础上直接扩展即可获得.而对于串并型混合级联三腔体,通过将位于三腔体公共面上的孔缝等效为三端口网络节点,并根据三端口网络散射参数定义推导获得该节点的散射矩阵,最终得到串并型混合级联三腔体的广义BLT方程.本文方法对双腔体的计算结果与文献结果和实验结果相符合,对3组不同类型和尺寸开孔腔的屏蔽效能的计算结果与时域有限差分法计算结果符合较好.该算法不仅效率高,通过对所有计算结果和实验结果的误差统计分析,表明该算法具有较高的计算准确度.     

无线传感器网络中继节点布居算法的研究

本文表述的是在该应用背景下引入多约束条件, 并采用枚举法与贪婪寻优算法相结合的方法, 解决了在可以作为中继节点设置位置的预设中继节点位置集合内, 合理选择中继节点设置位置以及既存网络因添加新传感器节点所引起的中继节点追加的问题. 仿真实验表明, 本文提出的中继节点布居与追加优化算法能够保证多约束条件下网络的容错性. 同时提出的基于最小网络距离因子评价标准, 有效提高了中继节点布居算法的能效性.     

A Resiliency-Connectivity metric in wireless sensor networks with key predistribution schemes and node compromise attacks

Applications for wireless sensor networks require widespread, highly reliable communications even in the face of adversarial influences. Maintaining connectivity and secure communications between entities are vital networking properties towards ensuring the successful and accurate completion of desired sensing tasks. We examine the required communication range for nodes in a wireless sensor network with respect to several parameters. Network properties such as key predistribution schemes and node compromise attacks are modelled with several network parameters and studied in terms of how they influence global network connectivity. These networks are physically vulnerable to malicious behavior by way of node compromise attacks that may affect global connectivity. We introduce a metric that determines the resilience of a network employing a key predistribution scheme with respect to node compromise attacks. In this work,we provide the first study of global network connectivity and its relationship to node compromise attacks. Existing work considers the relationship between the probability of node compromise and the probability of link compromise and the relationship of the probability of secure link establishment and overall network connectivity for the Erdős network model. Here, we present novel work which combines these two relationships to study the relationship between node compromise attacks and global network connectivity. Our analysis is performed with regard to large-scale networks; however, we provide simulation results for both large-scale and small-scale networks. First, we derive a single expression to determine the required communication radius for wireless sensor networks to include the effects of key predistribution schemes. From this, we derive an expression for determining required communication range after an adversary has compromised a fraction of the nodes in the network. The required communication range represents the resource usage of nodes in a network to cope with key distribution schemes and node compromise attacks. We introduce the Resiliency-Connectivity metric, which measures the resilience of a network in expending its resources to provide global connectivity in adverse situations.     

Performance analysis of topologies for optical wavelength convertible networks

An architecture of wavelength converters shared per-node wavelength cross-connects is proposed to function the optical node in simulation. And first-fit wavelength allocation algorithm and Dijkstra shortest path routing algorithm are used. It is shown that star topology performs the best on blocking probability, average hop count and average packet delay, but it is unfavorable on link utilization. Furthermore, wavelength conversion is not ideal for the star topology. However, the ring topology network is the cost-optimal one if the appropriate wavelength conversion capability in network is to be considered.     

Detecting community structure using label propagation with weighted coherent neighborhood propinquity

Community detection has become an important methodology to understand the organization and function of various real-world networks. The label propagation algorithm (LPA) is an almost linear time algorithm proved to be effective in finding a good community structure. However, LPA has a limitation caused by its one-hop horizon. Specifically, each node in LPA adopts the label shared by most of its one-hop neighbors; much network topology information is lost in this process, which we believe is one of the main reasons for its instability and poor performance. Therefore in this paper we introduce a measure named weighted coherent neighborhood propinquity (weighted-CNP) to represent the probability that a pair of vertices are involved in the same community. In label update, a node adopts the label that has the maximum weighted-CNP instead of the one that is shared by most of its neighbors. We propose a dynamic and adaptive weighted-CNP called entropic-CNP by using the principal of entropy to modulate the weights. Furthermore, we propose a framework to integrate the weighted-CNP in other algorithms in detecting community structure. We test our algorithm on both computer-generated networks and real-world networks. The experimental results show that our algorithm is more robust and effective than LPA in large-scale networks.