[23-2] Girvan-Newman Algorithm Using networkx

1️⃣ 설정

 

필요한 모듈을 import 합니다.

import matplotlib.pyplot as plt             # 그래프를 그리기 위한 라이브러리

import numpy as np                          

import networkx as nx                       # 그래프의 기본적인 연산들을 위한 라이브러리

from networkx.algorithms import community   # modularity 계산을 위한 라이브러리

 

2️⃣ Girvan-Newman Algorithm

1) 전체 코드

def GirvanNewmanAlgorithm(G, nodeColorList):


    copyG = G.copy()                                                        # 기존 그래프를 복사하여, 복사된 그래프를 사용하여 엣지를 하나씩 제거하는 작업을 진행한다.
    
    pos = nx.spring_layout(copyG)
    

    """ 초기화 """
    
    step = 0                                                                # 엣지를 하나 제거할 때마다 한 step 증가
    
    logModularityList = []                                                  # 후에 modularity(군집성)를 plot하기 위하여 기록하는 용도   
   
    maxModCom = []                                                          # comRecord 는 modularity가 최대일 때의 커뮤니티의 정보들을 저장
    
    maxMod = -1                                                             # maxMod은 modularity가 최대일 때 값 기록, modularity 값의 범위는 [-1,1]
    
    maxStep = 0                                                             # maxStep은 modularity가 최대일 때 step값 기록


    
    """ Girvan-Newman algorithm """
    
    while len(copyG.edges())  > 0:                                                           # 모든 엣지가 사라질때까지 진행한다. 
        
        # nx.connected_components(copyG)를 사용하여 연결 요소 추출
        
        recComList = sorted(nx.connected_components(copyG), key=len, reverse=True)          # 현재 그래프에 존재하는 커뮤니티를 나타낸다. [{Com1}, {Com2}, {Com3} ... ]
        
        # 현재의 군집성 recMod
        
        recMod = community.modularity(G, communities=recComList)                             # G를 입력 그래프, recComList를 연결 요소로 줘서 군집성을 계산
        
        if recMod > maxMod :                                                                 # 이전 최대 modularity보다 현재 modularity가 높을 경우 기록
            
            maxModG = copyG.copy()
            
            maxMod = recMod
            
            maxModCom = []
            
            for j in range(len(recComList)):
                
                maxModCom = maxModCom + [recComList[j]]
            
            maxStep = step
            
        
        logModularityList = logModularityList + [recMod]                    # plot을 위해 저장한다.

        
        """ remove edge """
        
        step = step + 1
        
        betweenness = nx.edge_betweenness_centrality(copyG)                                     # 간선별 매개 중심성
        
        maxEdge = max(betweenness, key=betweenness.get)                                        # betweeness centrality가 가장 큰 엣지 선택


        nx.draw_networkx_nodes(copyG, pos, node_color= nodeColorList, node_size=100)
        
        nx.draw_networkx_edges(copyG, pos, edgelist=set(copyG.edges)-set(maxEdge), alpha=0.4)           # alpha: 기존 엣지들의 투명도를 조절하여 삭제되는 엣지가 돋보이도록하는 코드, alpha가 커질수록 진해짐.
        
        nx.draw_networkx_edges(copyG, pos, edgelist={maxEdge}, edge_color='black')         # 삭제 되는 엣지
        
        plt.show()
        
        print("Step: ", step, " ↑Modularity↑: ", recMod)

        
        copyG.remove_edge(maxEdge[0], maxEdge[1])                                                             # 엣지를 제거한다.

    
    return maxModG, maxMod, maxModCom, maxStep, logModularityList

 

2) 초기화

기존 그래프를 복사하여, 복사된 그래프를 사용하여 엣지를 하나씩 제거하는 작업을 진행합니다.

copyG = G.copy()  

spring_layout은 layeout 위치를 신중하게 결정하여 간선들이 최대한 중복되지 않도록 하는 역할을 수행합니다.

 

pos = nx.spring_layout(copyG)

나머지 변수들을 초기화 합니다.

step = 0                          # 엣지를 하나 제거할 때마다 한 step 증가

logModularityList = []            # 후에 modularity(군집성)를 plot하기 위하여 기록하는 용도   

