Barabasi-Albert model (BA model)은 graph를 만드는 generative model 중 하나로, 노도의 degree에 비례해서 해당 노드에 엣지가 붙을 확률이 결정되는 모델이다. 이번 글에서는 BA model이 무엇인지에 대해 알아보고, 그것의 특징도 함께 살펴보겠다.
정의
Barabasi-Albert model은 위에서도 언급했듯이 노드의 degree에 비례해서 해당 노드에 엣지가 붙을 확률이 결정된다. 각 노드 i에 새로운 노드가 붙을 확률을 식으로 표현하면, 아래와 같이 정의할 수 있다.
위 식에서 p_i는 노드 i에 새로운 노드가 붙을 확률을 의미하고, k_i는 노드 i의 degree를 의미한다. 예를 들어서, 현재 노드 1, 2, 3이 만들어져있고 1과 2, 2와 3이 연결된 다음과 같은 그래프가 있다고 하자.
위 그래프에서 노드 1의 degree는 1, 노드 2의 degree는 2, 노드 3의 degree는 1이다. 그러므로 각 노드에 다음 노드 4가 붙을 확률은 각각 0.25, 0.5, 0.25가 된다. 이러한 확률 분포에 따라 새로운 노드가 기존 그래프에 붙고, 이를 반복하면서 그래프를 generate한다.
특징
BA model은 ER model이 가지고 있던 한계점인 각 엣지가 만들어지는 확률을 다르게 할 수 없다는 점을 극복한다. 노드의 degree가 높을수록 해당 노드에 엣지가 생길 확률이 더 높아지기 때문에, 각 노드 간 preference가 다르다는 특징을 가진다. 즉, 더 많이 연결된 노드 에 노드가 연결될 확률이 더 높아진다. 이는 다른 말로 preferential attachment model이라고 부른다. 예를 들어서, 논문들이 있다고 하자. 우리는 자연스럽게 인용수(degree)가 높은 논문을 더 많이 읽어볼 것이고, 이들을 더 많이 인용(attach)할 것이다. 그러므로 degree가 높을수록 해당 노드에 엣지가 생길 확률이 더 높아진다고 할 수 있다.
다음으로 BA model이 가지는 특징은, 만들어진 그래프의 degree distribution이 다음과 같은 분포를 따른다는 것이다.
즉, BA model은 degree가 1인 노드는 1, degree가 2인 노드는 1/8, degree가 3인 노드는 1/27 등에 비례하는 degree distribution을 가진다. 이는 heavy tailed된 distribution이라고 볼 수 있다.
이번 글에서는 preference attachement model의 기본이 되는 모델인 BA model이 무엇인지에 대해 알아보았다.
최근댓글