그래프의 구조를 어떻게 분석할까?

그래프의 구조를 어떻게 분석할까?¶

---

✅ 군집 구조와 군집 탐색 문제¶

1️⃣ 군집의 정의¶

📌 군집(Community)이란 다음 조건들을 만족하는 정점들의 집합이다.¶

• 집합에 속하는 정점 사이에는 많은 간선이 존재한다.
• 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재한다.

이는 수학적으로 엄밀한 정의는 아니다. 예시 그래프에는 11개의 군집이 있는 것으로 보인다.

2️⃣ 군집 탐색 문제¶

📌 그래프를 여러 군집으로 "잘" 나누는 문제를 군집 탐색(Community Detection)문제라고 한다.¶

• 보통은 각 정점이 한 개의 군집에 속하도록 군집을 나눈다.
• 비지도 기계학습 문제인 클러스터링(Clustering)과 상당히 유사

먼저 성공적인 군집 탐색부터 정의하자

✅ 군집 구조의 통계적 유의성과 군집성¶

1️⃣ 비교 대상: 배치 모형¶

📌 성공적인 군집 탐색을 정의하기 위해 먼저 배치 모형(Configuration Model)을 소개한다.¶

주어진 그래프에 대한 배치 모형은,

• 각 정점의 연결성(Degree)을 보존한 상태에서
• 간선들을 무작위로 재배치하여서 얻은 그래프

배치 모형에서 임의의 두 정점 $i$와 $j$ 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례한다.

2️⃣ 군집성의 정의¶

📌 군집 탐색의 성공 여부를 판단하기 위해서, 군집성(Modularity)이 사용된다.¶

그래프와 군지들의 집합 S가 주어졌다고 하자
각 군집 s ∈ S 가 군집의 성질을 잘 만족하는 지를 살펴보기 위해,
군집 내부의 간선의 수를 그래프와 배치 모형에서 비교한다.

구체적으로 군집성은 다음 수식으로 계산된다.

• 여기서 기댓값을 사용한 이유는 배치 모형이 무작위성을 포함하고 있기 때문

즉, 배치 모형과 비교했을 때,
그래프에서 군집 내부 간선의 수가 월들이 많을 수록 성공한 군집 탐색이다.

📌 군집성은 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단한다.¶

• 군집성은 항상 -1 ~ +1 사이의 값을 갖는다.
• 보통 군집성이 0.3 ~ 0.7 정도의 값을 가질떄, 그래프에 존재한느 통계적으로 유의미한 군집들을 찾아냈다고 할 수 있다.

✅ 군집 탐색 알고리즘¶

1️⃣ Girvan-Newman 알고리즘¶

📌 Girvan-Newman 알고리즘은 대표적인 하향식(Top-Down) 군집 탐색 알고리즘이다.¶

• Girvan-Newman 알고리즘은 전체 그래프에서 탐색을 시작한다. 군집들이 서로 분리 되도록 간선을 순차적으로 제거한다.
• 어떤 간선을 제거해야 군집들이 분리 될까? 그건 서로 다른 군집을 연결하는 다리(Bridge) 역할의 간선을 분리해야한다.

📌 서로 다른 군집을 연결하는 다리 역할의 간선을 어떻게 찾아낼까?¶

• 간선의 매개 중심성(Betweenness Centrality)을 사용한다.
• 이는 해당 간선이 정점 간의 최단 경로에 놓이는 횟수를 의미한다.

가운데 간선의 16의 값은 왼쪽 4개의 점정은 오른쪽 4개의 점정에 최단 경로를 구했을때 가운데 간선은 무조건 포함되어야 한다. 따라서 저 간선의 매개 중심성은 4 x 4인 16의 값을 가진다.

정점 $i$로 부터 $j$로의 최단 경로의 수를 $\sigma_{i,j}$라고 하고
그 중 간선$(x,y)$를 포함한 것을 $\sigma_{i,j}(x,y)$라고 하자
간선 $(x,y)$의 매개 중심성은 다음 수식으로 계산된다.

$$\sum_{i<j} {\sigma_{i,j}(x,y) \over \sigma_{i,j}}$$¶

