The fuzzy shortest path length and the corresponding shortest path in a network

The fuzzy shortest path (SP) problem aims at providing decision makers with the fuzzy shortest path length (FSPL) and the SP in a network with fuzzy arc lengths. In this paper, each arc length is represented as a triangular fuzzy set and a new algorithm is proposed to deal with the fuzzy SP problem. First, we proposed a heuristic procedure to find the FSPL among all possible paths in a network. It is based on the idea that a crisp number is a minimum number if and only if any other number is larger than or equal to it. It owns a firm theoretic base in fuzzy sets theory and can be implemented effectively. Second, we propose a way to measure the similarity degree between the FSPL and each fuzzy path lengths. The path with the highest similarity degree is the SP. An illustrative example is given to demonstrate our proposed approach.     

Solving the fuzzy shortest path problem using multi-criteria decision method based on vague similarity measure

Many researchers have focused on the fuzzy shortest path problem in a network with non-deterministic information due to its importance to various applications. The goal of this paper is to select the shortest path in multi-constrained network using multi-criteria decision method based on vague similarity measure. In our approach, each arc length represents multiple metrics. The multi-constraints are equivalent to the concept of multi-criteria based on vague sets. We propose a similarity measure of vague sets in which the positive constraints and the negative constraints are defined. Furthermore, the procedures are developed to obtain the “best” and “worst” ideal paths. We evaluate similarity degrees between all candidate paths and two ideal paths with the proposed similarity measure. Through comparing the relative degrees of paths, it is shown that the path with the largest relative degree is the shortest path. Finally, we conduct two sets of numerical experiments—using Matlab to verify the feasibility and correctness of the proposed algorithm and developing a routing decision simulation system (RDSS) to demonstrate that the proposed approach is reasonable and effective.     

应急模糊网络系统最大满意度路径的选取

讨论给定限制期条件下的应急系统模糊路径问题.当边的长度为对称三角模糊数 (Symmetric Triangular Fuzzy Number)时,由于模糊数的不可比性,网络中一般不存在绝对 最短的路.为此,引入了路径满意度函数的概念,从而问题就变成:寻找一条从起点到终点的 通路,应急车辆经过此路的时间不超过限制期t的满意度最大.这样的路径选取问题实际可 转化为一个比例路径问题,尽管许多比例路径问题已被证明是NP问题,完全可以针对问题 的具体特点,运用最短路方法的变权迭代实现对该问题的精确求解.     

基于优先队列的时变网络最短路径算法

提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。     

A hill-jump algorithm of Hopfield neural network for shortest path problem in communication network

In this paper, we present a hill-jump algorithm of the Hopfield neural network for the shortest path problem in communication networks, where the goal is to find the shortest path from a starting node to an ending node. The method is intended to provide a near-optimum parallel algorithm for solving the shortest path problem. To do this, first the method uses the Hopfield neural network to get a path. Because the neural network always falls into a local minimum, the found path is usually not a shortest path. To search the shortest path, the method then helps the neural network jump from local minima of energy function by using another neural network built from a part of energy function of the problem. The method is tested through simulating some randomly generated communication networks, with the simulation results showing that the solution found by the proposed method is superior to that of the best existing neural network based algorithm.     

参考节点嵌入最短距离估算在图聚类中的应用

为解决社会关系网络图中节点没有坐标值、不能采用传统的欧几里得距离和曼哈坦距离进行聚类的问题,提出采用最短路径算法,来衡量点与点之间的相异度.针对最短路径算法具有时间复杂度大的缺点,引入基于参考节点嵌入的最短距离估算思想来估算两点之间的近似距离.在此基础上,针对DBLP数据集构成的社会关系网络图进行聚类,使用基于划分的k-medoids算法,分别采用以上两种距离算法,比较其优劣.实验证明改进后的算法和最短路径算法中的Dijkstra 算法相比,距离误差率小,时间复杂度大大降低,在提高效率的同时,取得了同样好的聚类效果.     

A biologically inspired solution for fuzzy shortest path problems

