05. Node centrality rating on Networks

그래프에서 어떤 노드가 가장 중요한 노드인지 에 대한 지표를 node centrality 라고 할 수 있다.
하지만 단순히 degree가 가장 높은 노드가 중요할 수도 있고, 노드를 거쳐서 최단거리가 되는 노드가 중요할 수도 있어
결국 어떤 속성의 네트워크인지와 어떤 것을 중점으로 볼 지에 따라 다르다.  대표적인 node centrality 에 대해서 알아보자.

*closeness centrality
 how close an actor to all the other actors in network

특정 노드에서 다른 모든 노드에 도달하는데 얼마나 많은 단계를 거치는지를 나타내는 지표, closeness가 높다는 것은 네트워크의 중심성이 낮다.

노드의 접근성에 따라서 중요도 부과.

* Betweeness centrality
number of shortest paths going through the actor

:bridges로서의 노드의 중요성, communication network 등에서 매우 중요.
betweenness centrality가 높다는 것은 해당 노드가 많은 shortest path 위에 있다는 것 , bridge역할을 한다는 것

* Eigenvector centrality

노드의 중요성은 이웃노드의 중요성에 의해 결정된다(recursive definition)

다만 undirected graph 에만 해당된다
왜? directed graph는 unsymmetric할 수 있고, eigenvector 는 symmetric matrix 에서는 무조건 존재하기 때문에.

A) Betweenness : bridges 
B) closeness centrality : geometric center 여부
C) Eigenvector : Eigenvector centrality 높은 노드위주로 뭉쳐있음
D) Degree : random scattered되서 큰 특징은없음
F) Harmonic
E) Katz

* Sinks :4번처럼 dead-end, 즉 out degree가 0인 노드를 의미한다
* Sources : 반대로 5번처럼 in degree가 0인 노드를 의미

## Graph theory

graph는 모든 노드들이 연결되어 있어 approachable 하다면 strongly connected라고 할 수 있고, 단순히 위의 그림 처럼 연결됐을 때는 connected 라고 한다.

greatest common divisor of the lengths of its cycles 이 1일 때, directed graph는 aperiodic 

 

## PageRank

페이지랭크는 user behavior 에 대한 모델이다. 웹페이지 네트워크에서 "random surfer"은 무작위로 페이지 내의 하이퍼링크를 타고 들어가면서 연결된 페이지에 랜덤하게 방문하게 된다. PageRank는 random surfer가 특정 페이지에 방문할 확률이다.

directed graph에서의 random walk 는 t시점의 노드에서 t+1 시점에 해당 노드로 도착할 확률의 합이다.
연결된 노드의 out-link의 수로 나눠주면 이웃노드에서 해당 노드로 갈 확률 개념으로 해석할 수 있고, rank vector r에 계소규해서 stochastic matrix M 을 곱하여 r을 업데이트한다면 , ${1 * r} = {M * r}$ 의 flow equation을 얻을 수 있다.