지난 포스팅에서는 네트워크를 시각화하는 그래프와 수학적으로 표현하는 행렬에 대한 기본 사항을 파악했습니다.
일반적으로, 네트워크의 특성은 노드 수준(Node level, 'centrality measures') 또는 네트워크 수준(Network level, 'global measures')에서 측정할 수 있습니다. 즉 네트워크 내에서 노드의 위치에 관심이 있다면 노드 수준에서 무언가를 측정하는 것이고, 반대로 시스템 전체의 구조를 이해하고 싶다면 네트워크 수준에서 무언가를 측정해야 합니다. 네트워크 분석은 두 가지 수준을 함께 고려합니다.
이번에 다룰 내용은 네트워크의 특성을 노드 수준에서 정량적으로 기술하는 작업입니다.
Centrality Concepts
'중심성' 지수는 해당 노드가 네트워크에서 얼마나 중요한지 측정하는 것입니다.
중심성 지수는 특징에 따라 연결 중심성(Degree Centrality), 매개 중심성(Betweeness Centrality), 고유벡터 중심성(Eigenvector Centrality), 그리고 근접 중심성(Closeness Centrality)으로 구분할 수 있습니다. 이외에도 카츠 중심성(Katz Centrality), 페이지랭크(PageRank) 등이 있습니다. 연결 중심성, 고유벡터 중심성, 카츠 중심성, 페이지랭크 중심성과 같은 경우는 연결성을 바탕으로 중심성을 측정하는 방법이고, 매개 중심성, 근접 중심성과 같은 경우는 위상학적(topological) 관점으로 중심성을 측정하는 방법입니다.
연결 중심성(Degree Centrality): 네트워크 내에서 마당발(hub)이 누구인가?
연결 중심성은 중심성 지수에서 가장 간단하면서 기본적인 지표입니다. 이 지표는 한 노드(Node)에 직접적으로 연결된 모든 링크(Link)의 개수로 지수를 평가합니다. 이를 통해 한 노드가 얼마나 많은 노드들과 관계를 맺고 있는지를 파악할 수 있으며, 해당 노드가 얼마나 많은 관계에 관여하는지 파악할 수 있습니다.
- Definition: 특정 노드에 연결된 링크의 수를 '도수(degree)'라고 합니다.
- Calculation: \(C _{degree}(i)=\frac{degree(i)}{|V|-1}\) - 특정 노드의 도수를 (네트워크를 구성하는 모든 노드의 수 - 1)로 나누어 줍니다.
- Implication: 연결정도가 높은 노드는 다른 노드들과의 관계를 통해 정보 전파 및 획득에 용이할 것이며, 네트워크 내에 핵심 노드일 가능성이 높습니다. 노드 간의 관계의 방향성에 따라 In-degree와 Out-degree로 구분할 수 있습니다. In-degree는 노드의 인기도(popularity)를 알 수 있는 척도이고, Out-degree는 노드의 영향력(activity)을 알 수 있는 척도입니다.
- Example: 페이스북의 경우, 한 사용자의 친구가 더 많을수록 해당 사용자의 중요도를 높게 봅니다. 그러나 인스타그램처럼 팔로우, 팔로워가 있는 경우에는 조금 다릅니다. 팔로우와 팔로워는 하나의 방향성으로 간주하기 때문입니다.
근접 중심성(Closeness Centrality): 네트워크 내에서 가장 중심(center)에 있는 사람은 누구인가?
근접 중심성은 '중요한 노드일수록 다른 노드까지 도달하는 경로가 짧을 것'이라는 가정을 두고 있습니다. 근접 중심성은 직접 연결된 노드의 개수를 측정하는 연결 중심성과 다르게 직·간접적으로 연결된 모든 노드들의 최소 경로를 측정합니다. 각 노드 간의 거리를 바탕으로 중심성을 측정하는 방식으로, 직접 연결되어 있는 노드들을 통해 접근할 수 있는 간접적인 노드 간의 관계까지 파악하며, 연결정도 중심성보다 넓은 범위에서 중심성을 측정하게 됩니다.
- Definition: 가장 짧은 단계로 네트워크의 다른 모든 노드에 도달할 수 있는지 측정하는 방법입니다.
- Calculation: \(Closeness Centrality(K)=\frac{1}{\frac{1}{N-1}\times \sum_{X\neq K}^{}Length(X,K)}=\frac{N-1}{\sum_{X\neq K}^{}Length(X,K)}\) - 근접 중심성은 타겟 노드에서 타겟 노드를 제외한 다른 노드까지 도달하는 최소 경로의 평균을 구한 다음 역수를 취하면 됩니다.
- Implication: 근접 중심성이 높은 중심자(center)는 얼마나 많은 관계가 연결되어 있느냐 보다는 전체 네트워크에서 얼마나 중심에 있느냐, 얼마나 핵심적인 위치에 있느냐에 대한 의미가 더 강조됩니다. 근접 중심성이라는 개념이 지니고 있는 핵심적인 키워드는 바로 '영향력' 또는 '전파력'이라 할 수 있습니다. 방향성이 있는 경우 In-closeness centrality는 특정 정보가 전달될 때, '누가 빨리 그 정보에 접할 수 있는지'에 대한 해답을 제공할 수 있는 한편, Out-closeness centrality는 특정 정보가 전달될 때, '누가 빨리 그 정보를 네트워크 내 모두에게 전달할 수 있는 위치에 있는지'에 대한 해답을 제공하빈다.
- Example: 교실 안에서 전염병 확산을 생각해본다면, 아는 사람들이 많지만(degree가 높지만) 교실 맨 끝자리에 앉아있는(closeness가 낮은) 사람과, 아는 사람이 적을지언정(degree는 낮지만) 교실의 중심에 위치하고 있는(closeness가 높은) 사람 중에서 교실 전체로의 전염병 확산 속도가 빠른 경우는 아마도 후자가 될 것입니다.
매개 중심성(Betweenness Centrality): 네트워크 내에서 연결해주는 사람(Linker)이 누구인가?
매개 중심성은 다른 노드들이 해당 노드를 통과하는 경로의 수에 따라 결정됩니다. 앞서 설명한 마당발의 개념 또한 연결해준다는 성격을 띄고는 있지만, Linker의 경우 대규모의 네트워켕서 마당발과는 다른 '매개'로서의 의미가 발현됩니다. 대부분의 분석과정에서 볼 수 있는 일정 규모 이상의 네트워크는 그 안에서 소규모의 네트워크들로 다시 분화됩니다. 이렇게 분화된 하위 소규모 네트워크들을 연결해주는 중요한 노드가 일부 발생합니다. 이러한 노드들이 곧 매개 중심성 지표가 높은 Linker 노드라고 표현합니다.
- Definition: 네트워크 내에서 특정 노드가 다른 노드들 사이에 위치하는 정도를 의미합니다.
- Calculation: 임의의 A, B 노드에 대해서 A-B의 최단 경로에 노드 X가 포함되어 있는 횟수로 계산합니다.
- Implication: 네트워크 내에서 어디에 위치하는지를 파악함으로써 해당 노드의 영향력을 판단합니다. 특정 정보를 전달하고자 할 때 네트워크 내에서 누가 꼭 필요한 존재일까?에 대한 답을 얻을 수 있습니다. 따라서 정보나 금전, 지식 등의 흐름에 대한 '통제력'으로 측정되기도 하며, 매개 중심성이 높은 노드를 제거하면 네트워크가 분리되고 전체 흐름에 영향을 끼칩니다.
- Example: 우리는 서울에서 경기 남부권으로 이동할 때 경부고속도로를 타고 내려갑니다. 이 때 만약 경부고속도로에 사고가 나서 도로를 통제할 경우 얼마나 많은 사람들이 피해를 입을까 생각해보면 매개 중심성에 대해서 쉽게 이해할 수 있을 겁니다. 또는 컴퓨터 네트워크 분야에서는 통신 장애와 같은 부정적인 효과를 매개 중심성을 이용해 측정합니다.
고유벡터 중심성(Eigenvector Centrality): 네트워크 내에서 중요한 사람을 누가 많이 알고있는가?
네트워크의 연결된 값들을 어떤 노드가 가장 많이 설명하는지 알려주는 지표입니다. 고유벡터 중심성은 '중요한 노드와 많이 연결된 노드가 중요'하다는 가정에서 시작합니다. 단순히 해당 노드의 숫자만을 고려하는 것이 아니라 다른 노드의 중심성까지 고려해 계산하는 방법입니다. 고유벡터라는 표현으로 인해 겉보기엔 매우 어려운 용어처럼 느껴질 수 있지만, 쉽게 말하자면 '종합 점수'의 의미와 다를 바 없습니다. 네트워크 내에서 각각의 노드들이 앞서 소개한 연결 중심성, 근접 중심성, 매개 중심성 개념에 따라 어느 정도의 수치를 종합적으로 지니고 있는지를 알 수 있는 값이 고유벡터 중심성입니다.
- Definition: 특정 노드와 연결된 다른 노드들의 중심성을 가중치에 반영하는 지표입니다.
- Implication: 고유벡터 중심성이 높은 노드는 연결된 다른 노드가 네트워크에서 중요한 노드들과 많이 연결되었다는 것을 의미합니다.
- Example: 인스타그램에서 어느 유저가 돈으로 허위 유저를 매수해 팔로워의 수를 늘렸다면, 이 사용자의 연결 중심성(degree centrality)은 매우 높아집니다. 그럼 이 사용자는 인스타그램 네트워크에서 중요한 유저라고 할 수 있을까요? 팔로워가 아무리 많다고 해서 유명인사인 것은 아닙니다. 유명인사인 팔로워가 많을수록 유명인사라고 할 수 있을 겁니다. 이런 경우에 사용되는 것이 바로 고유벡터 중심성입니다.
이번 포스팅에서는 노드 수준에서 대표적인 네트워크 분석 지표를 살펴보았습니다. 다음 시간에는 네트워크 내에서 유사도를 측정하는 방법에 대해 이야기해보겠습니다.
'Data Science Deep Dive > Network Analysis' 카테고리의 다른 글
| [NA] #1 네트워크 분석 개요(Introduction to network analysis) (1) | 2024.12.16 |
|---|