大數(shù)據(jù)下圖三角計算的研究進展

金宏橋，董一鴻

（寧波大學信息科學與工程學院，浙江 寧波 315211）

綜述

大數(shù)據(jù)下圖三角計算的研究進展

金宏橋，董一鴻

（寧波大學信息科學與工程學院，浙江 寧波 315211）

圖三角數(shù)量的計算是計算網(wǎng)絡聚集系數(shù)和傳遞性的重要步驟，廣泛應用于重要角色識別、垃圾郵件檢測、社區(qū)發(fā)現(xiàn)、生物檢測等。 在大數(shù)據(jù)背景下，計算圖中三角形算法主要面臨時空消耗和計算準確性兩大難題。介紹了代表性的大圖中計算三角形的算法，主要存在準確計算和近似計算兩大類。 準確計算算法又分為內(nèi)存算法、外存算法和分布式算法，時空消耗或 I／O 消耗很大。 近似計算算法中，有輔助算法、非流式算法和流式算法之分。最后對計算三角形算法進行了歸納總結。

準確計算；近似計算；三角形；圖

1 引言

隨著網(wǎng)絡技術和社會網(wǎng)絡服務的發(fā)展，網(wǎng)絡中的數(shù)據(jù)量和信息量越來越大。在這種大數(shù)據(jù)的環(huán)境下，對數(shù)據(jù)的分析和挖掘顯得尤為重要。近年來，對有大規(guī)模數(shù)據(jù)的網(wǎng)絡的分析得到越來越多的關注。計算機學科的數(shù)據(jù)結構圖可以作為很多種網(wǎng)絡的模型，如萬維網(wǎng)、P2P 網(wǎng)絡和社交網(wǎng)絡等都可以用含有特定信息的圖作為它們的模型。對網(wǎng)絡的分析逐漸轉化為對保存網(wǎng)絡重要信息的圖的分析。由于網(wǎng)絡中的關系和個體數(shù)量非常多，所以作為其模型的圖的規(guī)模也很大。

社會網(wǎng)絡的同質(zhì)性和傳遞性產(chǎn)生了對圖中三角形的研究。圖中的三角形是復雜網(wǎng)絡分析的重要角色，不論是來自社會交互、計算機交流、金融交易、蛋白質(zhì)還是生態(tài)學網(wǎng)絡，其中三角形的數(shù)量都是巨大的，它在這些領域中有著非常廣泛的應用。通過三角形的分布可以區(qū)分哪些是垃圾郵件的主人。角色行為識別中，通過使用者參與的三角形的數(shù)量可以判斷這個使用者的地位。生物信息學中的主題檢測需要計算三元組的頻率。三角形巨大的數(shù)量可以與蛋白質(zhì)交互網(wǎng)絡的拓撲結構和功能性相聯(lián)系。三角形各點度數(shù)之間的關系也可以作為基礎圖的描述符，在數(shù)據(jù)庫中，三角形也有具體的應用。

目 前 圖 中 三 角 形 的 計 算 主 要 分 為 準 確 計 算 （exact counting）和 近 似 計 算 （approximate counting）兩 種 類 型 。準確計算可以準確地計算圖中三角形的數(shù)量，對于大圖來說，規(guī)模很大，所以計算的時空消耗很大，外存算法的I／O 消耗也 會很大 。研 究人員 的重點就是 在保持準確計算的情況下，減少時空消耗和 I／O 次數(shù)。近年來，分 布式框架 MapReduce 的出現(xiàn)，也使很多研究人員研究此框架下的計算三角形算法。相較而言，近似計算比準確計算的實際應用更廣泛，同時空間消耗較少。在保持一定準確度的情況下，研究人員對近似計算三角形數(shù)量更感興趣。對于近似計算，大部分的研究者將重點放在采樣上，通過一定的采樣方法證實，采樣得到的三角形數(shù)量與實際數(shù)量的差值很小，同時將時間空間的復雜度降低。目前，采樣方法很多，各有所長。準確計算三角形算法的部分關鍵點也可以用在近似計算算法上。如上文所述，隨著互聯(lián)網(wǎng)的快速發(fā)展，大規(guī)模的圖不斷涌現(xiàn)，在圖流中使用限制的內(nèi)存來估算三角形的數(shù)量，這個問題的研究意義越來越顯著，同時難度也越來越大。

2 圖三角的基本概念

定 義 1 （三 角 形 ）給 定 一 個 圖 G=（V，E），它 包 含 了 一個 頂 點 集 合 V、一個邊的 集 合 E，|V|和|E|分 別 表 示 頂 點 和邊 的 個 數(shù) 。如 果 頂 點 u、υ、w∈V ，邊｛u，υ｝、｛υ，w｝、｛w，u｝∈E，那 么 3 個 頂 點 和 3 條 邊 組 成 一 個 三 角 形 ，稱為 ?uυw。

定義 2 （三角形的實際數(shù)量、準確數(shù)量和估算數(shù)量）用 T 表示圖 G 中三角形的實際數(shù)量，用 t表示通過準確算法得出的圖 G 中三角形的數(shù)量，用 T＇表示通過估計算法得出的圖G中三角形的數(shù)量。

定 義 3 （度 和 鄰 域 ）頂 點 υ的 鄰 域 Γ（υ）表 示 所 有 與頂 點 υ相 鄰 的 點 ，滿 足 Γ（υ）=｛u∈V：（u，υ）∈E｝。頂 點 υ的 度 d（υ）是頂點 υ連 接 的 所 有 邊 的 個 數(shù)或 者 是 它 的 鄰 域 ，滿 足d（υ）=|Γ（υ）|。圖 G 最 大 的 度 dmax（G）是指圖中頂點最大的度，即 dmax（G）=max｛d（υ）：υ∈V｝。 m、n 分 別 表 示 圖 中 邊 、點 的 個數(shù)，頂點的度和圖中的邊數(shù)滿足。入度和出度是對于有向圖來說的，一個頂點的入度等于被所有箭頭所指的數(shù)量，一個頂點的出度等于被所有箭尾所指的數(shù)量。

