많은 데이터 문제는 노드(node)와 그 사이를 연결하는 엣지(edge)로 구성된 네트워크(network)의 관점에서 볼 수 있다.
예를들어, 페이스북에서는 사용자가 노드라면 그들의 친구 관계는 엣지가 된다.
웹에서는 각 웹페이지가 노드이고 페이지 사이를 연결하는 하이퍼링크가 엣지가 된다.
페이스북의 친구 관계는 상호적이다.
내가 당신과 친구라면 당신은 반드시 나와 친구이다.
즉, 이런 경우를 엣지에 방향이 없다(undirected)고 한다.
반면 하이퍼링크는 그렇지 않다.
내 홈페이지에는 대한민국 국회 홈페이지에 대한 링크가 있어도,
반대로 대한민국 국회 홈페이지에는 내 홈페이지에 대한 링크가 없을 수 있다.
이런 네트워크에는 방향이 있기 때문에 방향성 네트워크(directed network)라고 한다.
1장에서 우리는 데이텀 네트워크에서 친구의 수를 셈으로써 중심이 되는 주요 핵심 인물을 찾았다.
여기서는 몇 가지 추가적인 접근법을 살펴보자.
In [1]:
from __future__ import division
import math, random, re
from collections import defaultdict, Counter, deque
from linear_algebra import dot, get_row, get_column, make_matrix, magnitude, scalar_multiply, shape, distance
from functools import partial
users = [
{ "id": 0, "name": "Hero" },
{ "id": 1, "name": "Dunn" },
{ "id": 2, "name": "Sue" },
{ "id": 3, "name": "Chi" },
{ "id": 4, "name": "Thor" },
{ "id": 5, "name": "Clive" },
{ "id": 6, "name": "Hicks" },
{ "id": 7, "name": "Devin" },
{ "id": 8, "name": "Kate" },
{ "id": 9, "name": "Klein" }
]
네트워크는 사용자와 친구 관계를 나타낸다.
In [2]:
friendships = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4),
(4, 5), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9)]
친구 목록을 각 사용자의 dict에 추가하기도 했다.
In [3]:
# give each user a friends list
for user in users:
user["friends"] = []
# and populate it
for i, j in friendships:
# this works because users[i] is the user whose id is i
users[i]["friends"].append(users[j]) # add i as a friend of j
users[j]["friends"].append(users[i]) # add j as a friend of i
1장에서 연결 중심성(degree centrality)을 살펴볼 때는, 우리가 직관적으로 생각했던 주요 연결고리들이 선정되지 않아 약간 아쉬웠다.
대안으로 사용할 수 있는 지수 중 하나는 매개 중심성(betweenness centrality)인데, 이는 두 사람 사이의 최단 경로상에 빈번하게 등장하는 사람들이 큰 값을 가지는 지수이다.
구체적으로는, 노드 $i$의 매개 중심성은 다른 모든 노드 $j,k$ 쌍의 최단 경로 중에, $i$를 거치는 경로의 비율로 계산한다.
임의의 두 사람이 주어졌을 때 그들 간의 최단 경로를 구해야 한다.
이 책에서는 덜 효율적이더라도 훨씬 이해하기 쉬운 'Breadth-first search'라고도 알려진 알고리즘을 사용한다.
In [4]:
#
# Betweenness Centrality
#
def shortest_paths_from(from_user):
# 특정 사용자로부터 다른 사용자까지의 모든 최단 경로를 포함하는 dict
shortest_paths_to = { from_user["id"] : [[]] }
# 확인해야 하는 (이전 사용자, 다음 사용자) 큐
# 모든 (from_user, from_user의 친구) 쌍으로 시작
frontier = deque((from_user, friend)
for friend in from_user["friends"])
# 큐가 빌 때까지 반복
while frontier:
prev_user, user = frontier.popleft() # 큐의 첫 번째 사용자를
user_id = user["id"] # 제거
# 큐에 사용자를 추가하는 방법을 고려해 보면
# prev_user까지의 최단 경로를 이미 알고 있을 수도 있다.
paths_to_prev = shortest_paths_to[prev_user["id"]]
paths_via_prev = [path + [user_id] for path in paths_to_prev]
# 만약 최단 경로를 이미 알고 있다면
old_paths_to_here = shortest_paths_to.get(user_id, [])
# 지금까지의 최단 경로는 무엇일까?
if old_paths_to_here:
min_path_length = len(old_paths_to_here[0])
else:
min_path_length = float('inf')
# 길지 않은 새로운 경로만 저장
new_paths_to_here = [path_via_prev
for path_via_prev in paths_via_prev
if len(path_via_prev) <= min_path_length
and path_via_prev not in old_paths_to_here]
shortest_paths_to[user_id] = old_paths_to_here + new_paths_to_here
# 아직 한번도 보지 못한 이웃을 frontier에 추가
frontier.extend((user, friend)
for friend in user["friends"]
if friend["id"] not in shortest_paths_to)
return shortest_paths_to
그리고 각 노드에 대해 생성된 dict들을 저장하자.
In [5]:
for user in users:
user["shortest_paths"] = shortest_paths_from(user)
그러면 이제 매개 중심성을 구할 준비가 다 되었다.
이제 각각의 최단 경로에 포함되는 각 노드의 매개 중심성에 $1/n$을 더해 주자.
In [6]:
for user in users:
user["betweenness_centrality"] = 0.0
for source in users:
source_id = source["id"]
for target_id, paths in source["shortest_paths"].items(): # python2에서는 items 대신 iteritems 사용
if source_id < target_id: # 잘못해서 두 번 세지 않도록 주의하자
num_paths = len(paths) # 최단 경로가 몇 개 존재하는가?
contrib = 1 / num_paths # 중심성에 기여하는 값
for path in paths:
for id in path:
if id not in [source_id, target_id]:
users[id]["betweenness_centrality"] += contrib
In [7]:
for user in users:
print(user["id"], user["betweenness_centrality"])
사용자 0과 9의 최단 경로 사이에는 다른 사용자가 없으므로 매개 중심성이 0이다.
반면 사용자 3, 4, 5는 최단 경로상에 무척 빈번하게 위치하기 때문에 높은 매개 중심성을 가진다.
대게 중심성의 절댓값 자체는 큰 의미를 가지지 않고, 상대값만이 의미를 가진다.
그 외에 살펴볼 수 있는 중심성 지표 중 하나는 근접 중심성(closeness centrality)이다.
먼저 각 사용자의 원접성(farness)을 계산한다. 원접성이란 from_user와 다른 모든 사용자의 최단 경로를 합한 값이다.
In [8]:
#
# closeness centrality
#
def farness(user):
"""모든 사용자와의 최단 거리 합"""
return sum(len(paths[0])
for paths in user["shortest_paths"].values())
이제 근접 중심성은 간단히 계산할 수 있다.
In [9]:
for user in users:
user["closeness_centrality"] = 1 / farness(user)
In [10]:
for user in users:
print(user["id"], user["closeness_centrality"])
계산된 근접 중심성의 편차는 더욱 작다. 네트워크 중심에 있는 노드조차 외곽에 위치한 노드들로부터 멀리 떨어져 있기 때문이다.
여기서 봤듯이 최단 경로를 계산하는 것은 꽤나 복잡하다. 그렇기 때문에 큰 네트워크에서는 근접 중심성을 자주 사용하지 않는다. 덜 직관적이지만 보통 더 쉽게 계산할 수 있는 고유벡터 중심성(eigenvector centrality)을 더 자주 사용한다.
고유벡터 중심성에 대해 알아보기 전에 먼저 고유벡터가 무엇인지 살펴봐야 하고, 고유벡터가 무엇인지 알기 위해서는 먼저 행렬 연산에 대해 알아봐야 한다.
In [11]:
def matrix_product_entry(A, B, i, j):
return dot(get_row(A, i), get_column(B, j))
def matrix_multiply(A, B):
n1, k1 = shape(A)
n2, k2 = shape(B)
if k1 != n2:
raise ArithmeticError("incompatible shapes!")
return make_matrix(n1, k2, partial(matrix_product_entry, A, B))
def vector_as_matrix(v):
"""(list 형태의) 벡터 v를 n x 1 행렬로 변환"""
return [[v_i] for v_i in v]
def vector_from_matrix(v_as_matrix):
"""n x 1 행렬을 리스트로 변환"""
return [row[0] for row in v_as_matrix]
def matrix_operate(A, v):
v_as_matrix = vector_as_matrix(v)
product = matrix_multiply(A, v_as_matrix)
return vector_from_matrix(product)
행렬 A의 고유 벡터를 찾기 위해, 임의의 벡터 $v$를 골라 matrix_operate를 수행하고, 결과값의 크기가 1이 되게 재조정하는 과정을 반복 수행한다.
In [12]:
def find_eigenvector(A, tolerance=0.00001):
guess = [1 for __ in A]
while True:
result = matrix_operate(A, guess)
length = magnitude(result)
next_guess = scalar_multiply(1/length, result)
if distance(guess, next_guess) < tolerance:
return next_guess, length # eigenvector, eigenvalue
guess = next_guess
결과값으로 반환되는 guess를 matrix_operate를 통해 결과값의 크기가 1인 벡터로 재조정하면, 자기 자신이 반환된다. 즉, 여기서 guess는 고유벡터라는 것을 의미한다.
모든 실수 행렬에 고유벡터와 고유값이 있는 것은 아니다. 예를 들어 시계 방향으로 90도 회전하는 연산을 하는 다음 행렬에는 곱했을 때 가지 자신이 되는 벡터는 영벡터밖에 없다.
In [13]:
rotate = [[0, 1],
[-1, 0]]
이 행렬로 앞서 구현한 find_eignevector(rotate)를 수행하면, 영원히 끝나지 않을 것이다.
한편, 고유벡터가 있는 행렬도 때로는 무한루프에 빠질 수 있다.
In [14]:
flip = [[0, 1],
[1, 0]]
이 행렬은 모든 벡터 [x, y]를 [y, x]로 변환한다. 따라서 [1, 1]은 고유값이 1인 고유벡터가 된다.
하지만 x, y값이 다른 임의의 벡터에서 출발해서 find_eigenvector를 수행하면 x, y값을 바꾸는 연산만 무한히 수행할 것이다.
(NumPy같은 라이브러리에는 이런 케이스까지 다룰 수 있는 다양한 방법들이 구현되어 있다.)
이런 사소한 문제에도 불구하고, 어쨌든 find_eigenvector가 결과값을 반환한다면, 그 결과값은 곧 고유벡터이다.
고유벡터가 데이터 네트워크를 이해하는데 어떻게 도움을 줄까?
얘기를 하기 전에 먼저 네트워크를 인접행렬(adjacency matrix)의 형태로 나타내 보자. 이 행렬은 사용자 i와 사용자 j가 친구인 경우 (i, j)번째 항목에 1이 있고, 친구가 아닌 경우 0이 있는 행렬이다.
In [15]:
#
# eigenvector centrality
#
def entry_fn(i, j):
return 1 if (i, j) in friendships or (j, i) in friendships else 0
n = len(users)
adjacency_matrix = make_matrix(n, n, entry_fn)
In [16]:
adjacency_matrix
Out[16]:
각 사용자의 고유벡터 중심성이란 find_eigenvector로 찾은 사용자의 고유벡터가 된다.
In [17]:
eigenvector_centralities, _ = find_eigenvector(adjacency_matrix)
In [18]:
for user_id, centrality in enumerate(eigenvector_centralities):
print(user_id, centrality)
연결의 수가 많고, 중심성이 높은 사용자들한테 연결된 사용자들은 고유벡터 중심성이 높다. 앞의 결과에 따르면 사용자 1, 사용자 2의 중심성이 가장 높은데, 이는 중심성이 높은 사람들과 세번이나 연결되었기 때문이다. 이들로부터 멀어질수록 사용자들의 중심성은 점차 줄어든다.
데이텀이 인기를 별로 끌지 못하자, 순이익 팀의 부사장은 친구 모델에서 보증(endorsement)모델로 전향하는 것을 고려 중이다. 알고 보니 사람들은 어떤 데이터 과학자들끼리 친구인지에 대해서는 별로 관심이 없었지만, 헤드헌터들은 다른 데이터 과학자로부터 존경 받는 데이터 과학자가 누구인지에 대해 관심이 많다.
이 새로운 모델에서 관계는 상호적인 것이 아니라, 한 사람(source)이 다른 멋진 한 사람(target)의 실력에 보증을 서주는 (source, target) 쌍으로 비대칭적인 관계를 표현하게 된다.
In [19]:
#
# directed graphs
#
endorsements = [(0, 1), (1, 0), (0, 2), (2, 0), (1, 2), (2, 1), (1, 3),
(2, 3), (3, 4), (5, 4), (5, 6), (7, 5), (6, 8), (8, 7), (8, 9)]
for user in users:
user["endorses"] = [] # add one list to track outgoing endorsements
user["endorsed_by"] = [] # and another to track endorsements
for source_id, target_id in endorsements:
users[source_id]["endorses"].append(users[target_id])
users[target_id]["endorsed_by"].append(users[source_id])
그리고 가장 보증을 많이 받은 데이터 과학자들의 데이터를 수집해서, 그것을 헤드헌터들한테 팔면 된다.
In [20]:
endorsements_by_id = [(user["id"], len(user["endorsed_by"]))
for user in users]
sorted(endorsements_by_id,
key=lambda x: x[1], # (user_id, num_endorsements)
reverse=True)
Out[20]:
사실 '보증의 수'와 같은 숫자는 조작하기가 매우 쉽다. 가장 간단한 방법 중 하나는, 가짜 계정을 여러 개 만들어서 그것들로 내 계정에 대한 보증을 서는 것이다. 또 다른 방법은, 친구들끼리 짜고 서로가 서로를 보증해 주는 것이다. (아마 사용자 0, 1, 2가 이런 관계일 가능성이 크다.)
좀 더 나은 지수는, '누가' 보증을 서는지를 고려하는 것이다. 보증을 많이 받은 사용자가 보증을 설 때는, 보증을 적게 받은 사용자가 보증을 설 때보다 더 중요한 것으로 받아들여지는 것이 타당하다. 그리고 사실 이것은 유명한 페이지랭크(PageRank) 알고리즘의 기본 철학이기도 하다.
1. 네트워크 전체에는 1.0(또는 100%)의 페이지랭크가 있다.
2. 초기에 이 페이지랭크를 모든 노드에 고르게 배당한다.
3. 각 스텝을 거칠 때마다 각 노드에 배당된 페이지랭크의 대부분은 외부로 향하는 링크에 균등하게 배당한다.
4. 각 스텝을 거칠 때마다 각 노드에 남아 있는 페이지랭크를 모든 노드에 고르게 배당한다.
In [21]:
def page_rank(users, damping = 0.85, num_iters = 100):
# 먼저 페이지랭크를 모든 노드에 고르게 배당
num_users = len(users)
pr = { user["id"] : 1 / num_users for user in users }
# 매 스텝마다 각 노드가 받는
# 적은 양의 페이지랭크
base_pr = (1 - damping) / num_users
for __ in range(num_iters):
next_pr = { user["id"] : base_pr for user in users }
for user in users:
# 페이지랭크를 외부로 향하는 링크에 배당한다.
links_pr = pr[user["id"]] * damping
for endorsee in user["endorses"]:
next_pr[endorsee["id"]] += links_pr / len(user["endorses"])
pr = next_pr
return pr
In [22]:
for user_id, pr in page_rank(users).items():
print(user_id, pr)
페이지랭크에 따르면 사용자 4(Thor)가 가장 랭킹이 높은 데이터 과학자이다. 비록 Thor가 사용자 0, 1, 2에 비해 보증의 수는 적지만(2개), 보증을 서 준 사용자들이 보증을 많이 받았기 때문에 그 수가 Thor에게 누적이 된다. 게다가 이 사용자들은 Thor 외의 다른 사용자에게 보증을 서 주지 않은 것도 Thor의 중심성을 더 높게 하는 요인이 된다.
In [ ]: