모두들 아시겠지만 요즘 SNS의 인기에 따라서 소셜 네트워크와 같은 네트워크를 분석하는 것이 엄청난 인기를 누리고 있습니다. 그 중에서 가장 기본적인 Adjacency matrix와 그것을 활용하여 다른 node에 도달할 수 있는지를 알아보는 Reachability matrix까지 살펴보겠습니다.
아래와 같은 Directed graph(방향성이 있는 그래프)를 살펴봅시다. 이렇게 graph로도 표현이 가능하지만, 이것을 matrix형태로 바꿀 수도 있습니다. 이 때 이 matrix를 Adjacency Matrix라고 부릅니다. 각 행은 출발하는 node를 의미하고, 각 열은 도착하는 node를 의미합니다. 1번 node에서는 2번과 3번 node로 갈 수 있기 때문에, matrix의 첫째 행은 2번과 3번에만 1이 들어가게 됩니다.
이렇게 한 번 이동해서 갈 수 있는 거리를 hop이라고 하는데요, Adjacency matrix는 1 hop으로 도달할 수 있는 node들을 표시했다고 할 수 있습니다. 그렇다면 $n$ hops 만큼 가서 도달할 수 있는 path의 수는 어떻게 알 수 있을까요? 답은 놀랍게도 \[A^n\] 을 통해서 쉽게 해당 노드로 $n$ hops만에 도달할 수 있는 path의 수를 구할 수 있게 됩니다. 구체적인 설명을 하지는 않겠지만, matrix 곱셈 연산의 특성상 이러한 정의가 가능해지게 됩니다. 그럼 위의 예를 가지고 한번 구해보겠습니다.
>>> import numpy as np
## Adjacency matrix
>>> A = np.array([[0,1,1,1,0],[0,0,1,0,0],[0,1,0,0,0],[0,0,0,1,0],[0,1,0,0,0]])
>>> print A
[[0 1 1 1 0]
[0 0 1 0 0]
[0 1 0 0 0]
[0 0 0 1 0]
[0 1 0 0 0]]
## A^2를 구해서 2 hops만에 도달할 수 있는 경우의 수를 알아봅시다.
>>> A2 = A.dot(A)
>>> print A2
[[0 1 1 1 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 1 0 0]]결과를 분석해 보면, A2에서 첫째행, 즉 1번 노드에서 출발하는 녀석들을 살펴봅시다. 2, 3, 4번 노드를 2 hops에 걸쳐서 갈 수 있고, 그 경로는 1개라고 되어있는데요, 1->2로 갈 때는 3을 거쳐서 가는 1가지가 있고, 1->3을 갈때는 2를 거쳐서 가는 1가지, 1->4를 갈때는 4로 가서 self-loop을 도는 1가지가 있어서 위와 같은 결과가 나오게 됩니다.
이를 통해서 결국 어떤 한 network에서 $n$ hops를 거쳐서 도달할 수 있는 노드들은 $A^n$을 통해 쉽게 알아낼 수 있겠죠? :) 그런데 만약 우리가 특정 노드에 $n$ hops 내에 도달할 수 있는지를 확인하고 싶으면 어떻게 하면 될까요? 우리가 앞서 구한 방법은 정확히 $n$ hops를 사용해야 하기 때문에 이 질문에는 적합하지 않습니다. 하지만 간단한 트릭을 사용해서 우리가 원하는 바를 얻어낼 수 있습니다.
$n$개의 노드를 가지고 가장 멀리 떨어뜨려놓을 수 있는 경우는 $n$개의 노드가 일렬로 배열된 형태를 지닐 때일 것입니다. 따라서 이 때 $n-1$ hops를 가지기 때문에, 특정 노드로 몇 hops를 사용하건 도달을 할 수 있는지 파악하는 Reachability matrix는 아래와 같은 식으로 구할 수 있습니다. \[R=A\quad |\quad A^2 \quad | \quad … \quad | \quad A^{n-1} \] 여기서 $|$는 OR 연산자로서 matrix의 해당 ($i,j$) element가 0이 아니면 무조건 1을 만들어주는 것입니다. 이렇게 하면 $n-1$ hops 내에 도달하는지를 체크할 수 있겠죠?
>>> n = 5
>>> An = A
>>> R = A
>>> for i in range(2, n):
... An = An.dot(A)
... R += An
>>> R = 1*(R>0)
>>> print R
[[0 1 1 1 0]
[0 1 1 0 0]
[0 1 1 0 0]
[0 0 0 1 0]
[0 1 1 0 0]]물론 더 다양하고 효율적인 방법들이 있겠지만, 개념적으로 알아보고자 했기 때문에 여기서 마치겠습니다 :) 네트워크 분석에서 꽤나 많이 쓰이는 방법들이므로 반드시 잘 숙지하고 넘어가면 좋겠습니다.