定 義 4 （（1+ε）-approximation） 返 回 q 的 以 ε為 因 子的估計值 q＇，當 q 滿足（1-ε）q≤q＇≤（1+ε）q，其中，ε＜0。

定義 5 （（ε，δ）-approximation）返 回 q 的 以 ε、δ為 因 子的估計值 q＇，當 q 至少以 1-δ的可能性滿足，（1-ε）q≤q＇≤（1+ε）q，其中，ε＜0，δ＜1。

定義 6 （圖流）圖中的邊是以一串流的形式加入的。

3 圖三角的準確計算

圖三角的計算有準確計算和近似計算兩種類型。準確計算圖三角算法目前有內(nèi)存算法、外存算法、分布式算法 3 類。內(nèi)存算法指當內(nèi)存能容納整個圖，可以在內(nèi)存中將圖中的三角形計算出來的算法；外存算法是指當圖的規(guī)模很大，不能全部存入內(nèi)存進行計算時，通過一定的策略將圖分為幾個部分存入內(nèi)存進行計算，這種算法會產(chǎn)生一定數(shù)量的 I／O 操作；分布式算法是指用分布式框架來計算圖中三角形數(shù)量，目前主要采用 MapReduce 框架。內(nèi)存算法中除了具有代表性的Node-iterator［1］和 Edge-iterator算法，還有 Matrix-multiplication［2］算法。基于點邊迭代和矩陣相乘也出現(xiàn)了一系列改進的算法 ，有 AYZ［3］、Node-iterator-core［4］、Forward［5］、Forward-hashed［6］、Compact-forward［7］。 時 隔 多 年 又 出 現(xiàn) 了 結 合 點 邊 迭 代 的Combined Iterator［8］算 法 。本 文 將 介 紹 兩 個 外 存 算 法 ：Chu 和Cheng［9］提 出 的 基 于 圖 劃 分 的 算 法 和 Hu［10］提 出 的 有 效 I／O的算法。近些年來，隨著分布式框架的應用，出現(xiàn)了基于MapReduce 框 架 的 GP［11］、TTP［12］以 及 CTTP［13］算 法 。目 前 出現(xiàn)的準確計算圖三角算法都應用在靜態(tài)圖上。以下將一一介紹。

3.1 內(nèi)存算法

內(nèi)存算法最初適用于規(guī)模比較小的圖，小圖完全可以存入計算機內(nèi)存中，并進行計算。內(nèi)存算法最先找到了如何使用計算機解決三角形計算問題的方法，并且不斷地在算法細節(jié)中得到突破，以減少運行時空成本。其中，基本迭代算法簡單，但成本高，不適合規(guī)模大的圖。Fast Common Neighbor Iteration 算 法 通 過 混 合 線 性 掃 描 二 分 法 和 分 段 索引法，在時間上進行了很大優(yōu)化，同時增加了空間的開銷。隨著圖規(guī)模的增長，內(nèi)存算法需要更大內(nèi)存的計算機。

3.1.1 迭代算法

Node-iterator（點 迭 代 ）算 法 檢 測 每 一 個 頂 點 的 每 一 對鄰點之間是否有一條邊，如果有，那么就得到一個三角形，反之得不到。為了使每一個三角形只被計算一次，需要安排 每 個 頂 點 的 順 序 。Edge-iterator（邊 迭 代 ）算 法 迭 代 所 有邊，比較每條 邊 兩個頂點 的 領域，對于一條 邊｛u，w｝，僅當 υ同時出現(xiàn)在 Γ（u）和 Γ（w）中，3 點｛u，υ，w｝才組成一個三角形。

Alon、Yuster 和 Zwick 將 點 迭 代 和 矩 陣 相 乘 結 合 在 一起，得到 AYZ 算法。算法將點集分為度數(shù)低的頂點集合Vlow=｛υ∈V：d（υ）≤β｝和 度 數(shù) 高 的 頂 點 集 合 Vhigh=V／Vlow，其 中 ，β=mγ-1／γ+1，γ 是 矩 陣 乘 法 指 數(shù) 。低 度 數(shù) 的 點 集 采 用 標 準 點 迭代方法，高 度 數(shù) 點 集 采 用 快 速 矩 陣 乘 法 。Node-iterator-core算法是在點迭代的基礎上，在每次選擇頂點迭代時選擇當前度數(shù)最小的頂點，當此頂點所在的三角形全部被計算后，將此頂點刪除。Forward 算法是邊迭代算法的改進。在邊迭代算法中，需要將邊兩個頂點的所有鄰接頂點都比較一下，在 Forward 算法中只需要比較邊迭代中所有鄰接頂點的子集 A。在這個算法中，由于所有的點都是有順序的，所以 可以將圖 視 為有向圖 ，方 便 理 解算法過 程 。A（υ）的 數(shù)據(jù)結構的大小是不大于點 υ的入度。Latapy M 提 出 了 一 個對 Forward 改 進 的 算 法 Compact-forward。Compact-forward使用迭代器迭代鄰接點的子集，迭代方法和邊迭代方法相同。鄰接點是排序過的，比較語句也在一個可達的確定指數(shù)前停止。雖然時間上界和 Forward 算法相同，但是它不需要額外的數(shù)組，因此節(jié)省了時間和空間。

