[시뮬레이션] python으로 BA 모델 만들기

 BA모델을 이해하더라도 실제 구현하기는 힘이 든다. BA모델 특징상 노드가 10,000 개 이상의 아주 큰 network 에서 그 특징이 뚜렷히 나타나기 때문이다. 그래서, BA모델을 만들어볼 수 있는 방법을 여러가지 소개해 보는 글을 쓰기로 했다.

BA모델 이론적 배경 관련 포스팅

2017/10/14 - [연구/리뷰] - [논문소개] Emergence of Scaling in Random Networks

2017/10/22 - [연구/리뷰] - [논문소개] Barabasi-Albert model (바라바시 알베르트 모델)

2018/04/26 - [연구/연구] - [연구] BA 모델 고찰

2018/05/10 - [연구/연구] - [고찰] BA 모델 고찰2

 환경은 python 3.5를 기반으로 작성하였다.

방법1. networkx package

---

 networkx는 python에서 networkx를 분석하는데 아주 유용한 패키지이다. 설치는 pip을 이용한 방법과 직접 다운로드 후 setup파일을 실행하는 방법이 있다.

 주소:  https://pypi.org/project/networkx/

 만드는 법은 아주 간단하다. networkx를 import 해주고, 내장함수인 barabasi_albert_graph를 이용하면 뚝딱 만들어진다.

<코드>

import networkx as nx

G = nx.barabasi_albert_graph(n=100000, m=1, seed=3)

 n은 성장을 마친 BA모델 노드 개수, m은 새롭게 추가되는 node와 기존 node들 사이에 생성되는 edge의 개수, seed는 초기 node 개수이다.

 degree(k) 별 node개수가 거듭제곱 분포를 이루는 것을 다음과 같이 확인해볼 수 있다.

<코드>

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

""" BA model 생성 """
G = nx.barabasi_albert_graph(n=100000, m=1, seed=5)

""" Graph G의 degree 정보 """
k = dict(nx.degree(G))
""" histogram data 생성 """
y, x = np.histogram(list(k.values()), bins=max(k.values()) - min(k.values()))
x = x[:-1]
y = y.astype('float')
""" y축 normalizing """
y /= np.sum(y)
plt.plot(x, y, ls='', marker='.')
plt.xscale('log')
plt.yscale('log')
plt.xlabel('k')
plt.ylabel('P(k)')
plt.show(block=False)

 <출력>

거듭제곱 계수 -3 이 나타는 것을 알 수 있다.

---

방법2. 직접 만들기

---

 직접 BA 모델을 만들 수 있는 알고리즘이다. pool의 개념을 이용하여 빠르게 BA 모델을 생성한다.

 BA모델에서 각 node가 선택될 확률은 node가 지니는 edge의 개수 k에 비례한다. 그래서 pool에는 edge의 개수만큼 node를 풀어놓는다. 

알고리즘은 intializing과, Network 성장 두 부분으로 나누었다.

 initializing에서는 seed로써 ring graph를 이용한다. BA 모델에서는 network가 성장할 수록 초기 조건의 영향이 사라지는데, 초기 조건이 compelete graph일 경우, 추가되는 edge의 개수 m보다 seed의 개수 가 클 경우, seed가 지니는 영향력이 사라지는데 까지 시간이 오래 걸리기 때문이다. ring graph는 node당 지니는 edge개수가 2인 graph이므로 영향력이 금방 사라지는 graph이다.

 Network 성장부에서는 pool에서 random하게 m개의 target을 선정하고, pool과 adjlist(친구 리스트)를 update한다.

 10만개의 노드에 대해 network를 생성하는데까지 1초가 걸리지 않는다. 100만개의 경우도 10초가 걸리지 않는다.

 

<코드>

import numpy as np
import matplotlib.pyplot as plt

