• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2016-06-28 13:19:17金宏橋董一鴻
    電信科學 2016年6期
    關鍵詞:鄰點子圖頂點

    金宏橋,董一鴻

    (寧波大學信息科學與工程學院,浙江 寧波 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

    猜你喜歡
    鄰點子圖頂點
    過非等腰銳角三角形頂點和垂心的圓的性質(zhì)及應用(下)
    圍長為5的3-正則有向圖的不交圈
    臨界完全圖Ramsey數(shù)
    關于頂點染色的一個猜想
    山東科學(2018年6期)2018-12-20 11:08:58
    基于頻繁子圖挖掘的數(shù)據(jù)服務Mashup推薦
    特殊圖的一般鄰點可區(qū)別全染色
    不含2K1+K2和C4作為導出子圖的圖的色數(shù)
    笛卡爾積圖Pm×Kn及Cm×Kn的鄰點可區(qū)別E-全染色研究
    頻繁子圖挖掘算法的若干問題
    采礦技術(2011年5期)2011-11-15 02:53:12
    邊染色 9-臨界圖邊數(shù)的新下界
    欧美日韩一区二区视频在线观看视频在线| 日韩大片免费观看网站| 超碰av人人做人人爽久久| 国产精品熟女久久久久浪| 91精品国产九色| 久久这里有精品视频免费| 免费av不卡在线播放| 哪个播放器可以免费观看大片| a级毛片免费高清观看在线播放| 18禁裸乳无遮挡免费网站照片| 特大巨黑吊av在线直播| 欧美+日韩+精品| 91午夜精品亚洲一区二区三区| 久久久成人免费电影| 成人漫画全彩无遮挡| 午夜老司机福利剧场| 久久精品久久久久久久性| 成年女人在线观看亚洲视频| 色网站视频免费| 日本午夜av视频| 激情 狠狠 欧美| a 毛片基地| 免费少妇av软件| 免费观看av网站的网址| 五月玫瑰六月丁香| 国产老妇伦熟女老妇高清| 国产亚洲av片在线观看秒播厂| 伦理电影大哥的女人| 国产真实伦视频高清在线观看| 久久久久人妻精品一区果冻| 99热全是精品| 伦精品一区二区三区| 日韩一本色道免费dvd| 啦啦啦在线观看免费高清www| 欧美成人一区二区免费高清观看| 中文字幕人妻熟人妻熟丝袜美| 伦理电影大哥的女人| 久久精品国产自在天天线| 视频中文字幕在线观看| 亚洲av不卡在线观看| 欧美人与善性xxx| 国产极品天堂在线| 国产综合精华液| 久久久久性生活片| 十八禁网站网址无遮挡 | 日韩av在线免费看完整版不卡| 大码成人一级视频| 下体分泌物呈黄色| 97超碰精品成人国产| 男女边摸边吃奶| 九色成人免费人妻av| 男人和女人高潮做爰伦理| 亚洲国产毛片av蜜桃av| 身体一侧抽搐| 欧美国产精品一级二级三级 | 成年女人在线观看亚洲视频| 亚洲精品自拍成人| 人人妻人人添人人爽欧美一区卜 | 国产免费福利视频在线观看| 97在线视频观看| 国产av国产精品国产| 99久国产av精品国产电影| av女优亚洲男人天堂| 国产精品一二三区在线看| 国产91av在线免费观看| 夜夜爽夜夜爽视频| 99re6热这里在线精品视频| 熟女电影av网| 国产亚洲5aaaaa淫片| 久久久成人免费电影| 激情 狠狠 欧美| 春色校园在线视频观看| 建设人人有责人人尽责人人享有的 | 插阴视频在线观看视频| 一级黄片播放器| 国产午夜精品一二区理论片| 国产极品天堂在线| 一区二区三区四区激情视频| 高清在线视频一区二区三区| 午夜福利网站1000一区二区三区| 多毛熟女@视频| 少妇熟女欧美另类| 黄色配什么色好看| 中国三级夫妇交换| 亚洲人与动物交配视频| 日韩在线高清观看一区二区三区| 美女主播在线视频| 日本一二三区视频观看| 少妇的逼水好多| 国产极品天堂在线| 日本爱情动作片www.在线观看| 极品教师在线视频| 亚洲欧美一区二区三区黑人 | 中文乱码字字幕精品一区二区三区| 中文字幕久久专区| 街头女战士在线观看网站| 久久人人爽av亚洲精品天堂 | 亚洲一级一片aⅴ在线观看| 亚洲精品成人av观看孕妇| 日韩视频在线欧美| 国产黄频视频在线观看| 亚洲成人手机| 国产高清三级在线| 亚洲精品,欧美精品| 少妇裸体淫交视频免费看高清| 亚洲av综合色区一区| 久久鲁丝午夜福利片| 日韩精品有码人妻一区| 日韩亚洲欧美综合| 少妇的逼水好多| 亚洲美女黄色视频免费看| 视频中文字幕在线观看| 99热这里只有是精品50| 亚洲精品aⅴ在线观看| 亚洲国产欧美人成| 久久久久国产精品人妻一区二区| 成人免费观看视频高清| 2018国产大陆天天弄谢| 欧美成人精品欧美一级黄| 国产精品.久久久| 最近最新中文字幕免费大全7| 国产精品久久久久成人av| 中文字幕久久专区| 欧美日韩精品成人综合77777| 一区二区三区免费毛片| 成人午夜精彩视频在线观看| 五月伊人婷婷丁香| 国产精品久久久久久精品电影小说 | 久久99热这里只有精品18| 亚洲国产最新在线播放| 另类亚洲欧美激情| 精品一区二区免费观看| 亚洲国产色片| 看免费成人av毛片| 精品久久久久久电影网| 欧美xxxx性猛交bbbb| 国产伦理片在线播放av一区| 久久久久久久久大av| 亚洲av免费高清在线观看| 国产伦精品一区二区三区四那| 国产精品国产三级专区第一集| 一级毛片久久久久久久久女| 最近最新中文字幕大全电影3| 午夜福利网站1000一区二区三区| 91在线精品国自产拍蜜月| 又爽又黄a免费视频| 寂寞人妻少妇视频99o| a级毛片免费高清观看在线播放| 婷婷色av中文字幕| 色网站视频免费| 汤姆久久久久久久影院中文字幕| 久久久成人免费电影| 午夜免费男女啪啪视频观看| 91久久精品电影网| 亚洲av.av天堂| 欧美少妇被猛烈插入视频| 欧美xxxx性猛交bbbb| 小蜜桃在线观看免费完整版高清| av在线观看视频网站免费| 成人国产av品久久久| 欧美国产精品一级二级三级 | 国产黄色视频一区二区在线观看| 大又大粗又爽又黄少妇毛片口| 午夜福利高清视频| 久久影院123| 水蜜桃什么品种好| tube8黄色片| 色综合色国产| 男人舔奶头视频| 国产国拍精品亚洲av在线观看| 美女内射精品一级片tv| 一级黄片播放器| 直男gayav资源| 国产毛片在线视频| 男的添女的下面高潮视频| 少妇人妻 视频| 成人影院久久| 亚洲高清免费不卡视频| 亚洲精品成人av观看孕妇| 老师上课跳d突然被开到最大视频| 小蜜桃在线观看免费完整版高清| av天堂中文字幕网| 国内揄拍国产精品人妻在线| 国产国拍精品亚洲av在线观看| 91久久精品国产一区二区成人| 中文字幕精品免费在线观看视频 | 亚洲三级黄色毛片| 亚洲色图av天堂| av在线观看视频网站免费| 18禁裸乳无遮挡动漫免费视频| 在线观看美女被高潮喷水网站| 精品少妇久久久久久888优播| 王馨瑶露胸无遮挡在线观看| 乱系列少妇在线播放| 直男gayav资源| 欧美高清成人免费视频www| 人人妻人人澡人人爽人人夜夜| 久久热精品热| 九九久久精品国产亚洲av麻豆| 久久久久人妻精品一区果冻| 中文字幕精品免费在线观看视频 | 欧美一级a爱片免费观看看| 免费大片黄手机在线观看| 欧美xxⅹ黑人| 精品久久久久久久久亚洲| 啦啦啦在线观看免费高清www| 日日摸夜夜添夜夜爱| 水蜜桃什么品种好| 亚洲国产精品国产精品| 午夜免费观看性视频| 久久女婷五月综合色啪小说| freevideosex欧美| 国产亚洲91精品色在线| 久久久久人妻精品一区果冻| 日韩免费高清中文字幕av| 国产精品一二三区在线看| 亚洲四区av| 色视频www国产| 国产 一区 欧美 日韩| 国产精品99久久久久久久久| 边亲边吃奶的免费视频| 草草在线视频免费看| 免费av中文字幕在线| 欧美成人一区二区免费高清观看| 久久久久国产精品人妻一区二区| 国产爽快片一区二区三区| 人妻 亚洲 视频| 91狼人影院| 亚洲第一区二区三区不卡| 亚洲精品日韩av片在线观看| 亚洲国产欧美人成| 欧美成人a在线观看| 国产亚洲一区二区精品| 乱码一卡2卡4卡精品| 国产又色又爽无遮挡免| 国产成人精品久久久久久| 黄片wwwwww| 国产亚洲最大av| 一本久久精品| 久久久久久久国产电影| 人人妻人人爽人人添夜夜欢视频 | 男人添女人高潮全过程视频| 亚洲欧美成人精品一区二区| 网址你懂的国产日韩在线| 2022亚洲国产成人精品| 99热网站在线观看| 黄色怎么调成土黄色| 亚洲国产精品成人久久小说| tube8黄色片| 久久精品国产亚洲av涩爱| 国产黄频视频在线观看| 国国产精品蜜臀av免费| 国产 精品1| 蜜桃亚洲精品一区二区三区| 久久这里有精品视频免费| 久久人妻熟女aⅴ| 日韩大片免费观看网站| 王馨瑶露胸无遮挡在线观看| 国产精品一二三区在线看| 精品亚洲成国产av| 99国产精品免费福利视频| 成人毛片60女人毛片免费| 搡女人真爽免费视频火全软件| 多毛熟女@视频| 在现免费观看毛片| 高清毛片免费看| 91精品一卡2卡3卡4卡| 日韩av不卡免费在线播放| 日韩三级伦理在线观看| 日日摸夜夜添夜夜爱| 夜夜骑夜夜射夜夜干| 九九爱精品视频在线观看| 色5月婷婷丁香| 欧美精品人与动牲交sv欧美| 成人国产av品久久久| 欧美日韩一区二区视频在线观看视频在线| 国产精品无大码| 国产视频首页在线观看| av女优亚洲男人天堂| 日本欧美视频一区| 国产白丝娇喘喷水9色精品| 国产黄色免费在线视频| 自拍欧美九色日韩亚洲蝌蚪91 | 卡戴珊不雅视频在线播放| 国产 精品1| tube8黄色片| 欧美最新免费一区二区三区| 少妇被粗大猛烈的视频| 国产综合精华液| 51国产日韩欧美| av专区在线播放| 男女免费视频国产| 丰满人妻一区二区三区视频av| 久久 成人 亚洲| 国产深夜福利视频在线观看| 不卡视频在线观看欧美| 亚洲精品亚洲一区二区| 黑人高潮一二区| 六月丁香七月| 高清毛片免费看| 国产伦在线观看视频一区| 成人毛片60女人毛片免费| 各种免费的搞黄视频| 欧美成人一区二区免费高清观看| 精品99又大又爽又粗少妇毛片| 亚洲性久久影院| 亚洲精品久久久久久婷婷小说| 在线观看三级黄色| av国产久精品久网站免费入址| 国产亚洲一区二区精品| 中国美白少妇内射xxxbb| 日韩av在线免费看完整版不卡| 有码 亚洲区| 国产片特级美女逼逼视频| 最近最新中文字幕大全电影3| 天堂中文最新版在线下载| 深夜a级毛片| 欧美日韩视频高清一区二区三区二| 性色av一级| 亚洲精品一二三| av网站免费在线观看视频| 国产成人精品婷婷| 久久久久精品性色| 国产av一区二区精品久久 | 日韩制服骚丝袜av| 插阴视频在线观看视频| av黄色大香蕉| 亚洲色图av天堂| 日韩国内少妇激情av| 国产高潮美女av| 国产精品一及| av国产久精品久网站免费入址| 精品99又大又爽又粗少妇毛片| 亚洲最大成人中文| 久久99蜜桃精品久久| 国产精品女同一区二区软件| 天堂俺去俺来也www色官网| 久久毛片免费看一区二区三区| 日韩av在线免费看完整版不卡| 中国三级夫妇交换| 国产精品熟女久久久久浪| 黄色欧美视频在线观看| 永久免费av网站大全| 五月玫瑰六月丁香| 国产免费视频播放在线视频| 人妻系列 视频| 欧美老熟妇乱子伦牲交| 久久99精品国语久久久| 深爱激情五月婷婷| 美女高潮的动态| 国产伦精品一区二区三区四那| 亚洲电影在线观看av| 99热网站在线观看| 春色校园在线视频观看| 精品亚洲成a人片在线观看 | 丰满迷人的少妇在线观看| 国产精品久久久久久av不卡| 最近中文字幕高清免费大全6| 欧美成人一区二区免费高清观看| 女人十人毛片免费观看3o分钟| 在线观看免费高清a一片| 美女xxoo啪啪120秒动态图| 欧美精品国产亚洲| 日韩不卡一区二区三区视频在线| 成人影院久久| 高清在线视频一区二区三区| 亚洲欧美精品专区久久| 性色avwww在线观看| 一级毛片aaaaaa免费看小| 日韩av不卡免费在线播放| 亚洲精品色激情综合| 国模一区二区三区四区视频| 久久精品国产a三级三级三级| www.av在线官网国产| 一区二区三区精品91| 国产一区亚洲一区在线观看| 午夜免费鲁丝| 国产69精品久久久久777片| 国产在线男女| 午夜日本视频在线| 亚洲欧洲日产国产| 99热全是精品| 亚洲精品一二三| 午夜福利网站1000一区二区三区| av免费在线看不卡| 国产精品精品国产色婷婷| 热99国产精品久久久久久7| 尤物成人国产欧美一区二区三区| 亚洲国产精品999| 插逼视频在线观看| 久久精品国产自在天天线| 美女xxoo啪啪120秒动态图| 一级av片app| 国产伦理片在线播放av一区| 久久99精品国语久久久| 天美传媒精品一区二区| 国产一级毛片在线| 国产精品99久久久久久久久| 亚洲av国产av综合av卡| 久久影院123| a 毛片基地| 欧美高清成人免费视频www| 免费播放大片免费观看视频在线观看| 亚洲aⅴ乱码一区二区在线播放| 色视频www国产| 国产成人freesex在线| 国产一区二区三区av在线| 亚洲,一卡二卡三卡| 欧美高清性xxxxhd video| 高清午夜精品一区二区三区| av又黄又爽大尺度在线免费看| 狂野欧美激情性bbbbbb| 成人午夜精彩视频在线观看| 黄片无遮挡物在线观看| 久久97久久精品| 亚洲图色成人| 全区人妻精品视频| 有码 亚洲区| 99热这里只有是精品在线观看| 亚洲欧美日韩东京热| 少妇人妻久久综合中文| 精品一区二区三区视频在线| 在线观看免费视频网站a站| 国产黄片美女视频| 亚州av有码| av女优亚洲男人天堂| 联通29元200g的流量卡| 国产精品成人在线| 国产免费视频播放在线视频| 国产高清三级在线| 天天躁夜夜躁狠狠久久av| 91在线精品国自产拍蜜月| 亚洲图色成人| 免费av不卡在线播放| 亚洲美女视频黄频| 夜夜骑夜夜射夜夜干| 成人综合一区亚洲| 中文欧美无线码| 欧美zozozo另类| 中文在线观看免费www的网站| 大话2 男鬼变身卡| 国产亚洲欧美精品永久| 熟女人妻精品中文字幕| 国产精品99久久久久久久久| 亚洲国产精品专区欧美| 春色校园在线视频观看| 久久这里有精品视频免费| 国产精品成人在线| 欧美一区二区亚洲| 亚洲美女搞黄在线观看| 久久精品熟女亚洲av麻豆精品| 老女人水多毛片| 亚洲精品自拍成人| 少妇猛男粗大的猛烈进出视频| 日韩视频在线欧美| 欧美日韩在线观看h| 亚洲精品国产av成人精品| 欧美日本视频| 少妇人妻久久综合中文| 一级黄片播放器| 波野结衣二区三区在线| 丰满乱子伦码专区| 纯流量卡能插随身wifi吗| 永久网站在线| 舔av片在线| 乱码一卡2卡4卡精品| 日产精品乱码卡一卡2卡三| 亚洲高清免费不卡视频| av视频免费观看在线观看| 国内揄拍国产精品人妻在线| 国产美女午夜福利| 夫妻性生交免费视频一级片| 国产精品免费大片| 国产精品蜜桃在线观看| 亚洲精品aⅴ在线观看| 欧美性感艳星| tube8黄色片| 精品人妻视频免费看| 色婷婷久久久亚洲欧美| 亚洲在久久综合| 2018国产大陆天天弄谢| 欧美成人精品欧美一级黄| 中文天堂在线官网| 国产av国产精品国产| av专区在线播放| 99久久精品热视频| 久久久久性生活片| 亚洲第一区二区三区不卡| 久久99热这里只频精品6学生| 日本欧美视频一区| 视频区图区小说| 日韩一区二区三区影片| 人体艺术视频欧美日本| 美女xxoo啪啪120秒动态图| 美女中出高潮动态图| 又粗又硬又长又爽又黄的视频| 99热这里只有精品一区| 我的老师免费观看完整版| 91在线精品国自产拍蜜月| 国产淫语在线视频| 日韩精品有码人妻一区| 国产 精品1| 美女脱内裤让男人舔精品视频| 青春草亚洲视频在线观看| 久久久久久久亚洲中文字幕| 观看av在线不卡| 亚洲欧美一区二区三区国产| 国产高清不卡午夜福利| 观看美女的网站| 人妻 亚洲 视频| 18禁裸乳无遮挡动漫免费视频| 特大巨黑吊av在线直播| 午夜日本视频在线| 免费观看的影片在线观看| 国产成人精品福利久久| 噜噜噜噜噜久久久久久91| 欧美97在线视频| 国产精品av视频在线免费观看| 日韩 亚洲 欧美在线| 99视频精品全部免费 在线| 久久99热这里只频精品6学生| 成人综合一区亚洲| 美女国产视频在线观看| 亚洲成人一二三区av| 男的添女的下面高潮视频| 日韩欧美精品免费久久| 亚洲欧美日韩东京热| 久久久久人妻精品一区果冻| 大又大粗又爽又黄少妇毛片口| 少妇被粗大猛烈的视频| 国产中年淑女户外野战色| 日本黄大片高清| 国模一区二区三区四区视频| 免费看光身美女| 国国产精品蜜臀av免费| 精品亚洲成国产av| 看非洲黑人一级黄片| 久久精品夜色国产| 1000部很黄的大片| 最后的刺客免费高清国语| 成人高潮视频无遮挡免费网站| 激情五月婷婷亚洲| 中文字幕久久专区| 久久久久久伊人网av| 中文字幕制服av| 国产亚洲5aaaaa淫片| 黄色视频在线播放观看不卡| 成年美女黄网站色视频大全免费 | 久久久久久久久久成人| 一级a做视频免费观看| 日本欧美视频一区| 亚洲av男天堂| 亚洲精品国产av蜜桃| 国产精品无大码| 三级国产精品片| 久久热精品热| a 毛片基地| 91久久精品电影网| 久久久色成人| 肉色欧美久久久久久久蜜桃| 丰满少妇做爰视频| 国产av精品麻豆| 六月丁香七月| 国产黄片美女视频| 国产高清有码在线观看视频| 国产精品99久久久久久久久| av一本久久久久| 美女中出高潮动态图| 国产亚洲欧美精品永久| 日韩视频在线欧美| 一边亲一边摸免费视频| 国产日韩欧美在线精品| 亚州av有码| 国产淫语在线视频| 日本猛色少妇xxxxx猛交久久| 大又大粗又爽又黄少妇毛片口| 成人国产av品久久久| 最近最新中文字幕免费大全7| 亚洲av在线观看美女高潮| 国产伦精品一区二区三区视频9| 免费黄网站久久成人精品| 日韩精品有码人妻一区| 国产精品一二三区在线看| 国产黄频视频在线观看| 妹子高潮喷水视频| av免费观看日本| 亚洲精品乱码久久久v下载方式| 又大又黄又爽视频免费| 久久久久久久大尺度免费视频| 日韩中字成人| 国产爽快片一区二区三区| 亚洲怡红院男人天堂| 亚洲精品乱码久久久v下载方式| 亚洲国产av新网站| 精品亚洲成a人片在线观看 | 香蕉精品网在线| av国产免费在线观看| 狠狠精品人妻久久久久久综合| 在线观看一区二区三区| 中文字幕制服av| 国产精品秋霞免费鲁丝片| 国产在线一区二区三区精| 久久久久精品久久久久真实原创| 亚洲美女搞黄在线观看| 亚洲av.av天堂| 黄色欧美视频在线观看| 欧美少妇被猛烈插入视频| 日日摸夜夜添夜夜添av毛片| 嫩草影院新地址| h日本视频在线播放| 国产精品久久久久久精品电影小说 | 国产免费福利视频在线观看| 女性被躁到高潮视频| 久久久久久九九精品二区国产| 一级黄片播放器|