Graph spectral partitioning/clustering with python

요즘 Machine learning with graph (CS224W) 강의 리뷰를 어느 분들이 감사하게 해주어서 보고있다.

오늘은 Spectral clustering에 대해 읽었는데, 처음 소개하는 알고리즘이 간단하게 보이기도 하고 networkx도 계속 연습할 겸 코딩함. 이것보다 발전된 방향은 여러가지 더 있다.

5.Spectral Clustering

5. Spectral Clustering

---

목적은 어떤 그래프가 주어졌을때, 밀집도를 비교하여 서로 비슷한 밀도를 가진 군집을 찾아내어 구분짓는 것이 목표이다.

수학적으로 전개와 증명을 이어나가는데, 하나하나 제대로 이해할 수는 없었다. 수학은 복잡한데 비해, 알고리즘은 간단하다.

1. 그래프의 Lapalcian matrix(L=Degree matrix-Adjacency matrix)를 구하고,

2. 그 행렬의 두번째로 작은 eigen value값을 구한 후 $\lambda_2$

3. 거기 해당하는 eigen vector 요소의 양수에 해당하는 노드들과 음수에 해당하는 노드들을

4. 다른 파티션이라고 여기면 된다.

 

"""
Author: Minjae Jung
Graph spectral partitioning

1. Calculate the laplacian matrix L = D-A
2. Calculate the lambda2(second minimum eigen value)
3. Calculate the corresponding eigen vector of the lambda2
4. Partition graph by sign of the corresponding eigen vector of the lambda2
"""

import networkx as nx
from networkx.linalg.spectrum import normalized_laplacian_spectrum

import numpy as np
from numpy.linalg import eig

import matplotlib.pyplot as plt


## Generate barbell graph
G = nx.barbell_graph(5,4)
pos = nx.spring_layout(G)

## 1. Calculate Laplcian
L = nx.linalg.laplacianmatrix.laplacian_matrix(G)
# Convert Scipy sparse matrix to numpy array
L_np = L.toarray()

## 2. Caculate eigen value and eigen vactor
eig_val, eig_vec = eig(L_np)

## 3. Calculate lambda2
lambda2_idx = np.argsort(eig_val)[1]
lambda2 = eig_val[lambda2_idx]

## 4. Partition graph by sign of the corresponding eigen vector of the lambda2
group_raw = eig_vec[:, lambda2_idx]
group_mask = group_raw > 0

# Positive side group
group1 = np.array(G.nodes)[group_mask]
# Negative side group
group2 = np.array(G.nodes)[~group_mask]

## Draw the partitioned graph with colored label
nx.draw_networkx_nodes(G, pos, nodelist=group1, node_color='r')
nx.draw_networkx_nodes(G, pos, nodelist=group2, node_color='b')
nx.draw_networkx_edges(G, pos)
plt.axis("off")
plt.show()

---

Experiment

1. Barbell graph의 경우

 

nx.barbell_graph(5,4)

2. Cubical graph의 경우

 

nx.cubical_graph()

 

3. Windmill graph의 경우

 

nx.windmill_graph(4, 5)

 

이런경우는 잘 안됨 클러스터가 여러개

 

4. Random graph의 경우

nx.gnp_random_graph()

밀집 상황

그냥 랜덤

isolate node 에 대해서도 어느정도 가능

---

클러스터가 여러개인 경우에 대한 방법도 수업에는 나와있다.

Graph neural network 저만해도 꽤나 긴 시리즈로 이어지는데 끝까지 완주하면 좋겠다.