Oracle Labs 的 Sevenich M 提 出 了 FCNI （fast common neighbor iteration）算 法 。該算法的基準算法是結合點迭代、邊迭代兩種迭代算法的 Combined Iterator算 法 ，該 基 準 與前面 提 到 的 Forward 算法類 似 ，多了鄰點 選擇 時 的 排 序。FCNI 算 法 指 出 Combined Iterator 算 法 的 主 要 部 分 是 重 復求出不同頂點對的共同鄰點，所以想要快速計算三角形的個數(shù)，就需要快速求出頂點對的共同鄰點。面臨的問題是：求一個度很高的頂點和其他頂點的共同鄰點需要很長的時間。于是他們提出了兩個方法來解決這個問題：混合線性掃描二分法和分段索引法。每個頂點的鄰點存儲在有序的鄰接數(shù)組中，問題轉化為求兩個有序數(shù)組的共有元素。當兩個數(shù)組長度差距過大時，采用二分法，算法從選擇長數(shù)組的中間元素和用二分查找短數(shù)組開始。當兩個數(shù)組度都較小時，采用線性掃描。算法又將度數(shù)高的頂點構建了索引，對他們的鄰點數(shù)組構造了分段索引。這兩個方法的應用使該算法的運行時間大大減少，在當前內(nèi)存算法中運行時間最少。

3.1.2 矩陣相乘算法

在 矩 陣 相 乘 （matrix-multiplication）算 法 中 ，假 設 A 是圖 G 的鄰接矩陣，A3對角線上的數(shù)字分別代表對應頂點所在三角形個數(shù)的兩倍。A3對角線上的數(shù)字之和代表圖 G中三角形個數(shù)的 6 倍，因為三角形由 3 個頂點組成，一個三角形會被重復計算 3×2 次。這會導致算法運行時間達到O（n3）。通過快速矩陣相乘的方法可以使運行時間下降。

3.2 外存算法

當圖的規(guī)模過大或者計算機的內(nèi)存不足以裝下整個圖時，采用外存算法是基本策略。外存算法需要解決的問 題是保證計算 的三角形個數(shù)的 準 確性，同時減 少 I／O 操作。Chu、Cheng 算法和 MGT 算法都是將圖的信息分段載入內(nèi)存進行計算。 不同的是，分別用不同的方法保證圖中三角形不被拆開。前者劃分子圖時保留了所有頂點的鄰點，后者在有向化圖之后載入子圖和頂點的鄰接表。表 1 是在 I／O 操 作 和 運 行 時 間 方 面 ，對 Chu、Cheng 算 法 DGP、RGP 和算法 MGT 在內(nèi)存使用率為 25%時，各算法在不同數(shù) 據(jù) 集 上 的 效 果 比 較 ，其 中 ，使 用 的 機 器 是 3 GHz CPU 和8 GB 的 內(nèi) 存 。MGT 算 法 在 I／O 操 作 數(shù) 和 運 行 時 間 上 都 優(yōu)于 Chu、Cheng 算法。

表1 DGP、RGP 和 MGT 的比較

3.2.1 基于圖劃分的算法

Chu 和 Cheng 提 出 了 基 于 圖 劃 分 的 外 存 圖 三 角 計 算算法，該算法首先將整個圖劃分成幾個子圖后，存在外存，子圖的規(guī)模小，就可以放入內(nèi)存。 然后依次將每個子圖調(diào)入內(nèi)存，計算當前子圖中的三角形數(shù)量。為了保證圖劃分后不會將三角形拆開，每個子圖實際上也保留了當前部分中所有頂點的鄰點，如圖 1、圖 2 所示。 根據(jù)劃分圖的方法 ，Chu 和 Cheng 有 兩 種 方 法 ：DGP （deterministic graph partition）和 RGP（randomized graph partitioning）。 前 者 采 用確定方法劃分子圖，后者采用隨機方法劃分子圖。 劃分子圖是一個難題，如果某部分子圖的鄰點很多，會使算法的時空效率變高。

圖1 基于圖劃分算法的原圖

3.2.2 有效 I／O 算法

Hu X C 和 Tao Y F 設 計 了 一 種 有 效 I／O 算 法 ，計 算 三角 形 算 法 MGT（massive graph triangulation），這 是 針 對 靜 態(tài)的圖。這個算法與 Chu 的算法有明確的不同。他們將無向圖以有向圖的形式表現(xiàn)出來，如圖 3所示。有向圖的有向邊是根據(jù)無向圖頂點的度和編號設置指向的。例如，當頂點 a的度小于 b的度或者 a的度等于 b的度但 a的編號小于 b 的 編號，定義 a＜b，此時 無 向邊｛a，b｝在 有 向 化后 是 a 指 向 b。無 向 三 角 形 ?uυw變 為 有 向 三 角 形，當 u＜υ＜ w，其 中 ，頂 點 u 被 稱 為 （cone vertex 錐 頂 點 ），邊 ｛υ，w｝被 稱為（pivot edge 中樞邊），如圖 4 所示。 算 法 的 準 備 工 作 是 將無向圖根據(jù)規(guī)則進行有向化，并以鄰接表的形式存儲，每一個頂點的鄰接表只存它的出—鄰居（即它指向的頂點）。MGT算法是逐步將有向圖中的邊載入內(nèi)存，根據(jù)需要從外存載入關聯(lián)的頂點，計算出三角形的數(shù)量。具體過程是：

·將有向圖中的一部分邊載入內(nèi)存；

·得出當前內(nèi)存中的邊所在的頂點；

· 對于每一個頂點 υ，從外存中得到它的鄰接表（出—鄰接表），將其出—鄰居與內(nèi)存中的頂點做交集。 將頂點υ到交集得到的頂點所成的邊與當前載入內(nèi)存中的有向圖的邊做并集，找出其中以 u為錐頂點的三角形個數(shù)，并釋放相應的空間。

