Stochastic block model (SBM)은 특정 노드끼리 community structure를 가지는 그래프를 만들 수 있는 generative model이다. 이번 글에서는 stochastic block model이 무엇인지와 함께 그것의 장점에 대해 알아보겠다.
정의
Stochastic block model은 위에서 언급했듯이 특정 노드끼리 community structure를 가진다. 즉, 각 노드들이 서로 가까운 관계를 가지는 노드들도 있고, 서로 먼 관계를 가지는 노드들도 있는데, 가까운 관계를 가지는 노드끼리 community를 형성하는 구조를 반영할 수 있는 것이다.
SBM을 정의하기 위해서는 몇 가지의 개념을 정의해야 한다. 우선, 우리에게 $\gamma$개의 block이 있다고 가정하고, 각 block을 $C_1, ..., C_\gamma$로 부른다고 하자. 그리고 각 노드가 block i ($C_i$)에 속할 확률을 $p_i$라고 하고, block i에 속한 노드와 block j에 속한 노드 사이에 엣지가 있을 확률을 $/boldmath{C}[i, j]$라고 나타낸다고 하자. 그러면 우리는 다음과 같은 과정으로 그래프를 만들 수 있다.
- 모든 노드들에 대해 각 노드가 속해야 하는 block $C_i$를 $(p_1, ..., p_\gamma)$로부터의 sampling을 통해 결정한다.
- 각 노드 쌍에 대해, 해당 노드들 사이에 엣지가 존재하는지의 여부를 $/boldmath{C}[i, j]$에 따라 sampling하여 결정한다.
장점
SBM을 통해 우리는 community structure를 표현할 수 있다. 예를 들어, i와 j가 같을 때, 즉 두 노드가 같은 block에 속할 때는 엣지가 생길 확률을 높게 하고, i와 j가 다를 때, 즉 두 노드가 다른 block에 속할 때는 엣지가 생길 확률을 낮게 함으로써 같은 block 속 노드들끼리는 잘 연결되고 다른 block 속 노드들끼리는 연결의 빈도가 낮게 만드는 것이 가능한 것이다.
이번 글에서는 SBM이 무엇인지에 대해 알아보았다. 이번 글에서 설명한 SBM은 가장 기본적인 형태이고, node feature가 있는 경우, bipartite graph의 경우 등 SBM의 다양한 variation들이 존재한다.
References
1. Hamilton, W. L. Graph Representation Learning.
최근댓글