📌 매개 중심성을 통해 서로 다른 군집을 연결하는 다리 역할의 간선을 찾아낼 수 있다.¶

• 위 그림은 전화 그래프이다. 매개 중심성이 높을 수록 붉은 색에 가깝다.
• 실제로 매개 중심성이 높은 간선들이 서로 다른 군집을 연결하는 다리 역할을 하는 것이 확인 된다.

📌 Girvan-Newman 알고리즘은 매개 중심성이 높은 간선을 순차적으로 제거한다.¶

간선이 제거 될 때마다, 매개 중심성을 다시 계산하여 갱신한다.

간선이 모두 제거될 때까지 반복한다.

간선의 제거 정도에 따라서 다른 입도(Granularity)의 군집 구조가 나타난다.

📌 간선을 어느 정도 제거하는 것이 가장 적절한가?¶

앞서 정의한 군집성을 그 기준으로 삼는다. 즉, 군집성이 최대가 되는 지점까지 간선을 제거한다.

• 단, 현재의 연결 요소들을 군집으로 가정하되, 입력 그래프에서 군집성을 계산한다.

🔎 요약¶

• 전체 그래프에서 시작한다.
• 매개 중심성이 높은 순서로 간선을 제거하면서, 군집성의 변화를 기록
• 군집성이 가장 커지는 상황을 복원
• 이 때, 서로 연결된 정점들, 즉 연결 요소를 하나의 군집으로 간주한다.

즉, 전체 그래프에서 시작해서 점점 작은 단위를 검색하는 하향식(Top-Down) 방법이다.

2️⃣ Louvain 알고리즘¶

📌 Louvain 알고리즘은 대표적인 상향식(Bottom-Up) 군집 탐색 알고리즘이다.¶

• Louvain 알고리즘은 개별 정점에서 시작해서 점점 큰 군집을 형성한다.

• 처음 각 정점이 하나의 군집을 형성하고 있다고 생각하고 진행한다.
• 그리고 병합 과정을 거친다.
• 이 과정을 하나의 pass라고 한다.

• 위 그림은 2번째 pass의 예시이다.

❗ 이때 어떤 기준으로 군집을 합쳐야 하는지는 역시 군집성에 의해서 합치게 된다.

📌 Louvain 알고리즘의 동작 과정¶

1. Louvain 알고리즘은 개별 정점으로 구성된 크기 1의 군집들로 부터 시작한다.

1. 각 정점 $u$를 기존 혹은 새로운 군집으로 이동시킨다. 이 때, 군집성이 최대화되도록 군집을 결정한다.
2. 더 이상 군집성이 증가하지 않을 때까지 2번을 반복한다.

1. 각 군집을 하나의 정점으로하는 군집 레벨의 그래프를 얻은 뒤 3번을 수행한다.

1. 한 개의 정점이 남을 때까지 4번을 반복한다.

✅ 중첩이 있는 군집 탐색¶

• 앞서 배운 Girvan-Newman 알고리즘, Louvain 알고리즘은 군집 간의 중첩이 없다고 가정한다.

1️⃣ 중첩 군집 모형¶

📌 이를 위해 아래와 같은 중첩 군집 모형을 가정한다¶

1. 각 정점은 여러 개의 군집에 속할 수 있다.
2. 각 군집 A에 대하여, 같은 군집에 속하는 두 정점은 $P_{A}$확률로 간선으로 직접 연결
3. 두 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적이다. 예를 들어, 두 정점이 군집 A와 B에 동시에 속할 경우 두 정점이 간선으로 직접 연결될 확률은 $1-(1-P_{A})(1-P_{B})$이다.
4. 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 $\epsilon$으로 직접 연결된다.

📌 중첩 군집 모형이 주어지면, 주어진 그래프의 확률을 계산할 수 있다.¶

그래프의 확률은 다음 확률들의 곱이다.

1. 그래프의 각 간선의 두 정점이 (모형에 의해) 직접 연결될 확률
2. 그래프에서 직접 연결되지 않은 각 정점 쌍이(모형에 의해) 직접 연결되지 않을 확률