By considering the uncertainty that exists in the edge weights of the network, fuzzy shortest path problems, as one of the derivative problems of shortest path problems, emerge from various practical applications in different areas. A path finding model, inspired by an amoeboid organism, Physarum polycephalum, has been shown as an effective approach for deterministic shortest path problems. In this paper, a biologically inspired algorithm called Fuzzy Physarum Algorithm (FPA) is proposed for fuzzy shortest path problems. FPA is developed based on the path finding model, while utilizing fuzzy arithmetic and fuzzy distance to deal with fuzzy issues. As a result, FPA can represent and handle the fuzzy shortest path problem flexibly and effectively. Distinct from many existing methods, no order relation has been assumed in the proposed FPA. Several examples, including a tourist problem, are given to illustrate the effectiveness and flexibility of the proposed method and the results are compared with existing methods.     

面向复杂网络的节点相似性度量

在复杂网络中,度量节点之间的相似性是一项基础且具有挑战性的工作。基于邻域节点的相似性度量仅考虑了节点的邻域信息。基于路径的相似性度量考虑了节点之间的路径信息,使得多数节点与大度节点相似。为了更准确地度量节点之间的相似性且避免多数节点与大度节点相似,定义了每个节点的距离分布,并在此基础上采用相对熵和距离分布提出了一种节点相似性度量方法(DDRE)。DDRE方法通过节点之间的最短路径生成每个节点的距离分布,根据距离分布计算节点之间的相对熵,进而得到节点之间的相似性。6个真实网络数据集的对比实验结果表明,DDRE方法在对称性以及SIR模型中影响其他节点的能力这两方面表现较好。     

基于引力模型及相对路径数的节点重要度评估算法

准确度量复杂网络中节点的重要度对于研究网络结构和功能等方面具有重要的指导意义。现有多数节点重要度评估算法考虑了节点及其邻居节点的相关信息,却忽略了节点间的拓扑结构对节点重要度的影响。针对此问题,提出了基于引力模型及相对路径数的节点重要度评估算法。该算法首先分析了相对最短路径数对节点间信息传播的影响效果,同时考虑到非最短路径及路径距离等因素的影响,然后以三阶范围内邻居节点与中心节点的相互作用力之和定义节点重要度值,最后在六个真实网络中进行仿真实验。实验结果表明,所提算法不仅能有效区分网络中不同节点之间的重要度差异,还能准确度量网络节点的重要度大小。     

最短路径距离矩阵修正的多维标度定位算法

为了减小最短路径距离矩阵与欧氏距离矩阵之间的差异,提高MDS-MAP(C)算法的节点定位精度,提出一种改进的多维标度节点定位算法.该算法对MDS-MAP(C)算法进行了以下改进:采用启发式的搜索策略对最短路径距离矩阵进行修正,以减少最短路径距离矩阵与实际的欧氏距离矩阵之间的误差;利用smacof算法迭代误差函数代替SVD分解来求解节点的定位问题,以优化和改善节点定位的求解过程.实验结果表明,与MDS-MAP(C)算法相比,改进算法能够减少最短路径距离的误差,有效提高节点的定位精度,并且对不规则网络具有更好的适应性.     

一种新的传感器网络混合广播调度方法

由于传感器网络所使用无线信道的共享性和相互干扰, 节点间数据广播会产生资源冲突, 广播调度要解决的即是为每个节点分配到一个无冲突传输时隙, 其目标是找到最优时分复用(TDMA: time division multiple access)调度解, 使得帧长度最短而信道利用率最大. 提出基于神经网络的两阶段混合广播调度算法. 在阶段一, 使用改进的顶点着色算法来获得调度所需最短时隙数目; 在阶段二, 使用模糊Hopfield网络将节点模糊聚类为M类, 同类 节点可以在同一时隙被调度, 不同类节点必须在不同时     

Optimal route selection based on Monte Carlo method and adaptive amoeba algorithm under uncertain environment

The fuzzy optimal path under uncertainty is one of the basic network optimization problems. Considering the uncertain environment, many fuzzy numbers are used to represent the edge weights, such as interval number and triangular fuzzy number. Then, these fuzzy numbers are converted to real numbers directly. This converting makes the optimal path the shortest path selection problem. However, much information of uncertainty get lost when converting fuzzy numbers to real numbers. In order to ensure all the origan data complete, in this paper, a fuzzy optimal path solving model based on the Monte Carlo method and adaptive amoeba algorithm is proposed. In Monte Carlo process, a random number which belongs to the fuzzy number is generated. Then, Physarum polycephalum algorithm is used to solve the shortest path every time and record the result. After many times calculation, many shortest paths have been found and recorded. At last, by analysing the characters of all the results, the optimal path can be selected. Several numerical examples are given to illustrate the effectiveness of the proposed method, the results show that the proposed method can deal with the fuzzy optimal path problems effectively.     

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

