使用Python实现的网络社团发现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:
        G.add_edge（int（line[0]）int（line[1]））

def CmtyStep（G）:
    init_number_comp = nx.number_connected_components（G）
    number_comp = init_number_comp
    while number_comp <= init_number_comp:
        bw = nx.edge_betweenness_centrality（G）#计算所有边的边介数中心性
        if bw.values（） == []:
            break
        else:
            max_ = max（bw.values（））#将边介数中心性最大的值赋给max_
        for k v in bw.iteritems（）:#删除边介数中心性的值最大的边
            if float（v） == max_:
                G.remove_edge（k[0]k[1]）
        number_comp = nx.number_connected_components（G）#计算新的社团数量

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 UpdateDeg（A nod