louvain社团检测算法(python)

壹、完整代码

参考连接：
https://blog.csdn.net/qq_34356768/article/details/104888579

贰、分步解释

Louvain

分为循环迭代的两个阶段。

假设有V个节点的加权网络（可存在自环）

# coding=utf-8
import collections
import random

# 加载（顶点1，顶点2，权重）得图表示
def load_graph(path):                 #参数path:文件路径字符串
    G = collections.defaultdict(dict) # 设置空白默认字典
    with open(path) as text:
        for line in text:
            vertices = line.strip().split()  
            # .strip()删除字符串line开头结尾处得空格 # .split()按照空格分隔
            # 返回一个列表，含有3个字符串元素
            v_i = int(vertices[0])
            v_j = int(vertices[1])
            w = float(vertices[2])
            G[v_i][v_j] = w
            G[v_j][v_i] = w
    return G

1.为网络中的每个节点分配一个社团；

每个节点具有属性：vid:节点编号；cid:社团编号；k_in:节点自环个数

class Vertex():
    def __init__(self, vid, cid, nodes, k_in=0):
        self._vid = vid
        self._cid = cid
        self._nodes = nodes   # 
        self._kin = k_in      # 结点内部的边的权重

2. 算法初始化

算法中的graph:_G_

算法中的总边数:_m_

有两个字典：

• _cid_vertices:用于存放社区编号，字典类型
  _cid_vertices[vid]:编号为vid的社区
• _vid_vertex:用于存放顶点编号，字典类型，每个顶点进行class Vertex实例化，赋予每个顶点各项初始属性
  _vid_vertex[vid]:编号为vid的顶点，字典类型

class Louvain():
    def __init__(self, G): # 算法初始化
        self._G = G  # G是一个嵌套字典
        self._m = 0  # 边数量
        # 下面两个空字典存放信息
        self._cid_vertices = {}  # 需维护的关于社区的信息(社区编号,其中包含的结点编号的集合)
        self._vid_vertex = {}    # 需维护的关于结点的信息(结点编号，相应的Vertex实例)
        for vid in self._G.keys(): # self._G.keyds()字典得键值列表
            # 含vid得社区名为vid,社区用列表表示，必含有Vid
            self._cid_vertices[vid] = set([vid]) 
            
            # 对于顶点vid进行‘类初始化 class Vertex'
            self._vid_vertex[vid] = Vertex(vid, vid, set([vid]))
            
            # 求graph得边数量：对每个vid得邻居 neighbor ,如果neirbor>vid，则加1，避免(i,j)和（j,i）重复
            self._m += sum([1 for neighbor in self._G[vid].keys() if neighbor > vid])
            

