Link prediction in complex networks : a network structural perspective = 복잡계 네트워크 링크 예측법의 구조적 의존성에 대한 분석

국문 초록 (Abstract)

본 논문에서는 유사도 지수를 활용한 네트워크 링크 예측법 방법론의 구조적 의존성에 대해 논하기 위한 모델 스터디와 이론적 설명 토대를 만드는 것을 목표로 하였다.
네트워크 분석은 복잡계를 분석하는 방법론으로 주목받고 있으며, 이는 빅데이터 기술에 힘입어 발전해왔다. 그러나 데이터가 현실의 모든 관계를 담고 있지 못하는 경우가 많으며, 이는 네트워크 분석의 신뢰도에 영향을 끼친다. 이를 해결하기 위한 방법론으로 링크 예측법을 활용하여 데이터의 신뢰도를 높일 수 있다.
이를 위하여 주로 유사도 지표가 활용된다. 유사도 지표는 네트워크 상의 두 노드가 얼마나 구조적으로 닮았는지 측정하는 양으로 정의된다. 유사도 지표에 따라 링크 예측법의 정확도가 달라지며, 따라서 실제 네트워크에서 정확도가 높은 유사도 지표를 정의하는 것이 연구의 주된 관심사이다.

그러나 현재까지 모든 네트워크에서 높은 정확도를 가지는 유사도 지표는 발견되지 않았다. 유사도 지표의 정확도는 네트워크의 구조에 의존하며, 이를 연구하는 것 또한 중요한 연구주제이다. 이와 관련되어 무엇이 링크 예측법의 정확도와 관련있는지에 대한 많은 추측이 있었다. 가령 유사도 지표가 포착하고자 하는 구조의 여부, 성장하는 네트워크의 메커니즘과 유사도 지표의 관계, 원본 네트워크의 유사도 분포의 분리 상태 등이 영향을 줄 것으로 예상되고 있다. 그러나, 이러한 추측들이 수치적으로 정확히 증명되지는 않고 있다.
본 학위논문에서는 이러한 추측들을 명확히 하기 위해, 링크 예측법의 이론적인 설명을 하는 것을 목표로 하고 있다. 이를 위해 네트워크 모델에 이를 적용해 유사도 지표와 정확도가 네트워크의 기본 성질과 어떻게 연관되어 있는지 살펴보았다. 이후 유사도 분포와 유사도 지표의 변화를 계산하여 링크 예측법의 과정을 수식으로 기술하여 유사도 지수의 특성과 이러한 지수별로 어떠한 구조적 특성이 정확도와 관련되어 있는지를 밝힌다.

우선 가장 유명한 두 네트워크 모델인 WS 모델과 BA 모델에 여러 가지 유사도 지표를 적용하였다. WS 모델은 현실 세계 네트워크가 밀집되어 있으면서 동시에 '작은 세상 효과' 가 어떻게 나타나는지를 설명하는 모델이다. BA 모델은 현실 세계 네트워크의 연결이 일부 노트에 치우친 현상을 설명하기 위한 모델이다. 이를 적용해 본 결과 모든 유사도 지표가 모델에 상관없이 평균 도수에 비례하여 정확도가 증가하는 모습을 보였으며, 이는 경험적으로 알려진 구조적 희소성 문제 (sparsity problem) 와 연관이 있음을 보였다. 또한 광역 유사도 지수 (global similarity index) 의 경우 대체적으로 좋은 성능을 보인다고 알려져 있으나, 모델에서의 결과를 통해 광역 유사도 지수가 항상 좋은 모습을 보이는 것은 아님을 보였다. 이를 통해 유사도 지수의 특성과 구조적인 의존성에 대해 이해하는 것이 중요한 문제임을 보였다.
다른 모델로서 노드 종류가 구별된 무작위 네트워크를 만들어 유사도 지수가 실제로 비슷한 노드를 잘 찾아내는지, 그리고 이것이 링크 예측법의 성능과는 어떤 관계가 있는지를 관찰하였다. 측정 결과 국소 유사도 지수 (local similarity index) 의 경우 다른 노드 종류 사이의 연결이 많은 경우에도 높은 성능을 보였다. 이들과 링크 예측법의 성능 관계를 관찰한 결과 서로 비례하나, 이 관계는 어떤 연결이 더 우세하느냐에 따라 비례하는 방향이 달라지는 것을 관찰할 수 있었다.
본 결과는 링크 예측법의 미시적 특성에 대해 알려준다. 링크 예측법의 성능은 서로 종류가 같은 노드 사이의 연결이 얼마나 잘 되어 있는지에 따라 결정되며, 이는 현실 세계 네트워크에서 주로 관찰되는 커뮤니티 구조와 관련이 있을 것으로 보인다.

