Page 460 - 《软件学报》2025年第9期

苟向阳 等: 高精度滑动窗口模型下的图流三角形近似计数算法 4371

Discovery from Data, 2010, 4(3): 13. [doi: 10.1145/1839490.1839494]
[8] Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: Simple building blocks of complex networks.
Science, 2002, 298(5594): 824–827. [doi: 10.1126/science.298.5594.824]
[9] Kang U, Meeder B, Papalexakis EE, Faloutsos C. HEigen: Spectral analysis for billion-scale graphs. IEEE Trans. on Knowledge and Data
Engineering, 2014, 26(2): 350–362. [doi: 10.1109/TKDE.2012.244]
[10] Yang Z, Wilson C, Wang X, Gao TT, Zhao BY, Dai YF. Uncovering social network Sybils in the wild. ACM Trans. on Knowledge
Discovery from Data (TKDD), 2014, 8(1): 2. [doi: 10.1145/2556609]
[11] Li ZJ, Lu YT, Zhang WP, Li RH, Guo J, Huang X, Mao R. Discovering hierarchical subgraphs of k-core-truss. Data Science and
Engineering, 2018, 3(2): 136–149. [doi: 10.1007/s41019-018-0068-2]
[12] Ding DM, Savi M, Pederzolli F, Siracusa D. Design and development of network monitoring strategies in P4-enabled programmable
switches. In: Proc. of the 2022 IEEE/IFIP Network Operations and Management Symp. Budapest: IEEE, 2022. 1–6. [doi: 10.1109/
NOMS54207.2022.9789848]
[13] Ahmed NK, Duffield N, Neville J, Kompella R. Graph sample and hold: A framework for big-graph analytics. In: Proc. of the 20th ACM
SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. New York: ACM, 2014. 1446–1455. [doi: 10.1145/2623330.2623757]
[14] Pavan A, Tangwongsan K, Tirthapura S, Wu KL. Counting and sampling triangles from a graph stream. Proc. of the VLDB Endowment,
2013, 6(14): 1870–1881. [doi: 10.14778/2556549.2556569]
[15] Wang PH, Qi YY, Sun Y, Zhang XL, Tao J, Guan XH. Approximately counting triangles in large graph streams including edge duplicates
with a fixed memory usage. Proc. of the VLDB Endowment, 2017, 11(2): 162–175. [doi: 10.14778/3149193.3149197]
[16] Gou XY, Zou L. Sliding window-based approximate triangle counting with bounded memory usage. The VLDB Journal, 2023, 32(5):
1087–1110. [doi: 10.1007/s00778-023-00783-3]
[17] De Stefani L, Epasto A, Riondato M, Upfal E. Trièst: Counting local and global triangles in fully dynamic streams with fixed memory
size. ACM Trans. on Knowledge Discovery from Data (TKDD), 2017, 11(4): 43. [doi: 10.1145/3059194]
[18] Shin K, Oh S, Kim J, Hooi B, Faloutsos C. Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Trans. on
Knowledge Discovery from Data (TKDD), 2020, 14(2): 12. [doi: 10.1145/3375392]
[19] Lee D, Shin K, Faloutsos C. Temporal locality-aware sampling for accurate triangle counting in real graph streams. The VLDB Journal,
2020, 29(6): 1501–1525. [doi: 10.1007/s00778-020-00624-7]
[20] Alon N, Yuster R, Zwick U. Finding and counting given length cycles. Algorithmica, 1997, 17(3): 209–223. [doi: 10.1007/BF02523189]
[21] Arifuzzaman S, Khan M, Marathe M. Patric: A parallel algorithm for counting triangles in massive networks. In: Proc. of the 22nd ACM
Int’l Conf. on Information & Knowledge Management. San Franciso: ACM, 2013. 529–538. [doi: 10.1145/2505515.2505545]
[22] Wang X, Yang XC. Study of triangle counting algorithm with sliding windows based on FLINK. Computer Science, 2020, 47(10): 83–90
(in Chinese with English abstract). [doi: 10.11896/jsjkx.190900014]
[23] Hu XC, Tao YF, Chung CW. Massive graph triangulation. In: Proc. of the 2013 ACM SIGMOD Int’l Conf. on Management of Data.
New York: ACM, 2013. 325–336. [doi: 10.1145/2463676.2463704]
[24] Park HM, Myaeng SH, Kang U. PTE: Enumerating trillion triangles on distributed systems. In: Proc. of the 22nd ACM SIGKDD Int’l
Conf. on Knowledge Discovery and Data Mining. San Francisco: ACM, 2016. 1115–1124. [doi: 10.1145/2939672.2939757]
[25] Bar-Yossef Z, Kumar R, Sivakumar D. Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proc.
of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms. San Francisco: Society for Industrial and Applied Mathematics, 2002.
623–632.
[26] Buriol LS, Frahling G, Leonardi S, Marchetti-Spaccamela A, Sohler C. Counting triangles in data streams. In: Proc. of the 25th ACM
SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems. 2006. 253–262. [doi: 10.1145/1142351.1142388]
[27] Jowhari H, Ghodsi M. New streaming algorithms for counting triangles in graphs. In: Proc. of the 11th Annual Int’l Conf. on Computing
and Combinatorics. Kunming: Springer, 2005. 710–716. [doi: 10.1007/11533719_72]
[28] Lim Y, Kang U. Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams. In: Proc. of the 21st ACM
SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Sydney: ACM, 2015. 685–694. [doi: 10.1145/2783258.2783285]
[29] Jha M, Seshadhri C, Pinar A. A space efficient streaming algorithm for triangle counting using the birthday paradox. In: Proc. of the 19th
ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Chicago: ACM, 2013. 589–597. [doi: 10.1145/2487575.2487678]
[30] Tsourakakis CE, Kang U, Miller GL, Faloutsos C. Doulion: Counting triangles in massive graphs with a coin. In: Proc. of the 15th ACM
SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Paris: ACM, 2009. 837–846. [doi: 10.1145/1557019.1557111]
[31] Gemulla R, Lehner W, Haas PJ. Maintaining bounded-size sample synopses of evolving datasets. The VLDB Journal, 2008, 17(2):
173–201. [doi: 10.1007/s00778-007-0065-y]