3. 第一阶段循环

 # 属于 class Louvain():
    def first_stage(self):
        mod_inc = False  # 用于判断算法是否可终止
        visit_sequence = self._G.keys()  # 需要拜访得节点列表(所有节点)
        random.shuffle(list(visit_sequence)) # 转化为列表后并打算列表得排列顺序
        while True:
            can_stop = True  # 第一阶段是否可终止
            for v_vid in visit_sequence:
                # 随机选择第一个节点v_vid(随机体现在shuffle),
                # 其’属性_vid_vertex'是对节点实例化后，令‘属性_cid'(即节点所在得社区编号)赋值
                v_cid = self._vid_vertex[v_vid]._cid
                
                # 假设G={1102:{1221:2,1321:3},1221:{1102:2,1456:4}}
                # G[1102].values()=[2,3] ，sum求和后表示含节点1102得边数目  # kin初始化为0
                # k_v表示节点v_vid的所有边权重之和
                k_v = sum(self._G[v_vid].values()) + self._vid_vertex[v_vid]._kin
                
                cid_Q = {}
                # G[1102].keys()=[1221,1321],即节点1102得邻居
                for w_vid in self._G[v_vid].keys():
                    w_cid = self._vid_vertex[w_vid]._cid  # 邻居所在得社区编号
                    if w_cid in cid_Q:
                        continue    # 若邻居w_ci的社区在 字典cid_Q中则不操作
                    else:   
                        '''
                        _cid_vertices[w_cid]：表示编号为w_cid的社区，k是社区w_cid的节点
                         G[k].values()：是权重值
                         sum(self._G[k].values()) ：节点k的所有出边的边总数
                         _vid_vertex[k]._kin： 表示对节点k的‘属性k_in’(自环边)
                         sum([k的所有边(出边+自环边)])：社区w_cid的内部边+连接边 
                        '''
                        tot = sum(
                            [sum(self._G[k].values()) + self._vid_vertex[k]._kin \
                            for k in self._cid_vertices[w_cid]])
                        '''
                         v_vid节点的邻居w_vid的
                         v_vid的社区编号v_cid；w_vid的社区编号为w_cid
                         如果v_vid与其邻居w_vid的社区编号相同，则移除v_vid后计算社团的边权重之和
                         '''
                        if w_cid == v_cid:
                            tot -= k_v
                        
                        '''
                        _cid_vertices[w_cid]:表示社区编号为w_cid的社区，k是社区内的节点
                        G[v_vid].items():G[1102].items()=dict_items([(1221, 2), (1321, 3)])
                        k_v_in:当遍历节点v_vid的邻居时判断k如果是w_cid社区内的节点，则求权重之和
                        '''                                             
                        k_v_in = sum([v for k, v in self._G[v_vid].items() if k in self._cid_vertices[w_cid]])
                        
                        delta_Q = k_v_in - k_v * tot / self._m  # 由于只需要知道delta_Q的正负，所以少乘了1/(2*self._m)
                        cid_Q[w_cid] = delta_Q

                cid, max_delta_Q = sorted(cid_Q.items(), key=lambda item: item[1], reverse=True)[0]
                '''
                参量 key：表示排序的关键字
                参量 reverse=True:表示逆序，从大到小排列
                lambda item :item[1]: item 是一个sorted的变量(即为字典的items迭代量)，形式为（key,value）的二元组
                                      item[1],即表示上述二元组的value
                整体含义为：按照字典中的value,从大到小排序
                '''
                if max_delta_Q > 0.0 and cid != v_cid:
                    self._vid_vertex[v_vid]._cid = cid
                    self._cid_vertices[cid].add(v_vid)
                    self._cid_vertices[v_cid].remove(v_vid)
                    can_stop = False
                    mod_inc = True
            if can_stop:
                break
        return mod_inc            
            

4. 第一阶段文字图片双解释

随机选择random.shuffle(list(visit_sequence))

while True
1.can_stop:用于判断第一阶段是否终止
2.for v_vid in 考虑G中所有的节点:
​ 2.1 选择一个顶点v_vid,得到其属性：1️⃣社团编号v_cid;2️⃣连接到v_vid的边的权重之和k_v
​ 2.2 cid_Q={} 空字典，用于存储 模块度增量
​ 2.3 for w_vid in 考虑顶点v_vid的所有邻居节点：
​ 2.3.1 can_stop=True
​ 2.3.2 （也就是计算将节点v_vid移动到其邻居所在的社区后，计算模块度增量）
​ 2.3.4 选择邻居w_vid,得到其属性：
​ 2.3.4.1 1️⃣社团编号w_cid
​ 2.3.4.2 2️⃣判断社团编号w_cid是否是cid_Q的键；
​ 2.3.4.2.1 ✔️continue
​ 2.3.4.2.2 ✖️将原节点v_vid移除所属社团，加入其邻居所属的社团，评估模块度收益
​ 2.3.4.2.2.1🥇tot:邻居所在的社团w_cid内的所有节点的边的权重之和以及节点自环的权重如果w_cid==v_cid(即属于同一个社团),tot-=k_v (节点v_vid移除社团后的权重变化)
​ 2.3.4.2.2.2🥈k_v_in:表示‘移动节点v_vid’连接移动到社团w_cid内的节点的边的权重之和
​ 2.3.4.2.2.3 🥉delta_Q：模块度增量的表达式，并将其结果存入字典cid_Q
​ 2.4.& 1102的邻居: 1221 1321
​   & 移动后的$\Delta Q$: $\Delta Q_1$ $\Delta Q_2$
​ 2.5 cid, max_delta_Q :是对上述的[$\Delta Q_1$,$\Delta Q_2$]从大到小排序后，获得的对应社区号以及模块度增量
​ 2.6 if max_delta_Q > 0.0 and cid != v_cid:（ 将v_vid移动到cid社区后，更新相关属性信息）
​ 2.6.1 1️⃣v_vid的社区编号v_cid更新
​ 2.6.2 2️⃣社区[cid]的增加新成员
​ 2.6.3 3️⃣社区[v_cid]删除旧成员v_vid
​ 2.6.4 4️⃣can_stop=False 当下只对一个节点移动了，继续寻找，第一阶段不停止
​ 2.6.5 5️⃣mod_inc = True 算法可以终止了
3.if can_stop: break

