In recent decades social network analysis has become one of the most attractive issues in data mining. In particular, community detection in networks, also known as graph clustering, is a fundamental problem in social network analysis. This is the procedure of identifying the community structure, with many edges joining vertices in the same community and relatively few edges joining vertices of different communities. Many theories, models, and methods have been actively developed for this purpose. However, owing to a wide variety of network structures, there remain challenges to determining community structures from social networks. Among them, we focus on solving four important problems for community detection with different underlying structures. These are identifying the community structure of a graph when it consists of (i) overlapping community structure, (ii) highly mixed community structure, (iii) complex sub-structure, and (iv) highly mixed overlapping community structure.
In this dissertation, we address these interesting problems by developing transformation techniques for the networks. Our key motivation is that the transformation of a given network can provide us an improved structure to identify the community structure of an original network, as a kernel trick does for data mining and machine learning. We propose a transformation-based community detection algorithm for networks that converts an original graph to a transformed graph that reflects the structure of the original network and has a superior structure for each problem. We identify the community structure using the transformed graph and then the membership on the transformed graph is translated back to that of the original graph. Using these techniques, we solve the four problems in this dissertation.
For the first problem, we present a novel notion of the link-space transformation. This notion enables us to combine the advantages of both the original graph and the line graph, thereby conveniently achieving high-quality overlapping communities. Based on this notion, we develop two overlapping community detection algorithms: LinkSCAN and $LinkSCAN^{\ast}$ . The latter is an enhancement of the former for higher efficiency. We conduct extensive experiments using various synthetic and real-world networks. The results on the synthetic networks demonstrate that, in terms of the Normalized Mutual Information (NMI), the proposed algorithms outperform the existing algorithms, especially for networks with many highly overlapping nodes and those with various base structures (e.g., a wide range of average degrees or community densities). Furthermore, for real-world networks, the proposed algorithms demonstrate higher quality and coverage than existing algorithms.
For the second problem, we propose a new community detection algorithm that we call BlackHole. Motivated by the common nature between community detection and graph embedding, we explore the possibility of applying the techniques of graph embedding to community detection. The proposed new graph embedding model attempts to place the vertices of the same community at a single position, similar to how a black hole in space attracts everything nearby. Then, these positions are easily grouped by a conventional clustering algorithm. The lesson from graph embedding is that we should consider not only attractive forces and but also repulsive forces. We theoretically prove the superiority of the proposed algorithm to representative embedding-based algorithms and empirically verify our claims through extensive experiments. The proposed algorithm is proven to achieve extremely high performance regardless of the difficulty of community detection in terms of the mixing parameter, the clustering coefficient, and other factors. If the community structure is not easily detectable, the strength of the proposed algorithm becomes indeed prominent because other algorithms frequently fail to detect communities.
For the third problem, we propose a motif-based embedding method for graph clustering by modeling higher-order relationships among vertices in a graph. The proposed embedding method considers the degree-weighted repulsive forces and motif-based attractive forces to enhance the clustering tendency of points in the output space of graph embedding. We theoretically prove the relationship with graph clustering and verify the performance and applicability through extensive experiments. In particular, we verify the superiority of using triangle- and wedge- based embedding for identifying community structure corresponding to such substructures of interest.
For the fourth problem, we develop an algorithm to address the highly mixed overlapping community detection problem. The proposed algorithm LinkBlackHole is also a transformation-based community detection algorithm; however, its transformation consists of a sequence of two different transformations. By first applying the link-space transformation and then the BlackHole transformation, we can detect highly mixed communities of the link-space graph and highly mixed link communities equivalently. Therefore, a merger of the two transformations uncovers the highly mixed overlapping community structure. We also present a set of experimental results confirming that the algorithm outperforms the existing algorithms for such structures.
The strength of this dissertation is based on a wide variety of community detection problems from social networks. We believe that this work will enhance the quality of community discovery for social network analysis.
최근 소셜 네트워크 분석은 데이터 마이닝 분야의 중요한 문제 중 하나로 연구되고 있다. 특히, 커뮤니티 발견 또는 그래프 군집화 문제는 소셜 네트워크 분석의 핵심적인 문제 중 하나이다. 이는 네트워크의 커뮤니티 구조를 찾는 과정으로, 커뮤니티 내부에서의 연결이 밀집되어 있고 서로 다른 커뮤니티 간의 연결은 상대적으로 적은 경우를 찾는 것을 목표로 한다. 커뮤니티 발견을 위한 다양한 이론, 모형, 방법 등이 제시됐지만, 소셜 네트워크의 경우 구조의 다양성으로 인해 아직 도전적인 문제로 여겨지고 있다. 본 학위논문에서는 다양한 구조적 특성을 보이는 커뮤니티 구조를 발견하는 문제들을 다루었으며, 다음 네 가지 구조에 대해 초점을 맞췄다: (i) 중첩을 허용하는 커뮤니티 구조, (ii) 과하게 섞인 커뮤니티 구조, (iii) 복잡한 부분구조, (iv) 과하게 섞인 중첩을 허용하는 커뮤니티 구조.
본 학위논문에서는 변환 기법을 개발하여 문제에 접근했다. 데이터 마이닝 및 기계 학습 분야에서 많이 쓰이는 커널 기법에 착안하여, 주어진 문제를 다른 공간의 문제로 변환하여 더 목적에 적합하게 다룰 수 있는 방식을 취했다. 우리가 제안한 변환 기반 커뮤니티 발견 알고리즘은, 주어진 네트워크를 풀고자 하는 문제에 적합하도록 그래프의 성질을 반영하면서 다른 그래프로 변환하는 기법을 사용한다. 제안된 알고리즘은 변환된 그래프의 커뮤니티 구조를 찾고, 이를 기존 그래프의 커뮤니티 구조로 되돌리는 과정을 거친다. 이러한 기법을 통해 우리는 앞서 언급한 네 가지 커뮤니티 발견 문제를 해결하였다.
첫 번째 문제에서, 우리는 링크-공간 변환(link-space transformation)이란 개념을 제안하였다. 이는 기존 그래프와 라인 그래프의 장점을 함께 취할 수 있는 방식으로, 중첩을 허용하는 커뮤니티를 우수하게 찾아낼 수 있다. 이를 활용하여 우리는 중첩을 허용하는 커뮤니티 발견 알고리즘 두 개를 제안하였다: LinkSCAN, $LinkSCAN^{\ast}$ . 후자는 전자에서 효율성을 증대한 것이다. 제안한 알고리즘들의 평가를 위해 다양한 합성 네트워크 및 실세계 네트워크 구조에서 실험해보았다. 합성 네트워크의 경우, 특히 과하게 중첩되는 노드들이 많은 네트워크 및 다양한 기본 구조(예를 들면, 다양한 범위의 평균 연결수, 커뮤니티 내부 연결 밀도 등)를 나타내는 경우, 제안한 알고리즘들이 NMI라는 기준으로 평가한 정확도에 대해 기존 알고리즘들보다 앞섰다. 또한, 실세계 네트워크의 경우, 제안한 알고리즘들이 품질(quality) 및 포함 범위(coverage) 등의 기준에 대해 기존 알고리즘들에 앞선 것을 확인할 수 있었다.
두 번째 문제에서, 우리는 새로운 커뮤니티 발견 알고리즘인 BlackHole을 제안하였다. 커뮤니티 발견과 그래프 임베딩이라는 서로 다른 분야에서 나타내는 공통적인 특성에 착안하여, 그래프 임베딩에서 쓰이는 기법이 커뮤니티 발견에 적용될 가능성에 대해 탐구하였다. 새로 제안한 그래프 임베딩 모형은 동일 커뮤니티에 속하는 노드들을 한 점에 가까이 위치하도록 하는 방식으로 마치 우주에서 블랙홀이 주변의 것들을 끌어당기는 것과 유사한 현상을 나타내어 블랙홀 변환(BlackHole transformation)이라 이름을 붙였다. 이러한 임베딩 후엔 점들이 쉽게 군집화가 가능했다. 그래프 임베딩에서 사용되는 인력과 척력을 함께 분석하여 커뮤니티 발견에 유리한 임베딩을 가능케 하였다. 우리는 제안한 알고리즘의 우수성을 이론적으로 증명했고 다양한 실험을 통해서도 확인했다. 제안한 알고리즘은 커뮤니티 간 연결이 과하게 섞인 경우에도 매우 높은 성능을 보이는 등 다른 알고리즘들이 커뮤니티 발견에 실패하는 경우에 있어서도 잘 검출해낼 수 있다는 장점을 보였다.
세 번째 문제에서, 우리는 네트워크 내 노드 간의 고차원 연결 구조가 있는 경우를 다루는 커뮤니티 발견 문제에 사용될 수 있는 motif 기반 임베딩(motif-based embedding) 방법을 제안하였다. 제안한 임베딩 방법은 연결수 기반 척력과 motif 기반 인력을 함께 고려하여, 임베딩 결과 점들의 클러스터링 경향성(clustering tendency)을 높이는 방식을 취했다. 우리는 제안한 임베딩 방법의 커뮤니티 발견 문제의 연관성을 증명하고 성능 및 활용도에 대해 다양한 실험을 통해 입증하였다. 특히, 삼각형 및 경로 등의 부분구조를 motif로 하였을 때 소셜 네트워크, 이분 그래프(bipartite graph) 등 다양한 형태의 네트워크에서 커뮤니티 발견에 적용할 수 있고 성능이 우수함을 확인하였다. 알고리즘 활용에서 네트워크 내 부분구조에 대한 이해를 수반한 motif 설정은 중요한 부분 중 하나이다.
네 번째 문제에서, 우리는 과하게 섞인 중첩을 허용하는 커뮤니티 발견 알고리즘인 LinkBlackHole을 제안하였다. 이 알고리즘은 본 학위논문 전반에서 쓰인 변환 기반 커뮤니티 발견 방식을 따르며, 링크-공간 변환과 블랙홀 변환을 차례로 적용하는 2-단계 변환(two-step transformation) 방법을 사용하였다. 이러한 순차적 적용으로 인한 결과로 과하게 섞인 링크-공간 그래프의 커뮤니티를 발견할 수 있고, 이는 과하게 섞인 링크 커뮤니티와 같다. 따라서, 순차적 변환을 활용한 변환-기반 커뮤니티 검출은 과하게 섞인 중첩을 허용하는 커뮤니티를 찾아낼 수 있다. 마찬가지로 실험을 통해 과하게 섞인 정도가 심할 때 제안한 알고리즘이 다른 링크 기반 변환을 사용한 커뮤니티 발견 알고리즘들보다 정확도가 앞서는 것을 보였다.
본 학위논문은 소셜 네트워크를 위한 다양한 커뮤니티 발견 문제들을 해결했다는 것에 강점이 있다. 우리는 본 연구가 소셜 네트워크를 위한 커뮤니티 발견 연구 분야를 더 발전시켰다고 생각한다.
