[NetworkX] 새로운 노드는 어디에 어떤 노드와 연결될까?Preferential Attachment Model (Barabasi Albert Model)

---

실 세계에서의 Degree 분포

한 학교에 새로 전학생이 왔습니다.

이 친구는 누구와 친구가 될 가능성이 가장 높을까요?

앉는 자리와 같은 변수를 제거한다면, "이미 친구가 많은" 아이와 친구가 될 가능성이 가장 높습니다.

 

실제 세계에서는 관계망을 이미 많이 가진 것들이 더 많은 관계를 가지게 될 가능성이 높습니다.

• A: 한 영화에 같이 나온 적이 있는 영화배우들의 관계망
• B: 하이퍼링크로 연결된 웹 연결망
• C: 미국 전력 변전 연결망

A,B,C의 네트워크 모두,

관계(Degree)를 극도로 많이 가지고 있는 노드는 극소수이고,

적은 수의 관계를 가지고 있는 노드가 다수임을 확인할  수 있습니다.

 

관계망의 빈익빈 부익부인 셈이죠.

 

이러한 실 세계 현상을 모델화 한 것을

바라바시 알베르트 모델(Barabasi Albert Model), 혹은 Preferential attatchment model이라고 합니다.

 

Preferential Attachment Model (Barabasi Albert Model)

기본적인 아이디어는 위에서 했던 설명과 같습니다.

• 새로 유입된 node는 이미 edge가 많은 node와 연결될 가능성이 높다

(6)은 (2)와 연결될 가능성이 가장 높습니다.

위의 (1)~(5) 그래프 그림에서, 각 노드 위에 적혀있는 숫자는

• 각 노드가 차지하고 있는 edge 비율을 의미합니다. (하나의 엣지를 두개의  노드가 공유하고 있음에 유의)
• 이는 곧, 새로 들어온 (6)과 연결될 확률을 의미하기도 합니다.

 

실습

바라바시 알베르트 모델은 네트워크 이론에서 그래프 생성모델로 여겨집니다.

위에서 살펴보았듯, 노드의 degree의 비율에 따라 그래프가 지속적으로 성장하기 때문이죠.

• barabasi_albert_graph(n,m)
• n: 몇개의 노드로 이루어진 네트워크 그래프인가?
• m: 새로운 노드는 몇개의 노드와 연결관계를 갖게 될 것인가?

import matplotlib.pyplot as plt

n_li = [5,10,20,50]

plt.figure(figsize=(12,10))

for i in range(4):
    plt.subplot(2, 2, i+1)
    G = nx.barabasi_albert_graph(n_li[i], 1)
    pos = nx.kamada_kawai_layout(G)
    nx.draw(G, pos, with_labels=True)

    plt.title(f"Number of Nodes = {n_li[i]}")

 

확률에 기반해 그려진 그래프이기 때문에, seed를 고정하지 않는 한 그래프 만들때마다 다른 그래프가 생성됩니다.