Mining Diversified Top-$r$r Lasting Cohesive Subgraphs on Temporal Networks

Longlong Lin, Pingpeng Yuan, Rong-Hua Li, Hai Jin

Abstract

Temporal subgraph mining is recently ubiquitous. Identifying diversified and lasting ingredients is a fundamental problem in analyzing temporal networks. In this paper, we investigate the problem of finding diversified lasting cohesive subgraphs from temporal networks. Specifically, we first introduce a new model, called maximal lasting <inline-formula><tex-math notation="LaTeX">$(k,\sigma)$</tex-math></inline-formula> -core, for characterizing lasting cohesive subgraphs on temporal networks so as to the nodes in the subgraph are connected densely and also the subgraph's structure remains unchanged for a period of time. To enhance the diversity of results, we then formulate a diversified lasting cohesive subgraphs problem, which finds <inline-formula><tex-math notation="LaTeX">$r$</tex-math></inline-formula> maximal lasting <inline-formula><tex-math notation="LaTeX">$(k,\sigma)$</tex-math></inline-formula> -cores with maximum coverage regarding the number of vertices and timestamps. Unfortunately, we show that the optimization problem is NP-hard. To tackle this issue, we first devise a greedy algorithm named <i>GreLC</i> with (1-1/e) approximation ratio. However, <i>GreLC</i> has prohibitively high time and space complexity, resulting in poor scalability. Then, an improved DFS-based search algorithm called <i>TopLC</i> with 1/4 approximation ratio is proposed to lower the computational cost. Finally, empirical studies on six real-world temporal networks demonstrate that the proposed solutions perform efficiently and accurately, and our model is better than temporal cohesive subgraphs detected by existing approaches.
BibTeX
@article{lin2022mining,
  author = {Longlong Lin and Pingpeng Yuan and Rong-Hua Li and Hai Jin},
  title = {{Mining Diversified Top-$r$r Lasting Cohesive Subgraphs on Temporal Networks}},
  journal = {IEEE Trans. Big Data},
  year = {2022},
  doi = {10.1109/tbdata.2021.3058294},
}

Loading related content...

Figure