NetworKit 11.2.1 대규모 그래프 분석 튜토리얼
오늘날 네트워크 과학은 우리가 상호 작용하는 복잡한 시스템을 이해하기 위한 필수 도구로 부상했습니다. 소셜 네트워크에서 생물학적 네트워크에 이르기까지 그래프는 이러한 연결된 시스템을 표현하는 강력한 프레임워크를 제공합니다. 이러한 네트워크가 커짐에 따라 그래프 분석 기술을 효율적으로 처리하고 이해하는 능력은 매우 중요합니다. NetworKit은 이러한 요구를 해결하기 위해 설계된 강력한 C++ 라이브러리로, 속도, 메모리 효율성, 버전 안전 API를 제공합니다.
이 튜토리얼에서는 NetworKit 11.2.1을 사용하여 프로덕션 등급의 대규모 그래프 분석 파이프라인을 구현하는 방법을 살펴보겠습니다. 여기에는 대규모 자유 네트워크를 생성하고, 가장 큰 연결 구성 요소를 추출하고, k-코어 분해 및 중심성 순위를 통해 구조적 백본 신호를 계산하고, PLM을 사용하여 커뮤니티를 감지하고, 모듈러리티를 사용하여 품질을 정량화하고, 효과적이고 추정된 지름을 사용하여 거리 구조를 추정하고, 마지막으로 주요 속성을 유지하면서 그래프를 희소화하는 과정이 포함됩니다. 그런 다음 희소화된 그래프를 에지 목록으로 내보내 다운스트림 워크플로, 벤치마킹 또는 그래프 ML 전처리에 재사용할 수 있습니다. 그래프 분석은 데이터 과학, 사회 과학, 공학 등 다양한 분야에서 점점 더 중요해지고 있습니다.
1단계: NetworKit 환경 설정 및 기본 설정
이 튜토리얼을 시작하기 전에 NetworKit 및 종속성을 설치해야 합니다. 이 튜토리얼에서는 Colab 환경을 사용하지만 로컬 시스템에서 NetworKit을 사용할 수도 있습니다. 먼저 NetworKit을 설치하고 필요한 라이브러리(pandas, numpy, psutil)를 가져오겠습니다.
pip -q install networkit pandas numpy psutil
import gc, time, os
import numpy as np
import pandas as pd
import psutil
import networkit as nk
print("NetworKit:", nk.__version__)
k.setNumberOfThreads(min(2, nk.getMaxNumberOfThreads()))
k.setSeed(7, False)
이 코드는 NetworKit과 관련된 필수 라이브러리를 설치하고 가져옵니다. 또한 스레드 사용을 지정하고 재현성을 위해 임의의 시드를 설정합니다. 그래프 분석 작업을 수행하기 위한 기본적인 환경 설정을 제공합니다. NetworKit의 버전 정보도 출력합니다.
2단계: 대규모 그래프 생성 및 LCC 추출
NetworKit을 사용하기 위한 준비가 되면 대규모 그래프를 생성하는 데 집중할 수 있습니다. 이 튜토리얼에서는 Barabási–Albert 모델을 사용하여 자유 네트워크를 생성합니다. Barabási–Albert 모델은 인터넷이나 소셜 네트워크와 같은 많은 실제 네트워크에서 관찰되는 현상인 선호적 첨부 프로세스에 기반합니다.
t0 = tic()
G = nk.generators.BarabasiAlbertGenerator(M_ATTACH, N).generate()
toc(t0, "Generated BA graph")
report(G, "G")
Barabási–Albert 생성기를 사용하면 지정된 연결 수(M_ATTACH)와 노드 수(N)를 기반으로 그래프를 생성할 수 있습니다. 그런 다음 연산 시간을 측정하고 연결 그래프의 속성을 보고합니다. 그런 다음 연결 구성 요소를 계산하여 그래프의 단편화를 파악합니다. 이 단계는 특히 네트워크가 여러 개의 분리된 구성 요소로 분할된 경우 분석을 위한 지침을 제공합니다. 최종적으로 가장 큰 연결 구성 요소(LCC)를 추출하여 나머지 파이프라인의 성능과 안정성을 개선합니다. 그래프 분석의 핵심 단계입니다.
3단계: 구조적 백본, 커뮤니티 감지 및 지름 추정
LCC를 추출한 후 구조적 백본을 계산하고 커뮤니티를 감지하고 지름을 추정하는 데 집중할 수 있습니다. 구조적 백본은 네트워크의 가장 중요하고 연결된 부분을 나타냅니다. k-코어 분해를 사용하면 그래프에서 각 노드의 핵심을 식별하여 중요도를 측정할 수 있습니다. 다음은 그래프 분석에서 중요 노드를 식별하는 데 도움이 됩니다.
t0 = tic()
core = nk.centrality.CoreDecomposition(G)
core.run()
toc(t0, "CoreDecomposition")
core_vals = np.array(core.scores(), dtype=np.int32)
print("degeneracy (max core):", int(core_vals.max()))
print("core stats:", pd.Series(core_vals).describe(percentiles=[0.5, 0.9, 0.99]).to_dict())
k_thr = int(np.percentile(core_vals, 97))
t0 = tic()
nodes_backbone = [u for u in range(G.numberOfNodes()) if core_vals[u] >= k_thr]
G_backbone = nk.graphtools.subgraphFromNodes(G, nodes_backbone)
toc(t0, f"Backbone subgraph (k>={k_thr})")
report(G_backbone, "Backbone")
PLM을 사용한 커뮤니티 감지는 네트워크의 모듈성을 파악하는 데 도움이 됩니다. 모듈성은 네트워크가 얼마나 잘 구성되어 있는지를 측정하는 지표입니다. 모듈성이 높다는 것은 네트워크가 밀접하게 연결된 커뮤니티로 구성되어 있음을 나타냅니다. 마지막으로 효과적이고 추정된 지름을 사용하여 네트워크의 전반적인 거리를 평가합니다. 그래프 분석에서 이러한 측면을 이해하는 것은 네트워크의 속성과 동작에 대한 귀중한 통찰력을 얻는 데 필수적입니다.
4단계: 그래프 희소화 및 다운스트림 워크플로 준비
분석이 완료되면 그래프를 희소화하여 크기를 줄이고 다운스트림 워크플로에 적합하게 만들 수 있습니다. 희소화는 그래프의 가장 중요한 속성을 유지하면서 가장 덜 중요한 에지를 제거하는 프로세스입니다. 이 튜토리얼에서는 Local Similarity Sparsifier를 사용합니다.
t0 = tic()
sp = nk.sparsification.LocalSimilaritySparsifier(G, 0.7)
G_sparse = sp.getSparsifiedGraph()
toc(t0, "LocalSimilarity sparsification (alpha=0.7)")
report(G_sparse, "Sparse")
희소화된 그래프를 분석하여 중요 신호가 보존되었는지 확인합니다. 그런 다음 희소화된 그래프를 에지 목록으로 내보내 다운스트림 워크플로, 벤치마킹 또는 그래프 ML 전처리에 사용할 수 있습니다. 그래프 분석 파이프라인의 효율성을 높이는 데 중요한 단계입니다.
결론
이 튜토리얼에서는 NetworKit 11.2.1을 사용하여 프로덕션 등급의 대규모 그래프 분석 파이프라인을 구현하는 방법을 살펴보았습니다. 이러한 기술을 통해 다양한 실제 네트워크의 복잡성을 이해하고 중요한 통찰력을 얻을 수 있습니다.
이 튜토리얼을 통해 실용적인 템플릿을 제공하여 실제 데이터 세트에 적용할 수 있습니다. 이 템플릿은 그래프 생성에서 분석, 희소화 및 내보내기에 이르기까지 다양한 단계를 다룹니다. 이러한 다양한 기술은 그래프 분석의 힘을 발휘하여 다양한 분야에 걸쳐 의미 있는 통찰력을 제공하는 데 도움이 될 수 있습니다.
심층 분석 및 시사점
Array
