라플라시안 행렬(Laplacian Matrix)을 사용하여 그래프 분할하기

이 예제에서는 그래프의 라플라시안 행렬을 사용하여 피들러 벡터(Fiedler Vector)를 계산하는 방법을 보여줍니다. 피들러 벡터는 그래프를 두 개의 부분 그래프로 분할하는 데 사용할 수 있습니다.

데이터 불러오기

바벨형 그래프의 희소 인접 행렬과 노드 좌표가 포함된 데이터 세트 barbellgraph.mat를 불러옵니다.

load barbellgraph.mat

그래프 플로팅

사용자 지정 노드 좌표 xy를 사용하여 그래프를 플로팅합니다.

G = graph(A,'omitselfloops');
p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'Marker','.');
axis equal

라플라시안 행렬과 피들러 벡터 계산

그래프의 라플라시안 행렬을 계산합니다. 그런 다음, eigs를 사용하여 2개의 가장 작은 고유값과 이에 대응하는 고유벡터를 계산합니다.

L = laplacian(G);
[V,D] = eigs(L,2,'smallestabs');

피들러 벡터(Fiedler Vector)는 그래프에서 두 번째로 작은 고유값에 대응하는 고유벡터입니다. 가장 작은 고유값은 0이며, 이는 그래프에 하나의 연결성분이 있음을 나타냅니다. 이 경우, V의 두 번째 열은 두 번째로 작은 고유값 D(2,2)에 대응합니다.

D

D = 2×2
10-3 ×

    0.0000         0
         0    0.2873

w = V(:,2);

피들러 벡터를 구하는 것은 고유값과 고유벡터의 일부만 계산하는 것이므로 큰 그래프의 경우에는 eigs를 사용하는 것이 좋고, 작은 그래프의 경우에는 라플라시안 행렬을 전체 저장 형식으로 변환하여 eig(full(L))을 사용하는 것이 좋습니다.

그래프 분할

피들러 벡터 w를 사용하여 그래프를 2개의 부분 그래프로 분할합니다. 노드의 w가 양의 값이면 노드는 부분 그래프 A에 할당됩니다. 그렇지 않으면 노드는 부분 그래프 B에 할당됩니다. 이런 방식을 부호 절단(Sign Cut) 또는 영점 임계값 절단(Zero Threshold Cut)이라고 합니다. 부호 절단은 절단의 가중치를 최소화하며, 여기에는 그래프의 모든 자명하지 않은 절단의 가중치에 대한 상한과 하한이 적용됩니다.

부호 절단을 사용하여 그래프를 분할합니다. w>=0인 노드의 부분 그래프를 빨간색으로 강조 표시하고, w<0인 노드의 부분 그래프를 검은색으로 강조 표시합니다.

highlight(p,find(w>=0),'NodeColor','r') % subgraph A
highlight(p,find(w<0),'NodeColor','k') % subgraph B

바벨형 그래프의 경우, 이와 같이 분할하면 그래프가 2개의 동일한 노드의 집합으로 정확히 이등분됩니다. 그러나, 부호 절단이 항상 균형 잡힌 절단을 생성하는 것은 아닙니다.

w의 중앙값을 계산하고 이 중앙값을 임계값으로 사용하면 항상 그래프를 이등분할 수 있습니다. 이러한 분할을 중앙값 절단(Median Cut)이라고 하며, 이 경우 각 부분 그래프에 동일한 개수의 노드가 할당됩니다.

중앙값 절단을 사용할 경우, 먼저 중앙값을 기준으로 w의 값을 이동합니다.

w_med = w - median(w);

그런 다음, w_med의 부호를 기준으로 그래프를 분할합니다. 바벨형 그래프의 경우, w의 중앙값이 0에 가까우므로 절단 후에는 거의 이등분으로 나뉩니다.

참고 항목

graph | digraph | laplacian | subgraph

관련 항목

• 유방향 그래프와 무방향 그래프