Cohesive Subgraph Computation Over Large Sparse Graphs
Lijun Chang, Lu Qin · 2019
With the rapid development of information technology, huge volumes of graph data are accumulated. Real graphs are usually sparsely connected from a global point of view, but typically contain subgraphs that are locally densely connected. It is of great importance to identify dense (i.e., cohesive) subgraphs in a large sparse graph. Cohesive subgraph computation can either be the main goal of a graph analysis task, or act as a preprocessing step aiming to reduce/trim the graph by removing sparse/unimportant parts such that more complex and time-consuming analysis can be conducted. In the literature, the cohesiveness of a subgraph is usually measured by the minimum degree, the average degree, or their higher-order variants. Cohesive subgraph computation based on different cohesiveness measures extracts subgraphs with different properties, and also requires different levels of computational efforts. In this tutorial, we survey the models and state-of-the-art algorithms for efficient cohesive subgraph computation based on different cohesiveness measures. We discuss details of the algorithms, including time complexity and implementation matters. Finally, we present open problems for future research.