资源简介

传统的GN算法只适用于无向无权图的社区发现,通过对边介数进行调整得到无向有权图的GN算法实现

资源截图

代码片段和文件信息

#coding:utf-8
import networkx as nx
import math
import csv
import random as rand
import sys
import matplotlib.pyplot as plt

def buildG(G file_ delimiter_):
    reader = csv.reader(open(file_) delimiter=delimiter_)
    for line in reader:
        if int(line[2]) != 0:
            G.add_weighted_edges_from([(line[0]line[1]int(line[2]))])

def CmtyStep(G):
    init_number_comp = nx.number_connected_components(G)
    print ‘init : %d‘%init_number_comp
    number_comp = init_number_comp
    while number_comp <= init_number_comp:
        bw = nx.edge_betweenness_centrality(G)  # edge betweenness for G
        # find the edge with max centrality
        max_ = 0.0
        # find the edge with the highest centrality and remove all of them if there is more than one!
        for k v in bw.iteritems():
            # print v
            _BW = float(v) / float(G[k[0]][k[1]][‘weight‘])   # weighted version of betweenness
            if _BW >= max_:
                max_ = _BW
        for k v in bw.iteritems():
            if float(v) / float(G[k[0]][k[1]][‘weight‘])  == max_:
                # print “remove an edge!“
                # print k
                G.remove_edge(k[0] k[1])  # remove the central edge
        number_comp = nx.number_connected_components(G)  # recalculate the no of components

def GetModularity(G deg_ m_):
    New_A = nx.adj_matrix(G)#建立一个表示边的邻接矩阵
    New_deg = {}
    New_deg = UpdateDeg(New_A G.nodes())
    #计算Q值
    comps = nx.connected_components(G)#建立一个组成的列表
    print ‘Number of communities in decomposed G: %d‘ % nx.number_connected_components(G)
    Mod = 0#设定社团划分的模块化系数并设初始值为0
    for c in comps:
        AVW = 0#两条边在邻接矩阵中的值
        K = 0#两条边的度值
        for u in c:
            AVW += New_deg[u]
            K += deg_[u]
        Mod += ( float(AVW) - float(K*K)/float(2*m_) )#计算出Q值公式累加符号后的值
    Mod = Mod/float(2*m_)#计算出模块化Q值
    return Mod

def 

评论

共有 条评论