MGT 算法可以正確地找出所有的三角形，因為第一步保證了每一條有向圖的邊都可以在一個獨特的迭代中載入內(nèi)存。同時第二步保證了可以找出以當前載入內(nèi)存的邊為中樞邊的三角形。MGT 算法在 I／O 和 CPU 上都非常高效。

圖2 基于圖劃分算法劃分后的圖

圖3 無向圖變?yōu)橛邢驁D

圖4 有向三角形

3.3 分布式算法

由于分布式算法的普及，一些研究使用 MapReduce算法計算圖三角。目前使用 MapReduce 框架的算法是基于圖劃分來分析問題的。在某些方面加快了計算算法，但同時也出現(xiàn)了一些問題。接下來介紹 3種基于MapReduce 框架的算法。這 3 個算法有一個共同的基礎，是圖的分割。圖的分割算法是先將頂點均分為p個部分（partition），V=V1∪V2∪ … ∪Vp，其 中 ，當 i≠j 時 ，Vi∩Vj=Φ 。 同 時 定 義 Vijk=Vi∪ Vj∪ Vk，Eijk= ｛（u，w ）∈ E ：u，w ∈Vijk｝，Gijk= （Vijk，Eijk）。Gijk叫 做 3-partition ，Gij是 2-partition ，Gi是 1-partition ，Gijk和 Gij的 含 義 如 圖 5 、圖 6 、圖 7 所 示 。GP算法是 三 角 形 計 算 在 MapReduce 上 的 初 次 應 用 ，GP 算法有很多冗余計算。TTP 算法發(fā)現(xiàn) GP 算法有很多冗余計算，原因是在 map 階段輸出了重復的邊。為了避免GP 算法冗余計算的產(chǎn)生，TTP 算法定義了 3 個 類型的三 角 形 。CTTP （colored triangle type partition ）算 法 是 針 對GP 算 法 的 “curse of the last reducer”而 被 提 出 的 ，避 免了 不 均 衡 。表 2 是 在 時 間 和 每 輪 MapReduce 中 數(shù) 據(jù) shuffle大 小 上 ，對 GP、TTP、CTTP 算 法 的 比 較 。運 行 平 臺 是Hadoop，集群由 40 臺機器組成 ，每臺機器的內(nèi)存為 4 GB。由表 2 可見，CTTP 算法在時間和空間上都優(yōu)于GP、TTP算法。

圖5 頂 點 平 均 分 為 p 個 部 分 （p=4 ）

圖6 3-partition Gijk

圖7 2-partition Gij

表2 GP、TTP、CTTP 算法的比較

3.3.1 GP 算法

Suri 和 Vassilvitskii 使 用 MapReduce 框 架 提 出 了 GP（graph partition）算 法 。算法的第一步是將圖中的頂點劃分為 p 個 部 分 ，Gi=（Vi，Ei），其 中 ，0＜i≤p，所 以 每 個 部 分 含 有 幾乎相同數(shù)目的頂點。GP算法使用內(nèi)存算法計算每一個3-partition Gijk中 三 角 形 的 數(shù) 目 ，其 中 ，0＜i＜j＜k≤p。最 后 根據(jù)三角形的頂點是否被分到同一個部分，將結果整合起來，得出最終的結果。如果三角形的 3個頂點都出現(xiàn)在同一 個 部 分 中 ，那 么 對 于 3-partition Gijk，此 三 角 形 便 被 計 算了3次。

3.3.2 TTP 算法

Park 和 Chung 針 對 GP 算 法 的 不 足 提 出 了 TTP（triangle type partition）算 法 。Park 和 Chung 認 為 GP 算 法有很多冗余計算，比如上面提到一個三角形可能被計算多次。他們發(fā)現(xiàn)三角形被計算多次的原因是，在 map 階段輸出了重復的邊。為了避免這個情況的產(chǎn)生，TTP 算法定義了3種類型的三角形。第1類三角形是三角形的3個點在同一個部分中；第2類三角形任意兩個頂點在同一個部分中，另一個在其他部分中；第 3 類三角形是指 3 個頂點都在不同的部分中。GP 算法就是重復計算了第 1類和第2 類三角形。TTP 算法為了避免過多的重復計算，定義了 inner-edge：邊 的 兩 個 頂 點 在 一 個 部分中 ，相 反 的 即 是outer-edge。圖 8 表 示 不 含 inner-edge 的 3＇-partition。TTP算 法 在 2-partition 中 計 算 第 1 類 、 第 2 類 三 角 形 ，在3 ＇-partition 中 計 算 第 3 類 三 角 形 ，因 此 減 少 了 冗 余 計 算 ，減少了時間復雜度。

3.3.3 CTTP 算法

Park 和 Silvestri針對 GP 算法的 “curseofthelast reducer”，提 出 了 CTTP（colored triangle type partition）算 法 ，是 第 一 個保 證 了 每 個 reducer 的 最 大 輸 入 的 算 法 。該 算 法 是 在MapReduce 的 計 算 模 型 MR（m，M）中 提 出 來 的 ，其 中 ，m 是每個 mapper或者 reducer需要的空間，M 是整個計算中需要的空間。本算法進行 R 次 MapReduce 過程。CTTP 算法從 4-wise 獨 立 族 函 數(shù) 中 隨 機 選 擇 一 個 顏 色 函 數(shù) h（·），進 行頂點劃分。CTTP 算法在 TTP 算法基礎上，將問題分解為子 問 題 。 子 問 題 分 為 兩 類 ： 一 類 是 （i， j，k）子 問 題 ，用 來 計 算 第 3 類 三 角 形 ；另 一 類 是（i，j）子 問 題 ，用來計算第 1 類和第 2 類三角形。CTTP 通過均勻地將 K個 子 問 題 分 配 給 R=pE／M round 的 方 法 ，解 決 一 個 子 問 題只需要一個 reducer的問題。如果 R 不是 2 或者 3，那么每一 個 round 解 決 K／R 個 子 問 題 。這 個 算 法 保 證 了 每 一 個mapper發(fā)出同樣數(shù)量的數(shù)據(jù)對。因此這個算法避免了被一些慢的 mapper延遲了計算。

