Social services such as Facebook, Twitter, and YouTube establish networks by connecting individuals to one another and linking individuals to various services. These services aim to enhance user experiences by uncovering hidden information in the data and providing users with recommendations for new connections. The primary problems in finding hidden information are community detection and graph matching. Community detection involves dividing nodes into suitable groups by using the fact that connections between nodes within the same community are denser than connections between nodes in different communities. Graph matching, on the other hand, focuses on finding similarities by comparing the statistical properties of nodes in each anonymized graph that are correlated. While numerous algorithms have been proposed in both fields, their performance cannot be sufficiently validated through experimentation alone. Results may vary in different experimental datasets, and it can be challenging to explain the success and failure of algorithms. Therefore, theoretical analysis of these algorithms is important. The objective of the thesis is to conduct a theoretical analysis of community detection and graph matching. The structure of the thesis can be divided into two sections. In Section 2, we will propose and analyze a graph matching algorithm that leverages community information, particularly in the Stochastic Block Model (SBM), a probabilistic graph model with a community structure. We will compare the proposed algorithm with other existing ones through both theoretical and experimental assessments. Moving on to Section 3, our analysis will focus on graph matching for community detection. We aim to determine the conditions required for the exact recovery of graph matching between two graphs generated from the correlated Contextual Stochastic Block Model (CSBM). Furthermore, we will investigate the advantages of community detection when correlated data is combined through graph matching under the conditions.
Facebook, Twitter, Youtube 등과 같은 소셜 서비스들에서 각 서비스들은 사람과 사람, 사람과 서비스를 연결하여 네트워크를 발생시킨다. 각 서비스들은 이 네트워크 데이터에서 숨겨진 정보를 찾아내서 사용자에게 양질의 서비스를 제공한다. 여기서 숨겨진 정보를 찾는 문제로 가장 대표적인 것은 커뮤니티 디텍션과 그래프 매칭이다. 커뮤니티 디텍션은 같은 커뮤니티 노드들 간의 연결이 다른 커뮤니티 간 연결보다 더 밀집하다는 것을 이용해 노드들을 적합한 그룹으로 나누는 문제이다. 그리고 그래프 매칭은 익명화된 두 그래프가 서로 유사성이 있을 때, 각 그래프 노드들 간 통계적 특성을 비교하여 유사도를 찾아 노드 간 상관 관계를 찾는 것이다. 두 분야에서 많은 알고리즘들이 제안되었지만, 그 성능은 실험만으로 증명하기엔 충분하지 않다. 다른 실험 데이터에서는 안 될 수 있고, 왜 잘 되는지, 어떤 경우에 안되는지 설명하기 힘들기 때문이다. 그래서 알고리즘의 이론적 분석은 매우 중요하다. 이번 졸업 논문의 목표는 네트워크 과학의 대표적인 알고리즘 분야인 커뮤니티 디텍션과 그래프 매칭을 이론적으로 분석하는 것이다. 졸업 논문의 구성은 크게 두가지로 나뉘어 Section 2에서는 커뮤니티를 이용한 그래프 매칭 알고리즘을 제안하고 분석할 것이다. SBM이라는 커뮤니티 구조를 가진 확률적 그래프 모델에서 커뮤니티 정보를 활용한 효율적인 알고리즘을 제안하여 다른 알고리즘들과의 이론적 실험적 비교를 진행할
것이다. 그리고 Section 3에서는 커뮤니티 디텍션을 위한 그래프 매칭을 분석할 것이다. Contextual SBM에서 생성된 두 그래프가 유사도가 있을 때, 정확한 그래프 매칭을 하기 위한 조건을 찾고, 그 조건에서 그래프 매칭을 통해 유사성 있는 두 데이터가 합쳐졌을 때 커뮤니티 디텍션에서 어떤 이점이 생겼는지 분석을 진행할 것이다.
