面向时序图的周期性三角形枚举算法研究

doi:10.3778/j.issn.1673-9418.2202004

摘要/Abstract

摘要： 真实世界中的图通常是时序图，即图中的边具有时间戳。随着图数据挖掘算法和现实需要的发展，时序图的数据挖掘算法开始成为热点问题。其中，周期性是时序数据中一个非常重要的特征。周期性出现的数据通常代表着现实世界中值得关注的行为模式。在静态图的数据挖掘算法中，三角形枚举是一个基础且重要的问题。基于时序图，提出了一种新的三角形社群模型，周期三角形，并将周期性数据挖掘与图中的三角形枚举算法相结合，提出了一种高效的时序图周期性三角形枚举算法。该算法主要包含三部分：高效的多级剪枝算法，该算法可以在较小的时间代价下删除不在任何周期三角形中的顶点和边；极大周期枚举算法，通过计算极大周期，提出的算法可以避免对时间维度上重叠社群进行重复枚举；边枚举边剪枝的高效的周期三角形枚举算法。实验表明，该算法可以快速枚举出图中的周期性三角形。

关键词: 时序图, 周期性, 三角形枚举

Abstract: Real-world graphs are usually temporal graphs, and their edges are associated with timestamps. With the development of algorithms on graph data mining and the increase of needs in real-world, data mining algorithms for temporal graphs have started to become a hot topic. Periodicity is a very important feature in temporal data. Patterns that occur periodically in real world usually indicate important features. In data mining algorithms for static graphs, triangle enumeration is a fundamental and important problem. In this paper, a new triangle model is proposed based on the temporal graph, the periodic triangle. In this paper, periodic data mining is combined with triangle enumeration algorithms in graphs, and an efficient algorithm for periodic triangle enumeration in temporal graphs is proposed. This algorithm contains three components: the first one is an efficient multi-level pruning algorithm which can delete vertices and edges which are not in any periodic triangle at low cost; the second one is a maximal periodic enumeration algorithm that can avoid enumeration on overlapping communities in time axis; the third one is an efficient periodic triangle enumeration algorithm that prunes unnecessary vertices and edges while enumeration. Experiments show that the algorithm proposed in this paper can enumerate periodic triangles in graphs efficiently.

Key words: temporal graph, periodicity, triangle enumeration

任泽槟, 李荣华, 戴永恒, 王国仁. 面向时序图的周期性三角形枚举算法研究[J]. 计算机科学与探索, 2023, 17(8): 1833-1841.

REN Zebin, LI Ronghua, DAI Yongheng, WANG Guoren. Research on Periodic Triangle Enumeration Algorithm for Temporal Graphs[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(8): 1833-1841.

参考文献

[1] YANG Y, YU J X, GAO H, et al. Mining most frequently changing component in evolving graphs[J]. World Wide Web, 2014, 17(3): 351-376.
[2] GURUKAR S, RANU S, RAVINDRAN B. Commit: a scalable approach to mining communication motifs from dynamic networks[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, May 31-Jun 4, 2015. New York: ACM, 2015: 475-489.
[3] MA S, HU R, WANG L, et al. Fast computation of dense temporal subgraphs[C]//Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering, San Diego, Apr 19-22, 2017. Washington: IEEE Computer Society, 2017: 361-372.
[4] WU H, CHENG J, LU Y, et al. Core decomposition in large temporal graphs[C]//Proceedings of the 2015 IEEE International Conference on Big Data, Santa Clara, Oct 29-Nov 1, 2015. Washington: IEEE Computer Society, 2015: 649-658.
[5] YANG Y, YAN D, WU H, et al. Diversified temporal subgraph pattern mining[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 1965-1974.
[6] WU H, HUANG Y, CHENG J, et al. Reachability and time-based path queries in temporal graphs[C]//Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering, Helsinki, May 16-20, 2016. Washington: IEEE Computer Society, 2016: 145-156.
[7] ROSSETTI G, CAZABET R. Community discovery in dynamic networks: a survey[J]. ACM Computing Surveys, 2018, 51(2): 1-37.
[8] LIN Y R, CHI Y, ZHU S, et al. FacetNet: a framework for analyzing communities and their evolutions in dynamic networks[C]//Proceedings of the 17th International Conference on World Wide Web, Beijing, Apr 21-25, 2008. New York: ACM, 2008: 685-694.
[9] CHEN Z, WILSON K A, JIN Y, et al. Detecting and tracking community dynamics in evolutionary networks[C]//Proceedings of the 2010 IEEE International Conference on Data Mining Workshops, Sydney, Dec 13, 2010. Washington: IEEE Computer Society, 2010: 318-327.
[10] AGARWAL M K, RAMAMRITHAM K, BHIDE M. Real time discovery of dense clusters in highly dynamic graphs: identifying real world events in highly dynamic environments[J]. Proceedings of the VLDB Endowment, 2012, 5(10): 980-991.
[11] QIN H C, LI R H, YUAN Y, et al. Periodic communities mining in temporal networks: concepts and algorithms[C]//Proceedings of the 2019 IEEE 35th International Conference on Data Engineering, Macau, China, Apr 8-11, 2019. Washington: IEEE Computer Society, 2019: 361-372.
[12] ZHANG Q, GUO D, ZHAO X, et al. Seasonal-periodic subgraph mining in temporal networks[C]//Proceedings of the 29th ACM International Conference on Information & Know-ledge Management, Ireland, Oct 19-23, 2020. New York: ACM, 2020: 2309-2312.
[13] SCHANK T, WAGNER D. Finding, counting and listing all triangles in large graphs, an experimental study[C]//LNCS 3503: Proceedings of the 2005 International Workshop on Experimental and Efficient Algorithms, Santorini Island, May 10-13, 2005. Berlin, Heidelberg: Springer, 2005: 606-609.
[14] HUANG X, CHENG H, QIN L, et al. Querying K-truss community in large and dynamic graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, Snowbird, Jun 22-27, 2014. New York: ACM, 2014: 1311-1322.
[15] WANG J, CHENG J. Truss decomposition in massive networks[J]. Proceedings of the VLDB Endowment, 2012, 5(9): 812-823.
[16] ORTMANN M, BRANDES U. Triangle listing algorithms: back from the diversion[C]//Proceedings of the 16th Workshop on Algorithm Engineering and Experiments, Portland, Jan 5, 2014. Philadelphia: SIAM, 2014: 1-8.
[17] SCHANK T. Algorithmic aspects of triangle-based network analysis[D]. Karlsruhe: University Karlsruhe, 2007.
[18] LATAPY M. Main-memory triangle computations for very large (sparse (power-law)) graphs[J]. Theoretical Computer Science, 2008, 407: 458-473.
[19] ITAI A, RODEH M. Finding a minimum circuit in a graph[J]. SIAM Journal on Computing, 1978, 7(4): 413-423.
[20] LI R H, SU J, QIN L, et al. Persistent community search in temporal networks[C]//Proceedings of the 2018 IEEE 34th International Conference on Data Engineering, Paris, Apr 16-19, 2018. Washington: IEEE Computer Society, 2018: 797-808.