Networks and graphical model - (2) adjacency matrix로 중요한 노드 찾기

중심성지수를 활용하는 이유

네트워크가 작을때는 노드들간의 관계가 눈에 보이지만, 노드가 만약 수천 수만개라면? 하나의 헤어볼처럼 보이기 쉽상이다. 

노드들이 복잡하게 엣지들과 연결되어 있을때 어떻게 중요한 노드를 알아볼 수 있을까?

이때 사용되는 중심성지수라는 것을 살펴보려한다. 

 

 

중심성지수의 종류와 예제

 

• 위세 중심성(Eigenvector Centrality)

예제를 살펴보자, 만약 BTS콘서트가 열리고 콘서트 티켓을 어떤 사람에게 주어야 다른 사람들에게 충분히 홍보가 될까? 

이는 중요한 노드가 무엇인지 찾는 과정이다. 

 

가장 간단한 방법으로는 가장 많은 친구가 있는 사람을 찾는 것이다. 가장 엣지가 많이 연결된 노드를 찾으면 된다. 

degree of node는 그 노드에 연결되어있는 엣지 개수이다. 이를 adjacency matrix에서 찾으려면 해당하는 노드의 행을 모두 더해주면 된다. 왜냐하면 adjacency matrix는 행과 열이 각각 node들이 연결되어 있는지 아닌지에 대한 행렬이기 때문이다. 

하지만, 이걸로 그 사람이 가장 중요하다고 따질 수 없다. 그 사람이 연결된 사람이 많을 뿐이지, 그 사람의 친구, 또 그 사람의 친구가 

계속 영향력 있는 사람일지는 모르기 때문이다. 

 

그렇다면 수학적으로 영향력이 계속 많은 친구의 중심은 어떻게 구할까? 

eigenvector centrality로 구한다. 이 방법은 해당하는 노드에 주변 모든 이웃들의 점수를 합산한 값을 내준다. 

 

또 다른 방법으로는 Page Rank가 있다. 이런 경우에는 indirected network에서 사용한다. 예를 들면, World Wide Web. 

 

• 근접 중심성(Clossness Centrality)

근접 중심성(Closeness Centrality)은 특정 노드가 다른 노드까지 도달하는 경로가 얼마나 짧은지를 나타낸다.

근접 중심성을 계산하는 수식은 노드 I에서 I를 제외한 다른 노드까지 도달하는 최소 경로의 평균을 구한 다음, 그 평균을 역수 취하면 된다.  

 

• 매개 중심성(Betweenness Centrality)

Bottleneck of network는 정보의 흐름을 유지하는데 가장 중요한 node를 말한다. 병목현상이 일어나는 지점이다. 정보의 양은 그 노드가 몇개의 경로를 통과하는지에 비례한다. 가장 많은 정보가 지나가는 노드를 발견하는데 사용되는 지표는 매개 중심성(Betweenness Centrality)이다. 매개 중심성은 한 노드가 다른 노드들과의 연결망을 구축하는데 얼마나 도움을 주는지 측정하는 지표로 두가지 가정을 한다. (1) 정보의 흐름은 일정한 속도를 갖는다. (2) 정보는 가장 짧은 경로로 다닌다.

 

이때, 모든 짝의 노드들을 지나는 가장 짧은 경로를 찾는 알고리즘으로 Floyd-Warshall algorithm을 사용한다. 

노드 I의 중요성이 아닌 임의의 X, Y 노드에 대해서 X-Y의 최단 경로에 노드 I가 포함되어 있는 횟수를 의미한다.