Community detection, also known as graph clustering, has been extensively studied in the literature. The goal of community detection is to partition vertices in a graph into densely-connected components so-called communities. In recent applications, however, an entity is associated with multiple aspects of relationships and multiple attributes from multiple data sources, which brings new challenges in community detection. These multimodal data sources can be naturally modeled as a multi-layer graph composed of multiple interdependent layers and mapping functions, where each layer represents an intra-relationship and each mapping function represents inter-relationship between two layers. Great efforts have therefore been made to tackle the problem of community detection in multi-layer graphs.
In this dissertation, we propose novel frameworks for community detection from multiple data sources based on the multi-layer graph model. Among various combinations of multiple data sources, we deal with two representative cases: (i) multiple aspects of relationships and (ii) multiple attributes. The first case deals with multiple social graphs which consist of a set of users involved with different types of relationships. The second case deals with attributed graphs which consists of a set of users involved with social relationships as well as associated with multiple attributes. Particulary, we focus on a geosocial graph which has attracted much attention thanks to the widespread use of location-aware mobile devices. Since locations accessed by users can be regarded as various geographic preferences or interests of users, a geosocial graph is a representative case of attributed graphs.
In the first part of this dissertation, we propose a novel framework for differential flattening, which facilitates the analysis of pillar multi-layer graphs, and apply this framework to community detection. Differential flattening merges multiple graphs into a single graph such that the graph structure with the maximum clustering coefficient is obtained from the single graph. It has two distinct features compared with the existing approaches. First, dealing with multiple layers is done independently of a specific community detection algorithm whereas previous approaches rely on a specific algorithm. Thus, any algorithm for a single graph becomes applicable to multi-layer graphs. Second, the contribution of each layer to the single graph is determined automatically for the maximum clustering coefficient. Since differential flattening is formulated as an optimization problem, the optimal solution is easily obtained by well-known algorithms such as interior point methods. Extensive experiments were conducted using the LFR benchmark networks as well as the DBLP, 20 Newsgroups, and MIT Reality Mining networks. The results show that our approach of differential flattening leads to discovery of higher-quality communities than baseline approaches and the state-of-the-art algorithms.
In the second part of this dissertation, we propose a novel framework for geosocial co-clustering, which facilitates the analysis of attributed graphs with a focus on a geosocial graph. Geosocial co-clustering is formulated by non-negative matrix tri-factorization with dual regularizers. The existing matrix tri-factorization algorithms, however, suffer from a significant computational overhead when handling large-scale data sets in many real world applications. Our proposed framework takes advantage of the intrinsic properties of geosocial networks to reduce the computational overhead without compromising accuracy. First, the numbers of users and locations are effectively reduced through coarsening of our framework. Then, we decompose the matrix tri-factorization of a single large matrix into a series of multiple smaller sub-matrix tri-factorizations. To this end, the optimal split of the entire matrix is determined by crossing minimization and optimization of the minimum description length. Experiments conducted using four real-world geosocial networks show that our framework for geosocial co-clustering reduces the elapsed time by 19 to 69 times while achieving the accuracy of up to 95.2% compared with the state-of-the-art co-clustering algorithm.
The strength of this dissertation lies in a wide variety of community detection from multiple heterogeneous data sources. Since the two cases proposed are expected to cover a significant proportion of the cases with multiple data sources, we believe that this work will enhance the quality of community detection in social networks from multiple data sources.
커뮤니티 발견(혹은 그래프 클러스터링)은 데이터 마이닝 분야에서 널리 연구되어 왔으며 이는 그래프 상에서 밀접하게 연결된 노드들의 집합을 찾는데 그 목적이 있다. 하지만 최근 응용에서 객체 들은 다양한 이종의 데이터 소스로부터 생성되는 복수 개의 관계들과 속성들로 연결되어 있기 때문에, 커뮤니티 발견 연구는 새로운 문제에 직면하게 되었다. 이러한 다양한 데이터 소스는 다층 그래프로 모델링이 가능하다. 다층 그래프는 복수 개의 그래프 층과 복수 개의 사상 함수로 정의 되는데, 여기서 각 그래프 층은 객체 간의 관계를 나타내며 각 사상 함수는 그래프 층 간의 관계를 나타낸다. 따라서, 다층 그래프에서의 커뮤니티 발견 문제를 해결하고자 하는 많은 연구들이 수행되어 왔다.
본 학위 논문에서는 다양한 데이터 소스로부터 커뮤니티를 발견하는 문제를 다층 그래프 모델에 기반하여 해결한다. 다양한 데이터 소스의 조합 가운데 두 가지 대표적인 경우인 복수 개의 관계 정보가 존재 할 때, 그리고 복수 개의 속성 정보가 존재 할 때로 나누어 문제를 정의하고 이를 해결한다. 즉, 첫 번째 문제에서는 다양한 관계로 형성된 복수 개의 소셜 그래프를 다루며, 두 번째 문제에서는 소셜 그래프 상에 복수 개의 속성 정보가 포함된 속성 그래프를 다룬다. 특히, 두 번째 문제에서는 속성 그래프의 대표적인 경우인 지리적 소셜 그래프에 집중한다. 지리적 소셜 그래프에서 사용자들이 방문한 다양한 장소들은 사용자들의 지리적 선호도나 관심 분야를 나타내기 때문에 이들은 다양한 속성 정보로 간주 될 수 있으며, 이는 최근 위치 인지 모바일 디바이스의 범용성 확대와 함께 연구의 필요성과 관심이 급증하고 있는 데이터 형태이다.
첫 번째 문제에서, 다층 그래프 분석을 통한 차등 평탄화 방법을 제안하고, 이를 커뮤니티 발견 문제에 적용한다. 차등 평탄화는 복수 개의 그래프를 클러스터링 계수가 최대가 되게 하는 하나의 그래프로 통합하는 방법으로 커뮤니티 발견 알고리즘과 독립적으로 복수 개의 그래프를 다루기 때문에 어떤 커뮤니티 발견 알고리즘도 차등 평탄화 기법과 함께 적용이 가능하며, 각 그래프의 중요도를 알고리즘 상에서 자동적으로 결정한다. 이를 위해 차등 평탄화 문제를 최적화 문제로 변환시키고, 최적화 문제에서 널리 사용되는 내점 방법을 통해 문제를 해결한다. 제안하는 차등 평탄화 방법을 통한 커뮤니티 발견 방법이 다층 그래프를 대상으로하는 최신 기술 커뮤니티 발견 알고리즘보다 우수하다는 것을 인조 데이터 셋과 세 가지 실제 데이터 셋을 통해 증명하였다.
두 번째 문제에서, 속성 그래프 분석에 기반하여 지리적 소셜 그래프에 대한 이중 클러스터링 방법을 제안한다. 지리적 소셜 그래프에 대한 이중 클러스터링 문제는 음수 미포함 행렬 3중 분해 문제로 변환이 가능하다. 하지만, 기존에 존재하는 음수 미포함 행렬 3중 분해 알고리즘은 복잡도와 계산 비용이 너무 크기 때문에 대용량의 실제 데이터 셋에 적용이 힘들다. 그에 반해 제안하는 이중 클러스터링 방법은 지리적 소셜 그래프 고유의 특징을 활용하여 계산상 오버헤드를 줄이고 정확도는 유지한다. 이를 위해 먼저 그래프 압축을 통해 사용자와 장소들의 수를 줄여준다. 그 다음 교차 최소화 방법과 최소 설명 길이 최적화 방법을 통해 하나의 큰 행렬 분해 문제를 여러 개의 작은 행렬 분해 문제로 분해한다. 제안하는 이중 클러스터링 방법이 지리적 소셜 그래프를 대상으로하는 최신 기술 커뮤니티 발견 알고리즘보다 우수하다는 것을 네 가지의 실제 데이터 셋을 통해 증명하였다.
본 학위 논문의 우수성은 다양한 이종의 데이터 소스로부터의 커뮤니티 발견 문제를 해결했다는 것에 있다.
본 학위 논문에서 다루는 두 가지 경우는 다양한 데이터 소스로부터 생성 될 수 있는 경우 들의 많은 부분을 포함할 것으로 기대되기 때문에 본 학위 논문의 의미와 공헌이 더욱 크다고 생각한다.