이후 두 가지 유사도 지수 (common-neighbor (CN) index, preferential attachment (PA) index) 에 대해 수학적으로 기술하여 이러한 결과들을 설명하였다. 이를 위해 유사도 지수가 링크 소실에 대해 어떻게 반응하는지 전이 확률을 계산하여 네트워크의 본래 구조와 어떤 연관성이 있는지를 확인하였다. 이를 통해 링크 예측법의 성능은 본래 네트워크의 유사도 분포와 연관성이 있고, 둘 사이의 관계는 유사도 지수의 특성에 따라 조금씩 달라질 수 있음을 보였다. 두 번째 단계로서 본래 네트워크의 유사도 분포가 어떤 구조적인 특성에 의해 결정되는지를 수식으로 기술하고 어떤 특성이 더 중요한지 관찰하였다. PA의 경우 이는 도수 분포와 도수 사이의 연결관계에 따라 결정되는 것을 관측하였으며, CN의 경우 서로 모두 연결된 부분 그래프 구조에 의존함을 보였다. 이를 통해 PA 의 구조적 의존성에 대한 추측에 대한 설명을 제시하였으며, CN 의 경우 성능과 연관되어있다고 알려진 결집 계수 (clustering coefficient) 가 직접적인 결정 인자가 아니라 이러한 부분 그래프 구조의 결과로서 나타나는 것임을 보였다.

본 논문에서는 최초로 링크 예측법의 구조적 의존성에 대한 문제를 수식 기반으로 설명하였다. 이를 통하여 링크 예측법에 대한 더 깊은 이론적 이해를 위한 토대를 마련하고, 유사성 지표를 실제로 적용할 때 혹은 새로운 유사도 지표를 정의할 때 이러한 이해가 밑바탕이 되어 발전될 수 있을 것으로 보인다.

다국어 초록 (Multilingual Abstract)

Link prediction is an important tool for restoring missed connections in real-world networks. Complex network analysis, based on graph theory, helps to infer the network structure from the statistical characteristics of the network. However, missed connections distort the complex network analysis; link prediction is a crucial tool for obtaining more-reliable results of complex network analysis.

A similarity index, which measures the topological proximity of node pairs, is usually employed to find missed connections because of its simplicity, low calculation complexity, and wide extensibility. Improving the link prediction performance is a key problem in both theoretical discussion and empirical application; therefore, numerous similarity indices are defined to improve the performance. However, the index that shows the highest performance in all the networks has not been reported because of the structural dependency of performance. Thus, the proper choice of similarity is also an important issue for superior performance. For this reason, the structural dependency of a similarity index has been investigated to solve this problem. Many related conjectures are suggested, such as the existence of a specific structural property, a relationship between growth mechanisms, correlation with structural quantities, and the distinguishment of a similarity distribution for the original network. Nevertheless, these conjectures have not been strictly proved. In this thesis, the structural dependency of the link prediction process is investigated based on model study and mathematical description.

Network models have revealed the statistical relationships of link prediction performances for various similarity indices. The sparsity problem has generally been observed from the positive correlation between the mean degree and performances. It has been observed from the results of the model why the structural dependence of the similarity index is important. Even a simple index can show the best performance, and a complicated global index can show inferior performances in a specific situation.

