Erdos-Renyi Model 설명 (Erdős–Rényi model이란? ER model이란?)

 이번 글에서는 graph를 만드는 generative model의 가장 기본이 되는 모델인 Erdos-Renyi model이 무엇이고, 그 특징이 어떤 것인지에 대해 알아보겠다.

정의

 Erdos-Renyi Model은, 한 마디로 정리하면 모든 엣지가 생길 확률이 일정한 generative model이다. 노드 u와 v 사이에 엣지가 생길 확률(r)은 아래와 같이 정의할 수 있다. 

 즉, 간단하게 어떤 노드 쌍을 가져오더라도 이들 사이에 엣지가 존재할 확률은 r인 모델인 것이다. 이 방식으로 그래프를 만드는 데에는 O(|V^2|)의 time complexity가 필요하다. (모든 노드 쌍에 대해 엣지가 존재할 지 여부를 결정해야 하기 때문이다.)

장단점

 Erdos-Renyi model의 장점은 간단하다는 것이다. 우리가 원하는 노드의 개수만 정하면 굉장히 직관적으로 이해할 수 있고, 구현도 할 수 있다. 단점은 realistic한 graph를 만들 수 없다는 것이다. 우리가 결정할 수 있는 요소가 노드와 노드 사이에 엣지가 생길 확률인 r밖에 없기 때문에, 이를 graph 내의 노드들의 평균 degree로 정하는 것 외에는 변화시킬 수 있는 것이 없다. 그렇기 때문에 degree distribution, node clustering coefficient 등은 만들어지는 그래프의 특성에 반영할 수 없는 것이다. 

 너무 오랜만에 현생의 스트레스 해소를 위해 (아주 짧긴 하지만) 2022 첫 포스팅. 2021년 결산은 생각하고 있는 일들이 정리가 좀 되면 꾸준한 블로그 글 작성과 함께..

References

1. Hamilton. William L., Graph Representation Learning.