The link prediction problem for social networks

Motivation

• Known: 소셜 네트워크가 시간에 따라 새로운 edge가 추가되며 진화한다는 것과, 이러한 네트워크가 small-world 속성, power-law degree distribution 등 특정 global structural feature를 가진다는 것은 이미 알려져 있었다. 또한 여러 network growth model들이 제안되어 왔다.
• Gap: 기존 network evolution model들은 주로 실제 네트워크에서 관찰되는 global structural feature를 재현하는지 여부로만 평가되어 왔고, 서로 다른 접근법을 원칙적인 기준에서 비교·평가하기 어려웠다. 네트워크 진화가 network 자체의 intrinsic feature만으로 어느 정도 예측 가능한지에 대한 체계적 정량 평가가 부재했다.
• Why: link prediction은 network evolution model을 평가하는 자연스럽고 원칙적인 기준을 제공하며, 조직 내 informal social network 분석, 테러 네트워크와 같은 security 분야의 숨겨진 상호작용 추론 등 실용적 응용 가치가 크다.
• Approach: training interval의 co-authorship network snapshot으로부터 node proximity를 측정하는 다양한 score(x,y) 기반 predictor들을 정의하고, 이를 test interval에 실제 나타난 새로운 edge와 비교하여 성능을 평가한다.

Achievement

1. Link prediction problem의 정식화: 소셜 네트워크의 snapshot G[t0, t0']로부터 미래 test interval G[t1, t1']에 나타날 edge를 예측하는 문제를 명확히 정의하고, Core 노드 집합과 성능 평가 지표(precision-like intersection measure)를 제안했다.
2. 대규모 co-authorship 네트워크 실험: arXiv의 5개 분야(astro-ph, cond-mat, gr-qc, hep-ph, hep-th) 데이터를 이용해 1994-1996 training, 1997-1999 test interval로 나누어 실증 실험을 수행했다.
3. 다양한 proximity measure 비교: shortest path, common neighbors, Jaccard's coefficient, Adamic/Adar, preferential attachment 등 그래프 이론 및 사회연결망 분석 기법에서 파생된 여러 measure를 체계적으로 비교했다.
4. 예측 성능 입증: 특정 proximity measure들이 무작위 예측(chance) 대비 40~50배의 성능 향상을 보였으며, path 기반의 infinite sum을 활용하는 미묘한 measure가 shortest-path distance나 단순 공통 이웃 수 같은 직접적 measure보다 우수함을 보였다.

How

• 그래프 G=⟨V,E⟩를 시간 정보가 부여된 edge들로 정의하고 training interval [t0,t0'] 및 test interval [t1,t1']을 설정
• Gcollab := ⟨A, Eold⟩ (training graph)와 Enew (test interval에 나타난 새 edge 집합) 정의
• 최소 논문 수 조건(κtrain=κtest=3)을 만족하는 노드들로 Core 집합 구성, E*new = Enew ∩ (Core×Core)
• 각 predictor는 score(x,y)를 계산하여 pair들을 랭킹하고, 상위 n=|Enew|개 예측과 실제 Enew의 교집합 크기로 성능 측정
• 비교 predictor: shortest path length, common neighbors |Γ(x)∩Γ(y)|, Jaccard's coefficient, Adamic/Adar 가중치 합, preferential attachment (|Γ(x)|·|Γ(y)| 비례), 및 path 기반 infinite sum measure들(예: Katz-style)

Originality

• 소셜 네트워크 진화를 예측 가능한 computational problem으로 최초로 명확히 정식화한 초기 연구 중 하나
• 기존 network growth model 평가 방식(global structural feature 재현 여부)에서 벗어나, 실제 미래 데이터에 대한 예측 정확도라는 새로운 평가 프레임을 제시
• 그래프 이론 및 정보 검색(IR)에서 사용되던 다양한 similarity measure(Jaccard, Adamic/Adar 등)를 사회 연결망의 link prediction 맥락에 체계적으로 이식하고 비교

Limitation & Further Study

• 저자 식별이 first initial + last name 방식이라 동명이인 등으로 인한 노이즈가 존재할 수 있음
• 평가 대상이 co-authorship 네트워크(arXiv 물리학 분야)로 한정되어 있어 다른 유형의 소셜 네트워크(예: 온라인 소셜 미디어, 조직 내 네트워크)로의 일반화 가능성은 추가 검증 필요
• topology 정보만을 활용하며, 노드 속성(예: 연구 주제, 소속기관 등) 등 exogenous feature를 결합하지 않음 (Popescul and Ungar 등 후속 연구에서 보완)
• 성능 지표가 상위 n개 예측과의 단순 교집합 크기로, 랭킹 전체의 품질을 세밀하게 평가하는 지표(AUC 등)는 사용되지 않음

Evaluation

총평: 소셜 네트워크의 link prediction이라는 문제를 최초로 엄밀하게 정식화하고 대규모 실증 실험으로 그 실현 가능성을 입증한 매우 영향력 있는 초기 연구로, 이후 network science와 recommender systems 분야에 지대한 영향을 미쳤다.