社区发现算法 加权GN算法的Python实现

#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