4 近似計算圖三角

由于準確計算圖三角的時空復雜度很大，同時很多應用只需要近似得到圖三角的數(shù)量，所以近年來近似算法得到了很多關注。本文將近似計算圖三角算法分為輔助算法、非流式算法和流式算法 3個類別進行介紹。

圖8 3＇-partitionGijk＇

4.1 輔助算法

輔助算法是指這類算法經(jīng)常被其他計算圖三角算法引用，常常作為其他算法的一部分。

4.1.1 DOULIN 算法

Tsourakakis C E ，Kang U，Miller G L 和 Faloutsos C發(fā) 明 了 DOULIN［14］算 法 。DOULIN 算 法 不 是 處 于 其 他 計 算三角形算法的對立面，而是處于所有算法的友好面。不論圖能裝進內(nèi)存還是裝不進，它都非常的實用。DOULIN 對每一個邊都投擲一枚硬幣，此邊被保留的可能性是 p，被刪除的可能性是 1-p。在最后剩下的圖中找到的三角形的個數(shù)乘以 1／p3就是對原圖三角形個數(shù)的估計。

4.1.2 Colorful Function 算法

Colorful Funtion（顏 色 函 數(shù) ）［15］算 法 為 圖 中 每 個 頂 點 分配一種顏色 ，總的顏 色數(shù)是 N=1／p，其中，p 是一個小于 1的參數(shù)。當一個邊的兩個頂點被分配同一種顏色時，這個邊稱作是單色的。然后從所有的單色邊中采樣，計算采樣到的單色邊組成的三角形的個數(shù)，最后將計算的個數(shù) 除以 p2，得 出近似估計的三角形個數(shù)。這個算法的關鍵點是關聯(lián)采樣的邊。

4.2 靜態(tài)算法

靜態(tài)算法是基于靜態(tài)圖的，適用于離線計算。目前近似計算的靜態(tài)算法只在單機上。在此方向上的研究較少，突破也很少，以下介紹的兩種方法是有特點的算法?；诙鹊捻旤c劃分的算法實現(xiàn)了時間空間更低的復雜度。隨機矩陣跡算法采用了蒙特卡洛模擬方法。這兩種方法均與其他方法有明顯的區(qū)別。

4.2.1 基于度的頂點劃分算法

Kolountzakis M N［16］等 人 研 究 發(fā) 現(xiàn) ，基 于 度 對 頂 點 進行劃分，能得出在計算三角形時更小的運行時間上界。因為每個三角形都對應一個三元組，于是他們構造了一個三元組集合 U，這個三元組集合包括了所有的三角形。在這個集合里，均勻地選出一些三元組，標記為 1 到 s。當?shù)?i個三元組被采樣時，如果它是一個三角形，那么 Xi為 1；如果不是，則賦值為 0。由于是均勻地選取，并且一共得出 t＇個 三 角 形 ，那 么 E（Xi）=t＇／|U|。因 為 每 個 Xi都 是 獨 立 的 ，所 以通過切諾夫界可以得到：

由于|U|≤n3，所 以 運 行 時 間 是 O（n3lgn／（te2））。根 據(jù) 度 劃分 頂 點 得 出 了|U|更小的上界。理由是：對 于 一 個 包 含 u 的三 元 組 （u，υ，w），如 果 ｛u，υ｝、｛u，w｝∈E，這 些 三 元 組 中 含 有 u的 個 數(shù) 最 多 是 d（u）2。 如 果｛υ，w｝∈E，那 么 三 元 組 中 含 有 u的個數(shù)最多是 m。當 d（u）2＞m 時，后者的界限更緊。所以，當頂 點 的 度 小 于 m1／2時 ，那 么 它 屬 于 低 度 頂 點 ，三 元 組 中 含有 低 度 頂 點 的 三 角 形 的 個 數(shù) 最 多 是 m3／2。當 所 有 頂 點 度 之和是 2m 時，三元組中含有高度頂點的三角形的個數(shù)最多是 2m3／2。 結 合 起 來 ，|U|的 上 界 是 3m3／2，所 以 得 到 |U|≤O（m3／2），時 間 上 界 是

4.2.2 隨機矩陣跡算法

Avron H［17］采 用 隨 機 矩 陣 跡 的 方 法 去 估 計 大 圖 中 三角形的個數(shù)。該方法依據(jù)的是準確計算三角形算法里的矩 陣 相 乘 算 法 ，采 用 Monte-Carlo 模 擬 來 估 算 三 角 形 個數(shù) 。每 一 個 樣 本 需 要 O（E）的 時 間 ，需 要 O（e-2lg（1／δ）ρ（G）2）個 樣 本 才 能 保 證 （ε，δ）-approximation，其 中 ，ρ（G）是 對 圖 G稀 疏 的 一 種 測 量。這個算法很高效，只需要 O（V）的空間和O（lg2|V|）個 樣 本 就 能 達 到 一 個 很 好 的 估 算 。一 個 維 數(shù) 高 的矩陣的立方計算量很大，所以這個算法生成一個隨機向量x=（xk）， 其 中 ，xi～N（0，1）（ 正 態(tài) 分 布 ）。 將 y 賦 值 為 Ax，Ti=（yTAy）／6，循 環(huán) M=|γln2n|次 ，最 后 三 角 形 的 個 數(shù) 估 計 為

4.3 流式算法

