[네트워크이론] Network Modularity 실제 사용 예 Girvan-Newman algorithm

 

[이전 글] 2018/02/18 - [연구/연구] - [네트워크이론] Network Modularity (네트워크의 모듈성)

 

이전 글에 이어서 이번에는 실제 예제로 계산해 보는 모듈성과 모듈성을 이용한 Girvan-Newman Community 추출 Algorithm에 대한 글을 써본다.

 예제로는 30명이 함께 있는 네트워크에서 1팀(8명), 2팀(10명), 3팀(12명)으로 구성된 내부 커뮤니티를 검출할 수 있을까 이다. 이를 위에 다음과 같이 설정하여 사회 네트워크를 구성하고, 이 때의 Modularity를 구해보는 과정을 Python을 이용하여 진행해보자.

 설정

---

  1. 각각의 사람은 0~29의 숫자로 표현한다.

  2. 팀 설정

1팀: 0~7

2팀: 8~17

3팀: 18~29

  3. 커뮤니티 l에서 커뮤니티 l'으로 연결된 연결의 수 m_ll'

3-1. 내부 연결 개수 

(내부 연결의 경우, 1팀 내의 i와 j의 연결은 m11 속에서 a_ij 와 a_ji 두번씩 더해지므로 실제 연결의 갯수에 2를 곱한다)

m11 = 15 * 2

m22 = 20 * 2

m33 = 25 * 2

3-2. 외부 연결 개수

(외부 연결의 경우 1팀의 노드 i와 2팀의 노드 j의 연결은 m12 와 m21에 따로따로 더해지므로 연결의 갯수로 나타낸다.)

m12 = m21 = 3

m13 = m31 = 3

m23 = m32 = 4

 위와 같은 설정에서 지난번 글에서 마지막으로 구한 Modularity Q를 구하기 위해 커뮤니티간의 연결 갯수를 행렬로 나타내는 작업을 한다.

 커뮤니티 간 연결의 행렬화

총 연결 갯수 * 2 값에 대한 각 연결의 비율을 행렬화

2M = 2 * 총 연결 갯수 = 2 * (15 + 20 + 25+ 3 + 3 + 4) = 140

---

Modularity Q

---

 모듈성은 다음 식으로 구해진다.(이전 글 참조)

 이를 Python으로 구현하면 다음과 같다.

import numpy as np

E = np.array([[15*2, 3, 3],[3, 20*2, 4],[3, 4, 25*2]]) / 140
Modularity = np.trace(E) - np.sum(np.dot(E, E))

print(Modularity)
0.512551020408

 이 네트워크를 1, 2, 3팀으로 나누었을 때, Modularity값은 0.513 임을 알 수 있다.

 더 나아가서, Modularity를 이용해서 Community에 관한 정보가 주어지지 않은 네트워크 속에서 최적의 Community를 찾아낼 수 있을까? 그 방법 중 하나가, Girvan-Newman Algorithm이다. 

---

Girvan-Newman Algorithm

---

 Girvan-Newman 알고리즘은 betweenness centrality를 이용한다. betweenness centrality는 네트워크 내의 한 지점 i에서 j를 연결하는 최단 거리의 선상에 특정 지점 k가 얼마나 많은 빈도로 등장하는지를 나타낸다. 최단거리 알고리즘을 통해 노드 내의 모든 지점 i와 j간의 최단거리 루트를 구하고, 그 안에 등장하는 노드들 k의 빈도를 조사하여, 수치화 한다. 즉, betweenness centrality를 통해 우리는 Community간의 bridge역할을 하는 노드들과 연결들을 조사할 수 있다. betweenness centrality가 높을 수록 커뮤니티간 네트웤에서 중요한 위치를 차지할 것이다.

 Girvan-Newman 알고리즘은 betweenness centrality가 높은 연결부터 한개씩 한개씩 끊어 나간다. Community들간의 연결을 한개씩 끊어나가는 것이다. 그리고는 그 때마다 나누어지는 그룹에 대해 Modularity를 계산한다. 그리고 마지막 연결까지 끊었을 때, 지금까지 나왔던 Modularity 중 가장 큰 값을 가지는 지점이 최상의 Community 검출이 이루어진 상태라고 가정한다.

