[네트워크이론] Label propagation algorithm for community detection

 지금까지 다뤄온 community detection의 방식(Girvan-Newman, Louvain, Link community)에서는 일련의 반복 알고리즘을 수행하며, 가장 최적의 검출 상태를 추정하기 위해 Modularity 또는 Partitional density라는 지표를 이용했다.

 Label propagation은 Agglomerative(점점 덩어리를 불려나가는) 방식과 개념 면에서는 흡사하지만, 지표를 사용하지 않는다는 면에서 조금 차이가 있다.

 Label propagation 알고리즘에는 내가 속한 Community는 나의 주변 사람들이 속한 Community일 확률이 높다는 직관적이지만 강력한 개념이 담겨있다. 예를 들어, 'B'라는 community에 속한 node i의 주변 node들 중 많은 비율이 'A'라는 community에 속해 있다면, node i의 community를 'B'➔'A'로 수정하는 것이다.

 이를 직관적으로 설명해 보자면, '개인이 바라보는 사회의 모습' 혹은 '사회에 의해 정의되는 개인'에 대한 규칙이다.

 이 알고리즘은 안정된 상태를  label propagation이 멈춘 상태, 즉, 나의 community와 내 주변인의 community 중 빈도가 가장 높은 community가 일치한 상태로 정의하기 때문에, Modularity와 같은 지표의 계산이 필요하지 않다. 지표의 계산이 필요 없으므로 빠른 속도의 검출에 용이하다. 

 알고리즘이 처음 발표된 논문[1]을 참조하여 내용을 간략히 정리해본다.

Algorithm

---

 1. 모든 node들은 각자의 label(community)를 지닌 상태에서 시작한다.

 2. node의 순서를 random하게 배치한 리스트를 작성한다.

 3. 리스트 순서대로 node를 선택한 후, 해당 node의 주변 node들이 지닌 label 중 가장 빈도가 높은 label (max freq label)로 해당 node의 label을 변경한다. (이 때, 동일 빈도의 label이 여러 개 발생한다면, 그 중 임의로 label을 선택한다.)

 4. 모든 node가 유일한 max freq label을 가질 때 까지 2-3을 반복한다. 

---

알고리즘의 종료 조건인 4번은 안정적인 community 배속 상태를 가늠하기 위한 조건이다. 주변 node들이 지닌 label 중 가장 높은 빈도로 나타나는 label이 여러 개 존재한다는 것은 여러 커뮤니티의 중간에 껴 있는 형태다. 알고리즘을 반복할 수록, 입지가 약한 community는 소멸하고, density가 높은 community를 중심으로 label이 결정되어간다. 고로, max freq label이 유일한 상태란, density가 높은 community 구조로부터 전파된 label이 안정적인 경계 상태에 돌입했다는 것을 뜻한다.

 알고리즘 3번은 node를 하나씩 순서대로 update 한다. 고로, node 리스트 중에서 이미 update된 node의 label을 다음 node의 update에 적용할지 말지에 따라 Asynchronous / Synchronous 방식으로 나누어진다.

 Synchronous는 모든 node의 업데이트에 이전 단계에서 node들이 지닌 label 정보를 이용하므로, 개념적으로는 깔끔해 보이지만, 2부 그래프(bipartite) 성질을 지닌 network에서 label propagation이 끝없이 진동해 버리는 현상이 발생한다는 단점이 있다. 두 뭉텅이의 node들이 번갈아 가며 label을 주고 받는 상황이 발생하는 것이다.

 고로, Asynchronous, 즉, 모든 node들의 label을 동시에 update하지 말고, 한 node 씩 update해 나가는 방식이 사용된다. Synchronous와 Asynchronous가 지니는 장단점을 보완하는 Semi-synchronous 방식[2]이 있다고 하는데, 다음에 기회가 되면 정리해 봐야겠다.

[1] Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. "Near linear time algorithm to detect community structures in large-scale networks." Physical review E 76.3 (2007): 036106.

[2] Cordasco, Gennaro, and Luisa Gargano. "Community detection via semi-synchronous label propagation algorithms." 2010 IEEE International Workshop on: Business Applications of Social Network Analysis (BASNA). IEEE, 2010.

Code (networkx를 이용한 network 생성)

---

import numpy as np
import copy
import networkx as nx
import matplotlib.pyplot as plt

def Add_Inner_edges(range, num):
    inner_edges = []
    while len(inner_edges) < num:
        tmp = np.sort(np.random.choice(range, size=2, replace=None)).tolist()
        tmp += [np.random.uniform(0, 1)]  # random weight
        new_edge = tuple(tmp)
        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)
        tmp = np.sort([np.random.choice(Community_all[group_choiced[0]], replace=None),
                 np.random.choice(Community_all[group_choiced[1]], replace=None)]).tolist()
        tmp += [np.random.uniform(0, 1)]  # random weight
        new_edge = tuple(tmp)
        if new_edge not in outter_edges:
            outter_edges = outter_edges + [new_edge]
    return outter_edges


""" Network 생성 """
# 총 150명
G = nx.Graph()
G.add_nodes_from(range(150))

