In ordinary life, networks are frequently found. Social network services (SNSs) such as Twitter or Facebook, co-authorship networks in scientific areas, or protein interaction networks are typical examples. As interests in network science have continuously grown since the early 1990’s, studying and analyzing such network relation-ships have become common tasks these days. Furthermore, most networks dynamically grow or change over time. Thus, understanding the expansion or changing mechanism of networks gives us wide opportunities to predict missing connections among nodes, for instance, suggesting new friends in SNSs, reducing the size of interacting protein candidates in protein interaction networks, or preventing crimes or terrors via analyzing al-ready-known crime networks. To do these tasks, it should be possible to predict undiscovered edges among nodes based on the current snapshot of the network; this is usually called “the link prediction problem.” However, common neighbor-based algorithms, which have shown the best performance so far, lack in-depth knowledge of the network, so they usually lack accuracy. Moreover, it has been impossible to detect single or multiple nodes, which play the most important role in a specific link between any two nodes.
In this paper, we propose a more sophisticated and comprehensive computational model for link prediction. The key idea of our method is that the connectivity of any two nodes is determined by the probability for the two nodes to form a group with their neighbors. To measure the membership degree of the neighbors, neighbors who were not shared by the two nodes as well as the shared neighbors, were considered. For each neighbor combination, we quantified its contribution to the link by inspecting the mutual dependency and appearance frequency of the neighbor combination. The link connectivity could be computed by integrating all the contributions, and the most influential neighbor combination could be detected by comparing the contribution degrees. For convenience, we regarded the link prediction problem as an object-object matching prediction by considering the neighbors of a node as features of a specific object. We devised a hybrid approach, which integrates the intra-object feature cohesion and the inter-object feature combination pair’s coupling power while other object matching prediction algorithms only focused on the inter-object features pair’s appearance frequency from the existing object pairs. In this paper, several formulas newly devised for the object matching prediction were also introduced with explanation of the network.
For validation of the framework, we developed both protein-protein interaction prediction and primary inte-racting feature combination pair prediction methods. In addition, the prediction model evaluated the various networks such as the scientific co-authorship network, communication network, and product co-purchasing network through comparison with existing link prediction methods. According to the evaluation, the framework was effective in developing a protein-protein interaction prediction method, which showed comparable or supe-rior prediction accuracy to the conventional protein-protein interaction prediction methods. In evaluating the scientific co-authorship network, our method showed the best performance among the existing link prediction methods. A web-based protein interaction prediction application using our new prediction framework was also demonstrated.
The contributions of this paper are threefold: (1) we propose a new link prediction method which considers neighbors’ interrelationships for the first time, (2) we propose a link prediction method which can quantify neighbors’ contribution of a specific link, and (3) we provide a prediction method which is applicable to general object matching problems
최근 네트워크 과학의 발전에 따라 우리 일상 생활 주변에 있는 네트워크에 대한 연구가 주목 받고 있다. 단백질 상호작용 네트워크 분석 및 새로운 상호작용 단백질 예측, SNS의 친구 추천, 쇼핑몰의 상품 추천, 회사 사내 조직 네트워크의 분석 등은 이제 일반적인 일이 되었으며 그 중요성은 점차 강조되고 있다. 네트워크 분석 연구 중에서도 특히 기존의 네트워크 구성 패턴을 분석 및 학습하여 연결 가능성이 높은 새로운 링크를 찾아내는 이른바 네트워크 링크 예측(network link prediction)은 대부분의 네트워크 분석 연구에 필수적인 작업이다. 그 동안 링크 예측에는 주로 이웃 기반의 방법과 경로 기반의 방법들이 사용되었다. 이웃 기반의 방법은 주로 공통 이웃 혹은 예측 대상 노드의 위상 정보를 이용한 반면, 경로 기반의 방법은 대상 노드 사이의 연결 가능한 경로의 개수 혹은 거리를 이용한다. 그러나 기존의 방법들은 당초 네트워크 연결 예측을 위하여 고안되지 않은 것이 대부분이며, 전반적인 예측 정확도 역시 실제로 활용되기에는 부족한 것이 사실이다. 또한 특정 링크의 예측 시 그 링크에 가장 큰 영향을 준 이웃을 알아내는 것과 같은 고도화된 정보 제공은 불가능하다.
본 논문에서는 링크 예측을 객체-객체 결합 문제로 변환한 모델을 제안한다. 이를 위해 네트워크의 노드는 이웃 노드들을 특성으로 가지는 객체로 간주하였다. 예측 모델에서는 객체 내에 존재하는 특성들 사이의 응집력과 객체 쌍 사이에 생성될 수 있는 특성 조합 쌍이 기존에 이미 발견된 객체 쌍 사이에서 나타나는 결합력을 계산한다. 이러한 응집력과 결합력 기반의 계산은 네트워크 상에서 연결을 예측하고자 하는 두 노드의 이웃들이 특정 그룹을 이룰 확률을 정량화 할 수 있게 한다. 특히 예측하려는 두 노드의 모든 이웃 쌍에 대하여 이웃의 이웃 정보를 추가적으로 활용하는 것은 본 논문만의 독창적인 방법으로 이웃들 사이에서 그룹이 존재 할 확률을 좀더 정교하게 계산하는 것이 가능하다. 또한, 예측 모델에서는 네트워크 상에서 위상 정보를 분석하여 적절한 최적화를 수행하는 방법 역시 제시하였다.
제안한 방법은 단백질 상호작용 네트워크에서 링크 연결에 가장 큰 영향을 미치는 도메인 조합에 대한 예측을 3차원 구조가 알려진 도메인들에 대하여 검증하였고, 기존의 링크 예측 방법들과의 비교는 학술 논문 공저자 네트워크, 사내 전자우편 교환 네트워크, Amazon의 동시 구매 상품 네트워크에서 수행하였다. 그 결과 제안하는 방법은 대부분의 네트워크에서 개선된 정확도를 보였으며, 특히 단백질 상호작용 네트워크에서는 상호작용하는 단백질 사이에서 실제로 기여한 도메인을 높은 수준의 정확도로 찾아냄을 보였다.
본 논문의 주요 기여 점은 다음과 같다. 1) 정교한 링크 예측 모델 고안, 2) 링크 예측에 있어 각 이웃들의 공헌도를 정량화 할 수 있는 모델 고안, 3) 이웃의 이웃 정보를 활용하는 최초의 링크 예측 모델 고안, 4) 일반적인 객체-객체 매칭 예측에 활용될 수 있는 모델 고안