Girvan-Newman Algorithm 순서

 1. betweenness Centrality가 가장 높은 연결(Edge)을 끊는다.

 2. 모두 이어져 있는 네트워크를 Community로 묶어, Modularity를 구한다.

 => Edge가 모두 없어질 때까지 반복한다.

 처음 위에서 설정한 커뮤니티에 대해서 Girvan-Newman Algorithm을 실행한 결과는 다음과 같다.

Girvan-Newman Algorithm 결과

  betweenness centrality가 높은 Edge를 순서대로 10개 끊어냈을 때 가장 높은 Modularity 값을 나타내는 것을 알 수 있다. 위에서 설정한 커뮤니티는 1, 2, 3팀의 세 커뮤니티로 이루어져 있고, 세 커뮤니티 간의 연결 개수가 3+3+4 = 10 인 것을 생각하면, betweenness centrality가 높은 연결이 모두 커뮤니티 간의 연결임을 알 수 있다. 또한, Modularity가 가장 높은 지점에서 커뮤니티는 0~7, 8~17, 18~29 세팀으로 구해졌음을 확인할 수 있고, 이 때의 Modularity는 '0.512551020408'로 위에서 행렬을 이용하여 직접 구한 Modularity와 일치함을 알 수 있다. 

 Modularity는 좋은 Community가 검출될 수록 확확 그 값이 치고 올라간다. 그리고, 적정 Community 보다 더 Edge를 쳐 내었을 때 그 값이 감소한다. 그래서, Modularity가 최대인 지점에서 최적의 Community가 검출되었다고 판단하게 되는 것이다.

 물론, 이번에 작성한 네트워크는 내부에 연결이 많도록 생성해낸 가상 네트워크이므로, 실제로는 조금 더 모호한 Community 검출이 이루어질 수 있다는 점은 조심해야할 부분이다.

Community Detection 결과

사용 Code

import matplotlib.pyplot as plt
import numpy as np
import networkx as nx
from networkx.algorithms import community


def Girvan_Newman_algorithm(G, weight):
    """ G는 원래 네트워크 g는 Edge를 한개씩 끊어나갈 네트워크 """
    g = G.copy()

    """ initial """
    step = 0                # step
    log_step = []           # step 기록
    log_modularity = []     # modularity 기록
    old_max_m = 0           # 이전 최대 modularity 기억
    max_g = g.copy()        # modularity가 최대일 때의 네트워크 여기서는 초기화 작업
    k = sorted(nx.connected_components(G), key=len, reverse=True)   # k 는 모두 연결되어있는 Community를 노드로 나타낸 값
    k_list = []
    for j in range(len(k)):
        k_list = k_list + [list(k[j])]
    max_k = k_list  # max_k 는 modularity가 최대일 때의 k 값 저장용
    m = community.modularity(G, communities=k, weight=weight)   # modularity
    max_m = m       # max_m은 modularity가 최대일 때 값 기록용
    max_step = 0    # max_step은 modularity가 최대일 때 step값 기록용

    """ Girvan-Newman algorithm """
    while len(g.edges()) > 0:
        k = sorted(nx.connected_components(g), key=len, reverse=True)  # 커뮤니티 추출
        m = community.modularity(G, communities=k, weight=weight)   # 추출된 커뮤니티의 modularity 계산
        if m > old_max_m:   # 이전 최대 modularity보다 현재 modularity가 높을 경우 기록
            max_g = g.copy()
            max_m = m
            k_list = []
            for j in range(len(k)):
                k_list = k_list + [list(k[j])]
            max_k = k_list
            max_step = step
            old_max_m = m
        log_step = log_step + [step]    # 로깅용
        log_modularity = log_modularity + [m]   # 로깅용
        print("step: ", step, "  modularity: ", m)

        """ remove edge """
        step = step + 1
        betweenness = nx.edge_betweenness_centrality(g, weight=weight)  # betweennes centrality 계산
        max_edge = max(betweenness, key=betweenness.get)    # betweeness centrality가 가장 큰 Edge 선택
        g.remove_edge(max_edge[0], max_edge[1])     # Edge 추출

    return log_step, log_modularity, max_g, max_m, max_k, max_step