The link prediction process is described via the mathematical description for two local indices: the common-neighbor (CN) index, defined as the number of common neighbors of a node pair, and the preferential-attachment (PA) index, defined as a product of degrees (the number of connections). The accuracy of link prediction was formulated through the similarity distribution of missing links and the similarity distributions of nonexistent links. These two distributions can be calculated from the transition probabilities of the similarity index and the distributions from the original network structure. This description can be verified from the scatter plot between link prediction performance and distinguishment performance, where correlation refers to the dependency of the similarity distribution of the original network and fluctuation comes from the characteristics of the similarity index. The CN index shows a clear correlation, which is related to the simple response of the transition probability. In contrast, the PA index shows a larger fluctuation, which is related to the discrepancy of between the transition probabilities for an adjacent and a nonadjacent case and the dependence on the degree.

The structural dependency of the similarity distribution of the original network structure was discussed. From this study, the “target structure” of indices was clarified, and which properties yield better performances was investigated. The distributions of the PA index are determined from the degree distribution and degree correlation. To calculate the distribution of the CN index, maximal clique decomposition, which decomposes a given network as a clique structure, was employed. The distributions of the CN index can be calculated from the decomposed structure, described by four distributions: the distributions for the size of cliques, number of included cliques, number of overlapped nodes between cliques, and number of common cliques. These equations are difficult to understand because of their complicated form. Thus, the dominant factor was investigated from model studies. It was observed that the degree correlation is the dominant factor for the PA index, and a larger clique with less overlap is important for the CN index.

These approaches help clarify many conjectures with quantitative description. This framework is expected to expand various indices with diverse situations, and it is expected to contribute to a deeper understanding of link prediction and improvement of performance in practical usage.

목차 (Table of Contents)

• I. Introduction
• II. Literature Review
• 2.1 Complex network analysis
• 2.2 Effect of Missing Links
• 2.3 Link Prediction
• 2.4 Relationship between Link Prediction Performance and Structural Property of Networks
• III. Methodology
• 3.1 Complex Network Analysis
• 3.1.1 Representative structural parameters
• 3.2 Similarity Index
• 3.2.1 1-level Index
• 3.2.2 2-level Index
• 3.2.3 3-level Index
• 3.2.4 Global Index
• 3.2.5 Quasi-local index
• 3.2.6 Probabilitic Methods
• 3.3 Overall Procedure of Link prediction
• 3.3.1 Missing Link Creation
• 3.3.2 Similarity Calculation
• 3.3.3 Missing link prediction
• 3.3.4 Performance Evaluation
• IV. Link Prediction on Network Models
• 4.1 Overview
• 4.2 Link prediction on network models
• 4.2.1 Dataset
• 4.2.2 Results
• 4.3 Link prediction on two-state random network
• 4.3.1 Dataset
• 4.3.2 Correlation between discrimination performance and structural parameters
• 4.3.3 Correlation between discrimination performance and link prediction performance
• 4.4 Discussion
• V. Mathematical Description of Link Prediction
• 5.1 Overview
• 5.2 Similarity Distribution and Transition Probability
• 5.3 Performance calculation from similarity distribution
• 5.3.1 Correlation Between Link Prediction Performance and Original Network Structure
• 5.3.2 Structural Dependency of Similarity Distribution for Original Network
• 5.4 Dataset
• 5.5 Results
• 5.5.1 Verification of Transition Probability
• 5.5.2 Correlation Between Link Prediction Performance and Original Network Structure
• 5.5.3 Validation for the Similarity Distribution of Original Network
• 5.6 Discussion and Summary
• VI. Structural Dependency of Link Prediction
• 6.1 Structural Dependency for the PA index
• 6.2 Structural Dependency for the CN index
• 6.3 Revise of the link prediction on network model
• 6.4 Discussion and Summary
• VII. Summary
• Summary (in Korean)
• References