어떤 network에 중심이 되는 사람은 어떤 사람일까요? 이런 질문에 대답하기 위해서 다양한 Centrality라는 개념이 사용됩니다. 그 중에서 가장 처음으로 가장 간단한 degree centrality라는 개념을 알아보겠습니다.
그림으로 쉽게 설명이 되겠지만, 가장 많은 connection을 가지고 있을수록 더 중요한 사람일 것 같다는 추리가 기본적으로 할 수 있는 추리겠죠? 따라서 degree centrality란 가장 많은 connection을 가지고 있는 사람을 가장 중요한 사람이라고 생각하는 개념입니다.
이번에 예제로 사용할 data는 SNAP에서 제공하는 wikipedia 투표 결과(맨 아래쪽에 Wiki-Vote.txt.gz를 클릭하시면 됩니다.)를 사용하도록 하겠습니다. 이 데이터는 실제로 2008년 1월까지 wikipedia의 편집 권한에 대한 투표결과를 반영하고 있습니다. 이 그래프는 투표이기 때문에 directed graph입니다. Data를 살펴보면,
# Directed graph (each unordered pair of nodes is saved once): Wiki-Vote.txt
# Wikipedia voting on promotion to administratorship (till January 2008). Directed edge A->B means user A voted on B becoming Wikipedia administrator.
# Nodes: 7115 Edges: 103689
# FromNodeId ToNodeId
30 1412
30 3352
30 5254
30 5543
30 7478
3 28
...fromNode와 toNode가 tab으로 분리되어 한줄씩 차지하고 있음을 보실 수 있죠? 이 data를 어떻게 읽어오는지 알아봅시다 :)
>>> import networkx as nx
>>> g = nx.read_edgelist('Wiki-Vote.txt', create_using=nx.DiGraph())
>>> print g.number_of_nodes(), g.number_of_edges()
7115 103689 #7115개의 노드를 가지고 있고, 103689개의 edge를 가지고 있습니다.잘 읽어왔다는 것을 확인할 수 있네요 :) 이제 각 노드가 몇 개의 connection(이것을 degree라고 표현합니다.)을 가지고 있는지 파악해 봅시다. 이것은 networkx의 degree라는 함수로 한번에 구할 수 있습니다.
>>> deg = nx.degree(g) #degree 함수는 dictionary형태로 노드를 입력했을 경우 그 노드가 가지는 degree를 리턴합니다.
>>> deg['5988'] #5988번 노드가 몇 개의 degree를 가지는지 리턴합니다.
4
>>> min(deg.values()), max(deg.values()) #degree의 최소와 최대값을 구해봅니다.
(1, 1167)
#degree를 많이 가지는 상위 10개 노드와 각 degree를 출력해봅시다.
>>> deg_sorted = sorted(deg.items(), reverse=True, key=lambda x:x[1])
>>> print deg_sorted[:10]
[(u'2565', 1167), (u'1549', 832), (u'766', 773), (u'1166', 743), (u'11', 743), (u'457', 732), (u'2688', 618), (u'1374', 551), (u'1151', 543), (u'5524', 538)]그러면 degree의 분포를 알아보기 위해 100개의 구간으로 나눈 histogram으로 그려서 나타내 보겠습니다.
import matplotlib.pyplot as plt
%matplotlib inline
h = plt.hist(deg.values(), 100)
대부분의 degree가 매우 작은 것을 확인할 수 있죠?? 연구할 때에는 보통 이를 log-log그래프로 나타냅니다. 앞서 hist함수를 통해서 x값과 y값을 받아오기 때문에, 이를 plot하면
y = h[0] #각 degree구간에 해당하는 수의 degree를 몇 개의 노드가 가지고 있는지...
x = h[1][1:] #h[1]은 bins의 edge값들이 들어있는데, 오른쪽 edge값을 기준으로 삼기 위해 맨 왼쪽 값을 제외해줍니다.
plt.loglog(x, y)
위의 그래프를 degree distribution이라고 하는데요, 이것은 network의 특성을 결정짓는 아주 중요한 factor이고, 가장 먼저 해야할 분석중의 하나이므로 잘 알고계시면 좋겠습니다 :)
참고로 보통의 실제 네트워크는 scale-free network의 형태를 가지는데, 이 때 degree distribution이 위와 같은 분포를 갖습니다.