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 5
September  2022
Turn off MathJax
Article Contents
Abstract
References
Supplements
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
Citation: 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
shu

Discovering Cohesive Temporal Subgraphs with Temporal Density Aware Exploration

  • National Engineering Research Center for Big Data Technology and System, Huazhong University of Science and Technology, Wuhan 430074, China
    Service Computing Technology and System Laboratory, Huazhong University of Science and Technology, Wuhan 430074, China
    Cluster and Grid Computing Laboratory, Huazhong University of Science and Technology, Wuhan 430074, China
    School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

Funds: The work was supported by the National Key Research and Development Program of China under Grant No. 2018YFB1402802 and the National Natural Science Foundation of China under Grant Nos. 61932004 and 62072205.
More Information
  • Author Bio:

    Ping-Peng Yuan received his Ph.D. degree in computer science from Zhejiang University, Hangzhou, in 2002. He is now a professor in the School of Computer Science and Technology at Huazhong University of Science and Technology (HUST), Wuhan. His research interests include databases, knowledge representation and reasoning, and natural language processing, with a focus on high performance computing. He is the principle developer in multiple system prototypes, including TripleBit, PathGraph and SemreX.

  • Corresponding author:

    Ping-Peng Yuan E-mail: ppyuan@hust.edu.cn

  • Received Date: April 15, 2022
  • Revised Date: August 21, 2022
  • Accepted Date: September 07, 2022
  • Published Date: September 29, 2022
    Abstract
  • Real-world networks, such as social networks, cryptocurrency networks, and e-commerce networks, always have occurrence time of interactions between nodes. Such networks are typically modeled as temporal graphs. Mining cohesive subgraphs from temporal graphs is practical and essential in numerous data mining applications, since mining cohesive subgraphs gets insights into the time-varying nature of temporal graphs. However, existing studies on mining cohesive subgraphs, such as Densest-Exact and k-truss, are mainly tailored for static graphs (whose edges have no temporal information). Therefore, those cohesive subgraph models cannot indicate both the temporal and the structural characteristics of subgraphs. To this end, we explore the model of cohesive temporal subgraphs by incorporating both the evolving and the structural characteristics of temporal subgraphs. Unfortunately, the volume of time intervals in a temporal network is quadratic. As a result, the time complexity of mining temporal cohesive subgraphs is high. To efficiently address the problem, we first mine the temporal density distribution of temporal graphs. Guided by the distribution, we can safely prune many unqualified time intervals with the linear time cost. Then, the remaining time intervals where cohesive temporal subgraphs fall in are examined using the greedy search. The results of the experiments on nine real-world temporal graphs indicate that our model outperforms state-of-the-art solutions in efficiency and quality. Specifically, our model only takes less than two minutes on a million-vertex DBLP and has the highest overall average ranking in EDB and TC metrics.
    • FullText(HTML)
    • References (40)
  • [1]
    Chang L, Qin L. Cohesive subgraph computation over large sparse graphs. In Proc. the 35th IEEE International Conference on Data Engineering, April 2019, pp.2068-2071. DOI: 10.1109/ICDE.2019.00241.
    [2]
    Goldberg A V. Finding a maximum density subgraph. Technical Report, University of California Berkeley, 1984. https://digicoll.lib.berkeley.edu/record/136696, July 2022.
    [3]
    Rozenshtein P, Gionis A. Mining temporal networks. In Proc. the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2019, pp.3225-3226. DOI: 10.1145/3292500.3332295.
    [4]
    Lin L, Yuan P, Li R H, Wang J, Liu L, Jin H. Mining stable quasi-cliques on temporal networks. IEEE Trans. Systems, Man, and Cybernetics: Systems, 2022, 52(6): 3731-3745. DOI: 10.1109/TSMC.2021.3071721.
    [5]
    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, April 2018, pp.797-808. DOI: 10.1109/ICDE.2018.00077.
    [6]
    Yang Y, Yan D, Wu H, Cheng J, Zhou S, Lui J C S. Diversified temporal subgraph pattern mining. In Proc. the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2016, pp.1965-1974. DOI: 10.1145/2939672.2939848.
    [7]
    Bassett D S, Yang M, Wymbs N F, Grafton S T. Learning-induced autonomy of sensorimotor systems. Nature Neuroscience, 2015, 18(5): 744-751. DOI: 10.1038/nn.3993.
    [8]
    Rozenshtein P, Bonchi F, Gionis A, Sozio M, Tatti N. Finding events in temporal networks: Segmentation meets densest subgraph discovery. Knowledge and Information Systems, 2020, 62(4): 1611-1639. DOI: 10.1007/s10115-019-01403-9.
    [9]
    Chu L, Zhang Y, Yang Y, Wang L, Pei J. Online density bursting subgraph detection from temporal graphs. Proceedings of the VLDB Endowment, 2019, 12(13): 2353-2365. DOI: 10.14778/3358701.3358704.
    [10]
    Ma S, Hu R, Wang L, Lin X, Huai J. Fast computation of dense temporal subgraphs. In Proc. the 33rd IEEE International Conference on Data Engineering, April 2017, pp.361-372. DOI: 10.1109/ICDE.2017.95.
    [11]
    Boden B, Gunnemann S, Hoffmann H, Seidl T. MiMAG: Mining coherent subgraphs in multi-layer graphs with edge labels. Knowledge and Information Systems, 2017, 50(2): 417-446. DOI: 10.1007/s10115-016-0949-5.
    [12]
    Zhu R, Zou Z, Li J. Diversified coherent core search on multi-layer graphs. In Proc. the 34th IEEE International Conference on Data Engineering, April 2018, pp.701-712. DOI: 10.1109/ICDE.2018.00069.
    [13]
    Hashemi F, Behrouz A, Lakshmanan L V S. FirmCore decomposition of multilayer networks. In Proc. the 2022 ACM Web Conference, April 2022, pp.1589-1600. DOI: 10.1145/3485447.3512205.
    [14]
    Liu G, Wong L. Effective pruning techniques for mining quasi-cliques. In Proc. the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases, September 2008, pp.33-49. DOI: 10.1007/978-3-540-87481-2.
    [15]
    Pei J, Jiang D, Zhang A. On mining cross-graph quasi-cliques. In Proc. the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, August 2005, pp.228-238. DOI: 10.1145/1081870.1081898.
    [16]
    Cheng J, Ke Y, Chu S, Özsu M. T. Efficient core decomposition in massive networks. In Proc. the 27th IEEE International Conference on Data Engineering, April 2011, pp.51-62. DOI: 10.1109/ICDE.2011.5767911.
    [17]
    Li R H, Qin L, Yu J X, Mao R. Influential community search in large networks. Proceedings of the VLDB Endowment, 2015, 8(5): 509-520. DOI: 10.14778/2735479.2735484.
    [18]
    Khuller S, Saha B. On finding dense subgraphs. In Proc. the 36th International Colloquium on Automata, Languages, and Programming, July 2009, pp.597-608. DOI: 10.1007/978-3-642-02927-1.
    [19]
    Tsourakakis C. The k-clique densest subgraph problem. In Proc. the 24th International Conference on World Wide Web, May 2015, pp.1122-1132. DOI: 10.1145/2736277.2741098.
    [20]
    Tsourakakis C, Bonchi F, Gionis A, Gullo F, Tsiarli M. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees. In Proc. the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2013, pp.104-112. DOI: 10.1145/2487575.2487645.
    [21]
    Charikar M. Greedy approximation algorithms for finding dense components in a graph. In Proc. the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, September 2000, pp.84-95. DOI: 10.1007/3-540-44436-X.
    [22]
    Andersen R, Chellapilla K. Finding dense subgraphs with size bounds. In Proc. the 6th International Workshop on Algorithms and Models for the Web-Graph, February 2009, pp.25-37. DOI: 10.1007/978-3-540-95995-3.
    [23]
    Epasto A, Lattanzi S, Sozio M. Efficient densest subgraph computation in evolving graphs. In Proc. the 24th International Conference on World Wide Web, May 2015, pp.300-310. DOI: 10.1145/2736277.2741638.
    [24]
    Gionis A, Tsourakakis C E. Dense subgraph discovery: KDD 2015 tutorial. In Proc. the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2015, pp.2313-2314. DOI: 10.1145/2783258.2789987.
    [25]
    Silva A, Singh A, Swami A. Spectral algorithms for temporal graph cuts. In Proc. the 27th International Conference on World Wide Web, April 2018, pp.519-528. DOI: 10.1145/3178876.3186118.
    [26]
    Peajcariaac J E, Tong Y L. Convex Functions, Partial Orderings, and Statistical Applications (1st edition). Academic Press, 1992.
    [27]
    Eagle N, Pentland A. Reality mining: Sensing complex social systems. Personal and Ubiquitous Computing, 2006, 10(4): 255-268. DOI: 10.1007/s00779-005-0046-3.
    [28]
    Yuan L, Qin L, Lin X, Chang L, Zhang W. Diversified top-k clique search. The VLDB Journal, 2016, 25(2): 171-196. DOI: 10.1007/s00778-015-0408-z.
    [29]
    Lu C, Yu J X, Wei H, Zhang Y. Finding the maximum clique in massive graphs. Proceedings of the VLDB Endowment, 2017, 10(11): 1538-1549. DOI: 10.14778/3137628.3137660.
    [30]
    Wang J, Cheng J. Truss decomposition in massive networks. arXiv:1205.6693, 2012. https://doi.org/10.4/arXiv.1205.6693, July 2022.
    [31]
    Galimberti E, Bonchi F, Gullo F, Lanciano T. Core decomposition in multilayer networks: Theory, algorithms, and applications. ACM Trans. Knowledge Discovery from Data, 2020, 14(1): Article No. 11. DOI: 10.1145/3369872.
    [32]
    Galimberti E, Ciaperoni M, Barrat A, Bonchi F, Cattuto C, Gullo F. Span-core decomposition for temporal networks: Algorithms and applications. ACM Trans. Knowledge Discovery from Data, 2020, 15(1): Article No. 2. DOI: 10.1145/3418226.
    [33]
    Wu H, Cheng J, Huang S, Ke Y, Lu Y, Xu Y. Path problems in temporal graphs. Proceedings of VLDB Endowment, 2014, 7(9): 721-732. DOI: 10.14778/2732939.2732945.
    [34]
    Wu H, Huang Y, Cheng J, Li J, Ke Y. Reachability and time-based path queries in temporal graphs. In Proc. the 32nd IEEE International Conference on Data Engineering, May 2016, pp.145-156. DOI: 10.1109/ICDE.2016.7498236.
    [35]
    Rozenshtein P, Gionis A. Temporal PageRank. In Proc. the European Conference on Machine Learning and Knowledge Discovery in Databases, September 2016, pp.674-689. DOI: 10.1007/978-3-319-46227-1.
    [36]
    Akrida E C, Mertzios G B, Spirakis P G, Zamaraev V. Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 2020, 107: 108-123. DOI: 10.1016/j.jcss.2019.08.002.
    [37]
    Mertzios G B, Molter H, Zamaraev V. Sliding window temporal graph coloring. In Proc. the 33rd AAAI Conference on Artificial Intelligence, January 27-February 1, 2019, pp.7667-7674. DOI: 10.1609/aaai.v33i01.33017667.
    [38]
    Lin L, Yuan P, Li R, Jin H. Mining diversified top-r lasting cohesive subgraphs on temporal networks. IEEE Trans. Big Data. DOI: 10.1109/TBDATA.2021.3058294.
    [39]
    Qin H, Li R, Yuan Y, Wang G, Yang W. Periodic communities mining in temporal networks: Concepts and algorithms. IEEE Trans. Knowledge and Data Engineering, 2022, 34(8): 3927-3945. DOI: 10.1109/TKDE.2020.3028025.
    [40]
    Zhang Y, Lin L, Yuan P, Jin H. Significant engagement community search on temporal networks. In Proc. the 27th International Conference on Database Systems for Advanced Applications, April 2022, pp.250-258. DOI: 10.1007/978-3-031-00123-9.
    • Relative Articles
  • Supplements (2)

  • Others

Catalog

    Get Citation
    PDF
    XML
    Read Online
    Article views (113) PDF downloads (1) Cited by()
    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