[네트워크이론] degree에 따른 attachment rate 구하기 - 실전편

 이전에 작성했던 degree에 따른 attachment rate 구하기 방법의 특징을 BA model을 이용해서 확인해 본다.

 BA model은 이전에 작성했던 방법을 조금 수정하여 작성했다. 

 BA model을 100,000 스탭 성장 시킨 후, 세 방법을 적용해 구한 attachment rate 결과는 다음과 같다. BA model은 실제로 degree에 비례한 attachment rate로 성장시킨 model인 degree-attachment rate가 선형 관계를 지닌 model이다.

 세 방법 모두 다 degree가 증가할 수록 attachment rate가 비례하여 증가하는 경향을 보여준다. BA model이 지닌 degree에 비례한 attachment rate의 특성이 잘 나타난다.

 Jeong's method에는 bias가 있는 것을 알 수 있다. 이 분석에서는 50000개의 기존 node에 대해 신규 유입된 50000개의 node가 유입된 패턴을 분석하였다. 50000~100000 step 사이에 신규 유입된 50000개의 node들은 실제로는 각 step마다 변화하고 있는 degree와 attachment rate의 변화가 무시되어 bias가 형성된다.

 Newman method는 degree 30정도까지는 실제 attachment rate를 잘 반영하고 있다. 하지만 그보다 높은 degree에서는 실제보다 낮은 attachment rate의 평가가 이루어 진다. Newman's method의 문제점은 모든 영역의 degree 가 네트워크의 성장에 균등히 존재한다는 암묵적 해석에 있다. 실제 Network는 시간이 흐름에 따라 점점 성장한다. 그래서 낮은 degree 는 네트워크의 초반부터 줄곧 존재하고, 높은 degree k는 네트워크 후반부터 잠시 등장한다. 당연히 높은 영역대의 degree k에 대한 weight가 더 낮게 책정된다.

 Corrected Newman method에서는 이점이 개선된 것을 알 수 있다. 하지만 높은 degree 영역에서는 적은 Data양으로 인해 지저분한 결과를 보여준다. 이 부분은 data로부터 역추적 하는 attachment rate 추론의 한계이므로 어쩔 수 없을 것이다.

코드

 Code는 너무 대충 작성했지만 일단 첨부..

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import copy
import collections


""" model """
class BA_model():

    def __init__(self, m=1, seed=3):
        self.m = m
        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의 크기

        """ 초기 정보 저장 """
        self.init_nodes = copy.deepcopy(self.nodes)
        self.init_adjlist = copy.deepcopy(self.adjlist)

    def add_nodes(self, n):
        """"""""""""" Network 성장 """""""""
        for i in range(n):
            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 개수 증가


""" Caculate attachment rate """
def Jeongs_attachment_rate_model(graph, T1, T2):
    G1_n = list(range(T1[0], T1[1]))
    G2_n = list(range(T2[0], T2[1]))
    Gf_n = list(range(T2[1], len(graph.nodes)+1))

    cited = []
    citing = []
    i = 0
    for info in graph.adjlist:
        cited += info[:graph.m]
        citing += [i]*graph.m
        i += 1
    df_CI = pd.DataFrame(data={'cited': cited, 'citing': citing})

    """ Sort by k """
    df_CI_tmp = df_CI[df_CI['cited'].isin(G1_n) & ~df_CI['citing'].isin(Gf_n)]  # delete future data from G1
    G1_k = df_CI_tmp['cited'].value_counts()  # Cited number in G1

    """ Sort edges """
    df_CI_fromG2_toG1 = df_CI[df_CI['cited'].isin(G1_n) & df_CI['citing'].isin(G2_n)]  # G2 to G1 edges

    N = len(G1_n)
    m = len(df_CI_fromG2_toG1)
    k_log = []
    A_log = []
    k_list = np.unique(G1_k.values)
    for k in k_list:
        n1_list = G1_k[G1_k == k].index
        nk = len(n1_list)
        mk = len(df_CI_fromG2_toG1[df_CI_fromG2_toG1['cited'].isin(n1_list)])
        A = float(N) * float(mk) / float(m) / float(nk)
        k_log += [k]
        A_log += [A]

    return np.array(k_log), np.array(A_log)


