Centrality

중심성(Centrality)

그래프에는 많은 엔티티(노드)를 가지고 있는데, 그중 우리가 집중해야 하는 중요한 엔티티(노드)를 결정하는 기준은?

 

케빈 베이컨의 6단계 이론

- "모든 배우들은 케빈 베이컨과 6다리 이내로 안다"

- 왜냐면 케빈 베이컨은 많은 사람들과 일했고, 그들도 또 많은 사람들과 일했고.. 이렇기에!

- 그럼 케빈 베이컨이 co-acting graph에서 중심에 있게 된다.

 

그치만, 케빈에 대한 평균 거리는 2.998이었고, Harvey Keitel에 대한 평균 거리는 2.848이었다.

즉, 케빈보다 하비가 더 중심이라는 것.

 

중심성 : 그래프의 각 노드에 숫자를 부여해 중요도를 나타낸다. 중심에 있을 수록 중요한 것!

Degree Centrality : 노드의 연결개수

Eccentricity Centrality : 최대거리의 역수, c(vi) = 1/e(vi)

-> Degree 중심성은 단순 연결 수 기반. but Eccentricity는 중심과 말단을 구분하는 정교한 방법임

 

Closeness Centrality

그래프에서 노드와 다른 모든 노드 사이 최단 경로 길이의 합의 역수

eccentricity 중심성에서는 최대 거리를 최소화하는 것을 목표로 한다.

clossness 중심성에서는 평균 거리를 최소화하는 것을 목표로 한다.

 

Betweenness Centrality

노드 v의 중심성 측도

v를 통과하는 가장 짧은 경로들의 개수로 정의됨.

이렇게 구할 수 있고, 분모는 s->t의 최단경로의 개수이고,

분자는 s->t로 갈 때 v를 거치는 최단경로의 개수이다.