class BA_model():

    def __init__(self, n=1000, m=1, seed=3):
        self.m = m
        self.n = n
        self.seed = seed

        """"""""""""" initialize seed condition """""""""
        self.nodes = list(range(seed))
        self.N = len(self.nodes)    # nodes 개수
        """ make ring graph """
        """ 인접 node 리스트: adjlist[i] = [j, k] -> edge (i, j), (i, k) """
        self.adjlist = [[i-1, i+1] for i in range(len(self.nodes))]     # 앞뒤 노드에 edge 생성
        self.adjlist[0][0] = seed - 1     # [-1, 1]의 -1부분을 제일 끝 노드(seed-1)에 연결
        self.adjlist[-1][-1] = 0          # [seed-1, seed]의 seed부분을 제일 앞 노드(0)에 연결

        """ pool 생성 """
        self.pool = self.nodes * 2  # ring graph 이므로 초기조건에서 각 node들의 edge 수는 2
        self.P = len(self.pool)     # pool의 크기


        """"""""""""" Network 성장 """""""""
        for i in range(n-seed):
            if i % 10000 == 0:
                print(i)    # step 표시

            self.nodes.append(self.N)   # node추가

            targets = []  # 신규 node와 연결을 갖는 기존 node 선정

            counter = 0
            while counter < self.m:     # target 수가 m개 선정될 때 까지
                r = np.random.randint(self.P)   # pool 속에서 한개의 target 선정
                if self.pool[r] not in targets:     # pool 속에서 선정한 target이 중복하지 않기 위함
                    counter += 1
                    targets.append(self.pool[r])

            """ pool update """
            self.pool += targets                # target으로 선정된 node들을 pool에 추가
            self.pool += [self.N] * self.m      # 신규노드를 pool에 추가 (신규 node는 m개의 edge를 지니므로 m배)
            self.P += 2 * self.m    # 성장으로 인해 pool의 크기가 2 * m 성장 (= len(targets) + len([self.N] * self.m)

            """ adjlist update """
            for j in targets:
                self.adjlist[j] += [self.N]     # target으로 선정된 node에 신규 node를 친구로 추가
            self.adjlist += [targets]           # 신규 node에 target node를 친구로 추가

            self.N += 1     # node 개수 증가


""" Model 생성 """
a = BA_model(n=100000, m=1, seed=3)

""" Plot """
fig = plt.figure()
k = [len(i) for i in a.adjlist]
y, x = np.histogram(k, bins=int(np.max(k)) - int(np.min(k)))
x = x[:-1]
y = y.astype('float')
y /= np.sum(y)
plt.plot(x, y, ls='', marker='.')
plt.xscale('log')
plt.yscale('log')
plt.xlabel('k')
plt.ylabel('P(k)')
plt.show(block=False)

<출력>

---

가시화

---

 10만개만 되더라도 network가 엄청나게 커진다. 그래서 networkx와 같은 python package로 가시화 하려면 몇시간이 걸릴지 모른다..(1000개만 하더라도 5분 정도 걸림)

 그래서 사용하는 프로그램이 gephi다.

 주소: https://gephi.org/users/download/

 gephi를 사용하기 위해서는 python에서 생성한 network를 gexf 파일로 출력할 필요가 있다. 출력에는 networkx 패키지를 이용한다.

 우선 networkx를 이용하여 만든 graph는 그대로 gexf파일로 출력할 수 있다.

<코드>

import networkx as nx


G = nx.barabasi_albert_graph(n=100000, m=1, seed=3)
nx.write_gexf(G, "n100000_m1_s3.gexf")

 직접 생성한 모델은 networkx의 그래프 G로 옮기는 작업이 필요하다.

""" BA Model 'a' 생성 """
a = BA_model(n=100000, m=1, seed=3)

""" networkx Graph 생성"""
G = nx.Graph()
G.add_nodes_from(a.nodes)   # G에 'a' 노드추가
# G 에 'a' edge 추가
edge_list = []
for cnt in range(len(a.adjlist)):
    for friend in a.adjlist[cnt]:
        edge_list += [(cnt, friend)]
G.add_edges_from(edge_list) 

""" gexf 파일 출력"""
nx.write_gexf(G, "n100000_m1_s3.gexf")

 이제 gephi를 켜고, open에서 생성한 gexf파일을 열어준다. 상단의 Overview 메뉴를 누른 후 좌측 하단 Layout에서 ForceAtlas 2를 골라주고 마음에 들 때 까지 Run! 다른 layout 방법은 큰 network일 대 너무 많은 시간이 걸려서 사실상 불가능하다.

 node나 edge사이즈를 일괄적으로 조정할수도, degree나 centrality같은 척도를 이용해 조정할 수도 있어 굉장히 유용하다. 자세한건 사이트 manual 참조!

 Overview에서 그래프 형태를 마음에 들게 만든 후, 상단의 Preview 버튼을 눌러 setting을 조정하고, 좌측 하단의 Refresh를 클릭하면 우측에 export할 graph의 형태가 나타난다.

 마음에 든다면 좌측 하단의 Export를 클릭, SVG/PDF/PNG type으로 export할 수 있는데, PDF는 큰 network에서는 좀 더럽게 나온다.

 PNG로 출력한 아름다운 BA model의 모습

 <출력>

<출력2>

 node와 egde가 유입된 시간을 기록하면 다음과 같이 동영상으로 network의 성장을 볼 수 도 있다.

 영상을 보면 중심부에 hub에 신규 node들이 집중되는 것, 하지만 외곽에서도 차근차근히 node들이 유입되며 전체적인 모습을 유지하며 서서히 성장해 나가는 network의 모습을 볼 수 있다.

 이건 작은 모델에서 노드가 추가되는 모습

---