计算机网络病毒传播的概率模型

计算机网络病毒在全球范围迅速蔓延,在对普通用户造成危害的同时也使全球特别是亚洲地区的因特网主干网一度瘫痪.文章主要针对网络病毒的传播机制进行研究,希望找出一种能够计算病毒传播的时间的数学期望的算法.文中根据病毒在网络上随机传播的各种特性分别进行数学建模,通过比较分析不同方法的利弊,最终找到一种相对准确的算法用以计算出:在某种给定的网络拓扑结构中,某一个节点被感染后,另外一个节点被感染的时间的数学期望值.但是由于该算法计算复杂性较高,故笔者提出相应的优化方法.     

融合LeaderRank和标签传播的社区发现算法

由于社会网络的日益复杂,具有线性时间复杂度的标签传播算法越来越被广泛的运用,然而在标签传播过程中存在随机性,致使社区划分不稳定.因此,对节点标签初始化、节点更新顺序和节点标签传播选择过程这三个方面改进,提出一种稳定性较高的标签传播算法.该方法引入LeaderRank算法计算节点影响力,在此基础上选取关键节点并为这些关键节点赋予标签,节点更新顺序依据于节点影响力由高到低更新,在标签传播过程中考虑节点之间的传播能力.采用真实网络数据进行实验,和传统算法相比,论文算法在相关质量指标上均有优势.     

手机蓝牙网络中一种具有可变感染率的SIRQD病毒传播模型

针对手机蓝牙网络中的蠕虫病毒传播,提出了一种具有可变感染率的SIRQD病毒传播模型。在对节点平均度的计算方法进行改进的基础上,将节点状态划分成五类,指出感染率是时间t的函数且和已感染数量成负相关。仿真研究表明,该模型很好地模拟了蓝牙病毒的传播过程,为病毒的防治提供了理论依据。     

基于概率转移矩阵的社会网络影响最大化算法

现有近似求解影响最大化算法的时间复杂度较高,为此,提出一种扩展的线性阈值模型及其概率转移矩阵,给出该模型的传播过程及规则,设计基于概率转移矩阵的影响最大化算法,并利用贪心方法寻找到k个最具影响的节点。该算法通过矩阵乘积的方法得到,时刻节点之间的影响概率,无需在每个时刻计算所有非活跃节点的边际效益,从而在较短时间内提高运行时的效率,使得在规模较大的社会网络中被影响的节点最多且信息传播范围最广。仿真实验结果表明,在大规模社会网络中,该算法对社会网络节点的影响范围广且时间复杂度低。     

基于多标签传播的重叠社区发现优化算法

标签传播算法是一种被广泛应用的社区发现算法,该算法为网络中的每个节点分配一个初始标签,然后通过传播标签来发现复杂网络中的潜在社区,具有时间复杂度低的特点。当前基于标签传播的重叠社区发现算法存在忽略节点重要性差异、需要人为设置参数等不足。针对该类算法在重叠社区发现方面的缺陷,提出一种基于多标签传播的重叠社区发现优化算法。该算法使用K-核分解方法找出若干个社区核心节点,以这些节点为种子节点,逐层向外传播标签;在进行标签选择的时候以邻居节点标签的种类来决定重叠节点的标签个数。实验表明,该算法明显改善了社区发现的性能,提高了划分结果的稳定性和准确性。     

基于节点重要性与相似性的标签传播算法

标签传播算法是一种常用的社区发现方法,具有近似线性的时间复杂度,但该算法存在随机性和不稳定性.为了解决标签传播算法存在的准确性低和稳定性差的问题,本文提出了基于节点重要性与相似性的标签传播算法(Label Propagation Algorithm based on node Importance and Similarity,LPA IS).首先,基于节点重要性提出种子节点集和算法更新序列的获取方法.其次,利用节点重要性与相似性提出了一种计算标签综合影响力的方法,任意节点根据其邻居标签的综合影响力更新自身的标签.在真实网络和人工合成网络上进行实验,结果表明,与其它5种典型标签传播类算法对比,LPA IS算法能够在一定程度上提高算法的准确性和稳定性,并且能够减少算法的迭代次数.     

基于随机游走的改进标签传播算法

