基于FLINK窗口操作的三角形計(jì)數(shù)算法

　　三角形計(jì)數(shù)旨在計(jì)算圖中全局三角形和局部三角形的數(shù)量，是圖數(shù)據(jù)挖掘中的一類重要工作。三角形的數(shù)量被廣泛應(yīng)用于角色識別、推薦系統(tǒng)、社區(qū)發(fā)現(xiàn)、垃圾郵件和欺詐檢測等領(lǐng)域。在以流形式給岀的圖中，邊具有時(shí)間性，冋時(shí)現(xiàn)實(shí)生活中的圖存在著大量的重復(fù)邊。為充分利用圖中的時(shí)間信息以挖掘網(wǎng)絡(luò)知識，研究在多圖流上計(jì)算滑動窗口內(nèi)全局和局部三角形數(shù)量的問題，使用窗口機(jī)制同時(shí)硏究多個(gè)窗口以利用隱含的時(shí)間關(guān)系獲取更多信息。文中提出基于 FLINK窗口操作的三角形計(jì)數(shù)算法和基于滑動窗口的三角形増量計(jì)數(shù)算法，以現(xiàn)有的邊采樣工作為基礎(chǔ)，使用邊集存儲窗口歷史數(shù)據(jù)實(shí)現(xiàn)一遍流計(jì)算，從而準(zhǔn)確地計(jì)算面向多圖流的滑動窗口內(nèi)全局和局部三角形數(shù)量?；?FLINK窗口操作的三角形計(jì)數(shù)算法使用 FLINK提供的窗口機(jī)制，基于滑動窗口的三角形増量計(jì)數(shù)算法，通過計(jì)算窗口滑入和滑岀數(shù)據(jù)來實(shí)現(xiàn)窗口計(jì)數(shù)，避免了相鄰兩個(gè)窗口間重合邊的大量重復(fù)計(jì)算，無縫地處理多個(gè)時(shí)間窗口，對于滑入和滑出數(shù)據(jù)中的重復(fù)數(shù)據(jù)，使用去重機(jī)制來進(jìn)一步減小計(jì)算量。論證明兩種算法可以實(shí)現(xiàn)滑動窗口內(nèi)三角形準(zhǔn)確計(jì)數(shù)，并通過實(shí)驗(yàn)分析了窗口大小、滑動距離、數(shù)據(jù)分布和數(shù)據(jù)流速等因素對窗口處理時(shí)間的影響。與 TRIEST算法相比，當(dāng)窗口較小時(shí)，基于 FLINK窗口操作的三角形計(jì)數(shù)算法和基于滑動窗口的三角形增量計(jì)數(shù)算法速度更快;當(dāng)窗口較大時(shí)，保證了計(jì)算結(jié)果的準(zhǔn)確性。