流式算法基于動態(tài)圖流，與靜態(tài)算法相比，適用于在線計算。圖流有不同形式，主要分為任意流（arbitrary streams）和事件流（incidence streams）兩類。在任意流中，邊在流中是不重復的，且是以任意順序出現(xiàn)的；在事件流中，邊是按照每個頂點的鄰邊出現(xiàn)的，例如，首先頂點 υ1的所有鄰點出現(xiàn)，接著 υ2的所有鄰點出現(xiàn)。υ1，υ2，…，υn的順序是由輸入方確定的。根據(jù)算法通過流的次數(shù)，可以將算法又分為 one-pass算法和 multiple-passes 算法。

下 面 介 紹 一 個 multiple-passes 采 樣 三 角 形 的 算 法 ，這里 的 流 是 任 意 流 ，算 法 是 Buriol L S［18］提 出 的 3-passes 算法 ：將流中所有邊的數(shù)目計算出來，為|E|；從 流 中 均 勻 選 擇一條邊 e=｛a，b｝，也均勻選擇出一個頂點 υ，這個頂點屬于 V＼｛a，b｝；如果｛a，υ｝和｛b，υ｝都屬于 E，計數(shù) β=1，否 則 計 數(shù) β=0。最后 返 回 β值 。這 個 算 法 中 有 一 定 數(shù) 目 的 估計器（estimator），每個估計器得到一個 β值，求出期望 E［β］后 ，三 角形的個數(shù) T ＇就 估 算 為 E ［β］·|E|·（|V|-2）／3 。

multiple-passes 算 法 可 以 合 成 為 one-pass 算 法 ，Buriol L S 將 3-passes 算 法 合 成 的 1-pass 算 法 是 ：隨 機 取一個頂點 υ，并在流中采樣一條邊｛a，b｝，如果能在接下來的流 中 檢 測 到 邊 ｛a，υ｝和 ｛b，υ｝，則 三 角 形 計 數(shù) ，否 則 不 計 數(shù) 。multiple-passes 算 法 的 消 耗 多 于 one-pass 算 法［30］。

下面介紹 3 種 one-pass算法：基于鄰居采樣（Neighborhood sampling）算 法 、基 于 2-path 和 圖 稀 疏 的 算 法 和 TRIEST 算法，都與采樣有關。但由于采樣方法各不相同，3 種算法的時空消耗顯而易見?；?2-path 和圖稀疏的算法需要存儲多個稀疏圖，所以空間消耗很大，TRIEST 算法對每條邊的到來都進行一次鄰點交集計算，所以時間消耗很大。3種算法的準確率也有差異。表 3是 3個算法準確度的比較。對于幾種不同的數(shù)據(jù)集，并沒有完全優(yōu)勢的算法。可見對于含有不同數(shù)據(jù)意義的應用，需要采用不同的算法。

表3 3種流式算法的準確度比較

4.3.1 基于鄰居采樣算法

Pavany A 和 Tangwongsan K［19］等 人 設 計 了 一 個 時 間 空間效率都挺高的圖流算法。這個算法是基于鄰居采樣的one-pass算法：首先從流中隨機采樣一條邊，然后采樣和該邊有共同頂點的邊。N（e）表示在流中與邊 e 相鄰，但是在 e邊 后 面 到 來 的 邊 。其中，c=c（e）=|N（e）|。 數(shù)據(jù)以塊的形式到達，塊的大小是 w。對于每一個邊的到來，設置 r個估計器，以 m／（w+m）的概率保留這條邊。然后采樣邊的鄰邊，以 c+（e）／（c-（e）+ c+（e））的 概 率 從 N（e）∩B 采樣一條邊。最后判斷這兩條邊能否與后來的邊組成一個三角形。這個算法的時間空間復雜度都是 O（r+w）。

4.3.2 基于 2-path 和圖稀疏的算法

Bulteau L 和 Froese V［20］等 人 設 計 了 一 個 基 于 2-path采樣和圖稀疏的方法，來估計動態(tài)增刪圖流中三角形的數(shù)量，采用的是 one-pass。相對基礎圖流采樣對刪除邊后采樣的子圖是否仍存在的未知，圖稀疏能處理邊的刪除。 該算法 最 大 的 挑 戰(zhàn) 是 顯示 了 稀 疏 圖 中 的 2-path 采樣 幾 乎 等 同于 原 圖 的 2-path 采 樣 。 隨 機 選 擇 了 大 量 的 2-path，與 用 其中能組成三角形的 2-path 數(shù)量去估計傳遞系數(shù)。對于圖流中 每 一 個 增 刪 邊 的 到 來 會 更 新 SME （second moment estimator），圖流完全通過將返回整體 2-path 值 。與此同時，用 顏 色 散 列 （coloring hash）函 數(shù) 族 去 稀 疏 圖 流 ，得 到 數(shù) 個稀疏圖。對于 每一個稀 疏 圖 ，隨 機采樣一 定 數(shù)目的 2-path判斷是否組成三角形，并計數(shù)。最后用稀疏圖中采樣的2-path 中 能 組 成 三 角 形 的 數(shù) 量 與 采 樣 的 2-path 數(shù) 量 的 比值 ，與 整體 2-path 數(shù) 量 比 較 ，去 估 計 整 個圖 流 中 三角 形 的數(shù)量。該算法得到了圖流中計算三角形復雜度的下界。

4.3.3 TRIEST 算法

由于基于采樣的流算法，事先都要確定邊采樣的概率p，所以會造成一些問題。如在存儲空間有限的情況下，需要知道流的規(guī)模；采樣留下的邊的規(guī)模會增長，如果 p 較大，會溢出存儲空間，如果 p 較小，得到的結果是次優(yōu)的；即使設定了特定的 p，使在流結束時恰好裝滿存儲空間，得到的結果也不是最好的。TRIEST 算法針對這些問題提出了解決方法。