📌 중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정이다.¶

• 현실에서는 그래프는 주어지지만 중첩 군집 모형은 주어지지 않는다.
• 따라서 통계 용어를 빌리면, 최우도 추정치(Maximum ikelihood Estimate)를 찾는 과정

📌 중첩 군집 탐색을 용이하게 하기 위하여 완화된 중첩 군집 모형을 사용한다.¶

• 완화된 중첩 군집 모형에서는 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현
• 즉, 기존 모형에서는 각 정점이 각 군집에 속하거나 속하지 않거나 둘 중 하나였는데, 중간 상태를 표현할 수 잇게 된 것이다.
• 위 그림은 실숫값을 간선의 두께로 표현하였다.
• 최적화 관점에서는, 모형의 매개변수들이 실수 값을 가지기 때문에 익숙한 최적화 도구(경사하강법 등)을 사용하여 모형을 탐색할 수 있다는 장점이 있다.

✅ Girvan-Newman 알고리즘 구현 및 적용¶

1️⃣ Girvan-Newman 알고리즘¶

라이브러리 로드 & 데이터 로딩¶

In [1]:

import matplotlib.pyplot as plt             # 그래프를 그리기 위한 라이브러리
import numpy as np                          
import networkx as nx                       # 그래프의 기본적인 연산들을 위한 라이브러리
from networkx.algorithms import community   # modularity 계산을 위한 라이브러리

G = nx.Graph()
f = open('../실습코드/data/lab/lab5/community_graph.txt')    # 만약 그래프가 잘 로딩되지않는다면, ls/cd 명령어를 통해 해결 가능
for line in f:
    v1, v2 = map(int, line.split())
    G.add_edge(v1, v2)

In [2]:

szCom1 = 8          # nodeColor: Red
szCom2 = 10         # nodeColor: Yellow
szCom3 = 12         # nodeColor: Blue
nodeColorList=[]
for i in range(szCom1+szCom2+szCom3):
    if i<szCom1:
        nodeColorList = nodeColorList + ['red']
    elif i<szCom1+szCom2:
        nodeColorList = nodeColorList + ['yellow']
    else:
        nodeColorList = nodeColorList + ['blue']
print("그래프의 노드의 개수는 {}, 엣지의 개수는 {}개입니다.".format(G.number_of_nodes(), G.number_of_edges()))

그래프의 노드의 개수는 30, 엣지의 개수는 90개입니다.

Giravan-Newman 알고리즘¶

In [3]:

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값 기록
    
    ''' 초기상태의 그래프 시각화 '''
    nx.draw_networkx_nodes(G, pos, node_color= nodeColorList, node_size=100)
    nx.draw_networkx_edges(G, pos)
    plt.title('Initial state graph')
    plt.show()
    
    
    """ Girvan-Newman algorithm """
    # 군집성을 계산하여 관련 정보를 갱신
    while len(copyG.edges()) > 0:                                                          # 모든 엣지가 사라질때까지 진행한다. 
        # connected_components()로 연결 요소를 추출한다.
        recComList = sorted(nx.connected_components(copyG), key=len, reverse=True)          # 현재 그래프에 존재하는 커뮤니티를 나타낸다. [{Com1}, {Com2}, {Com3} ... ]
        # modularity()함수를 통해서 군집성을 구한다.
        recMod = community.modularity(G, communities=recComList)                            # 추출된 커뮤니티의 modularity 계산
        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
        # edge_betweenness_centrality()함수를 통해 간선별 매개 중심성을 측정
        betweenness = nx.edge_betweenness_centrality(copyG)                 # betweennes centrality 계산
        maxEdge = max(betweenness, key=betweenness.get)                     # betweeness centrality가 가장 큰 엣지 선택
        
        # 앞에 3개만 시각화 해서 보여준다.
        if step <= 3:
            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.3)           # alpha: 기존 엣지들의 투명도를 조절하여 삭제되는 엣지가 돋보이도록하는 코드, alpha가 커질수록 진해짐.
            nx.draw_networkx_edges(copyG, pos, edgelist={maxEdge}, edge_color='black')         # 삭제 되는 엣지
            plt.title(f'Step: {step} ↑Modularity↑: {recMod}')
            plt.show()

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

    return maxModG, maxMod, maxModCom, maxStep, logModularityList, pos