社区发现是挖掘社交网络隐藏信息的一个有用的工具，而标签传播算法（LPA）是社区发现算法中的一种常见算法，不需要任何的先验知识，且运行速度快。针对标签传播算法有很强的随机性而导致的社区发现算法结果不稳定的问题，提出了一种基于随机游走的改进标签传播算法（LPARW）。首先，根据在网络上进行随机游走确定了节点重要性的排序，从而得到节点的更新顺序；然后，遍历节点的更新序列，对每个节点将其与排序在其之前的节点进行相似性计算，若该节点与排序在其之前的节点是邻居节点且它们之间的相似性大于阈值，则将排序在其之前的节点选为种子节点；最后，将种子节点的标签传播给其余的节点，得到社区的最终划分结果。将所提算法与一些经典的标签传播算法在4个有标签的网络和5个无标签的真实网络上进行比较分析，实验结果表明所提算法在标准互信息（NMI）、调整兰德系数（ARI）和模块度等经典的评价指标上的性能均优于其余对比算法，可见该算法具有很好的社区划分效果。     

基于标签传播能力的改进LPA算法

随着网络规模的不断增大,在时间复杂度上具有明显优势的标签传播算法受到广泛关注,但是其内在机制存在不确定性和随机性,导致社团发现结果不够准确和稳定。为此,提出一种新的改进标签传播算法。在K-shell分解算法的基础上,构造节点重要性计算方法,利用节点重要性分析标签传播算法中的标签传播能力,通过节点重要性排序和标签传播能力制定新的标签更新策略,得出最终的社团划分结果。在人工网络和真实网络上的实验结果表明,该算法有较高的准确性和稳定性。     

基于全局消息传播的贝叶斯推理

在贝叶斯网络中，常常需要作不确定概率推理。然而针对一般复杂网络，精确推理算法由于计算复杂度太高而常常被摒弃。针对这一问题，本文提出了一种基于全局传播的PPJT近似推理算法。PPJT算法采用消息传播机制，通过消息的收集与分发过程，可以更新和修正连接树节点的团势并最终生成相容连接树。与另一种常用的近似推理算法即似然权重（Likelihood Weighting）算法的时间性能对比实验显示，采用消息传播机制的PPJT算法有效地降低了计算的时间复杂度；同时与似然权重算法的性能对比实验表明，在相对小规模观察样本输入条件下，PPJT算法能够保证更高的概率推理精度。PPJT算法为实现一般复杂网络中的概率推理提供了一种新的理论工具。     

基于随机游走相似度矩阵的改进标签传播算法

基于标签传播的社区发现算法因其时间效率高而得到广泛关注。针对该算法因标签传播的随机性导致其社区划分准确度难以保证的问题,提出一种基于随机游走的改进算法。首先,引入随机游走思想,计算得到一种衡量网络节点间相似度的矩阵;其次,在标签传播过程中,当邻居节点中标签出现频率存在多个最高时,不是随机选择一个,而是选择相似度最高的邻居节点所拥有的标签来更新,避免了标签在社区之间的任意传播;最后,用不同的真实网络进行测试,结果表明在社区发现中该算法比原始标签传播算法取得更好的表现。     

点对点网络容错路由算法的路径长度分析

用概率性分析方法 ,研究了在结点错误概率性分布的情形下超立方体网络点对点容错路由算法的路径长度 ,得出了算法的路径长度期望值 ,分析表明 :对于结点错误概率 p≤ 10时 ,源点 U到终点 V所在的 k维子立方体的路径长度期望值不超过 1.11* h,比以往通常的长度分析结果 2 * h小得多 .提出一种改进的算法并证明这一新算法所构造的路径长度的期望值不大于 1.11h- 0 .11k 2 ,这大大改进了以前的路径 2 h k 2 ,其中 h为 U与 V的 Ham ming距离 .     

基于联合节点行为策略的WSN覆盖控制算法

针对无线传感器网络在对移动目标节点覆盖过程中出现网络能量快速消耗问题，提出了一种基于联合节点行为策略的覆盖算法。根据网络模型建立传感器节点与目标节点从属关系，确定覆盖关联模型；利用概率理论求解邻居节点冗余覆盖度，确定最少传感器节点数量；给出了邻居节点覆盖期望值的求解方法；仿真实验表明，该算法与其他算法在网络覆盖率和网络生存周期两个性能指标上均提升了12.39%和15.01%，从而验证了算法的有效性。     

Optimal total exchange in Cayley graphs

Consider an interconnection network and the following situation: Every node needs to send a different message to every other node. This is the total exchange or all-to-all personalized communication problem, one of a number of information dissemination problems known as collective communications. Under the assumption that a node can send and receive only one message at each step (single-port model), it is seen that the minimum time required to solve the problem is governed by the status (or total distance) of the nodes in the network. We present a time-optimal solution for any Cayley network. Rings, hypercubes, cube-connected cycles, and butterflies are some well-known Cayley networks which can take advantage of our method. The solution is based on a class of algorithms which we call node-invariant algorithms and which behave uniformly across the network     

