We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 37 Issue 6
December  2022
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Supplements
Yuan Li, Jie Dai, Xiao-Lin Fan, Yu-Hai Zhao, Guo-Ren Wang. I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks[J]. Journal of Computer Science and Technology, 2022, 37(6): 1337-1355. DOI: 10.1007/s11390-022-2367-3
Citation: Yuan Li, Jie Dai, Xiao-Lin Fan, Yu-Hai Zhao, Guo-Ren Wang. I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks[J]. Journal of Computer Science and Technology, 2022, 37(6): 1337-1355. DOI: 10.1007/s11390-022-2367-3
shu

I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks

  • 1School of Information Science and Technology, North China University of Technology, Beijing 100144, China
    2School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China
    3School of Computer, Beijing Institute of Technology, Beijing 100081, China

Funds: This work was supported by the National Natural Science Foundation of China under Grant Nos. 61902004, 61772124, 61732003, and 61977001, the Project of Beijing Municipal Education Commission under Grant No. KM202010009009, Innovative Talents of Higher Education in Liaoning Province under Grant No. LR2020076, and the Basic Research Operating Funds for National Defense Major Incubation Projects under Grant No. N2116017.
More Information
  • Author Bio:

    Yu-Hai Zhao received his B.S., M.S., and Ph.D. degrees in computer science and technology from the North- eastern University, Shenyang, in 1999, 2004, and 2007, respectively. He is currently a professor with the School of Computer Science and Engineering, Northeastern University, Shenyang. He is a senior member of CCF. His current research interests include data management, data mining, and bioinformatics.

  • Corresponding author:

    Yu-Hai Zhao E-mail: zhaoyuhai@mail.neu.edu.cn

  • Received Date: March 29, 2022
  • Revised Date: October 23, 2022
  • Accepted Date: November 07, 2022
  • Published Date: December 08, 2022
    Abstract
  • Temporal networks are an effective way to encode temporal information into graph data losslessly. Finding the bursting cohesive subgraph (BCS), which accumulates its cohesiveness at the fastest rate, is an important problem in temporal networks. The BCS has a large number of applications, such as representing emergency events in social media, traffic congestion in road networks and epidemic outbreak in communities. Nevertheless, existing methods demand the BCS lasting for a time interval, which neglects the timeliness of the BCS. In this paper, we design an early bursting cohesive subgraph (EBCS) model based on the k-core to enable identifying the burstiness as soon as possible. To find the EBCS, we first construct a time weight graph (TWG) to measure the bursting level by integrating the topological and temporal information. Then, we propose a global search algorithm, called GS-EBCS, which can find the exact EBCS by iteratively removing nodes from the TWG. Further, we propose a local search algorithm, named LS-EBCS, to find the EBCS by first expanding from a seed node until obtaining a candidate k-core and then refining the k-core to the result subgraph in an optimal time complexity. Subsequently, considering the situation that the massive temporal networks cannot be completely put into the memory, we first design an I/O method to build the TWG and then develop I/O efficient global search and local search algorithms, namely I/O-GS and I/O-LS respectively, to find the EBCS under the semi-external model. Extensive experiments, conducted on four real temporal networks, demonstrate the efficiency and effectiveness of our proposed algorithms. For example, on the DBLP dataset, I/O-LS and LS-EBCS have comparable running time, while the maximum memory usage of I/O-LS is only 6.5 MB, which is much smaller than that of LS-EBCS taking 308.7 MB.
    • FullText(HTML)
    • References (33)
  • [1]
    Holme P, Saramäki J. Temporal networks. Physics Reports, 2012, 519(3): 97-125. DOI:  10.1016/j.physrep.2012.03.001.
    [2]
    Li R H, Su J, Qin L, Yu J X, Dai Q. Persistent community search in temporal networks. In Proc. the 34th IEEE International Conference on Data Engineering, Apr. 2018, pp.797-808. DOI:  10.1109/ICDE.2018.00077.
    [3]
    Semertzidis K, Pitoura E, Terzi E, Tsaparas P. Finding lasting dense subgraphs. Data Min. Knowl. Discov., 2019, 33(5): 1417-1445. DOI:  10.1007/s10618-018-0602-x.
    [4]
    Qin H, Li R H, Wang G, Huang X, Yuan Y, Yu J X. Mining stable communities in temporal networks by density-based clustering. IEEE Trans. Big Data, 2022, 8(3): 671-684. DOI:  10.1109/TBDATA.2020.2974849.
    [5]
    Lin L, Yuan P, Li R, Jin H. Mining diversified top-r lasting cohesive subgraphs on temporal networks. IEEE Transactions on Big Data. DOI: 10.1109/TBDATA.2021.3058294.
    [6]
    Li Y, Liu J, Zhao H, Sun J, Zhao Y, Wang G. Efficient continual cohesive subgraph search in large temporal graphs. World Wide Web, 2021, 24(5): 1483-1509. DOI:  10.1007/s11280-021-00917-z.
    [7]
    Qin H, Li R H, Wang G, Qin L, Cheng Y, Yuan Y. Mining periodic cliques in temporal networks. In Proc. the 35th IEEE International Conference on Data Engineering, Apr. 2019, pp.1130-1141. DOI:  10.1109/ICDE.2019.00104.
    [8]
    Zhang Q, Guo D, Zhao X, Li X, Wang X. Seasonal-periodic subgraph mining in temporal networks. In Proc. the 29th ACM International Conference on Information and Knowledge Management, Oct. 2020, pp.2309-2312. DOI:  10.1145/3340531.3412091.
    [9]
    Qin H, Li R H, Wang G, Qin L, Yuan Y, Zhang Z. Mining bursting communities in temporal graphs. arXiv:19, 2019. https://arxiv.org/abs/1911.02780, Jul. 2022.
    [10]
    Chu L, Zhang Y, Yang Y, Wang L, Pei J. Online density bursting subgraph detection from temporal graphs. Proc. VLDB Endow., 2019, 12(13): 2353-2365. DOI:  10.14778/3358701.3358704.
    [11]
    Palen L, Hughes A L. Social media in disaster communication. In , Rodrı́guez H, Donner W, Trainor J E (eds.), Springer Cham, 2018, pp.497-518. DOI:  10.1007/978-3-319-63254-4.
    [12]
    Jain V, Sharma A, Subramanian L. Road traffic congestion in the developing world. In Proc. the 2nd ACM Symposium on Computing for Development, Mar. 2012, Article No. 11. DOI:  10.1145/2160601.2160616.
    [13]
    Cooper I, Mondal A, Antonopoulos G C. A SIR model assumption for the spread of COVID-19 in different communities. Chaos, Solitons & Fractals, 2020, 139: Article No. 110057. DOI:  10.1016/j.chaos.2020.110057.
    [14]
    Barbieri N, Bonchi F, Galimberti E, Gullo F. Efficient and effective community search. Data Min. Knowl. Discov., 2015, 29(5): 1406-1433. DOI:  10.1007/s10618-015-0422-1.
    [15]
    Cui W, Xiao Y, Wang H, Wang W. Local search of communities in large graphs. In Proc. the 2014 ACM SIGMOD International Conference on Management of Data, Jun. 2014, pp.991-1002. DOI:  10.1145/2588555.2612179.
    [16]
    Dai J, Li Y, Fan X, Sun J, Zhao Y. Finding early bursting cohesive subgraphs in large temporal networks. In Proc. the 2021 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Internet of People and Smart City Innovation, Oct. 2021, pp.264-271. DOI:  10.1109/SWC50871.2021.00044.
    [17]
    Li R H, Qin L, Yu J X, Mao R. Influential community search in large networks. Proc. VLDB Endow., 2015, 8(5): 509-520. DOI:  10.14778/2735479.2735484.
    [18]
    Li R, Qin L, Yu J X, Mao R. Finding influential communities in massive networks. VLDB J., 2017, 26(6): 751-776. DOI:  10.1007/s00778-017-0467-4.
    [19]
    Chen S, Wei R, Popova D, Thomo A. Efficient computation of importance based communities in web-scale networks using a single machine. In Proc. the 25th ACM International Conference on Information and Knowledge Management, Oct. 2016, pp.1553-1562. DOI:  10.1145/2983323.2983836.
    [20]
    Bi F, Chang L, Lin X, Zhang W. An optimal and progressive approach to online search of top-k influential communities. Proc. VLDB Endow., 2018, 11(9): 1056-1068. DOI: 10.14778/3213880.3213881.
    [21]
    Zheng Z, Ye F, Li R H, Ling G, Jin T. Finding weighted k-truss communities in large networks. Inf. Sci., 2017, 417: 344-360. DOI: 10.1016/j.ins.2017.07.012.
    [22]
    Sun L, Huang X, Li R, Choi B, Xu J. Index-based intimate-core community search in large weighted graphs. IEEE Trans. Knowl. Data Eng., 2022, 34(9): 4313-4327. DOI:  10.1109/TKDE.2020.3040762.
    [23]
    Lahiri M, Berger-Wolf T F. Mining periodic behavior in dynamic social networks. In Proc. the 8th IEEE International Conference on Data Mining, Dec. 2008, pp.373-382. DOI:  10.1109/ICDM.2008.104.
    [24]
    Qin H, Li R, Yuan Y, Wang G, Yang W, Qin L. Periodic communities mining in temporal networks: Concepts and algorithms. IEEE Trans. Knowl. Data Eng., 2022, 34(8): 3927-3945. DOI: DOI: 10.1109/TKDE.2020.3028025.
    [25]
    Maheshwari A, Zeh N. A survey of techniques for designing I/O-efficient algorithms. In Algorithms for Memory Hierarchies, Meyer U, Sanders P, Sibeyn J (eds.), Springer, 2003, pp.36-61. DOI:  10.1007/3-540-36574-5.
    [26]
    Cheng J, Ke Y, Chu S, Özsu M. Efficient core decomposition in massive networks. In Proc. the 27th IEEE International Conference on Data Engineering, Apr. 2011, pp.51-62. DOI:  10.1109/ICDE.2011.5767911.
    [27]
    Sun P, Wen Y, Duong T N B, Xiao X. GraphMP: I/O-efficient big graph analytics on a single commodity machine. IEEE Trans. Big Data, 2020, 6(4): 816-829. DOI:  10.1109/TBDATA.2019.2908384.
    [28]
    Wen D, Qin L, Zhang Y, Lin X, Yu J X. I/O efficient core graph decomposition at web scale. In Proc. the 32nd IEEE International Conference on Data Engineering, May 2016, pp.133-144. DOI:  10.1109/ICDE.2016.7498235.
    [29]
    Yuan L, Qin L, Lin X, Chang L, Zhang W. I/O efficient ECC graph decomposition via graph reduction. VLDB J., 2017, 26(2): 275-300. DOI:  10.1007/s00778-016-0451-4.
    [30]
    Zhang Z, Yu J X, Qin L, Chang L, Lin X. I/O efficient: Computing SCCs in massive graphs. VLDB J., 2015, 24(2): 245-270. DOI:  10.1007/s00778-014-0372-z.
    [31]
    Jiang Y, Huang X, Cheng H. I/O efficient k-truss community search in massive graphs. VLDB J., 2021, 30(5): 713-738. DOI: 10.1007/s00778-020-00649-y.
    [32]
    Li Y, Wang G, Zhao Y, Zhu F, Wu Y. Towards k-vertex connected component discovery from large networks. World Wide Web, 2020, 23(2): 799-830. DOI: 10.1007/s11280-019-00725-6.
    [33]
    Li Y, Sheng F, Sun J, Zhao Y, Wang G. A k-connected truss subgraph discovery algorithm in large scale dual networks. Chinese Journal of Computers, 2020, 43(9): 1721-1736. DOI: 10.11897/SP.J.1016.2020.01721. (in Chinese)
    • Relative Articles

  • Related Articles

    [1]Chun-Xue Zhu, Long-Long Lin, Ping-Peng Yuan, Hai Jin. Discovering Cohesive Temporal Subgraphs with Temporal Density Aware Exploration[J]. Journal of Computer Science and Technology, 2022, 37(5): 1068-1085. DOI: 10.1007/s11390-022-2431-z
    [2]Hao Liao, Qi-Xin Liu, Ze-Cheng Huang, Ke-Zhong Lu, Chi Ho Yeung, Yi-Cheng Zhang. Accumulative Time Based Ranking Method to Reputation Evaluation in Information Networks[J]. Journal of Computer Science and Technology, 2022, 37(4): 960-974. DOI: 10.1007/s11390-021-0471-4
    [3]Li Minglu, Sun Yongqiang, Sheng Huany. Nondeterministic Temporal Relations in Multimedia Data[J]. Journal of Computer Science and Technology, 1997, 12(3): 244-251.
    [4]Tang Changjie, Xiong Min. The Temporal Mechanisms in Hbase[J]. Journal of Computer Science and Technology, 1996, 11(4): 365-371.
    [5]Zhong Shaochun, Liu Dayou. Processing of Uncertainty Temporal Relations[J]. Journal of Computer Science and Technology, 1996, 11(1): 72-82.
    [6]Sun Yuan. The Modelling of Temporal Data in the Relational Database Environment[J]. Journal of Computer Science and Technology, 1995, 10(2): 163-174.
    [7]Xie Hongliang, Gong Jie, C.S.Tang. A Structured Temporal Logic Language:XYZ/SE[J]. Journal of Computer Science and Technology, 1991, 6(1): 1-10.
    [8]Zhou Chaochen, Liu Xinxin. Denote CSP with Temporal Formulas[J]. Journal of Computer Science and Technology, 1990, 5(1): 17-23.
    [9]Li Renwei. A Natural Deduction System of Temporal Logic[J]. Journal of Computer Science and Technology, 1988, 3(3): 173-185.
    [10]Feng Yulin. Hierarchical Protocol Analysis by Temporal Logic[J]. Journal of Computer Science and Technology, 1988, 3(1): 56-69.
    • Supplements (2)

  • Others

  • Cited by

    Periodical cited type(2)

    1. Jie Dai, Yixiao Liu, Yuan Li, et al. I/O efficient core maintenance in large graphs. Expert Systems with Applications, 2025. DOI:10.1016/j.eswa.2025.128234
    2. Hong Zeng, Xuanrui Zhou, Xitong Geng, et al. GLIPR2 emerges as a potential predictor of prognosis for renal clear cell carcinoma, exhibiting substantial relevance with cellular metastasis and CD8+ T cell infiltration. Informatics in Medicine Unlocked, 2024, 49: 101371. DOI:10.1016/j.imu.2023.101371

    Other cited types(0)

Catalog

    Get Citation
    PDF
    XML
    Read Online
    Article views (100) PDF downloads (25) Cited by(2)
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return