Effective and efficient community search over large attributed graphs

Abstract

Communities, which are prevalent in attributed graphs such as social networks and knowledge bases, can be used in emerging applications such as product advertisement and setting up of social events. Given a graph G and a vertex q ∈ G, the community search query returns a subgraph of G that contains vertices related to q. In this thesis, we study community search over three common attributed graphs, where (1) vertices are associated with keywords; (2) vertices are augmented with location information; and (3) edges are directed. Our goal is to study effective and efficient algorithms for finding communities over these graphs.

For keyword-based attributed graphs, we investigate the keyword-based attributed community query (or KAC query), which returns a KAC for a query vertex. A KAC satisfies both structure cohesiveness (i.e., its vertices are tightly connected) and keyword cohesiveness (i.e., its vertices share common keywords). The KAC query enables a better understanding of how and why a community is formed (e.g., members of a KAC have a common interest in music, because they all have the same keyword ``music''). To enable efficient KAC search, we develop the CL-tree index and three fast algorithms. We evaluate our solutions on six large graphs. Our results show that KAC search is more effective and efficient than existing community retrieval approaches. Moreover, a KAC contains more precise and personalized information than those of existing methods.

For spatial-based attributed graphs, we aim to find the spatial-aware community (or SAC), whose vertices are close structurally and spatially, for a query vertex in an online manner. To enable efficient SAC search, we develop two exact and three approximation algorithms. We evaluate SAC search on both large real and synthetic datasets. The experimental results show that SACs achieve higher effectiveness than communities returned by existing community retrieval solutions. Moreover, our solutions are faster than the baseline approaches.

For directed graphs, we study the problem of finding a community, in which each vertex has some in-neighbors and out-neighbors. We call this problem community search on directed graph (or CSD problem). Given a directed graph, our goal is to find a dense subgraph of a query vertex, in which each vertex has both high in-degree and out-degree. To solve the CSD problem, we propose the concept of D-core number and develop index-based algorithms. The experimental results on real large graphs show that our solutions are able to find better communities than existing solutions. Moreover, our algorithms are efficient and scalable.

We further develop the C-Explorer system to assist users in extracting, visualizing, and analyzing KACs. C-Explorer provides online and interactive community retrieval facilities, allowing a user to view her interesting communities for a query vertex. Moreover, C-Explorer implements several state-of-the-art community retrieval algorithms, as well as functions for analyzing their effectiveness.