[그래프 ML] 그래프 생성 - 파이썬 NetworkX

목차

• ※ 이전 글 참고
• 1. 간단한 그래프
  • 1.1. 완전 연결 무향 그래프(Fully Connected Undirected Graph)
  • 1.2. 롤리팝 그래프(Lollipop Graph)
  • 1.3. 바벨 그래프(Barbell Graph)
  • 1.4. 그래프 병합
• 2. 그래프 생성 모델
  • 2.1. 와츠-스트로가츠 모델(Watts-Strogatz Model; 1998)
  • 2.2. 바라바시-알베르트 모델(Barabasi-Albert Model; 1999)

 

※ 출처 : 그래프 머신러닝 (클라우디오 스타밀레 외, 김기성·장기식 옮김)

 

※ 이전 글 참고

2024.03.08 - [인공지능/그래프] - [그래프 ML] 파이썬 networkx 시작하기

2024.03.11 - [인공지능/그래프] - [그래프 ML] 그래프 속성 - 파이썬 networkx

 

1. 간단한 그래프

1.1. 완전 연결 무향 그래프(Fully Connected Undirected Graph)

* $n$개의 노드일 때, $\frac{n(n-1)}{2}$개의 간선과 군집 계수 $C=1$을 가짐
* 더 큰 그래프를 구성하는 기본 구성 요소(building block)
  - $n$개의 노드로 구성된 완전 연결 부분그래프를 크기가 $n$인 클리크(clique)라 함
  - 클리크를 찾는 작업(clique problem)은 컴퓨터 공학에서 연구되는 비결정적 다항시간 완전(NP-complete) 문제로 밝혀짐

import networkx as nx


fully_connected_undirected_G = nx.complete_graph(n=7)
nx.draw(fully_connected_undirected_G, with_labels=True)

완전 연결 무향 그래프(Fully Connected Undirected Graph)

 

1.2. 롤리팝 그래프(Lollipop Graph)

* 크기가 $m$인 클리크와 $n$개 노드의 가지(branch)가 있는 그래프

lollipop_G = nx.lollipop_graph(m=7, n=3)  # m: 클리크 크기, n: 가지의 노드 개수
nx.draw(lollipop_G, with_labels=True)

롤리팝 그래프(Lollipop Graph)

 

1.3. 바벨 그래프(Barbell Graph)

* 크기가 $m1$인 클리크 2개가 $m2$개 노드의 가지로 연결된 그래프

barbell_G = nx.barbell_graph(m1=7, m2=4)  # m1: 클리크 크기, m2: 가지의 노드 개수
nx.draw(barbell_G, with_labels=True)

바벨 그래프(Barbell Graph)

 

1.4. 그래프 병합

* networkx.disjoint_union_all 함수 사용

import numpy as np


all_G = nx.disjoint_union_all([fully_connected_undirected_G, lollipop_G, barbell_G])
for _ in range(2):  # 임의의 간선 추가
    all_G.add_edge(np.random.choice(all_G.nodes), np.random.choice(all_G.nodes))

nx.draw(all_G, with_labels=True)

완전 연결 무향 그래프, 롤리팝 그래프, 바벨 그래프 병합

 

2. 그래프 생성 모델

* 그래프가 자동으로 성장하는 확률 모델(probabilistic model)과 생성 모델(generative model)로 그래프를 구성할 수 있음

 

2.1. 와츠-스트로가츠 모델(Watts-Strogatz Model; 1998)

* 작은세상 네트워크(Small-world network)를 생성하는 대표적인 그래프 생성 모델
  - 작은세상 네트워크(Small-world network) : 높은 군집화 계수, 짧은 평균 경로 길이를 갖는 네트워크

* 생성 과정
  1. 고리 격자(Ring lattice) 구조의 정규 그래프를 생성
    . 각 노드는 양쪽으로 일정 거리 이내의 노드들과 연결됨
  2. 각 간선에 대해 일정 재배선 확률(rewiring probability; $p$)로 한쪽 끝을 다른 임의의 노드로 재배선

G = nx.watts_strogatz_graph(n=20, k=5, p=0.2)  # n: 노드 개수, k: 이웃 노드 개수(n의 절반보다 작아야 함), p: 재배선 확률(0~1)
nx.draw(G)

와츠-스트로가츠 모델(Watts-Strogatz Model; 1998)

 

2.2. 바라바시-알베르트 모델(Barabasi-Albert Model; 1999)

* 척도없는 네트워크(Scale-free network)를 생성하는 대표적인 그래프 생성 모델
  - 척도없는 네트워크(Scale-free network) : 노드 차수 분포가 멱함수 분포를 따르는 네트워크
    . 소수의 노드가 매우 높은 차수를 갖고, 대다수의 노드는 작은 차수를 가짐

* 생성 과정
  1. 초기에 $n0$개 노드로 구성된 작은 그래프를 생성
  2. 새로운 노드를 하나씩 추가하며, 새 노드를 기존 노드들과 $m$개의 간선으로 연결
  3. 새 노드와 기존 노드를 연결할 때, 기존 노드 $i$가 가진 차수 $k_i$에 비례하는 확률 $p_i$로 연결
$$p_i = \frac{k_i}{\sum k_j}$$
    . 부가적 선호 연결(Preferential attachment) 원리

G = nx.extended_barabasi_albert_graph(n=20, m=1, p=0.2, q=0.2)  # n: 최종 노드 개수, m: 각 새 노드가 연결될 간선 개수, p: 부가적 선호 연결 확률, q: 노드 생성 확률 
nx.draw(G)

바라바시-알베르트 모델(Barabasi-Albert Model; 1999)