参数解释：

._m=10
$$\Delta Q=\frac{s_{i,in}}{2E}-\frac{{\sum }_{tot}\cdot s_i}{2E^2}$$
其中$s_{i,in}$=k_v_in:节点i连接到社团m内节点的边权重和
${\sum }_{tot}$=tot:连接到社团m内节点的边的权重总和
$E$=.m:表示网络中边权重总和
初始化的时候每个节点为独立的社团，如上图所示，用5个颜色表示5个社团

第一次选择移动节点v_vid=1321

邻居节点w_vid=1102，连接到社团1102的边的权重之和$tot_{1102}$=3+2=5,$s_{1321,in}$=3,E=10,$s_{1321}=3$, $2 \cdot 10 \cdot \Delta Q=2\cdot 10\cdot (\frac{3}{2\cdot 10}-\frac{5\cdot 3}{2 \cdot 10^2})=2.5>0$

1321移动到邻居1102社区，1321的社区编号为1102

第二次选择移动节点v_vid=1102

邻居节点有：1321，1221

• 首先1321的社区编号为1102，社区1102中有{1102，1321},k_v=5
  ,$to{t}_{1102}=sum(sum[2,3],[3])=8$,$to{t}_{1102}=to{t}_{1102}-k_v=3$,
  $s_{1102,in}=3$,$s_{1102}=2+3=5$,
  $2\cdot 10\Delta Q_{1321}=3-\frac{3\cdot 5}{10}=1.5>0$
• 其次1221的社区编号为，社区1221中只有节点1221，k_v=1+2+4=7，
  $to{t}_{1221}=7,s_{1102,in}=2,s_{1102}=5$
  $2\cdot 10\Delta Q_{1221}=2-\frac{7\cdot 5}{10}=-0.5<0$

1102移除1102社区后又重新加入1102社区，即不变动

第三次选择移动节点v_vid=1221

邻居节点有：1102，1421，1456

• 首先1102的社区编号为1102.社区中有{1102，1321}，k_v=7
  $to{t}_{1102}=8,s_{1221,in}=2,s_{1221}=7$
  $2\cdot 10\Delta Q=2-\frac{8\cdot 7}{10}=-3.6<0$
• 其次1421的社区编号为1421，社区中只有1421，k_v=1
  $to{t}_{1421}=1.s_{1221,in}=1$
  $2\cdot 10\Delta Q=1-\frac{1\ast 1}{10}=0.9>0$
• 最后1456的社区编号为1456，社区中只有1456，k_v=4
  $to{t}_{1456}=4,s_{1221,in}=4$
  $2\cdot 10\Delta Q=4-\frac{4\cdot 4}{10}=2.4>0$

1221移除1221社区后加入1456社区

第四次选择移动节点v_vid=1456

显然1456是不移动的

第五次选择移动节点v_vid=1421

1421的邻居节点为1221

• 1221的社区编号为1456，社区中有{1221，1456}k_v=1
  $to{t}_{1456}=sum(sum[1,2,4],[4])=11,s_{1421,in}=1$
  $2\cdot 10\Delta Q=1-\frac{11\cdot 1}{10}=-0.1<0$

因为模块度增量减少，所以不移动

最终得到3个社区：社区1102{1102，1321}+社区1456{1221，1456}+社区1421{1421}

5.第二个阶段

它在于构建一个新网络，其节点属于第一阶段发现的社团。因此，新节点之间的连边权重由相应的两个社团的节点连边权重和给定。同以社团内的节点会导致新网络中社团出现自身环。

算法：

1. 搭建两个新字典，用于存放新社团和新节点
2. 对旧社团遍历构造新节点：
   2.1 如果旧社团为空，跳过
   2.2 以‘旧社团编号’作为新节点的节点编号、新社团编号
   2.3 对新节点的‘node’属性，利用set()集合表示，将旧社团的节点update进去
   2.4 对新节点的‘kin’属性，1️⃣包含就社团节点中的所有kin属性，2️⃣包含旧社团中节点的所有内边的权重之和
3. 对新节点放入存放字典，并将每个新节点当作独立的新社团存放入字典
4. 搭建新网络(在新节点之间添加边的权重)，设置默认字典G
5. 对旧社团中的(社团编号cid1，vertices1[节点列表])遍历
   5.1 如果旧社团cid1为空，则跳过
   5.2 对旧社团中(社团编号cid2,vertices2[节点列表])遍历
   ​ 5.2.1 if 避免新边重复、自环以及避免第二个新节点为空的情形
   ​ 5.2.2 设置新边的初始权重为0
   ​ 5.2.3 用vid 对旧社团cid1中的节点列表 vertices1遍历
   ​ 5.2.3.1 用(wid,v)对节点vid 的邻居vid.items()遍历
   ​ 5.2.3.1.1 判断wid 如果是旧社团cid2中的节点，则将权重v增加
   ​ 5.2.4 如果新边权重不为0，则将这条新边记录到图G中
6. 将新节点字典、新社团字典、新图G更新

# calss louvain():
    def second_stage(self):
        # 搭建两个新字典，用于存放新社团和新节点
        cid_vertices = {}
        vid_vertex = {}
        '''
        _cid_vertices:字典，键为社区编号，值为对应社区中的节点构成的列表
        _cid_vertices={1102:[1102,1321],1456:[1221,1456],1421:[1421],1321:[],1221:[]}
         '''
        for cid, vertices in self._cid_vertices.items():
            if len(vertices) == 0:
                continue   # 如果是空社区跳过
            # 将非空社团的作为新节点，新节点编号为社区编号，社区编号不变，节点设置为空集
            new_vertex = Vertex(cid, cid, set()) 
            # 更新新节点的各种属性
            for vid in vertices:
                # 新节点的_nodes属性中增加社团中的节点，update类似于append
                new_vertex._nodes.update(self._vid_vertex[vid]._nodes)
                # 新节点的_kin属性，是包含社团中节点的所有自环
                new_vertex._kin += self._vid_vertex[vid]._kin
                # 新节点的_kin属性，是包含社团中节点的内边的权重之和(边不重复)
                for k, v in self._G[vid].items():
                    if k in vertices:
                        new_vertex._kin += v / 2.0
            # 前面部分搭建完新节点属性后，对每个新节点作为一个新的社团，且搭建新节点存放         
            cid_vertices[cid] = set([cid])
            vid_vertex[cid] = new_vertex
        
        # 构建新网络
        G = collections.defaultdict(dict)
        # 在原社团字典中，搭建新网络的连边，
        $ 节点1(cid1)，节点2(cid2)都是是原社团中的社团编号
        for cid1, vertices1 in self._cid_vertices.items():
            if len(vertices1) == 0:
                continue # 如果社团为空，则跳过
            for cid2, vertices2 in self._cid_vertices.items():
                if cid2 <= cid1 or len(vertices2) == 0:                 
                    continue # 如果cid2与cid1相同或者cid2社团为空，则跳过，<是为避免重复
                '''
                新节点边的初始权重为0，取社团cid1的节点vid,再取vid的邻居wid及权重v,
                判断wid如果在社团cid2中，则新边权重增加v
                '''
                edge_weight = 0.0
                for vid in vertices1:
                    for wid, v in self._G[vid].items():
                        if wid in vertices2:
                            edge_weight += v
                # 如果新边权重不为0，则将这条新边记录到图G中
                if edge_weight != 0:
                    G[cid1][cid2] = edge_weight
                    G[cid2][cid1] = edge_weight
        # 新构建的节点、新社团划分、新图G更新
        self._cid_vertices = cid_vertices
        self._vid_vertex = vid_vertex
        self._G = G