def Newmans_attachment_rate_model_fast_for_m(graph):

    k1 = [len(degree) for degree in graph.adjlist]
    degree_max = max(k1)
    t_max = len(graph.nodes)

    """ wAk : w_k*Ak, wk : w_k"""
    """ 모든 정보는 degree k 에 따라 저장 """
    wAk = np.zeros(degree_max)
    wk = np.zeros(degree_max)

    """ Calculate attachment rate"""
    degree_list = [len(adj) for adj in graph.init_adjlist]  # 각 node의 degree list 생성
    tmp_k = max(degree_list)
    degree_num = [degree_list.count(k) for k in range(1, tmp_k + 1)]    # degree별 개수 정보를 저장하는 list 생성
    """ Time period (T1 ~ T2(max)) """
    start_t = len(degree_list)
    t_list = list(range(start_t, t_max))
    for t in t_list:
        """ 신규 node에게 선택된 기존 node와 그 node들의 degree 정보 """
        node_s = graph.adjlist[t][:graph.m]
        degree_node_s = [degree_list[node] for node in node_s]
        dict_mk_t = collections.Counter(degree_node_s)

        """ N_t는 현재의 t값 """
        N_t = t
        """ 신규 link의 수는 그래프 성장 규칙에 따른 m값 """
        m_t = graph.m

        """ degree list in before t """
        k = 0
        for nk_t in degree_num:
            k += 1
            mk_t = 0
            if k in degree_node_s:
                mk_t = dict_mk_t[k]     # 신규 link 중 degree k 인 node에게 연결된 link의 수
            if nk_t != 0:   # degree k 인 node의 개수가 0이 아닐 때, 정보 업데이트
                wk_t = m_t
                wk[k - 1] += wk_t
                wAk[k - 1] += wk_t * N_t * mk_t / nk_t / m_t

        """ degree list 업데이트 """
        for node in node_s:
            degree_list[node] += 1
        degree_list += [graph.m]

        # 선택받은 노드의 degree 가 n이었던 경우 이전 degree num[n-1] 이 1감소
        # degree_num[n] (n+1 degree의 개수) 은 1 증가
        # 없을 경우 새로운 열 추가
        degree_num[graph.m - 1] += 1
        for degree_node in degree_node_s:
            degree_num[degree_node - 1] -= 1
            try:
                degree_num[degree_node] += 1
            except:
                degree_num += [1]

    """ Calculate  Newman attachment rate """
    result = wAk

    """ Calculate  Corrected Newman attachment rate """
    wk[wk == 0] = 1
    result_C = wAk / wk

    degree = np.arange(len(result))

    degree = degree[result != 0]
    result = result[result != 0]
    result_C = result_C[result_C != 0]

    k_log = degree + 1
    A_log = result / result.sum()
    A_C_log = result_C / result_C.sum()

    return k_log, A_log, A_C_log



""" model 생성 """
BA = BA_model(m=2, seed=3)
BA.add_nodes(n=100000)

""" Attachment rate 분석"""
k_J, A_J = Jeongs_attachment_rate_model(graph=BA, T1=[0, 50000], T2=[50000, 100000])
k, A, A_C = Newmans_attachment_rate_model_fast_for_m(graph=BA)

""" Plot """
fig = plt.figure()
plt.plot(k_J, A_J/A_J[0],ls='',marker='.', label="Jeong's method")
plt.plot(k, A/A[0],ls='',marker='.', label="Newman's method")
plt.plot(k, A_C/A_C[0],ls='',marker='.', label="corrected Newman's method")
plt.xscale('log')
plt.yscale('log')
plt.xlabel('Degree')
plt.ylabel('Attachment rate (Normalized)')
plt.legend()
plt.show()