TRIEST［21］算 法 是 在 one-pass 下 的 ，相 對 于 只 有 增 加 邊的 流 算 法 MSCOT［22］，它 還 有 刪 除 邊 的 流 ，時 刻 計 算 三 角 形的數(shù)量，并且存儲空間是固定的。該算法采用水庫采樣（reservoir sampling）和 隨 機 配 對 （random pairing）兩 種 采 樣方案使得存儲空間盡可能多地被利用。由于是時刻計算三角形的數(shù)量，圖采用了時間標記 Gt，每到來一條邊，時間增長一個單位。該算法默認對一條邊的刪除一定是在對這條邊增加之后。如果設定的內(nèi)存大小是 M，對于當前流入的插 入 邊 e=｛a，b｝，如 果 之 前 圖 的 大 小 Gt-1不 大 于 M，當 前 邊被保留。如果之前的圖的大小已經(jīng)達到過 M，這時以 M／t的概率決定直接舍棄當前邊，或者選擇刪除之前圖中的一條邊，且插入當前邊，這是標準水庫采樣的應用。若插入了當前邊，便計算當前邊是否組成三角形。對于當前流入的邊是刪除邊，計算當前邊是否在之前流入的圖中組成三角形，如果組成，便減去相應的數(shù)量。為保證存儲空間在增加邊和刪除邊的時 候都能 充分利用設 定的內(nèi) 存，TRIEST 基于隨機配對做了補償策略，刪除邊需要被未來的插入邊補償 。設 置 了 兩 個 計 數(shù) 器 din和 dout。如 果 之 前 流 入 圖 的 大 小Gt-1已經(jīng)達到內(nèi)存大小 M，當 前 邊 是 一 條 刪 除 邊 ，如 果 此 刪除 邊 仍 在 Gt-1中 ，din加 一 ；如 果 此 刪 除 邊 之 前 被 替 換 出 去 ，不 在 Gt-1中 ，dout加 一 。 之 后 到 來 的 增 加 邊 會 根 據(jù) din和 dout的 值 被 保 留 或 不 被 保 留 。如 果 din、dout之 和 等 于 零 ，增 加 邊采 用 標 準 的 水 庫 采 樣 方 案 。如 果 不 等 于 零 ，便 以 din／（din+dout）的 概 率 保 留 增 加 邊 ，如 果 保 留 ，din-1，否 則 dout-1。TRIEST算法在完全動態(tài)的圖流中做到了無偏、低方差、高質(zhì)量的估計。并且在有數(shù)十億條邊的大圖中有更小的平均估計誤差。

5 性能比較

綜上所述，在計算圖三角的算法中，準確計算圖三角與近似計算圖三角算法有區(qū)別也有聯(lián)系。準確計算中，點邊迭代算法和矩陣相乘算法是最基礎的算法。但是對于數(shù)據(jù)量越來越大的圖來說，在普通計算機上運行這些算法的時間空間復雜度非常高，并不適用。基于它們的改進算法FCNI提供了快速實現(xiàn)求共同鄰點的方法，也使在大規(guī)模圖中計算三角形的運行時間大大提高，但是實驗機器成本很高。外存計算算法很好地解決了圖規(guī)模過大，普通機器內(nèi)存不夠用的問題。Chu 和 Cheng 提出的基于圖劃分的算法，一定程度上避免了內(nèi)存小的問題，但是對于不均勻的圖來說，劃分是一個難 題。Hu 提出的 有 效 I／O 的算 法 ，巧妙避免了重復計算，時空復雜度為目前最好，且可以移植到不同平臺上進行計算。GP、TTP 和 GTTP 采用分布式框架為圖三角算法提供了新的平臺，提供了更多的內(nèi)存，又可以并行，使時空復雜度減少。TTP、GTTP 分別針對 GP 的重復計算和冗余等待時間做了改進，在 MapReduce 框架下取得了好的效果。近似計算中，DOULION 算法和顏色函數(shù)對采樣很有幫助，被很多其他算法運用。靜態(tài)圖的計算圖三角算法中，基于度分割和隨機矩陣跡是有特點的方法，但是空間消耗都較大、效率不高。部分算法是基于動態(tài)圖流 的 ，multiple-passes 算 法 時 空 消 耗 大 ，更 多 算 法 采 用 的 是one-pass。近似算法大部分采 用采樣 方法，各有 優(yōu)缺點 。 Pavany A 提出的鄰居采樣算法的空間效率很高，但是參數(shù)過多。Laurent提出的基 于 2-path 和圖稀疏 的 算法效果 一般，但首次達到了每邊的固定處理時間。TRIEST 算法是目前準確率最高的，且可以在固定內(nèi)存中時刻計算圖流中三角形數(shù)量。近似計算應用范圍很廣，并且較準確計算來說需要的時空復雜度明顯降低，但準確度是一個關鍵問題。大部分近似算法是在準確計算的基礎上進行改進的，如矩陣跡算法是在矩陣相乘算法上加入了蒙特卡洛方法。上文幾種采樣算法是在點邊迭代算法的基礎上加入了采樣策略。

本文將近幾年的計算圖三角算法按準確計算和近似計算進行了比較，見表 4、表 5。

表4 準確計算三角形算法比較

表5 近似計算三角形算法比較

6 結束語

面對社會網(wǎng)絡的快速發(fā)展，圖的規(guī)模越來越大，關于圖的問題也越來越多樣化。選擇合適圖存儲模型和計算模型對圖的計算很重要。根據(jù)不同的問題需要選擇不同的解決方案，面對新的應用也要研究出新的方法。近年來出現(xiàn)的高效的分布式系統(tǒng)為圖三角算法提供了新的平臺。基于分布式的三角形計算算法的可行性越來越大，這將會成為三角形計算的下一個研究重點。

［1］ THOMAS S.Algorithmic aspects of triangle-based network analysis［J］.Phd in Computer Science，2007：26-29.

