[네트워크이론] Link communities (링크 커뮤니티)

 점(노드)과 선(엣지)으로 나타내는 네트워크 구조를 통해 새로운 정보를 얻는 것은 참 매력적이다. 커뮤니티 추출법은 네트워크의 구조 속에서 노드간, 엣지간의 관계를 통해 커뮤니티를 추출하는 방법이다.

 저번에는 네트워크 속 커뮤니티의 모듈성을 이용한 커뮤니티 추출법에 대해 공부했었다. 

2018/02/18 - [연구/연구] - [네트워크이론] Network Modularity 실제 사용 예 Girvan-Newman algorithm

 오늘은 새로운 관점의 커뮤니티 추출법 "Link Community"에 대해 소개한다. Link community는 Edge를 기반으로 커뮤니티를 추출한다. 지난번의 Modularity를 이용한 방법과 다른 점은, 한개의 Node가 여러 개의 Community에 소속될 수 있다는 것이다.

 이 방법은 새로운 관점을 제공한다. 내가 A라는 그룹에도 속하고, B라는 그룹에도 속한다면 기존의 Node기반 커뮤니티 추출에서는 조금이라도 내가 더 관계를 지니는 그룹에 속하도록 추출이 이루어진다. Link 커뮤니티는 Edge를 기반으로 추출하기 때문에, 나는 A와 B라는 그룹과 관계가 있다는 방식으로 추출이 이루어질 수 있다.

 다음 그림은 Link community로 추출한 Community의 예이다.

 

예전 Modularity 방식으로 추출했다면, Node 0, 8, 4가 모여 이루는 Community는 추출될 수 없었을 것이고, 특히 Node 8은 커뮤니티에 소속되지 않았을 것이다. 어떠한 관점이 옳다고 할 수는 없지만, link community의 관점이 필요한 경우가 있다.

 그럼 link community를 추출하는 방법을 소개한다.

 link community는 간략히 다음과 같은 과정으로 추출된다.

 1. Edge간 유사성(Similarity)를 계산

 2. 유사성을 이용하여 Edge를 계층적 군집화(Hierarchical Clustering)

 3. 네트워크 분할 밀도(Partition Density)가 최대가 되는 Clustering step을 결정

 4. Edge의 군집화를 통해 Community 표현

 Modularity와 유사하다. Modularity는 betweenness centrality가 높은 Edge를 한개씩 잘라가며, 최대의 Modularity를 지니는 Community 분할 방식을 탐색한다면, Link community는 Edge를 유사성이 높은 집단으로 단계별로 군집화 하며, Partition density를 최대로 하는 단계를 탐색한다.

Edge간 유사성(Similarity)

---

"Jarccard coefficient"를 이용하여 유사성을 계산한다.

 유사성 계산 대상은 한 Node를 공유하는 서로 다른 Edge이다.

 점 k를 공유하는 Edge (i, k)와 Edge (j, k)의 유사성은 다음의 식으로 표현한다.

 

 n+는 자신을 포함한 인접한 Node의 개수고, 절대값 표시는 개수를 의미한다. Node i와 Node j 의 친구 중 얼마나 많은 친구가 공통된 친구인지를 나타낸다.

Similarity는 Weighted Network로 확장할 수 있다. 

이 때의 Similarity는 Jarcaard 계수를 일반화한 Tanimoto coefficient 를 통해 구할 수 있다.

 vector a_i를 다음과 같이 둔다.

 

복잡해 보이지만

i = j일 때, i에 연결된 모든 엣지의 Weight을 엣지의 개수로 나눈, 즉, i에 연결된 Edge Weight의 평균값

i != j일 때, Edge (i, j)의 Weight

을 값으로 지니는 vector이다.

 이 벡터를 이용하면 Similarity의 일반화 식을 다음과 같이 나타낼 수 있다.

 이 일반화된 식에서 분모는 합집합, 분자는 교집합의 개념을 지니며, Unweighted, Weighted 뿐만 아니라 Directed Network 까지 Similarity를 확장할 수 있게 해준다.

---

Hierarchical Clustering

---

 위에서 구한 유사성을 이용하여 Edge를 군집화한다. 

 군집화는 가까운 거리의 개체를 한개의 군집으로 묶는 방식이기 때문에, 위에서 구한 S값을 군집화 하기 위해서는 Dissimilarity = (1 - S)의 값을 이용한다.

 군집화 거리 계산과 군집화 방식은 여러가지가 있는데, 오늘 예제로 드는 방법은 유클리디안 거리를 이용한 Ward법을 이용하기로 한다.

 가장 가까운 거리(Dissimilarity가 가장 낮은 Edge)의 Edge를 한개의 군집으로 묶고, 군집을 대표하는 값을 Ward법으로 나타내어, 다시 가장 가까운 거리의 Edge 또는 군집을 묶어나가는 과정을 반복한다.

 계층 클러스터링에 대한 이야기는 여기:

2018/04/11 - [연구/연구] - [연구] 계층 클러스터 분석

---

Partitional Density

---

 Hierachical Clustering 의 군집화 정도를 평가하기 위해 Partitional Density라는 지표를 이용한다.

 

m_c : 커뮤니티 내에 포함되는 Edge의 개수

n_c : 커뮤니티 내에 포함되는 Node의 개수

 D_c는 Community 속에서 Edge의 개수가 가장 적을 때 0을, 가장 많을 때 1의 값을 가진다. Edge의 개수가 가장 적을 때는 Node간 Edge가 한개씩 밖에 없는 상태이며 이 때 m_c는 (n_c - 1)의 값을 가진다. 가장 많을 때는 모든 노드 간에 Edge가 연결된 상태이며 이 때 m_c 는 n_c(n_c - 1)/2의 값을 가진다.

 D_c에 Edge의 개수를 곱한 값을 커뮤니티 별로 다 더하여, 전체 Edge의 개수로 나눈 값을 D(분할밀도)로 정한다.

 

 D값이 최대가 되는 Hierachical Clustering Height을 구하여 Community를 분할한다.

---

Link community 추출 결과

---

 unweighted network 와 weighted network의 link community 추출 결과는 다음과 같다.

 두 경우 모두 적절한 Link community가 추출된 것을 알 수 있다. Partition Density 가 Max가 되는 Dendrogram 의 Height을 구하여, 그 때의 Clustering 결과를 Link community 추출에 이용한다. weighted에서는 Weighted가 Similarity에 포함되기 때문에 좀더 가깝고 먼 관계를 상세하게 나타내기 때문에 더 자세한 Clustering이 가능하다.

---

사용 코드

---

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import pandas as pd
import seaborn as sns
from scipy.cluster.hierarchy import dendrogram, linkage, cophenet
from scipy.spatial.distance import pdist


""" Similarity 계산 함수 """
def CAL_s(g, i, j, style):
    s = 0
    if style == 'unweighted':
        a_i = np.array([1 if v in list(g[i]) else 0 for v in list(g.nodes())], dtype=float)
        a_i[i] = np.sum(a_i) / len(np.where(a_i != 0)[0])
        a_j = np.array([1 if v in list(g[j]) else 0 for v in list(g.nodes())], dtype=float)
        a_j[j] = np.sum(a_j) / len(np.where(a_j != 0)[0])
        s = np.sum(a_i * a_j) / (np.sum(a_i * a_i) + np.sum(a_j * a_j) - np.sum(a_i * a_j))
    elif style == 'weighted':
        a_i = np.array([g[i][v]['weight'] if v in list(g[i]) else 0 for v in list(g.nodes())], dtype=float)
        a_i[i] = np.sum(a_i) / len(np.where(a_i != 0)[0])
        a_j = np.array([g[j][v]['weight'] if v in list(g[j]) else 0 for v in list(g.nodes())], dtype=float)
        a_j[j] = np.sum(a_j) / len(np.where(a_j != 0)[0])
        s = np.sum(a_i * a_j) / (np.sum(a_i * a_i) + np.sum(a_j * a_j) - np.sum(a_i * a_j))
    else:
        print("check spell of style")
    return s


