平均最短パス長-ネットワークモデリングの基本指標

平均最短パス長-ネットワークモデリングの基本指標(1)
基礎知識
図G(N,E)は、無重み無方向図であり、Nは図Gのノード集合であり、Eは図Gのエッジ集合である.
距離(distance)定義:2点間の距離は、2点相互接続で通る最小エッジの数です.
直径(diameter)定義:この図で最も長い距離.
≪平均最短パス長定義｜Average Short Path Length Definition｜oem_src≫:すべてのノードペアの距離の平均値(グラフおよびサンプルが追加されます)
コードディスプレイ(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