[CS224w, 2018] Network Centrality

 

 

Motivation

social network가 주어졌을 때, 어떤 node가 더 중요 (more important, influential) 할까? 

이때 centrality measure는 node 중요도를 설명해줄 수 있다.

Network Centrality (Stanford CS224W-2018]

Centrality measure로 Geometric measure, Spectral measure, Path-based measure, Subgraph-based measure가 있다.

Geometric Measures

In-degree Centrality

\[ c_{\text{deg}}(x) = d_{in}(x) \]

distance가 $1$인 node의 개수이다. 또한 majority voting과 동일하다. 

Closeness Centrality

더 central한 node일 수록 다른 노드에 도달하는 distance가 더 작다는 아이디어에서 시작한다.

$d(y, x)$를 $y$에서 $x$까지의 shortest path의 길이라고 정의하면

\[ c_{\text{clos}}(x) = \cfrac{1}{\sum_y d(y, x)} \]

Example: Closeness Centrality

Closeness Centrality (Stanford CS224W-2018)

5개의 노드 A, B, C, D, E가 일직선으로 연결된 그래프를 생각하자.

$d(B, A)=1$, $d(C,A)=2$, $d(D,A)=3$, $d(E, A)=4$이므로 $c_{\text{clos}}(A)=\cfrac{1}{1+2+3+4}=0.1$ 이다.

Problem: 주어진 그래프는 반드시 (strongly) connected 여야 한다.

null scores when not connected (Standford CS224W-2018)

 

Harmonic Centrality

graph가 strongly connected하지 않은 경우에, 거리의 합을 조화평균(harmonic mean)으로 대체한다.

\[ c_{\text{har}}(x) = \sum_{y \neq x} \cfrac{1}{d(y, x)} = \sum_{d(y,x) < \infty, y \neq x}\cfrac{1}{d(y, x)} \]

 

closeness centrality와 매우 강한 상관성을 갖는다.

그리고 서로 닿을 수 없는 node도 자연스럽게 설명할 수 있다.

당연히 not strongly connected graph에 적용할 수 있다.

Harmonic Centrality (Stanford CS224W-2018]

Examples of Closeness centrality, and Harmonic Centrality of the same graph (Stanford CS224W-2018)

반응형

Spectral Measures

node centrality는 이웃들의 centrality의 함수라는 아이디어로 시작한다.

central node에 연결된 node들은 non-central node에 연결된 node보다 더 큰 centrality score를 갖는다.

Eigenvector Centrality, Katz's index, PageRank, HITS 등이 해당한다. 

(PageRank, HITS는 따로 포스팅할 예정)

Eigenvector Centrality (Eigen Centrality)

\[ c_{\text{eig}}(x) = \cfrac{1}{\lambda}\sum_{y \to x} c_{\text{eig}}(y) \]

여기서 $\lambda$는 normalizing constant로 $\lambda = \| c_{eig} \|_2$ 이다.

 

How to compute? Power iteration!

$\mathbf{c}^{(0)} \leftarrow 1, \ k \leftarrow 1$
1: $\mathbf{c}^{(k)} \leftarrow \mathbf{Ac}^{(k-1)}$
2: $\mathbf{c}^{(k)} \leftarrow \cfrac{\mathbf{c}^{(k)}}{\| \mathbf{c}^{(k)} \|_2}$
3: if $\| \mathbf{c}^{(k)} - \mathbf{c}^{(k-1)} \| > \epsilon$:
4:        $k \leftarrow k + 1$, goto 1

Example graph (Stanford CS224W-2018)

수렴한 $\mathbf{c}$는 다음과 같다

 

Problem: Graph는 반드시 stronly connected 여야 한다.

 

Katz's Index

pair of nodes간의 total number of walk를 influence로 생각하는 idea이다.

그리고 Katz's index는 acyclic graph에 적합하다.

 

\[ c_{\text{katz}}(x) = \beta \sum_{k=0}^{\infty} \sum_{x \to y} \alpha^k (A^k)_{xy} \]

$(A)^{k}_{xy}$: $x$와 $y$ 사이에 길이가 $k$인 walk의 전체 개수

$\alpha$: attention factor이고 $\alpha \in [0, \frac{1}{\lambda}]$ ($\lambda$는 $A$의 largest eigenvalue)

$\beta$: 어떤 노드들에 previlage를 줄 수 있다.

 

$\alpha < 0$이면 long path는 short path보다 더 작은 가중치를 갖는다.

$\mathbf{c}^{(0)} \leftarrow 1$, $k \leftarrow 1$
1: $\mathbf{c}^{(k)} \leftarrow \alpha \mathbf{Ac}^{(k-1)} + \mathbf{1}$
2: if $\| \mathbf{c}^{(k)} - \mathbf{c}^{(k-1)} \| > \epsilon$:
3:      $k \leftarrow k + 1$, goto 1

Example of Katz's Index (Stanford CS224W-2018)

How to choose $\alpha$ ?

• $\alpha$가 $0$에 가까워지면, 1보다 큰 walk의 영향이 매우 급격히 작아진다. Katz score는 사실상 short walk에 영향을 받는다. (대부분의 indegree로부터)
• $\alpha$가 커지면, katz score는 network의 위상(topology)에 영향을 받는다.
• Katz's index는 $\alpha > \frac{1}{\lambda}$일 경우 발산한다.

Path-based Centrality

Node Betweenness Centrality

\[ c_{\text{bet}}(x) = \sum_{y,z \neq x, \ \sigma_{yz} \neq 0} \cfrac{\sigma_{yz}(x)}{\sigma_{yz}} \]

$\sigma_{yz}$: $y$에서 $z$로 가는 shortest walk의 개수

$\sigma_{yz}(x)$: $\sigma_{yz}$ 중에서 $x$를 거쳐가는 walk의 수

Example: Betweenness Centrality (Stanford CS224W-2018)

C는 (A, D), (A, E), (B, D), (B, E) walk 중간에 거쳐진다.

 

Comparing Centrality Measures

 

Comparing Centrality Measures (Stanford CS224W-2018)

이 3가지 centrality measure는 매우 연관되어 있지만(related) 조금씩 다르다.

 

Comparing Centrality Measures (Stanford CS224W-2018)