传感网中延迟限定的非汇聚数据移动式收集

在大规模的无线传感器网络中收集数据,不仅需要考虑节点的能量消耗,而且还需要考虑数据收集延迟.如何有效地均衡节点的能量消耗,同时最小化数据收集延迟,是一个具有挑战性的问题.为了均衡节点的能量消耗,利用移动数据收集器收集数据.以此为基础,提出一种DC-Collection算法来解决数据收集延迟和能耗的问题.首先,在网络中构造最短路径树,网络非连通时,不同的网络子图可以构造多棵最短路径树,它们构成一个最短路径树集合;其次,在每一棵最短路径树上选取部分节点作为采集节点和逗留节点,使得以采集节点为根的限高树的高度不超过h,且在每个采集节点的通信区域内至少有一个逗留节点;再次,在每棵限高树内调整树的结构,让能量高的节点承担更多的子孙节点,最大化限高树的生命周期;最后,移动数据收集器从Sink出发,遍历逗留节点所在位置收集数据,最终回到起点,并将数据发送给Sink.通过理论分析和大量仿真实验,其结果表明:与现有的数据收集协议相比,DC-Collection不仅能够均衡各节点的能量消耗从而延长网络生命周期,而且能够缩短移动数据收集器收集数据行走的路径长度,从而缩短数据收集延迟.     

改进的基于元胞自动机扩展模型的图的最短路径算法

在基于元胞自动机单源点到单节点图的最短路算法的基础之上,通过改进控制演化的终止条件和记录演化过程中的路径信息,提出了单源点到多节点的元胞自动机扩展模型求解图的最短路算法模型，将该算法应用于城市道路交通网的实证研究之中,可以得到路段上任意两端点之间的最短路径及路权。     

切换到高一层路网最近四个点的最短路算法

针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图T再加上这8个最短路径形成图T',在T'上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。     

基于半边数据结构的最短路径算法及其实现

在分析传统最短路径算法数据结构的基础上,提出并实现了一种以半边数据结构存储网络拓扑数据的最短路径算法。该算法充分利用半边数据结构存储格式紧凑、操作直观高效等方面的优点,采用较传统方法不同的路径检索方式,实现了快速计算网络中任一结点到其他所有结点的最短路径。实验表明,基于半边数据结构的最短路径算法可以大幅度提高网络中最短路径的计算效率,其性能在网络结点显著增多时愈加明显。     

Reconstruction of graphs based on random walks

The analysis of complex networks is of major interest in various fields of science. In many applications we face the challenge that the exact topology of a network is unknown but we are instead given information about distances within this network. The theoretical approaches to this problem have so far been focusing on the reconstruction of graphs from shortest path distance matrices. Often, however, movements in networks do not follow shortest paths but occur in a random fashion. In these cases an appropriate distance measure can be defined as the mean length of a random walk between two nodes — a quantity known as the mean first hitting time.In this contribution we investigate whether a graph can be reconstructed from its mean first hitting time matrix and put forward an algorithm for solving this problem. A heuristic method to reduce the computational effort is described and analyzed. In the case of trees we can even give an algorithm for reconstructing graphs from incomplete random walk distance matrices.     

Shortest path problem with uncertain arc lengths

Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, it investigates solutions to the α-shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the α-shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the α-shortest path and the most shortest path. Roughly speaking, this algorithm can be broken down into two parts: constructing a deterministic network and then invoking the Dijkstra algorithm.     

Finding the shortest path in stochastic networks

Common network parameters, such as number of nodes and arc lengths are frequently subjected to ambiguity as a result of probability law. A number of authors have discussed the calculation of the shortest path in networks with random variable arc lengths. Generally, only a subset of intermediate nodes chosen in accordance with a given probability law can be used to transition from source node to sink node. The determination of a priori path of the minimal length in an incomplete network is defined as a probabilistic shortest path problem. When arc lengths between nodes are randomly assigned variables in an incomplete network the resulting network is known as an incomplete stochastic network. In this paper, the computation of minimal length in incomplete stochastic networks, when travel times between nodes are allowed to be exponentially distributed random variables, is formulated as a linear programming problem. A practical application of the methodology is demonstrated and the results and process compared to the Kulkarni’s [V.G. Kulkarni, Shortest paths in networks with exponentially distributed arc lengths, Networks 16 (1986) 255–274] method.