def Add_Inner_edges(range, num):
    inner_edges = []
    while len(inner_edges) < num:
        new_edge = tuple(np.sort(np.random.choice(range, size=2, replace=None)))
        if new_edge not in inner_edges:
            inner_edges = inner_edges + [new_edge]
    return inner_edges


def Add_Outer_edges(Community_all, num):
    # 두 커뮤니티 선택
    outter_edges = []
    while len(outter_edges) < num:
        #group_choiced = np.random.choice(range(len(Community_all)), size=2, replace=None) # 범용적으로 커뮤니티 선택할 시
        if len(outter_edges) < 3:
            group_choiced = np.random.choice([0, 1], size=2, replace=None)
        elif len(outter_edges) < 6:
            group_choiced = np.random.choice([0, 2], size=2, replace=None)
        elif len(outter_edges) < 10:
            group_choiced = np.random.choice([1, 2], size=2, replace=None)
        new_edge = tuple(np.sort([np.random.choice(Community_all[group_choiced[0]], replace=None),
                    np.random.choice(Community_all[group_choiced[1]], replace=None)]))
        if new_edge not in outter_edges:
            outter_edges = outter_edges + [new_edge]
    return outter_edges


""" 본문 """

""" Network 생성 """
# 8명, 10명, 12명 의 3팀 생성, 총 30명
G = nx.Graph()
G.add_nodes_from(range(30))
# Community 설정
Community1 = range(0, 8)
Community2 = range(8, 18)
Community3 = range(18, 30)
Community_all = Community1, Community2, Community3

# 내부 연결 추가
Inner_edges_1 = Add_Inner_edges(range=Community1, num=15)
Inner_edges_2 = Add_Inner_edges(range=Community2, num=20)
Inner_edges_3 = Add_Inner_edges(range=Community3, num=25)
G.add_edges_from(Inner_edges_1)
G.add_edges_from(Inner_edges_2)
G.add_edges_from(Inner_edges_3)

# 외부 연결 추가
Outter_edges = Add_Outer_edges(Community_all, 10)
G.add_edges_from(Outter_edges)

""" 수동 Modularity 계산 """
E = np.array([[30, 3, 3],[3, 40, 4],[3, 4, 50]]) / 140
Modularity = np.trace(E) - np.sum(np.dot(E, E))


""" Girvan Newman algorithm"""
log_step, log_modularity, max_g, max_m, max_k, max_step = Girvan_Newman_algorithm(G, weight=None)   # weight='weight' : weighted network
# Algorithm 실행결과 플롯
fig = plt.figure()
plt.subplots_adjust(hspace=0.5, wspace=0.3)
plt.plot(log_step, log_modularity)
plt.xlabel('step')
plt.ylabel('modularity')
plt.title("unweighted")
plt.show(block=False)


""" Graph G Plot """
pos = nx.spring_layout(G)
fig = plt.figure(figsize=(7, 6))
node_size = 100
node_color_list = []
# max_k, 즉 Modularity 가 가장 높은 지점의 Community k 별로 색깔 설정
for i in range(len(G.nodes)):
    if i in max_k[0]:
        node_color_list = node_color_list + ['red']
    elif i in max_k[1]:
        node_color_list = node_color_list + ['yellow']
    elif i in max_k[2]:
        node_color_list = node_color_list + ['blue']
im = nx.draw_networkx_nodes(G, pos, node_color=node_color_list, node_size=node_size)
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_labels(G, pos, font_size=10, font_color="black")
plt.xticks([])
plt.yticks([])
plt.show(block=False)

---