［2］ COPPERSMITH D ，WINOGRAD S.Matrix multiplication viaarithmetic progressions ［J］.Journal of Symbolic Computation，1990，9（3）：251-280.

［3］ ALON N，YUSTER R，ZWICK U.Finding and counting given length cycles［J］.Algorithmica，1997，17（3）：209-223.

［4］ THOMAS S，WAGNER D.Finding，counting and listing all triangles in large graphs，an experimental study ［C］／／The 4th International Workshop，May 10-13，2005，Santorini Island，Greece.New York：Springer，2005.

［5］ CHIBA N，NISHIZEKI T.Arboricity and subgraph listing algorithms［J］.Siam Journal on Computing，1985，14（1）：210-223.

［6］ KUMAR R，RAGHAVAN P，RAJAGOPALAN S，et al.The web as a graph：measurements，models，and methods ［C］／／The 5th Annual International Conference，July 26-28，1999，Tokyo，Japan.New York：ACM Press，2000：1-17.

［7］ LATAP M.Theory and practice of triangle problems in very large （sparse （power-law）） graphs［EB／OL］. ［2006-09-20］.http：／／arxiv.org／pdf／cs／0609116.pdf.

［8］ SEVENICH M，HONG S，WELC A，et al.Fast in-memory triangle listing for large real-world graphs［C］／／The 8th Workshop on Social Network Mining and Analysis SNAKDD，August 24-27，2008，Las Vegas，NV，USA.New York：ACM Press，2014.

［9］ CHU S，CHENG J.Triangle listing in massive networks and its applications ［C］／／The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， August 21-24，2011，San Diego，CA，USA.New York：ACM Press，2011：672-680.

［10］HU X C ，TAO Y F.I／O efficient algorithms on triangle listing and counting ［J］.ACM Transactions on Database System，2014，39（4）：1-30.

［11］SURI S，VASSILVITSKII S.Counting triangles and the curse of the last reducer ［C］／／The 20th International Conference on World Wide Web，March 28-April 1，2011，Hyderabad，India.New York：ACM Press，2011：607-614.

［12］PARK H M，CHUNG C W.An efficient MapReduce algorithm for counting triangles in avery large graph ［C］／／ACM Conference of Information and Knowledge Management， October 27-November 1，2013，San Francisco，CA，USA.New York：ACM Press，2013：539-548.

［13］PARK H M，SILVESTRI F，KANG U，et al.MapReduce triangle enumeration with guarantees［C］／／ACM Conference of Information and Knowledge Management，November 3-7，2014，Shanghai，China.New York：ACM Press，2014.

［14］TSOURAKAKIS C E，KANG U，MILLER G L，et al.DOULIN：counting triangles in massive graphs with acoin ［C］／／The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，June 28-July 1，2009，Paris，F(xiàn)rance.New York：ACM Press，2009：837-846.

［15］PAGH R，TSOURAKAKIS C E.Colorful triangle counting and Mapreduce implementation ［J］.Information Processing Letters，2011，112（7）：277-281.

［16］KOLOUNTZAKIS M N，MILLER G L，PENG R，et al.Efficient triangle counting in large graphsvia degree-based vertex partitioning［J］.Internet Mathematics，2010，8（1-2）：15-24.

［17］AVRON H.Counting triangles in large graphs using randomized matrix trace estimation ［J］.In Large-Scale Data Mining：Theory and Applications （KDD Workshop），2010.

［18］BURIOL L S，F(xiàn)RAHLING G，LEONARDI S，et al.Counting triangles in data streams ［C］／／The 25th ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems，June 26-28，2006，Chicago，Illinois，USA.New York：ACM Press，2006：253-262.

［19］PAVANY A，TANGWONGSAN K，TIRTHAPURAZ S，et al. Counting and sampling triangles from a graph stream ［J］. Proceedings of the Vldb Endowment，2013，6（14）：1870-1881.

［20］BULTEAU L，F(xiàn)ROESE V，KUTZKOV K，et al.Triangle counting in dynamic graph streams ［EB／OL］. ［2015-07-14］.http：／／itu.dk／people／konk／papers／dtc_full.pdf.

［21］STEFANI L D，EPASTO A，RIONDATO M，et al.TRIEST：counting local and global triangles in fully-dynamic streams with fixed memory size［EB／OL］.［2016-02-24］.http：／／arxiv.org／abs／1602.07424.

［22］LIM Y，KANG U.MASCOT：memory-efficient and accurate sampling for counting local triangles in graph streams ［C］／／The 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD，August 10-13，2015，Hilton，Sydney.New York：ACM Press，2015：685-694.

Research progress of triangle counting in big data

JIN Hongqiao，DONG Yihong
Faculty of Electrical Engineering and Computer Science，Ningbo University，Ningbo 315211，China

Counting triangles in a graph is an important step to calculate the clustering coefficient and the transitivity ratio of the network，which is widely used in important role identification，spam detection，community discovery，biological detection etc.Counting triangles algorithm is mainly faced with two major problems of space-time consumption and accuracy.The representative algorithm of the counting triangles in the big graph was introduced.There existed two kinds of algorithms，which were exact counting algorithm and approximate counting algorithm.Exact counting algorithms were divided into internal memory algorithm，external memory algorithm and distributed algorithm.The space-time consumption or I／O consumption of exact counting algorithm was very large. Approximate counting algorithms were divided into auxiliary algorithm，static algorithm and streaming algorithm.In the end，the counting triangles algorithms were summarized.

exact counting，approximate counting，triangle，graph

TP391

：A

10.11959／j.issn.1000-0801.2016169

金宏橋（1993-），女，寧波大學信息科學與工程學院碩士生，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘。

董一鴻（1969-），男，博士，寧波大學教授，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘和人工智能。

2016-04-05；

：2016-06-12