Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Abstract
Keywords
Electronic Supplementary Material
References
Show full outline
Hide outline
Regular Paper

Discovering Cohesive Temporal Subgraphs with Temporal Density Aware Exploration

Chun-Xue Zhu1,2,3,4, Long-Long Lin1,2,3,4, Ping-Peng Yuan1,2,3,4(), Hai Jin1,2,3,4
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
Show Author Information

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.

Keywords

temporal networktemporal feature distributioncohesive subgraphconvex property

Electronic Supplementary Material

Download File(s)
jcst-37-5-1068-Highlights.pdf (1.1 MB)

References

[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.
Crossref
[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.
Crossref
[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.

Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.

Crossref Google Scholar
[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.

Crossref Google Scholar
[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.

Crossref Google Scholar
[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.
Crossref
[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.

Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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_3.
Crossref
[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.
Crossref
[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.
Crossref
[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.

Crossref Google Scholar
[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_50.
Crossref
[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.
Crossref
[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.
Crossref
[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_10.
Crossref
[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_3.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref
[26]
Peajcariaac J E, Tong Y L. Convex Functions, Partial Orderings, and Statistical Applications (1st edition). Academic Press, 1992.
Crossref
[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.

Crossref Google Scholar
[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.

Crossref Google Scholar
[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.

Crossref Google Scholar
[30]
Wang J, Cheng J. Truss decomposition in massive networks. arXiv: 1205.6693, 2012. https://doi.org/10.4855-0/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.

Crossref Google Scholar
[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.

Crossref Google Scholar
[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.

Crossref Google Scholar
[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.
Crossref
[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_42.
Crossref
[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.

Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.

Crossref Google Scholar
[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_20.
Crossref
Journal of Computer Science and Technology
Volume 37 Issue 5,
September 2022
Pages 1068-1085
DOI: 10.1007/s11390-022-2431-z
Cite this article:
Zhu C-X, Lin L-L, Yuan P-P, et al. Discovering Cohesive Temporal Subgraphs with Temporal Density Aware Exploration. Journal of Computer Science and Technology, 2022, 37(5): 1068-1085. https://doi.org/10.1007/s11390-022-2431-z
Metrics & Citations  
Article History
Copyright
Return