Efficient Community Search on Large Directed Graphs

Directed graphs are widely adopted to model various entities and their relationships in nature and human society, such as social networks, biological networks, transportation networks, finance networks, citation networks, email networks, and so on. The edges in a directed graph represent the semantic relations between nodes, such as Twitter followers, money transfer diffusions, and communication links. Enabling personalized network discovery, community search has been considered as an important tool in network analysis, aiming to find densely connected subgraphs containing query vertices. While community search has been extensively studied for undirected graphs, directed graphs have only recently received attention. However, existing studies suffer from several drawbacks, e.g., the vertices with varied in-degrees and out-degrees cannot be included in a community at the same time.

To address these limitations, in this project, we systematically investigate a family of new problems regarding community search over large directed graphs. Conventional community discovery techniques cannot handle these new problems, because they either apply undirected community models (e.g., k- core, k-truss, and k-plex) by neglecting edge directions, or only find global answers without considering personalized query inputs. To tackle these drawbacks, we propose novel community models and techniques for efficient community search algorithms over large-scale directed graphs. Specifically, we plan to design 1) a D-truss-based community model with which to capture the densely-connected community structure in directed graphs; 2) an extendable algorithmic framework to process D-truss community search problems for different applications, including attributed community search and interactive community search; 3) novel index structures to support the efficient search of D-truss communities over large graphs; 4) user-friendly techniques for interactive graph exploration and community search. With our extensive research experience in graph query processing and community discovery, we expect the outcomes of this project to lead to a set of new tools for social network analysis and discovery, thereby improving the graph analytics and recommendation services in the industry.