A community structure in a graph is defined as a set of nodes where nodes in the same community are densely connected by edges. In this dissertation, we present two methods of discovering community structures: 1) community detection that finds all community structures in a graph, and 2) community search that finds some community structures having particular properties. In recent years, the size of graph data has increased significantly. Most existing community detection algorithms do not consider the case where the size of main memory is not sufficient to handle large amount of graph data, and they incur excessive disk I/O and thrashing. In the first part, we propose an I/O-efficient community detection method for large-scale graph data. An input graph is partitioned into several subgraphs smaller than memory, local community structures are detected for each subgraph. And then the local communities from the subgraphs are merged so that global results can be obtained in the point of view of an original graph. We also propose a cluster maintenance method for large-scale dynamic graphs that change over time. The proposed method produces scalable performance even for very large graphs. In the second part of the dissertation, we propose an efficient method of searching influential communities that contain highly influential members. Although there are many metrics that describe influences of objects, the existing methods search for influential communities in terms of only one influence type without comprehensively considering other influence types. The influences are modeled as multidimensional vectors, where each dimension in the vectors explains each influence type. For properly ranking communities, we utilize the concept of the top-$\gamma$ dominating query for multi-dimensional point data. Extensive experiments show that our proposed method effectively finds influential communities based on multiple influence types, and is orders-of-magnitude faster than the baseline solution.
그래프의 커뮤니티 구조는 에지를 통해 밀도 높게 연결된 노드들의 집합으로 정의된다. 커뮤니티 검출은 그래프에서 모든 커뮤니티 구조를 찾는 기법이다. 기존 방법들은 메모리의 크기가 그래프 데이터를 처리하기에 충분히 크지 않을 경우를 고려하지 않으며, 메모리에 로드 되지 않은 데이터를 사용할 때 임의 디스크 접근이 일어나 큰 디스크 입출력 비용이 발생한다. 이 문제를 해결하기 위해, 디스크 입출력 비용 측면에서 효율적인 알고리즘을 제안한다. 그래프의 노드/에지 추가 및 삭제로 그래프가 변경되었을 때, 새로운 커뮤니티 정보를 효율적으로 업데이트하는 기법에 대해서도 다룬다. 제안 기법은 사용 가능한 메모리의 크기가 주어진 데이터 크기에 비해 월등히 적은 경우에도 매우 효율적이다. 커뮤니티 검색은 특정 조건을 만족하는 몇몇의 커뮤니티 구조를 찾는 방법이다. 영향 커뮤니티 모델은 영향력이 높은 노드들로 구성되어 있는 커뮤니티들을 찾는 기법이며, 기존 기법들은 하나의 영향력 지수만을 이용한다. 여러 종류의 영향력 지수를 종합적으로 고려하여 커뮤니티를 검색하는 방법을 제안한다. 커뮤니티 구조의 영향력 정도를 다차원 벡터로 표현하며, 다차원 포인트 데이터 간 지배 관계 개념을 활용하여 커뮤니티 구조들을 랭킹 후 효과적으로 영향력 높은 커뮤니티를 검색한다.