Deterministic broadcasting time with partial knowledge of the network

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v. Apart from that, each node knows the maximum degree Δ of the network. One node of the network, called the source, has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time.

We show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is Θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radius 1. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.     

Time-efficient and complete coverage path planning based on flow networks for multi-robots

Complete coverage path planning (CCPP), specifically, the efficiency and completeness of coverage of robots, is one of the major problems in autonomous mobile robotics. This study proposes a path planning technique to solve global time optimization. Conventional algorithms related to template-based coverage can minimize the time required to cover particular cells. The minimal turning path is mostly based on the shape and size of the cell. Conventional algorithms can determine the optimum time path inside a cell; however, these algorithms cannot ensure that the total time determined for the coverage path is the global optimum. This study presents an algorithm that can convert a CCPP problem into a flow network by exact cell decomposition. The total time cost to reach the edge of a flow network is the sum of the time to cover the current cell and the time to shift in adjacent cells. The time cost determines a minimum-cost path from the start node to the final node through the flow network, which is capable of visiting each node exactly once through the network search algorithm. Search results show that the time-efficient coverage can obtain the global optimum. Simulation and experimental results demonstrate that the proposed algorithm operates in a time-efficient manner.     

Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

An efficient distributed algorithm for constructing small dominating sets

The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is important to locate a small number of centers in the network such that every node is nearby at least one center. Finding a dominating set of minimum size is NP-complete, and the best known approximation is logarithmic in the maximum degree of the graph and is provided by the same simple greedy approach that gives the well-known logarithmic approximation result for the closely related set cover problem. We describe and analyze new randomized distributed algorithms for the dominating set problem that run in polylogarithmic time, independent of the diameter of the network, and that return a dominating set of size within a logarithmic factor from optimal, with high probability. In particular, our best algorithm runs in rounds with high probability, where n is the number of nodes, is one plus the maximum degree of any node, and each round involves a constant number of message exchanges among any two neighbors; the size of the dominating set obtained is within of the optimal in expectation and within of the optimal with high probability. We also describe generalizations to the weighted case and the case of multiple covering requirements. Received: January 2002 / Accepted: August 2002 RID="*" ID="*" Supported by NSF CAREER award NSF CCR-9983901 RID="*" ID="*" Supported by NSF CAREER award NSF CCR-9983901     

融合节点覆盖范围和结构洞的影响力最大化算法

影响力最大化是社交网络分析中的一个重要问题,旨在挖掘可以使得信息在网络中传播范围最大化的一小组节点（通常称为种子节点）。基于网络拓扑结构的启发式影响力最大化算法通常仅考虑某单一的网络中心性,没有综合考虑节点特性和网络拓扑结构,导致其效果受网络结构的影响较大。为了解决上述问题,提出了一种融合覆盖范围和结构洞的影响力最大化算法NCSH。该算法首先计算所有节点的覆盖范围和网格约束系数;然后通过覆盖范围增益最大原则选择种子节点;其次,若存在多个节点增益相同,则按照网格约束系数最小原则选取;最后,重复上述步骤直至选出所有种子节点。NCSH在不同种子数量和不同传播概率条件下,在六个真实网络数据集上均保持着优异的效果,在影响力传播范围方面,比同类的基于节点覆盖范围的算法（NCA）平均提高了3.8%;在时间消耗方面,比同类的基于结构洞和度折扣的最大化算法（SHDD）减少了43%。实验结果表明,NCSH能有效解决影响力最大化问题。     

基于差分进化的无线传感器网络二阶段定位算法

近年来优化算法在无线传感器网络定位算法中得到了广泛应用.在对差分进化算法研究的基础上提出一种二阶段定位算法,第一阶段在Euclidean定位算法的基础上,加入了距离路由思想,通过与未知节点距离两跳之内的两个锚节点和距离两跳之外的任一锚节点利用Euclidean算法来计算估计位置.第二阶段利用差分进化算法进行迭代寻优,提...     

Self-adaptive clock synchronization for computational grid

This paper presents an innovative method to synchronize physical clocks for a computational grid, in particular for a computational grid linked through the asynchronous In-tranet or Internet environments. The method discussed is an asynchronous self-adaptive clock synchronization mechanism. Two strategies for clock synchronisation are introduced. (1) Use con-tinuous time intervals to calculate the precision of clocks, which can reduce the effect of network delay effciently. (2) Every node synchronizes its clock with its leader actively. In addition, a node self-adaptive model is presented, and the relationship between the clock precision and synchroniza-tion time is induced, hence a node can predict when it should begin the synchronization process.Detailed simulation and extension of this issue are provided at the end of the paper. The presented model is both practical and feasible.