이번 글에서는 문서를 네트워크로 표현하는 방법론에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 참고로 했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

네트워크?

네트워크(network)란 간선(edge)으로 연결된 꼭지점(node)들의 집합을 의미합니다. 일반적인 의미에서 그래프(graph)와 유사한 개념입니다. 다양한 분야에서 쓰이는 관련용어를 한번 정리해보겠습니다.

네트워크의 종류는 아래처럼 크게 네 가지로 나눌 수 있습니다. 무방향(Undirected) 네트워크는 간선의 방향성이 없는 네트워크를, 방향(Directed) 네트워크는 방향성이 있는 네트워크를 의미합니다. 간선의 가중치가 있는지 여부에 따라 binary, valued 네트워크로 나뉩니다. 텍스트 마이닝에서는 무방향 네트워크가 더 자주 쓰입니다.

네트워크 표현

위와 같은 무방향 네트워크는 아래와 같이 인접행렬(adjacency matrix)로 표현할 수 있습니다. 인접행렬의 각 요소를 보면 어느 꼭지점들이 간선으로 연결되어 있는지를 알 수 있습니다. binary 네트워크에서는 꼭지점이 간선으로 연결돼 있을 경우 1, 그렇지 않으면 0으로 표시됩니다(Valued 네트워크라면 인접행렬의 요소값이 가중치값이 됩니다). 무방향 네트워크는 방향성이 존재하지 않기 때문에 인접행렬이 대칭행렬(symmetric matrix)입니다.

마찬가지로 아래와 같은 방향 네트워크도 인접행렬로 표현할 수 있습니다. 방향 네트워크는 무방향 네트워크와 달리 인접행렬이 대칭행렬이 아님을 확인할 수 있습니다.

꼭지점의 수가 많아질수록 인접행렬은 0이 많은 희소행렬(sparse matrix) 형태가 됩니다. 그만큼 메모리를 많이 잡아먹는다는 뜻입니다. 이 때문에 상당수 네트워크 처리 라이브러리는 인접행렬 말고 아래와 같이 Adjacency List, Arc List 형태로 네트워크를 분석합니다. 아래는 첫 예시인 무방향 binary 네트워크를 표현한 것입니다.

Adjacency List

a|b

b|a c

c|b d e

d|c e

e|c d

Arc List

a b

b a

b c

c b

c d

c e

d c

d e

e c

e d

네트워크 시각화

네트워크를 시각화하는 방법은 무수히 많이 존재합니다. 예컨대 아래 네 개의 네트워크는 얼핏 보면 다른 것 같지만 동일한 네트워크인 걸 알 수 있습니다.

네트워크를 시각화하는 알고리즘도 많이 제안되었는데요. 이들 알고리즘이 지향하는 큰 원칙은 이렇습니다. 꼭지점이 한쪽으로 쏠리거나 간선이 겹치는 걸 최소화하고, 간선의 길이는 균일하게 맞추며, 전체적인 네트워크의 모양은 가급적 대칭적인 구조가 되게끔 하라 등등입니다.

네트워크의 속성

네트워크의 몇 가지 속성을 살펴보겠습니다.

크기(size) : 간선의 개수

밀도(density) : 실제 간선의 수 / 이론적으로 가능한 모든 간선의 수 (꼭지점이 n개일 경우 n * (n - 1) )

Out-degree : 하나의 꼭지점에서 다른 꼭지점으로 나가는(out) 간선 수의 합 (방향 네트워크에서 정의)

In-degree : 다른 꼭지점에서 하나의 꼭지점으로 들어오는(in) 간선 수의 합 (무방향 네트워크에서 정의)

꼭지점의 속성

개별 꼭지점의 속성을 따지는 지표는 몇 가지 있습니다.

1. 연결성(conectivity)

임의의 한 꼭지점이 다른 꼭지점과 어떻게 연결되어 있는지 나타내는 지표입니다.

도달가능성(reachablity) : 꼭지점과 꼭지점 사이에 간선으로 연결돼 있어야 ‘도달 가능’하다고 정의됩니다.

거리(Distance) : 도달가능할 경우 몇 단계를 거처야 해당 꼭지점에 도달할지를 따지는 지표입니다.

경로 개수(Number of paths) : 도달 가능한 경로가 몇 가지가 있는지를 따지는 지표입니다.

2. 중심성(centrality)

임의의 꼭지점이 네트워크 상에서 얼마나 중심에 위치하고 있는지 나타내는 지표입니다. 대개 중심에 위치한 꼭지점은 중요한 꼭지점으로 인식됩니다. 이 때문에 중심성은 곧 중요도로 받아들여지기도 합니다. 그 정의와 예시 그림은 아래와 같습니다.

중개중심성(degree centrality) : 한 꼭지점에 연결된 간선의 수

근접중심성(closeness centrality) : 특정 꼭지점이 그를 제외한 다른 꼭지점과 얼마나 가까이에 있는지를 나타내는 지표. 해당 꼭지점의 도달 가능 거리 총합의 역수(inverse)로 정의됩니다.

중개중심성(betweenness centrality) : 한 꼭지점의 중개중심성은 그 꼭지점을 제외한 다른 두 꼭지점을 잇는 최단거리에 해당 꼭지점이 얼마나 많이 등장하는지 빈도로 정의됩니다.

고유벡터중심성(eigenvector centrality) : 중요한 꼭지점에 연결된 꼭지점일 수록 그 중요도가 높아지는 지표입니다. 인접행렬 고유벡터(eigenvector)의 각 요소가 각 꼭지점의 고유벡터중심성입니다.