이번에 살펴볼 예제는 graph traverse의 가장 일반적인 스킬인 snowball sampling에 대해서 알아보겠습니다. 해석 그대로 눈덩이를 불리듯이 덩치를 키워나간다는 이 방식은, 중심 노드를 중심으로 계속해서 친구들을 불러들이면서 maximum depth까지 recursive하게 탐색해 나가는 방식입니다.
img

만약에 한 사람이 100명의 친구를 가지고 있다고 가정하면, $100^2$의 친구의 친구를 가지고 있고, depth=$n$의 경우 $100^n$의 노드를 가지고 있게 됩니다. 하지만 실제로 우리의 사회 네트워크를 보면 mutual friends가 많기 때문에 실제로 많은 overlap을 가지고 있게 되고, 100명의 친구는 2000-3000명 정도의 친구의 친구를 가진다고 합니다.

여기서 또 하나의 재미있는 사실은, 우리 인간은 social networks의 인식에 대해 한계를 가진다는 점입니다. 이것을 Horizon of Observability라고 표현하는데, 우리가 실제로 친구들까지는 잘 알지 몰라도, 친구의 친구에 대해서는 30%정도밖에 알지 못한다고 하네요. 그리고 친구의 친구의 친구는 거의 아는바가 없구요. 그렇기 때문에 우리가 실제 네트워크를 sampling할 때에도 보통 2~3정도의 depth만큼만 sampling을 해도 실제와 거의 동일한 네트워크라고 볼 수 있는 것입니다.

일단 우리가 이번에 사용할 예제는 ‘LiveJournal’이라는 사이트에서 그래프 관련 데이터를 직접 모아와서 구하도록 하겠습니다. ‘valerois’라는 아이디를 가진 사람의 graph데이터를 접속해 보면,

# Note: Polite data miners cache on their end.  Impolite ones get banned.
> bagira
> angerona
> yankel
> yelya
> ponka
> marinka
...
< murrka
< kisverchik
< kozerojka
< milady_winter
< galephys
< lengo

이런식으로 생겼는데요, ‘>’이것은 outgoing edge를 의미하고, ‘<’는 incoming edge를 의미합니다. 이 text데이터를 읽어서 그래프를 만들어 보겠습니다.

import urllib
import networkx as nx
def read_lj_friends(g, name):
    response = urllib.urlopen("http://www.livejournal.com/misc/fdata.bml?user="+name)
    for line in response.readlines():
        # '#'로 주석을 나타내므로 이런거는 스킵합니다.
        if line.startswith('#'):
            continue
        
        # '<'로 incoming edge를 나타내고, '>'로 outgoing edge를 나타냅니다.
        parts = line.split()
        # 만약 줄에 아무 문자도 없으면 스킵합니다.
        if len(parts) == 0:
            continue
        
        if parts[0] == '<': #incoming edge이면,
            g.add_edge(parts[1], name) #상대쪽에서 오는 edge를 추가합니다.
        else: #outgoing edge이면,
            g.add_edge(name, parts[1]) #상대쪽으로 가는 edge를 추가합니다.

>>> g = nx.Graph() #비어있는 그래프를 생성합니다.
>>> read_lj_friends(g, 'valerois')
>>> print len(g) #node수를 출력합니다.
300

데이터를 잘 읽어서 graph로 만들어주는 것을 확인하실 수 있습니다. 그렇다면 snowball sampling알고리즘은 어떤 것일까요? 굉장히 직관적이고 간단합니다.

  • 임의의 한 노드를 중심으로 시작합니다.
  • 그 노드의 이웃 노드들을 얻습니다.
  • 각 이웃들을 기준으로 다시 그 이웃의 이웃들을 가져옵니다.
  • 그 이웃의 이웃들을 기준으로 다시 그 이웃의 이웃의 이웃들을 가져옵니다.
  • …