In [4]:

'''
    maxModG             : 가장 큰 Modularity 값을 가지고 있을 때의 그래프
    maxMod              : 가장 큰 Modularity 값
    maxModCom           : 가장 큰 Modularity 값을 가졌을 때, 커뮤니티의 정보
    maxStep             : 가장 큰 Modularity 값을 가졌을 때, Step 값
    logModularityList   : 각 Step마다의 Modularity 값
    pos                 : 처음 그렸던 그래프의 node 위치들
'''
maxModG, maxM, maxModCom, maxStep, logModularityList, pos = GirvanNewmanAlgorithm(G, nodeColorList)

step별 군집성 그래프¶

In [5]:

# 각 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()

군집성을 토대로 선정된 최종 군집을 시각화¶

In [6]:

""" 그래프 출력 """
#pos = nx.spring_layout(G)
fig = plt.figure(figsize=(7, 6))
predictedNodeColorList = []                         # 예측한 커뮤니티에 따라서, 노드별의 색깔을 담은 리스트
for i in range(len(G.nodes)):                       # 각 노드 별로 인덱스에 맞추어 
    if i in maxModCom[0]:                           # 커뮤니티 별로 색깔을 지정해준다
        predictedNodeColorList = predictedNodeColorList + ['red']
    elif i in maxModCom[1]:
        predictedNodeColorList = predictedNodeColorList + ['yellow']
    elif i in maxModCom[2]:
        predictedNodeColorList = predictedNodeColorList + ['blue']
nx.draw_networkx_nodes(G, pos, node_color=predictedNodeColorList, node_size=100)
nx.draw_networkx_edges(G, pos)
plt.show()

2️⃣ 가라테 동아리 내의 군집 분석¶

주어진 레이블은 동아리가 둘로 분열 되었을 때, 어느 쪽에 속했는지를 의미¶

In [7]:

from networkx.algorithms.community import girvan_newman
from networkx.algorithms.community import kernighan_lin_bisection
from networkx.algorithms.community import greedy_modularity_communities

'''
    Karate Club Graph
    # of nodes :  34
    # of edges :  78
    Label : ['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)
def plotResult(G, pos, com):
    '''
        Community가 주어진다면, 해당 커뮤니티별로 노드의 색깔을 달리하여 그래프를 출력한다.
    '''
    nodeColorList = [0] * G.number_of_nodes()

    colors = ['red','blue','green','purple']            # 최대 4개의 커뮤니티
    for i in range(len(com)):
        for node in com[i]:
            nodeColorList[node] = colors[i];      
    nx.draw_networkx_nodes(G, pos, node_color=nodeColorList, node_size=100)
    nx.draw_networkx_edges(G, pos)
    plt.plot()

주어진 레이블¶

In [8]:

nodeColorList = []
for i in range(len(G.nodes)):                       # 각 노드 별로 인덱스에 맞추어 
    if label[i] == 'Mr. Hi':                        # 커뮤니티 별로 색깔을 지정해준다
        nodeColorList = nodeColorList + ['red']
    elif label[i] == 'Officer':
        nodeColorList = nodeColorList + ['blue']

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

군집 분석¶

In [9]:

comKarateList  = list(girvan_newman(G))     # Girvan-Newman 알고리즘의 경우, 각 step마다의 community가 저장되어 있기때문에 커뮤니티가 2개로 나누어진 시점의 Community를 가져온다.
for com in comKarateList:
    if len(com) == 2:
        comKarate = com
plotResult(G, pos, comKarate)

다양한 군집 분석 알고리즘 제공¶

In [10]:

comKarate  = list(kernighan_lin_bisection(G))
plotResult(G, pos, comKarate)

In [11]:

comKarate  = list(greedy_modularity_communities(G))
plotResult(G, pos, comKarate)