Link prediction problem for Social Networks 리뷰

https://www.cs.cornell.edu/home/kleinber/link-pred.pdf

 

1.

 

“Link Prediction Problem” 은 시간 T 에서의 네트워크에 대한 스냅샷에 주어졌을 때, 이후 T’의 시간에서 추가될 edge 를 예측하는 문제를 말한다.  즉, “Link Prediction Problem”은 네트워크 구조의 intrinsic한 특성(네트워크의 위상적 측면)이 네트워크의 진화에 얼마나 기여하는지에 관한 문제라고 볼 수 있다. 연구는 특정 node들 간의 “Proximity”가 클수록 향후 네트워크에서 그 노드 간의 edge 가 생성될 확률이 크다는 전제를 가지고, proximity를 측정하는 여러 방법들 중 어떤 방법이 가장 효과적으로 link prediction을 할 지를 분석한다.

 

2. 

- 모든 predictors 는 baseline 으로 둔 random predictor 보다 높은 성능을 보였다. link formation 에 네트워크 구조적인 측면이 존재한다는 뜻이다. 

 

- 실험 결과에서 일부 predictors 들이 생성될 edge 를 유사하게 예측하는 양상을 보였다. predictors 들끼리 각 측정방법이 다름에도 특정 edge 들에 대해 overlap 되었다는 측면에서 흥미롭다. 

 

- 또한 small worlds 문제가 예측에 걸림돌이 되는 진짜 "문제" 로 고려되었다. 즉, proximity 를 측정할 때 몇다리를 건너 내가 이사람을 아는 지는 크게 도움되지 않았는데, 이는 다들 몇다리만 건너면 거의 알았기 떄문이다.(small world problems).

 

 

 

- dataset으로 다섯 종류의 arXiv의 연구 섹션에서의 co-authorship network를 알아보기 위한 astro-ph, cond-mat, gr-qc, hep-ph, hep-th를 사용했는데, 특정 데이터셋에 대해선 전반적인 predictors 의 정확도가 높고, 또 다른 특정 데이터셋에 대해선 낮은 정확도를 보였다. 

논문에선 이를 "simpler"한 구조의 데이터셋(gr-pc), 또는 "difficult" 한 구조의 데이터셋(astro-ph)이라고 했다. 

 

 

simple 과 difficult 는 구조적인 측면만으로 얼마나 예측이 가능한가의 문제에 대한 난이도만을 얘기하는 거라면, 

각 예측이 잘되고 잘 안된 데이터셋이 어떤 모양이고, 노드와 엣지는 얼마나 많이 포함되어있고 하는 부분이 궁금했다. 

 

gr-qc 는 확실히 edge 나 authors, papers 수가 적은 데이터셋이었던 반면

가장 "어려운" astro-ph 는 authors 수는 평균이지만 paper 수는 적은편이었고, edge 는 다른 데이터셋보다 2배~약 7배까지 컸다. 

 

The set Core is the subset of the authors who have written at least κtraining = 3 papers during the training period and κtest = 3 papers during the test period. The sets Eold and Enew denote edges between Core authors which first appear during the training and test periods, respectively.