그래프의 중심성 척도: 수식, 직관, 그리고 몇 가지 주목할 만한 사항들
하단에 Embed된 pdf 파일은 2019-2학기 전기정보공학부의 '비선형제어특론'(심형보 교수님)의 수업을 통해 Francesco Bullo의 책 <Lectures on Network Systems>를 기반으로 하여 제작하게 된 발표자료이다. 그래프(혹은 네트워크)에서 어떤 노드가 구조적으로 중요한 역할을 하는지 측정하기 위한 다양한 지표들(중심성 척도, 중심도)에 대해 공부하여 개략적으로 정리하였고, 가능하다면 응용 사례도 첨부하고자 하였다.
첫째로 가장 기본적이라고 할 수 있는 차수 중심도(Degree centrality)는 각 노드가 몇 개의 간선(edge)을 가지고 있는지 세어 주는 것이다. 복잡 네트워크 과학 분야의 역사적 발달에 있어서, 차수 중심도의 분포가 멱법칙을 띠는 네트워크인 '척도 없는 네트워크'에 대해 A.-L. Barabasi, R. Albert, H. Jeong 등이 수행한 일련의 연구가 중요한 역할을 하기도 하였다.
고윳값 중심도(Eigenvalue centrality)는 특정 노드의 중심성을 평가할 때, 그 주변 노드의 중심성까지 고려하겠다는 철학으로 개발되었다. 각 노드의 중심도를 구하는 방정식이 고윳값 방정식의 형태를 보인다는 점에서 이와 같이 이름붙여진 것 같다. 주변 노드의 개수뿐 아니라, 주변 노드의 중요성 또한 자신의 중요성에 영향을 미치게 된다. 한편 카츠 중심도(Katz centrality)의 경우 차수 중심도와 고윳값 중심도의 특징을 합쳐 놓은 것이라고 할 수 있다.
다음으로 다룰 페이지랭크 중심도(PageRank centrality)는 구글의 창업 기반이 된 것으로 유명하며, 검색 순위 결정을 위해 각 웹 페이지의 유명세를 평가하는 데 사용되었다. 재미있게도 발명자이자 구글 창업자인 래리 페이지(Larry Page)의 이름을 따서 명명된 것이라고 한다. 페이지랭크 중심도의 철학은, (i) 어떤 웹 페이지가 유명한 페이지에게 인용당할수록 더 높게 평가되는 것, (ii) 무차별 수집가(collector, 수많은 페이지를 인용하는 페이지)보다는 세심한 비평가(delicate critic, 적은 수의 페이지만 선별하여 인용하는 페이지)에게 인용당할수록 더 높게 평가되는 것으로 요약될 수 있다.
마지막으로 다룰 Betweenness centrality(BC)와 closeness centrality(CC)의 가장 큰 특징은, 그 정의상 노드 1개의 중심성을 평가하는 데에 네트워크 전체가 직접적으로 involve되는 것이라고 할 수 있겠다. 네트워크 상에서 정보가 전달된다고 보았을 때, 특정 노드를 대체할 만한 경로가 없어 '병목 현상'이 일어날 경우 그 노드는 큰 BC 값을 가지게 된다.
한편, 네트워크는 spatial embedding을 가지고 있지 않은 구조이지만 노드간의 거리를 통해 대략적인 '지름'를 정의할 수 있는데, CC는 그 척도라고 할 수 있겠다. 어느 노드를 중심으로 CC를 평가하느냐에 따라 지름이 다르게 평가되게 되며, 지름이 작을수록 해당 노드는 전체 네트워크와 밀접하게 연결되어 있다는 뜻이 된다.
No comments:
Post a Comment