金宏橋，董一鴻

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

綜述

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

金宏橋，董一鴻

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

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

準(zhǔn)確計(jì)算；近似計(jì)算；三角形；圖

1 引言

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

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

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

2 圖三角的基本概念

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

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

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

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

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

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

3 圖三角的準(zhǔn)確計(jì)算

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

3.1 內(nèi)存算法

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

3.1.1 迭代算法

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

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

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

3.1.2 矩陣相乘算法

在 矩 陣 相 乘 （matrix-multiplication）算 法 中 ，假 設(shè) A 是圖 G 的鄰接矩陣，A3對(duì)角線上的數(shù)字分別代表對(duì)應(yīng)頂點(diǎn)所在三角形個(gè)數(shù)的兩倍。A3對(duì)角線上的數(shù)字之和代表圖 G中三角形個(gè)數(shù)的 6 倍，因?yàn)槿切斡?3 個(gè)頂點(diǎn)組成，一個(gè)三角形會(huì)被重復(fù)計(jì)算 3×2 次。這會(huì)導(dǎo)致算法運(yùn)行時(shí)間達(dá)到O（n3）。通過(guò)快速矩陣相乘的方法可以使運(yùn)行時(shí)間下降。

3.2 外存算法

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

表1 DGP、RGP 和 MGT 的比較

3.2.1 基于圖劃分的算法

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

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

3.2.2 有效 I／O 算法

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

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

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

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

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

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

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

圖4 有向三角形

3.3 分布式算法

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

圖5 頂 點(diǎn) 平 均 分 為 p 個(gè) 部 分 （p=4 ）

圖6 3-partition Gijk

圖7 2-partition Gij

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

3.3.1 GP 算法

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

3.3.2 TTP 算法

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

3.3.3 CTTP 算法

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

4 近似計(jì)算圖三角

由于準(zhǔn)確計(jì)算圖三角的時(shí)空復(fù)雜度很大，同時(shí)很多應(yīng)用只需要近似得到圖三角的數(shù)量，所以近年來(lái)近似算法得到了很多關(guān)注。本文將近似計(jì)算圖三角算法分為輔助算法、非流式算法和流式算法 3個(gè)類別進(jìn)行介紹。

圖8 3＇-partitionGijk＇

4.1 輔助算法

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

4.1.1 DOULIN 算法

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

4.1.2 Colorful Function 算法

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

4.2 靜態(tài)算法

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

4.2.1 基于度的頂點(diǎn)劃分算法

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

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

4.2.2 隨機(jī)矩陣跡算法

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

4.3 流式算法

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

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

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

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

表3 3種流式算法的準(zhǔn)確度比較

4.3.1 基于鄰居采樣算法

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

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

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

4.3.3 TRIEST 算法

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

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

5 性能比較

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

本文將近幾年的計(jì)算圖三角算法按準(zhǔn)確計(jì)算和近似計(jì)算進(jìn)行了比較，見(jiàn)表 4、表 5。

表4 準(zhǔn)確計(jì)算三角形算法比較

表5 近似計(jì)算三角形算法比較

6 結(jié)束語(yǔ)

面對(duì)社會(huì)網(wǎng)絡(luò)的快速發(fā)展，圖的規(guī)模越來(lái)越大，關(guān)于圖的問(wèn)題也越來(lái)越多樣化。選擇合適圖存儲(chǔ)模型和計(jì)算模型對(duì)圖的計(jì)算很重要。根據(jù)不同的問(wèn)題需要選擇不同的解決方案，面對(duì)新的應(yīng)用也要研究出新的方法。近年來(lái)出現(xiàn)的高效的分布式系統(tǒng)為圖三角算法提供了新的平臺(tái)?；诜植际降娜切斡?jì)算算法的可行性越來(lái)越大，這將會(huì)成為三角形計(jì)算的下一個(gè)研究重點(diǎn)。

［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-），女，寧波大學(xué)信息科學(xué)與工程學(xué)院碩士生，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘。

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

2016-04-05；

：2016-06-12