이런식으로 계속 눈덩이를 굴리듯이 네트워크를 넓혀나가는 것입니다. 함수의 핵심은 이미 방문했던 노드에 대해서는 다시 search하지 않는 것과, maximum depth만큼 이미 탐색했을 경우도 더 이상 탐색하지 않는 것입니다.

def snowball_sampling(g, center, max_depth=1, current_depth=0, taboo_list=[]):
    print center, current_depth, max_depth, taboo_list
    
    #만약 이미 최대 깊이로 탐색이 끝나면 방문했던 list를 리턴합니다.
    if current_depth==max_depth:
        return taboo_list
    
    #이미 방문했던 노드를 다시 방문하면, 방문했던 list를 리턴합니다.
    if center in taboo_list:
        return taboo_list
    else: #만약에 방문하지 않았다면, 방문했던 리스트에 추가해줍니다.
        taboo_list.append(center)
        
    read_lj_friends(g, center) #일단 현재 노드의 정보를 웹에서 읽어옵니다.
    
    #그래프의 현재 노드의 친구들을 기준으로 recursive하게 추가해 나갑니다.
    for node in g.neighbors(center):
        taboo_list = snowball_sampling(g, node, current_depth=current_depth+1, max_depth=max_depth, taboo_list=taboo_list)
    
    return taboo_list

>>> g = nx.Graph()
>>> snowball_sampling(g, 'kozel_na_sakse') #너무 커지므로 max_depth=1로 하겠습니다.
kozel_na_sakse 0 1 []
jenya_salaveya 1 1 ['kozel_na_sakse']
husky_wardsa 1 1 ['kozel_na_sakse']
vujurja 1 1 ['kozel_na_sakse']
doctor_livsy 1 1 ['kozel_na_sakse']
plastickfreakz 1 1 ['kozel_na_sakse']
cr 1 1 ['kozel_na_sakse']
cher_no_more 1 1 ['kozel_na_sakse']
to_to_i_ono_to 1 1 ['kozel_na_sakse']
letchikleha 1 1 ['kozel_na_sakse']
dr_livsig 1 1 ['kozel_na_sakse']
nikitosbro 1 1 ['kozel_na_sakse']
zina_korzina 1 1 ['kozel_na_sakse']
dachte 1 1 ['kozel_na_sakse']
klari 1 1 ['kozel_na_sakse']
tanyakotova 1 1 ['kozel_na_sakse']
gingea 1 1 ['kozel_na_sakse']
saper 1 1 ['kozel_na_sakse']
dumjtio 1 1 ['kozel_na_sakse']
periskop 1 1 ['kozel_na_sakse']
usolt 1 1 ['kozel_na_sakse']
solo_oboroten 1 1 ['kozel_na_sakse']
sovarh 1 1 ['kozel_na_sakse']
valerois 1 1 ['kozel_na_sakse']
fartasssea 1 1 ['kozel_na_sakse']
gde_moi_mozgi 1 1 ['kozel_na_sakse']
kirulya 1 1 ['kozel_na_sakse']
orteme_ru 1 1 ['kozel_na_sakse']
pussbigeyesz 1 1 ['kozel_na_sakse']
olimkasaz 1 1 ['kozel_na_sakse']
ak_bara 1 1 ['kozel_na_sakse']
jolita 1 1 ['kozel_na_sakse']
cheese_people 1 1 ['kozel_na_sakse']
ptfenix 1 1 ['kozel_na_sakse']
guy_gomel 1 1 ['kozel_na_sakse']
hamptonlanny 1 1 ['kozel_na_sakse']
emjudob 1 1 ['kozel_na_sakse']
olga_mama 1 1 ['kozel_na_sakse']
oshestak 1 1 ['kozel_na_sakse']

>>> len(g) #자신과 친구들의 수를 출력합니다.
39

잘 동작하네요 ^^ graph traversal은 정말 많이 등장하므로 매우 중요한 recursive 테크닉이고, 또한 우리가 실제 데이터를 sampling할 때 너무 방대할 경우 어떻게 적절한 샘플링을 해야하는지에 대해서도 배워볼 수 있었던 좋은 기회였습니다 :)