maxModCom = []                    # comRecord 는 modularity가 최대일 때의 커뮤니티의 정보들을 저장

maxMod = -1                       # maxMod은 modularity가 최대일 때 값 기록, modularity 값의 범위는 [-1,1]

maxStep = 0                       # maxStep은 modularity가 최대일 때 step값 기록

 

3) 알고리즘 구현

그래프 현재 상태에서 군집성을 계산하여 관련 정보를 갱신합니다.

while len(copyG.edges())  > 0:                                                 # 모든 엣지가 사라질때까지 진행한다. 

        # nx.connected_components(copyG)를 사용하여 연결 요소 추출
        
        recComList = sorted(nx.connected_components(copyG), key=len, reverse=True)          # 현재 그래프에 존재하는 커뮤니티를 나타낸다. [{Com1}, {Com2}, {Com3} ... ]
        
        # 현재의 군집성 recMod
        
        recMod = community.modularity(G, communities=recComList)                             # G를 입력 그래프, recComList를 연결 요소로 줘서 군집성을 계산
        
        if recMod > maxMod :                                                                 # 이전 최대 modularity보다 현재 modularity가 높을 경우 기록
        
            maxModG = copyG.copy()
            
            maxMod = recMod
            
            maxModCom = []
            
            for j in range(len(recComList)):
            
                maxModCom = maxModCom + [recComList[j]]
                
            maxStep = step

매개 중심성이 가장 큰 간선을 찾아 순차적으로 제거합니다.

 while len(copyG.edges())  > 0: 
 
 	...
        
        step = step + 1
        
        betweenness = nx.edge_betweenness_centrality(copyG)    # 간선별 매개 중심성
        
        maxEdge = max(betweenness, key=betweenness.get)
        
        copyG.remove_edge(maxEdge[0], maxEdge[1])      

 

4) 결과

결과는 다음과 같이 나옵니다.

 

각 Step별로 Modularity 값 플롯하면 다음과 같은 결과를 얻을 수 있습니다.

fig = plt.figure()

plt.subplots_adjust(hspace=0.5, wspace=0.3)

plt.plot(range(0,G.number_of_edges()), logModularityList)

plt.xlabel('Step')

plt.ylabel('Modularity')

plt.show()

 

3️⃣ Real World Graph : Karate Club Data

 

networkx에는 Karate Club graph를 지원합니다. 즉, 실제 세상의 데이터를 사용할 수 있습니다.

 

모듈을 import합니다.

networkx에는 girvan_newman 알고리즘을 존재하며, 불러와서 쉽게 사용할 수 있습니다.

from networkx.algorithms.community import girvan_newman

from networkx.algorithms.community import greedy_modularity_communities

from networkx.algorithms.community import kernighan_lin_bisection

from networkx.algorithms.community import _naive_greedy_modularity_communities

실제 그래프 노드의 라벨별로 색깔을 달리하여 출력합니다.

Mr.Hi 그룹과 Officer 그룹이 나눠져서 군집을 이루는 것을 알 수 있습니다.

G = nx.karate_club_graph()                              # Karate Club Graph 데이터 불러오기

label = [G.nodes[i]["club"] for i in range(len(G.nodes))]

pos = nx.spring_layout(G)

nodeColorList = []

for i in range(len(G.nodes)):                       # 각 노드 별로 인덱스에 맞추어 

    if label[i] == 'Mr. Hi':                        # Mr.Hi 그룹
    
        nodeColorList = nodeColorList + ['red']
        
    elif label[i] == 'Officer':                     # Officer 그룹
    
        nodeColorList = nodeColorList + ['blue']
        

nx.draw_networkx_nodes(G,pos, node_color=nodeColorList, node_size=100)

nx.draw_networkx_edges(G, pos)

plt.show()

 

만약 저렇게 색이 칠해져있지 않고 어떤 vertex가 어떤 군집인지 모른다는 가정하에 Girvan-Newman을 사용해서 군집을 예측하게 되면 어떻게 될까요?

놀랍게도 가운데 두 개의 vertex 빼고는 군집을 유사하게 예측합니다.

comKarateList  = list(girvan_newman(G))     

for com in comKarateList:

    if len(com) == 2:
    
        comKarate = com
        
plotResult(G, pos, comKarate)