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

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

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 알고리즘의 동작 과정¶

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

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

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

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

✅ 중첩이 있는 군집 탐색¶

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

1️⃣ 중첩 군집 모형¶

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

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

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

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

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

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

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

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

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

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

1️⃣ Girvan-Newman 알고리즘¶

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

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)

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 알고리즘¶

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

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

step별 군집성 그래프¶

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

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

""" 그래프 출력 """
#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️⃣ 가라테 동아리 내의 군집 분석¶

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

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

주어진 레이블¶

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

군집 분석¶

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)

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

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

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

그래프 신경망이란 무엇일까? (기본) (1)	2021.02.26
그래프를 추천시스템에 어떠게 활용할까? (심화) (0)	2021.02.25
그래프의 정점을 어떻게 벡터로 표현할까? (0)	2021.02.25
그래프를 추천시스템에 어떻게 활용할까?(기본) (0)	2021.02.24
그래프를 바이럴 마케팅에 어떻게 활용할까? (0)	2021.02.23
검색 엔진에서는 그래프를 어떻게 활용할까? (0)	2021.02.23
실제 그래프는 어떻게 생겼을까? (0)	2021.02.22
그래프란 무엇이고 왜 중요할까? (0)	2021.02.22

개발자CuCu