Efficient Community Search over Massive Multi-layer Networks

Graphs are widely used to depict various entities and their complex relationships in society and nature, such as social networks, chemical compounds, road networks, and so on. However, a singlelayer graph represents nodes and edges that belong to the same type, which is not accurate enough to model complex relations in real-life networks. To capture multiple modes of entities’ interactions, we study a different graph model of multi-layer networks, which exist widely in biomedical data of brain networks, financial networks, opinion dynamics, and geo-social networks. As an important graph analytics task, community search allows finding personalized communities, which has a wide range of applications in team formation, event organization, graph visualization, and recommendations. Although community search has been widely studied for single-layer graphs, the problem of community search over multi-layer graphs attracts limited attention. Existing community models in multi-layer graphs either take the same vertex set at different layers or consider a fixed number of cross-layers, which neglect their cross-layer interactions and fail to capture communities with the richest cross-layers. Another line of community search on heterogeneous information networks heavily relies on an input of meta-path patterns, which is hard to formulate.

To tackle these limitations, in this project, we intend to comprehensively investigate novel problems of community search over multi-layered networks, which aim at developing novel community models, efficient algorithms to handle large multi-layer graphs with massive nodes/edges and high layers, and also practical applications. Specifically, we plan to study the following tasks: 1) Multi-layer graph decomposition and indexing by extending a useful core subgraph to multilayer graphs and producing dense cross-layer subgraphs for visualization and efficient retrieval; 2) Multi-layer community search to find query-based communities by allowing path-connected and fully-connected connectivity; 3) Attributed multi-layer community search to support the vertices associated with attributes by finding high-quality communities with homogeneous attributes; and 4) Evaluation of proposed techniques on real-world datasets for further prototype system development. With our extensive research experience in the field of graph query processing and analytics, the outcomes of this project are expected to lead to new models and tools for community search over multi-layer networks, thereby benefiting the graph analytics industry.