TY - JOUR
T1 - Mining Diversified Top-r r Lasting Cohesive Subgraphs on Temporal Networks
AU - Lin, Longlong
AU - Yuan, Pingpeng
AU - Li, Rong Hua
AU - Jin, Hai
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2022/12/1
Y1 - 2022/12/1
N2 - 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 (κ,σ)-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 R maximal lasting (κ,σ)-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 GreLC with (1-1/e) approximation ratio. However, GreLC has prohibitively high time and space complexity, resulting in poor scalability. Then, an improved DFS-based search algorithm called TopLC 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.
AB - 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 (κ,σ)-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 R maximal lasting (κ,σ)-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 GreLC with (1-1/e) approximation ratio. However, GreLC has prohibitively high time and space complexity, resulting in poor scalability. Then, an improved DFS-based search algorithm called TopLC 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.
KW - Cohesive subgraphs
KW - diversified top-r search
KW - lasting pattern mining
KW - temporal networks
UR - http://www.scopus.com/inward/record.url?scp=85100866722&partnerID=8YFLogxK
U2 - 10.1109/TBDATA.2021.3058294
DO - 10.1109/TBDATA.2021.3058294
M3 - Article
AN - SCOPUS:85100866722
SN - 2332-7790
VL - 8
SP - 1537
EP - 1549
JO - IEEE Transactions on Big Data
JF - IEEE Transactions on Big Data
IS - 6
ER -