[发明专利]一种基于网络社区信息的点到点最短路径计算方法

摘要

本发明公开了一种基于网络社区信息的点到点最短路径计算方法，主要解决现有技术在处理大规模网络中点到点最短路径计算时间复杂度过大问题。其实现步骤为1.根据输入的网络和网络的社区信息构建网络社区图；2.在网络社区图中计算从源点社区到目标点社区的最短社区路径；3.有最短社区路径从输入的目标网络中提取网络子图；4.在子图中计算最短路径和最短路径距离；5.将子图得到的最短路径还原到原目标网络最短路径。本发明能准确有效的找到给定点到点的最短路径，在保证路径最优的前提下，很快的找到最短路径，网络规模越大，节省的时间越多，可用于解决网络最短路径问题。

主权项

一种基于网络社区信息的点到点最短路径计算方法，其特征在于包括下列步骤：(1)输入目标网络G＝(V,E)，其中，V表示网络中的节点集合，E为网络中边的集合；输入网络社区信息C，Ci为节点i的社区，C(k)为社区k包含节点的集合；源点S，目标点D；(2)构建目标网络的社区网络(2a)构建社区网络CG＝(CV,CE)，其中CV为社区网络节点的集合，CE表示网络中边的集合；初始化CV为目标网络社区，即社区网络的节点为目标网络的社区C，设置CG的边长度CE为无穷大inf；(2b)对于目标网络G的每一条边如果边的节点vi，vi不在同一个社区，即则比较此网络边与对应社区网络边的大小，如果小于对应社区网络边的大小，则令社区网络边的大小等于此网络边；(3)S所在的社区Cs作为源点，D的社区Cd为终点，使用迪杰特斯拉方法计算社区网络最短路径SPC；(4)计算目标网络最短路径(4a)由步骤(3)得到的社区网络最短路径SPC和目标网络社区信息C计算得子网络SUBG的节点SUBV＝C(SPC)和边长度SUBE＝E(SUBV)；(4b)对子网络节点进行顺序编号得子网络索引IND，INDi表示子网络节点i在原目标网络的节点，IND(k)为目标网络节点k在子网络的编号，对应子网络的边长度不变；(4c)IND(S)为源点，IND(D)为终点，使用迪杰特斯拉方法计算子网络最短路径SPS；(4d)由步骤(4b)得到的子网络索引IND和步骤(4c)获得的子网络最短路径SPS计算目标网络最短路径SP＝IND(SPS)；(5)输出步骤(4d)中的目标网络最短路径SP。