# Community 설정 3개의 커뮤니티
Community1 = range(0, 40)
Community2 = range(40, 90)
Community3 = range(90, 150)
Community_all = Community1, Community2, Community3

# 내부 연결 추가
Inner_edges_1 = Add_Inner_edges(range=Community1, num=200)  # Community 1 100개
Inner_edges_2 = Add_Inner_edges(range=Community2, num=250)  # Community 1 150개
Inner_edges_3 = Add_Inner_edges(range=Community3, num=300)  # Community 1 200개
G.add_weighted_edges_from(Inner_edges_1)
G.add_weighted_edges_from(Inner_edges_2)
G.add_weighted_edges_from(Inner_edges_3)

# 외부 연결 추가
Outter_edges = Add_Outer_edges(Community_all, 50)  # Community 1-2-3 간에 50개
G.add_weighted_edges_from(Outter_edges)
pos = nx.spring_layout(G)

# Plot
fig = plt.figure()
edges = G.edges()
weights = [G[u][v]['weight'] for u, v in edges]
node_size = 50
nx.draw_networkx_nodes(G, pos, node_size=node_size)
nx.draw_networkx_edges(G, pos, width=weights)
nx.draw_networkx_labels(G, pos, font_size=5, font_color="black")
plt.xticks([])
plt.yticks([])
plt.show(block=False)

의도대로 3개의 커다란 cluster 구조를 지닌 network가 생성된 것을 확인할 수 있다.

---

Python package인 networkx에는 label propagation을 구현한 함수가 포함되어 있다.

Code (community detection - networkx package)

---

""" Library """
c_iter = community.asyn_lpa_communities(G=G, weight=None)   # Asynchronous
# c_iter = community.label_propagation_communities(G=G)   # Semi-synchronous

max_k_w = []
for c in c_iter:
    max_k_w += [c]

""" Make Community Color list """
community_num_group = len(max_k_w)
color_list_community = [[] for i in range(len(G.nodes()))]
for i in range(len(G.nodes())):
    for j in range(community_num_group):
        if i in max_k_w[j]:
            color_list_community[i] = j

""" Plot """
fig = plt.figure()
edges = G.edges()
weights = [G[u][v]['weight'] for u, v in edges]
Feature_color_sub = color_list_community
node_size = 50
nx.draw_networkx_nodes(G, pos, node_size=node_size, node_color=Feature_color_sub, cmap='jet', vmin=0, vmax=max(color_list_community))
nx.draw_networkx_edges(G, pos, width=weights)
nx.draw_networkx_labels(G, pos, font_size=5, font_color="black")
plt.xticks([])
plt.yticks([])
plt.show(block=False)

 3개의 적절한 community detection이 이루어 졌음을 알 수 있다.

 async_lpa_communities : Asynchronous Label propagation

 label_propagation_communities : Semi-synchronous Label propagation

---

Code (community detection - Manual)

---

package 내용을 참조, manual code를 작성해서 community가 detection 되는 과정을 살펴 보았다. 

from collections import Counter
import random
import matplotlib.animation as animation


""" Manual """
weight = None
labels = {n: i for i, n in enumerate(G)}
cont = True
labels_log = [labels.copy()]
while cont:
    cont = False
    nodes = list(G)
    random.shuffle(nodes)
    # Calculate the label for each node
    for node in nodes:
        if len(G[node]) < 1:
            continue

        # Get label frequencies. Depending on the order they are processed
        # in some nodes with be in t and others in t-1, making the
        # algorithm asynchronous.
        label_freq = Counter()
        for v in G[node]:
            label_freq.update({labels[v]: G.edges[v, node][weight]
            if weight else 1})
        # Choose the label with the highest frecuency. If more than 1 label
        # has the highest frequency choose one randomly.
        max_freq = max(label_freq.values())
        best_labels = [label for label, freq in label_freq.items()
                       if freq == max_freq]
        new_label = random.choice(best_labels)
        labels[node] = new_label
        # Continue until all nodes have a label that is better than other
        # neighbour labels (only one label has max_freq for each node).
        cont = cont or len(best_labels) > 1
        labels_log += [labels.copy()]


def ANI_Undirected_plot(time, G, color_list, pos, fig):
    global step

    all_step = len(color_list)
    step_view = step % all_step

    plt.cla()

    Feature_color_sub = list(color_list[step_view].values())
    Gedges = G.edges()
    node_size = 50

    weights = [G[u][v]['weight'] for u, v in Gedges]
    nx.draw_networkx_nodes(G, pos, node_size=node_size, node_color=Feature_color_sub, cmap='jet', vmin=0, vmax=149)
    nx.draw_networkx_edges(G, pos, width=weights)
    nx.draw_networkx_labels(G, pos, font_size=5, font_color="black")
    plt.xticks([])
    plt.yticks([])

    plt.suptitle('step: ' + str(step_view))

    if step < all_step-1:
        step = step + 1


""" Plot Community (Dynamic) """
fig_ani = plt.figure(figsize=(7, 6))
step = 0
weight = True
ani = animation.FuncAnimation(fig_ani, ANI_Undirected_plot, fargs=(G, labels_log, pos, fig_ani),
                              interval=1, save_count=len(labels_log))
plt.show(block=False)

---