Social network analysis has attracted much attention in recent years. Link prediction is one of key research directions within this area. While various algorithms have been applied to link prediction, the k-nearest neighbor rule (k-NN), one of data mining techniques, is unsuitable for link prediction because the reference set of network data is generally large. The k-NN requires significant computational time and memory with large reference set. We propose an effective method (G2ED) to apply k-NN to link prediction. We set out to reduce the reference set without sacrificing classification accuracy and without incurring a significantly long editing time.
Eight data sets were used to compare the performance of the proposed method with that of existing methods from the literature. Proposed method reduced the reference set and recall time significantly. However the accuracies of k-NN with G2ED were virtually the same as those of other algorithms. In some datasets, the accuracies of k-NN with G2ED were better than those of other algorithms. The preliminary results indicate that the proposed method achieved the objective and thus merits further development.
Because the size of reference set for link prediction is generally huge, link prediction can be a good application for G2ED. We applied G2ED to link prediction in file sharing domain. In file sharing network, the nodes are users of web market where the users share their digital files each other and links mean that two users linked have shared their files in the period. We divided the whole dataset into six periods by time and used time window techniques to predict the link in the 6th period. Since the dataset is highly imbalanced, we tried oversampling techniques and used F-measure for performance measure instead of accuracy. The experiments resulted in the way we expected. G2ED reduced 69636 reference data points to 14014 that is about one-fifth. So the predicting time is also reduced to about one-sixth. Even more surprising is the increasing F-measure. We can conclude that the G2ED algorithm is suitable to condense the k-NN reference set in link prediction. Compared to other benchmark algorithms, experimental results show that k-NN with G2ED is the most efficient predictor. The k-NN, SVM, and NN have similar performance in accuracy and F-measure. In F-measure k-NN with G2ED performed the best. The k-NN with G2ED was much faster than SVM and NN. Decision tree was the fastest, but its accuracy and F-measure are relatively poor. As an additional experiment, G2ED was applied to patter selection for SVM. G2ED looks suitable for pattern selection technique not only for k-NN but also for other classifiers.
Some applications of link prediction in file sharing network were discussed. We focused the recommendation based on link prediction for an application of link prediction. The pairs of users that had not any link in the 5th period but are predicted to be linked in the 6th period have higher probability of being linked than the other pairs, when we recommend each other. To evaluate the performance of recommendation by link prediction, we conducted some simulations and used random recommendation for comparison. The number of link in the 6th period is 986 in original dataset. In the results of simulation, there will be 1174 links with random recommendation and 1486 links with recommendation by link prediction. Recommendation with link prediction can make two-and-a-half times more links than random recommendation.
본 학위 논문은 k-인접 이웃 분류(k-nearest neighbor rule, k-NN) 기법을 기반으로 자료 공유 네트워크에서 링크를 예측하는 것을 목표로 한다. k-인접 이웃 분류는 참조 데이터셋의 크기가 클 경우 높은 계산 복잡도를 갖는데, 링크 예측 분야에서는 일반적으로 그 크기가 크기 때문에 계산 복잡도 문제를 해결할 필요가 있다. 본 논문은 크게 두 가지 소주제로 구성되어 있다. 첫번째는 k-인접 이웃 분류의 계산 복잡도를 극복하는 참조 데이터셋 압축 방법을 제안하는 것이고, 두번째는 제안하는 방법을 링크 예측에 적용하는 것이다.
k-인접 이웃 분류는 분류하고자 하는 입력 데이터가 들어오면 보유하고 있는 참조 데이터 셋(reference set) 중에서 가장 가까운 k개의 데이터의 클래스를 통하여 분류하는 비모수 분류 알고리즘으로써, 단순하지만 우수한 성능을 갖는 기법이다. k-인접 이웃 분류는 다양한 분류 문제에 많이 사용되고 있으나, 참조 데이터 셋의 크기가 증가함에 따라 분류시간이 급격히 증가하기 때문에, 빠른 분류가 필요한 문제에 적용하기 어려웠다. 또한 이를 해결하기 위하여 참조 데이터 셋을 편집(editing)하는 많은 방법들이 제안되었지만, 편집에 매우 오랜 시간을 소요하여야 했다. 이 논문에서는 성능(accuracy)의 유지와 동시에 편집 시간(editing time)과 분류 시간(recall time) 모두를 크게 감소시키는 것을 목표로 하여, 분류 성능에 거의 영향을 미치지 않는 데이터들을 신속하게 제거함으로써 참조 데이터 셋의 크기를 감소시키는 G2ED (Growing froe 2 Extreme Datapoints) 방법을 제안하였다. 제안하는 방법은 최초 참조 데이터셋의 분류 경계는 유지하는 것을 목표로 하여, 분류 경계에 가까이 존재하는 데이터들만을 참조 데이터셋으로 구성하는 방법을 사용하였다. 다양한 데이터 셋에 대한 실험으로 이를 입증하였으며, 침입 탐지, direct marketing, 숫자 인식의 분야에서도 제안하는 방법이 효과적일 것임을 보여주었다. 제안하는 방법은 데이터셋에 따라 최대 1/100 정도로 분류 시간을 단축하면서도 예측 정확도는 유지하였다.
다음으로 일반적인 분류에서 효율적인 실험결과를 보여주었던 제안 알고리즘 G2ED를 활용하여 링크 예측을 수행하였다. 소셜 네트워크를 포함한 대부분의 네트워크는 정적으로 멈추어 있는 것이 아니라 시간이 지나면 그 구조가 변화한다. 즉 존재하지 않던 링크가 생기기도 하며, 때에 따라 존재하던 링크가 사라지기도 한다. 과거와 현재 시점의 네트워크 구조를 기반으로 미래의 네트워크 노드 쌍들의 링크 존재를 예측하는 것을 링크 예측이라 한다. 링크 예측을 수행하기 위하여 국내 온라인 디지털 파일 공유 사이트의 고객 데이터를 수집하였다. 두 고객이 서로의 디지털 파일을 공유하면 링크가 존재하고, 그렇지 않으면 둘 사이에는 링크가 없는 구조로 네트워크를 완성하였다. 링크 예측을 위한 독립변수로는 나이, 성별, 직업의 노드 정보와 링크 존재유무, 최단거리, 자료공유빈도, 네트워크 상에서 이웃의 수를 활용하였고, 클래스 불균형 문제를 극복하기 위하여 오버샘플링을 수행하였다. 기존의 k-NN은 6300초 가량의 시간을 소요하며 F-measure 0.18을 기록하였고, 제안하는 알고리즘 G2ED를 활용한 k-NN은 1000여초의 시간을 소요하며 0.19의 F-measure를 보여주었다. 신경망, 의사결정나무, SVM과 비교하여도 G2ED를 활용한 k-NN은 예측 시간과 정확도 면에서 가장 효율적인 결과를 보여주었다.
링크 예측 결과를 기반으로 비즈니스 측면에서 활용 방법에 대해서도 논하였는데, 특히 추천시스템에의 활용에 대하여 연구하였다. 링크가 생길 것으로 예측되는 고객 쌍에게 추천을 수행하면 서로의 자료를 공유할 확률이 높을 것으로 기대가 되기 때문이다. 시뮬레이션을 통하여 링크 예측 기반의 추천시스템의 효용을 간접적으로 증명하였다. 또한 고객 쌍들의 자료 공유 확률의 분포를 통하여 예산에 따른 추천 타깃 고객을 선별하는데에도 활용할 수 있다.
