Mining Method Seasonal-bursting Subgraphs in Temporal Graphs

被引：0
作者：
Zhang, Qian-Zhen [1 ]
Guo, De-Ke [1 ]
Zhao, Xiang [1 ]
机构：
[1] College of Systems Engineering, National University of Defense Technology, Changsha
来源：
Ruan Jian Xue Bao/Journal of Software | 2024年 / 35卷 / 12期
关键词：
dense subgraph; seasonal burstiness; subgraph mining; temporal graph; time span;
D O I：
10.13328/j.cnki.jos.007064
中图分类号：
学科分类号：
摘要：
Temporal graph is a type of graph where each edge is associated with a timestamp. Seasonal-bursting subgraph is a dense subgraph characterized by burstiness over multiple time periods, which can applied for activity discovery and group relationship analysis in social networks. Unfortunately, most previous studies for subgraph mining in temporal networks ignore the seasonal or bursting features of subgraphs. To this end, this study proposes a maximal (ω,θ)-dense subgraph model to represent a seasonal-bursting subgraph in temporal networks. Specially, the maximal (ω,θ)-dense subgraph is a subgraph that accumulates its density at the fastest speed during at least ω particular periods of length no less than θ on the temporal graph. To compute all seasonal bursting subgraphs efficiently, the study first models the mining problem as a mixed integer programming problem, which consists of finding the densest subgraph and the maximum burstiness segment. Then corresponding solutions are given for each subproblem, respectively. The study further conceives two optimization strategies by exploiting key-core and dynamic programming algorithms to boost performance. The results of experiments show that the proposed model is indeed able to identify many seasonal-bursting subgraphs. The efficiency, scalability, and effectiveness of the proposed algorithms are also verified on five real-life datasets. © 2024 Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：5526 / 5543
页数：17
相关论文
共 31 条
  • [1] Broder A, Kumar R, Maghoul F, Raghavan P, Rajagopalan S, Stata R, Tomkins A, Wiener J., Graph structure in the Web, Computer Networks, 33, 1–6, pp. 309-320, (2000)
  • [2] Boyd DM, Ellison NB., Social network sites: Definition, history, and scholarship, Journal of Computer-mediated Communication, 13, 1, pp. 210-230, (2007)
  • [3] Rual JF, Venkatesan K, Hao T, Et al., Towards a proteome-scale map of the human protein-protein interaction network, Nature, 437, 7062, pp. 1173-1178, (2005)
  • [4] Tsourakakis C, Bonchi F, Gionis A, Gullo F, Tsiarli M., Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees, Proc. of the 19th ACM Int’l Conf. on Knowledge Discovery and Data Mining, pp. 104-112, (2013)
  • [5] Cheng J, Ke YP, Chu SM, Ozsu MT., Efficient core decomposition in massive networks, Proc. of the 27th IEEE Int’l Conf. on Data Engineering, pp. 51-62, (2011)
  • [6] Uno T., An efficient algorithm for solving pseudo clique enumeration problem, Algorithmica, 56, 1, pp. 3-16, (2010)
  • [7] Tsourakakis C., The K-clique densest subgraph problem, Proc. of the 24th Int’l Conf. on World Wide Web, pp. 1122-1132, (2015)
  • [8] Mitzenmacher M, Pachocki J, Peng R, Tsourakakis C, Xu SC., Scalable large near-clique detection in large-scale networks via sampling, Proc. of the 21th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, pp. 815-824, (2015)
  • [9] Vanhems P, Barrat A, Cattuto C, Pinton JF, Khanafer N, Regis C, Kim BA, Comte B, Voirin N., Estimating potential infection transmission routes in hospital wards using wearable proximity sensors, PLoS One, 8, 9, (2013)
  • [10] Fournet J, Barrat A., Contact patterns among high school students, PLoS One, 9, 9, (2014)
1234