if __name__ == '__main__':
    
    """ Sample Graph(weighted) """
    G = nx.Graph()
    """ Add Nodes """
    node_num = 9
    G.add_nodes_from(range(node_num))
    """" Community """
    C_A = [0, 1, 2, 3]
    C_B = [0, 4, 8]
    C_C = [4, 5, 6, 7]
    """ ADD Edges """
    # Edge (i, j, w) 는 i-j Edge의 Weight이 w임을 표현
    L_A = []    # A 커뮤니티 내 Edge는 전결합, Weight는 1~4의 랜덤값 대입
    for node_i in C_A:
        for node_j in C_A:
            if node_j > node_i:
                new_edge = (node_i, node_j, np.random.randint(1, 4))
                L_A = L_A + [new_edge]
    L_B = [(0, 4, 1), (0, 8, 2), (4, 8, 1)]
    L_C = [(4, 5, 2), (4, 6, 1), (5, 6, 5), (5, 7, 4), (6, 7, 1)]
    G.add_weighted_edges_from(L_A)
    G.add_weighted_edges_from(L_B)
    G.add_weighted_edges_from(L_C)
    
    
    """ All_edge List"""
    all_edges = list(G.edges())
    all_edges.sort()
    
    
    """ Make Dissimilarity matrix(S, DIS) """
    S_matrix = np.zeros((len(all_edges), len(all_edges)))
    row = 0
    style = 'weighted'  # style: weighted, unweighted
    for (n1, n2) in all_edges:
        column = 0
        for (n3, n4) in all_edges:
            inter = {n1, n2} & {n3, n4}
            if len(inter) == 1:
                pool = list({n1, n2, n3, n4} - inter)
                S_matrix[row][column] = CAL_s(g=G, i=pool[0], j=pool[1], style=style)    # style: weighted, unweighted
            elif len(inter) == 2:
                S_matrix[row][column] = 1.0
            column = column + 1
        row = row + 1
    
    
    """ Clustering(average) """
    DIS_matrix = 1 - S_matrix
    HC = linkage(DIS_matrix, method='average', metric='euclidean')
    
    
    """ Hierachical Clustering Dendrogram 가시화 """
    fig = plt.figure()
    dn = dendrogram(Z=HC, labels=all_edges, leaf_rotation=90)
    plt.show(block=False)
    pd_DIS_matrix = pd.DataFrame(data=DIS_matrix, index=all_edges, columns=all_edges)
    sns.clustermap(pd_DIS_matrix)
    plt.show(block=False)
    
    
    """ Height """
    Heights_array = HC[:, 2]
    """ Clustering by Height"""
    H_list = Heights_array.tolist()
    D_sum_list = []
    Best_C = []
    Best_D = 0
    Best_H = 0
    for Height in Heights_array:
        step = np.array(HC[np.where(HC[:, 2] <= Height)][:, :2], dtype=int)
        C_edges = [[i] for i in all_edges]
        C_list = [[i] for i in all_edges]
        for [i, j] in step:
            C_edges.remove(C_list[i])
            C_edges.remove(C_list[j])
            C_edges = C_edges + [C_list[i] + C_list[j]]
            C_list = C_list + [C_list[i] + C_list[j]]
    
        """ CAL Partition density(D) """
        D_list = []
        for edges in C_edges:
            m = len(edges)
            n_pool = set(sum(edges, ()))
            n = len(n_pool)
            if n > 2:
                D = 2 * m * (m - n + 1) / (n-2) / (n-1)
            else:
                D = 0
            D_list = D_list + [D]
    
        D_sum = sum(D_list) / len(all_edges)
        D_sum_list = D_sum_list + [D_sum]
    
        if D_sum > Best_D:
            Best_C = C_edges
            Best_D = D_sum
            Best_H = Height
    
    
    """ Clustering When Best Height in Hierachical Clustering """
    Height = Best_H
    step = np.array(HC[np.where(HC[:, 2] <= Height)][:, :2], dtype=int)
    C_edges = [[i] for i in all_edges]
    C_list = [[i] for i in all_edges]
    for [i, j] in step:
        C_edges.remove(C_list[i])
        C_edges.remove(C_list[j])
        C_edges = C_edges + [C_list[i] + C_list[j]]
        C_list = C_list + [C_list[i] + C_list[j]]
    color_list = range(len(C_edges))
    group_num = 0
    for edge_group in C_edges:
        for edge in edge_group:
            G[edge[0]][edge[1]]['color'] = group_num
        group_num = group_num + 1
    
    
    """ 가시화 """
    fig = plt.figure()
    ax1 = fig.add_subplot(2, 1, 1)
    pos = nx.fruchterman_reingold_layout(G)
    edges = G.edges()
    nx.draw_networkx_nodes(G, pos, node_size=200, node_color="black")
    weights = np.array([G[u][v]['weight'] for u, v in edges])
    # weights = 2
    colors = [G[u][v]['color'] for u, v in edges]
    nx.draw_networkx_edges(G, pos, width=weights, edge_color=colors, arrows=True)
    nx.draw_networkx_labels(G, pos, font_size=10, font_color="white")
    plt.xticks([])
    plt.yticks([])
    plt.title(style)
    ax2 = fig.add_subplot(2, 3, (4, 5))
    dn = dendrogram(Z=HC, labels=all_edges, leaf_rotation=90, color_threshold=Height)
    plt.title('dendrogram')
    ax3 = fig.add_subplot(2, 3, 6)
    plt.plot(D_sum_list, H_list)
    plt.title('parition density')
    plt.show(block=False)
    

---

참고 논문

  Link communities reveal multiscale complexity in networks

  Yong-Yeol Ahn, James P. Bagrow, Sune Lehmann

  Nature 466, 761-764 (05 August 2010)

  url: https://www.nature.com/articles/nature09182