构造新节点

新节点属性名称	1102属性值	1456属性值	1421属性值
_vid	1102	1456	1421
_cid	1102	1456	1421
_nodes	（1102，1321）	（1221，1456）	（1421）
_kin	3	4	0

构造新网络,遍历三个旧社团

第一个旧社团cid1=1102

旧社团1102中有两个节点，vid:1102，1321。
选取另一个旧社团(cid2>cid1,且不为空)li,cid2:1456,1421.初始权重G[1102,1456]=0,G[1102,1421]=0

• vid =1102,邻居1321即不是社团1456中的节点，也不是社团1421的节点，跳过
• vid =1321,邻居有[1102，1221]

• 1102,既不是社团1456中的节点，也不是社团1421的节点，跳过
• 1221，是社团1456中的节点，则G[1102,1456]=0+2=2

第二个旧社团cid1=1456

旧社团1456中有两个节点，vid:1221,1456
选取另一个旧社团(cid2>cid1,且不为l空)，cid2,没得选，跳过

第三个旧社团cid1=1421

旧社团中只有1个节点，vid:1421
选取另一个旧社团(cid2>cid1,且不为l空)，cid2：1456。初始权重G[1421,1456]=0

• vid=1421,邻居1221是社团1456中的节点，则G[1421,1456]=0+1=1

6.获得社团

# class louvain():
    def get_communities(self):
        communities = []
        # vertices是社团中的节点列表
        for vertices in self._cid_vertices.values():
            # 如果社团不为空，则用vid遍历社团中的节点，将每个节点中node属性放入集合C中，再将集合放入列表
            if len(vertices) != 0:
                c = set()
                for vid in vertices:
                    c.update(self._vid_vertex[vid]._nodes)
                communities.append(c)
        return communities

7.两个阶段进行循环

# class louvain():
    def execute(self):
        iter_time = 1 # 迭代次数
        while True:
            iter_time += 1
            mod_inc = self.first_stage() # 第一阶段执行，
            if mod_inc:  # 若返回mod_inc=True，则执行第二阶段
                self.second_stage()
            else:        # 否则，跳出循环
                break
        return self.get_communities() # 返回得到的社团

8. 主函数进行调用运行

if __name__ == '__main__':
    G = load_graph('s.txt')
    algorithm = Louvain(G)
    communities = algorithm.execute()
    # 按照社区大小从大到小排序输出
    communities = sorted(communities, key=lambda b: -len(b)) # 按社区大小排序
    count = 0
    for communitie in communities:
        count += 1
        print("社区", count, " ", communitie)

9整体代码

# coding=utf-8
import collections
import random

def load_graph(path):
    G = collections.defaultdict(dict) # 设置空白默认字典,无向图
    DG=collections.defaultdict(dict) # 设置空白默认字典，有向图
    with open(path) as text:
        for line in text:
            vertices = line.strip().split()
            # .strip()删除字符串line开头结尾处得空格 # .split()按照空格分隔
            # 返回一个列表，含有3个字符串元素
            v_i = int(vertices[0])
            v_j = int(vertices[1])
            w = float(vertices[2])
            G[v_i][v_j] = w
            # G[v_j][v_i] = w
    return G

class Vertex():
    def __init__(self, vid, cid, nodes, k_in=0):
        self._vid = vid
        self._cid = cid
        self._nodes = nodes
        self._kin = k_in  # 结点内部的边的权重

