平均最短路径长度

2024-07-11 20:29| 来源: 网络整理| 查看: 265

平均最短路径长度——网络建模之基本指标（1）基础知识

图G（N,E）是一个无权无向图，N为图G的节点集合，E为图G的边集合。

距离(distance)定义：两点间的距离为两点互联所要走过的最少边的数量。

直径(diameter)定义：此图中最长的距离。

平均最短路径长度定义：所有结点对的距离的平均值(后续会加入图表及样例)

代码展示（Python） #coding=utf-8 ''' language python Created on 2017年10月24日 @author: NoTomatoTHX @parameter: table 二维邻接矩阵 ''' #输入邻接矩阵table，输出所有连通子图的平均最短路径长度vaspl(列表格式) def GetAverageShortest(table): #获取结点个数 length = len(table[0]) #设置最短路径矩阵，lenMax[i][j]为i到j的最短路径值，同样等于lenMax[j][i] lenMax = range(length) for i in range(length): lenMax[i] = range(length) lenMax[i][i] = 0 for k in range(i,length): if(table[i][k] == 1): lenMax[i][k] = 1 elif(table[i][k] == '-1'): lenMax[i][k] = 10000 #Floyed算法获得最短路径矩阵 for k in range(1,length): for i in range(1,length): for j in range(1,length): if(lenMax[i][k] + lenMax[k][j] < lenMax[i][j]): lenMax[i][j] = lenMax[i][k] + lenMax[k][j] #ssp set_of_start_points 起始结点列表 ssp = range(length) #ss set_of_subgraph 连通子图结点列表的列表 ss = [] while len(sp)>0: templist = [ssp[0]] for i in sp: if(lenMax[templist[0]][i] < 100): templist.append(i) ss.append(templist) ssp = list(set(ssp).difference(set(templist))) #value_of_average_shortest_path_length 每个连通子图的平均最短路径长度 vaspl = [] for subGraphlist in ss: value = 0 for i in subGraphlist: for j in subGraphlist[i:]: value += lenMax[i][j] vaspl.append(value*2.0/(len(subGraphlist)*(len(subGraphlist)-1))) return vaspl

【本文地址】

公司简介

联系我们