class Louvain():
    def __init__(self, G):
        self._G = G
        self._m = 0  # 边数量
        # 下面两个空字典存放信息
        self._cid_vertices = {}  # 需维护的关于社区的信息(社区编号,其中包含的结点编号的集合)
        self._vid_vertex = {}    # 需维护的关于结点的信息(结点编号，相应的Vertex实例)
        for vid in self._G.keys():
            self._cid_vertices[vid] = set([vid])
            self._vid_vertex[vid] = Vertex(vid, vid, set([vid]))
            self._m += sum([1 for neighbor in self._G[vid].keys() ])

    def first_stage(self):
        mod_inc = False  # 用于判断算法是否可终止
        visit_sequence = self._G.keys()
        random.shuffle(list(visit_sequence))
        while True:
            can_stop = True  # 第一阶段是否可终止
            for v_vid in visit_sequence:
                v_cid = self._vid_vertex[v_vid]._cid
                k_v = sum(self._G[v_vid].values()) + self._vid_vertex[v_vid]._kin
                cid_Q = {}
                for w_vid in self._G[v_vid].keys():
                    w_cid = self._vid_vertex[w_vid]._cid
                    if w_cid in cid_Q:
                        continue
                    else:
                        tot = sum(
                            [sum(self._G[k].values()) + self._vid_vertex[k]._kin for k in self._cid_vertices[w_cid]])
                        if w_cid == v_cid:
                            tot -= k_v
                        k_v_in = sum([v for k, v in self._G[v_vid].items() if k in self._cid_vertices[w_cid]])
                        delta_Q = k_v_in - k_v * tot / self._m  # 由于只需要知道delta_Q的正负，所以少乘了1/(2*self._m)
                        cid_Q[w_cid] = delta_Q

                cid, max_delta_Q = sorted(cid_Q.items(), key=lambda item: item[1], reverse=True)[0]
                if max_delta_Q > 0.0 and cid != v_cid:
                    self._vid_vertex[v_vid]._cid = cid
                    self._cid_vertices[cid].add(v_vid)
                    self._cid_vertices[v_cid].remove(v_vid)
                    can_stop = False
                    mod_inc = True
            if can_stop:
                break
        return mod_inc

    def second_stage(self):
        cid_vertices = {}
        vid_vertex = {}
        for cid, vertices in self._cid_vertices.items():
            if len(vertices) == 0:
                continue
            new_vertex = Vertex(cid, cid, set())
            for vid in vertices:
                new_vertex._nodes.update(self._vid_vertex[vid]._nodes)
                new_vertex._kin += self._vid_vertex[vid]._kin
                for k, v in self._G[vid].items():
                    if k in vertices:
                        new_vertex._kin += v / 2.0
            cid_vertices[cid] = set([cid])
            vid_vertex[cid] = new_vertex

        G = collections.defaultdict(dict)
        for cid1, vertices1 in self._cid_vertices.items():
            if len(vertices1) == 0:
                continue
            for cid2, vertices2 in self._cid_vertices.items():
                if cid2 <= cid1 or len(vertices2) == 0:
                    continue
                edge_weight = 0.0
                for vid in vertices1:
                    for k, v in self._G[vid].items():
                        if k in vertices2:
                            edge_weight += v
                if edge_weight != 0:
                    G[cid1][cid2] = edge_weight
                    G[cid2][cid1] = edge_weight

        self._cid_vertices = cid_vertices
        self._vid_vertex = vid_vertex
        self._G = G

    def get_communities(self):
        communities = []
        for vertices in self._cid_vertices.values():
            if len(vertices) != 0:
                c = set()
                for vid in vertices:
                    c.update(self._vid_vertex[vid]._nodes)
                communities.append(c)
        return communities

    def execute(self):
        iter_time = 1
        while True:
            iter_time += 1
            mod_inc = self.first_stage()
            if mod_inc:
                self.second_stage()
            else:
                break
        return self.get_communities()

if __name__ == '__main__':
    G = load_graph('s.txt')
    algorithm = Louvain(G)
    communities = algorithm.execute()
    # 按照社区大小从大到小排序输出
    communities = sorted(communities, key=lambda b: -len(b)) # 按社区大小排序
    count = 0
    for communitie in communities:
        count += 1
        print("社区", count, " ", communitie)

sql=“select top 1 [id] from [youtable] where id<”&Request.QueryString(“id”)
下一篇：有向图中的louvain社区检测（二）