• <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ù)的新下界
    国产精品一及| 色5月婷婷丁香| 最近视频中文字幕2019在线8| kizo精华| 97在线视频观看| 久久精品91蜜桃| 国产成人a区在线观看| av国产久精品久网站免费入址| 七月丁香在线播放| 亚洲精品,欧美精品| 国产精品人妻久久久久久| 欧美另类亚洲清纯唯美| 亚洲国产精品成人综合色| av播播在线观看一区| 国产精品电影一区二区三区| 99久久精品国产国产毛片| 亚洲av男天堂| 最近中文字幕2019免费版| 一级av片app| 岛国在线免费视频观看| 亚洲自拍偷在线| 亚洲性久久影院| 别揉我奶头 嗯啊视频| 男人的好看免费观看在线视频| 国产精品日韩av在线免费观看| 国产真实伦视频高清在线观看| 精品少妇黑人巨大在线播放 | 国产色爽女视频免费观看| 毛片女人毛片| 偷拍熟女少妇极品色| 看非洲黑人一级黄片| 国产熟女欧美一区二区| 国产精品野战在线观看| 午夜久久久久精精品| 麻豆精品久久久久久蜜桃| 亚洲欧美清纯卡通| 亚洲av电影在线观看一区二区三区 | 97热精品久久久久久| 又粗又硬又长又爽又黄的视频| 久久精品人妻少妇| 亚洲,欧美,日韩| 精品一区二区三区视频在线| 黄片wwwwww| 人人妻人人看人人澡| 免费搜索国产男女视频| 91午夜精品亚洲一区二区三区| 晚上一个人看的免费电影| 欧美成人a在线观看| 亚洲怡红院男人天堂| 日本-黄色视频高清免费观看| 嘟嘟电影网在线观看| 亚洲欧洲日产国产| 久99久视频精品免费| 亚洲激情五月婷婷啪啪| 99热这里只有是精品50| 日韩一区二区三区影片| 熟女人妻精品中文字幕| 美女国产视频在线观看| 一个人看的www免费观看视频| 亚洲国产精品久久男人天堂| 亚洲国产精品成人综合色| 国产免费视频播放在线视频 | 久久精品91蜜桃| 国产极品精品免费视频能看的| 国产精品国产高清国产av| 熟妇人妻久久中文字幕3abv| 日韩在线高清观看一区二区三区| 少妇的逼水好多| 赤兔流量卡办理| 欧美另类亚洲清纯唯美| 熟女人妻精品中文字幕| 国语对白做爰xxxⅹ性视频网站| 亚洲精品国产成人久久av| 黄片wwwwww| 你懂的网址亚洲精品在线观看 | 哪个播放器可以免费观看大片| 三级经典国产精品| 亚洲丝袜综合中文字幕| 女的被弄到高潮叫床怎么办| 在线免费十八禁| 一区二区三区免费毛片| 在线观看美女被高潮喷水网站| 精品久久久久久久久av| 国产成人免费观看mmmm| 国产精品国产三级专区第一集| 国产乱人视频| 1000部很黄的大片| 伦理电影大哥的女人| 国产淫语在线视频| 一级毛片aaaaaa免费看小| 亚洲美女搞黄在线观看| 女人被狂操c到高潮| a级毛色黄片| 国产69精品久久久久777片| 如何舔出高潮| 久久精品国产亚洲网站| 国产老妇伦熟女老妇高清| 六月丁香七月| 精品免费久久久久久久清纯| 久久99热这里只频精品6学生 | 一夜夜www| 欧美一区二区亚洲| 久久久精品欧美日韩精品| 国产视频首页在线观看| 久久久久久大精品| 男女国产视频网站| 九九热线精品视视频播放| 久久精品综合一区二区三区| 色综合站精品国产| 精品久久久久久久久av| 我的老师免费观看完整版| 国产在线男女| 日本三级黄在线观看| 国产真实乱freesex| 成人特级av手机在线观看| 国产一区二区三区av在线| 熟女电影av网| 99热精品在线国产| 可以在线观看毛片的网站| 99久久人妻综合| 日韩欧美国产在线观看| 国产成人a区在线观看| 免费人成在线观看视频色| 午夜免费男女啪啪视频观看| 欧美日本视频| 国内精品一区二区在线观看| 伦理电影大哥的女人| 久久久久国产网址| 免费观看精品视频网站| 午夜久久久久精精品| 免费看av在线观看网站| 一级黄片播放器| 在现免费观看毛片| 一本久久精品| 国产免费视频播放在线视频 | 日韩欧美三级三区| 丰满人妻一区二区三区视频av| 美女国产视频在线观看| 亚洲国产欧美在线一区| 久久人人爽人人爽人人片va| 国产精品国产三级国产av玫瑰| 美女国产视频在线观看| 亚洲国产欧洲综合997久久,| 亚洲18禁久久av| 国产黄a三级三级三级人| 久久精品久久精品一区二区三区| 淫秽高清视频在线观看| 99九九线精品视频在线观看视频| 观看美女的网站| 国产精品久久视频播放| 精品一区二区三区视频在线| 麻豆av噜噜一区二区三区| 欧美高清性xxxxhd video| 亚洲人成网站在线播| 熟女人妻精品中文字幕| 简卡轻食公司| 干丝袜人妻中文字幕| 欧美成人免费av一区二区三区| 成年av动漫网址| av线在线观看网站| 国产免费又黄又爽又色| 久久久欧美国产精品| 国产伦一二天堂av在线观看| 国产高清不卡午夜福利| 国内精品美女久久久久久| 男人舔奶头视频| 亚洲国产精品sss在线观看| 男人舔女人下体高潮全视频| 97超视频在线观看视频| 中文亚洲av片在线观看爽| 色综合色国产| 青春草视频在线免费观看| 99久国产av精品| 亚洲一区高清亚洲精品| 最近手机中文字幕大全| 嫩草影院新地址| 欧美一区二区亚洲| 国产精品国产三级国产av玫瑰| 99在线人妻在线中文字幕| 国产亚洲91精品色在线| 欧美精品国产亚洲| 欧美性猛交╳xxx乱大交人| 亚洲欧美日韩卡通动漫| 99久久精品国产国产毛片| 精品一区二区三区视频在线| a级毛色黄片| 色尼玛亚洲综合影院| 高清在线视频一区二区三区 | 日韩欧美精品免费久久| videossex国产| 男人和女人高潮做爰伦理| 毛片一级片免费看久久久久| 69人妻影院| av卡一久久| 午夜福利在线观看吧| 午夜老司机福利剧场| 国产精品熟女久久久久浪| 水蜜桃什么品种好| 麻豆av噜噜一区二区三区| 中文字幕免费在线视频6| 在线播放国产精品三级| 午夜精品一区二区三区免费看| 成人欧美大片| 欧美激情国产日韩精品一区| 国内精品一区二区在线观看| 全区人妻精品视频| 人体艺术视频欧美日本| 国产极品精品免费视频能看的| 亚洲精品久久久久久婷婷小说 | 国产成年人精品一区二区| 超碰av人人做人人爽久久| 18禁裸乳无遮挡免费网站照片| 桃色一区二区三区在线观看| 午夜福利成人在线免费观看| 内地一区二区视频在线| 高清在线视频一区二区三区 | 免费看光身美女| 日本免费在线观看一区| 日产精品乱码卡一卡2卡三| 亚洲精品成人久久久久久| 国产精品,欧美在线| 青青草视频在线视频观看| 亚洲va在线va天堂va国产| 韩国av在线不卡| 国产在线一区二区三区精 | 成年版毛片免费区| 亚洲激情五月婷婷啪啪| 日韩精品有码人妻一区| 九色成人免费人妻av| 国产精品久久久久久精品电影| 日韩欧美精品v在线| 国产精品无大码| 亚洲精品乱码久久久久久按摩| 日韩av不卡免费在线播放| 你懂的网址亚洲精品在线观看 | 国产亚洲最大av| 国产男人的电影天堂91| 国产精品国产三级国产av玫瑰| 久久精品影院6| 少妇猛男粗大的猛烈进出视频 | 亚洲国产精品合色在线| 我的老师免费观看完整版| 91av网一区二区| 大香蕉久久网| 欧美三级亚洲精品| 最近最新中文字幕免费大全7| 春色校园在线视频观看| 成人午夜精彩视频在线观看| 国产午夜福利久久久久久| 成年女人永久免费观看视频| 精品无人区乱码1区二区| 欧美日本视频| 久久久久久九九精品二区国产| 99热网站在线观看| 校园人妻丝袜中文字幕| 国产成人aa在线观看| 蜜桃亚洲精品一区二区三区| 青春草视频在线免费观看| 久久鲁丝午夜福利片| 国产成人精品久久久久久| av国产免费在线观看| 国产精品国产三级国产av玫瑰| 麻豆国产97在线/欧美| 国产黄片视频在线免费观看| 男人的好看免费观看在线视频| 国产精品国产三级国产专区5o | av.在线天堂| 国产精品福利在线免费观看| 亚洲国产精品专区欧美| 国产亚洲最大av| 久久久久九九精品影院| 99热这里只有是精品在线观看| 国产综合懂色| 久久亚洲国产成人精品v| 我的老师免费观看完整版| 成人国产麻豆网| 久久久久久久午夜电影| 精品久久久久久久末码| 久久精品久久久久久久性| 国产又黄又爽又无遮挡在线| 国产成人freesex在线| 亚洲精品亚洲一区二区| 久久99热这里只有精品18| 精品久久国产蜜桃| 亚洲va在线va天堂va国产| 久久久久久久国产电影| 两性午夜刺激爽爽歪歪视频在线观看| 国产爱豆传媒在线观看| 日韩欧美三级三区| 插阴视频在线观看视频| 国产老妇伦熟女老妇高清| 又爽又黄无遮挡网站| 国产成人a区在线观看| 亚洲色图av天堂| 久久国产乱子免费精品| 欧美性猛交黑人性爽| 春色校园在线视频观看| 日本三级黄在线观看| 日日摸夜夜添夜夜添av毛片| 22中文网久久字幕| 国产成年人精品一区二区| 午夜老司机福利剧场| 欧美高清性xxxxhd video| 特级一级黄色大片| 天天躁夜夜躁狠狠久久av| 欧美精品国产亚洲| 99久国产av精品国产电影| 级片在线观看| 伦理电影大哥的女人| 少妇被粗大猛烈的视频| 久久久成人免费电影| 我要看日韩黄色一级片| 国产黄色小视频在线观看| 国产成人a∨麻豆精品| 国产亚洲av嫩草精品影院| 欧美xxxx性猛交bbbb| 别揉我奶头 嗯啊视频| 国产免费又黄又爽又色| 岛国毛片在线播放| 欧美日韩一区二区视频在线观看视频在线 | 国产精品久久久久久久久免| 成人美女网站在线观看视频| 插逼视频在线观看| 亚洲av男天堂| 日本欧美国产在线视频| 精品久久久久久久久久久久久| 伦理电影大哥的女人| 欧美bdsm另类| 最近中文字幕高清免费大全6| 成人二区视频| 久久精品熟女亚洲av麻豆精品 | 少妇人妻精品综合一区二区| 久久久a久久爽久久v久久| 91狼人影院| 成人毛片a级毛片在线播放| 日韩欧美三级三区| av卡一久久| 如何舔出高潮| 搞女人的毛片| 免费看a级黄色片| 九九热线精品视视频播放| 99在线视频只有这里精品首页| 久久人妻av系列| 老司机影院毛片| 九九久久精品国产亚洲av麻豆| 91在线精品国自产拍蜜月| 啦啦啦啦在线视频资源| av在线老鸭窝| 久久久欧美国产精品| 精品一区二区三区人妻视频| 七月丁香在线播放| 久久久精品94久久精品| 亚洲欧美日韩卡通动漫| 狠狠狠狠99中文字幕| 好男人在线观看高清免费视频| 中文字幕人妻熟人妻熟丝袜美| 在线天堂最新版资源| 99久久中文字幕三级久久日本| 成年版毛片免费区| 嘟嘟电影网在线观看| 欧美成人午夜免费资源| 麻豆成人av视频| 婷婷色麻豆天堂久久 | 日本一二三区视频观看| 国产乱人偷精品视频| av.在线天堂| 长腿黑丝高跟| 一区二区三区乱码不卡18| 午夜精品国产一区二区电影 | 高清午夜精品一区二区三区| 久久久久久久久久黄片| 男人和女人高潮做爰伦理| 亚洲三级黄色毛片| 天天躁夜夜躁狠狠久久av| 久久久精品欧美日韩精品| 国产视频内射| 成人高潮视频无遮挡免费网站| 26uuu在线亚洲综合色| 欧美激情在线99| 亚洲人成网站高清观看| 一个人看视频在线观看www免费| 22中文网久久字幕| 99热网站在线观看| 精品免费久久久久久久清纯| 人妻少妇偷人精品九色| 天堂影院成人在线观看| 搞女人的毛片| 在线观看av片永久免费下载| 亚洲国产精品专区欧美| 午夜亚洲福利在线播放| 国产片特级美女逼逼视频| 直男gayav资源| 插逼视频在线观看| 高清日韩中文字幕在线| 国产片特级美女逼逼视频| 精品国内亚洲2022精品成人| 亚洲精品亚洲一区二区| 搡老妇女老女人老熟妇| 日本三级黄在线观看| 夜夜看夜夜爽夜夜摸| 国产男人的电影天堂91| 国产中年淑女户外野战色| 国产免费男女视频| 日韩精品有码人妻一区| 日韩高清综合在线| 男女那种视频在线观看| 麻豆久久精品国产亚洲av| 综合色av麻豆| 国产久久久一区二区三区| 高清午夜精品一区二区三区| 日韩三级伦理在线观看| 亚洲欧美一区二区三区国产| 在线播放无遮挡| av国产免费在线观看| 美女内射精品一级片tv| 高清在线视频一区二区三区 | 久久久亚洲精品成人影院| 国产精品日韩av在线免费观看| 国产黄色视频一区二区在线观看 | 国产精品人妻久久久影院| 简卡轻食公司| 国产成人一区二区在线| 自拍偷自拍亚洲精品老妇| 久久韩国三级中文字幕| 日韩欧美国产在线观看| 精品熟女少妇av免费看| 国产成人精品婷婷| 建设人人有责人人尽责人人享有的 | 亚洲国产精品sss在线观看| 一边摸一边抽搐一进一小说| 99热精品在线国产| 日本五十路高清| 欧美成人a在线观看| 99热精品在线国产| 91aial.com中文字幕在线观看| 久久午夜福利片| 成人一区二区视频在线观看| 亚洲精品成人久久久久久| 18禁在线无遮挡免费观看视频| 国产色婷婷99| 2022亚洲国产成人精品| 日日干狠狠操夜夜爽| av在线老鸭窝| 日日啪夜夜撸| 色播亚洲综合网| 精品久久久噜噜| 亚洲乱码一区二区免费版| 少妇猛男粗大的猛烈进出视频 | 国产精品无大码| 亚洲精品国产av成人精品| 少妇的逼水好多| 久久婷婷人人爽人人干人人爱| 国产老妇伦熟女老妇高清| 久久久久久久久久成人| 久久久久久久久久黄片| 99热全是精品| 波野结衣二区三区在线| 内地一区二区视频在线| 色网站视频免费| 一级毛片电影观看 | 国产亚洲精品av在线| 日韩精品有码人妻一区| 亚洲最大成人手机在线| 欧美日韩国产亚洲二区| 男的添女的下面高潮视频| 免费观看人在逋| 一卡2卡三卡四卡精品乱码亚洲| 日本免费在线观看一区| 一级毛片久久久久久久久女| 男女那种视频在线观看| 蜜臀久久99精品久久宅男| 性色avwww在线观看| 亚洲成av人片在线播放无| 最新中文字幕久久久久| 国产精华一区二区三区| 欧美日本视频| 日日撸夜夜添| 久久精品国产亚洲网站| 小说图片视频综合网站| 舔av片在线| 亚洲天堂国产精品一区在线| 亚洲精品久久久久久婷婷小说 | 成人鲁丝片一二三区免费| 夜夜看夜夜爽夜夜摸| 成人午夜高清在线视频| 成人综合一区亚洲| 少妇丰满av| 亚洲国产色片| www.av在线官网国产| 丰满乱子伦码专区| 在线播放国产精品三级| 久久精品人妻少妇| 国产成人a∨麻豆精品| 成人美女网站在线观看视频| 亚洲成人中文字幕在线播放| 久久久国产成人免费| 伦理电影大哥的女人| 国产高清国产精品国产三级 | 内地一区二区视频在线| 亚洲激情五月婷婷啪啪| 国语对白做爰xxxⅹ性视频网站| 尾随美女入室| 国产成人精品婷婷| 国产综合懂色| 只有这里有精品99| av女优亚洲男人天堂| 看十八女毛片水多多多| 男女边吃奶边做爰视频| 亚洲精品456在线播放app| 我的老师免费观看完整版| 好男人视频免费观看在线| 国产免费男女视频| 久久久久久久午夜电影| 日韩欧美国产在线观看| 亚洲乱码一区二区免费版| 国产老妇伦熟女老妇高清| 白带黄色成豆腐渣| 国产高清国产精品国产三级 | 极品教师在线视频| 男女啪啪激烈高潮av片| 国产亚洲av嫩草精品影院| 久久鲁丝午夜福利片| 国产成人福利小说| 天堂影院成人在线观看| 看非洲黑人一级黄片| 如何舔出高潮| 欧美一区二区亚洲| 国产欧美日韩精品一区二区| 色网站视频免费| 男女边吃奶边做爰视频| 国产亚洲av片在线观看秒播厂 | 一卡2卡三卡四卡精品乱码亚洲| 蜜臀久久99精品久久宅男| 国产麻豆成人av免费视频| 国产成人精品久久久久久| 男女视频在线观看网站免费| 欧美日本视频| 亚洲av成人av| 国产大屁股一区二区在线视频| 91av网一区二区| 三级国产精品片| 两个人的视频大全免费| 天美传媒精品一区二区| 日日摸夜夜添夜夜添av毛片| 一边亲一边摸免费视频| 久久久a久久爽久久v久久| 婷婷六月久久综合丁香| 韩国高清视频一区二区三区| 亚洲av日韩在线播放| 最后的刺客免费高清国语| 国产精品国产高清国产av| 久久综合国产亚洲精品| 国产精品野战在线观看| 国产欧美另类精品又又久久亚洲欧美| 欧美成人午夜免费资源| 少妇被粗大猛烈的视频| 国产一级毛片在线| 亚洲精品亚洲一区二区| 午夜爱爱视频在线播放| 寂寞人妻少妇视频99o| 亚洲va在线va天堂va国产| 女人久久www免费人成看片 | 乱码一卡2卡4卡精品| 日韩精品有码人妻一区| 亚洲av不卡在线观看| 男人舔女人下体高潮全视频| 一级黄片播放器| 国产成人精品久久久久久| 欧美xxxx黑人xx丫x性爽| 特级一级黄色大片| 久久精品综合一区二区三区| 精品久久久噜噜| 草草在线视频免费看| 三级国产精品片| 91午夜精品亚洲一区二区三区| 一本久久精品| 国产白丝娇喘喷水9色精品| 国产精品精品国产色婷婷| 国产免费又黄又爽又色| 国产成人91sexporn| 成人亚洲精品av一区二区| 久久99精品国语久久久| 在线免费十八禁| 亚洲欧美精品自产自拍| 禁无遮挡网站| 在线天堂最新版资源| 国产在视频线精品| 在线a可以看的网站| 一区二区三区免费毛片| 国产黄片美女视频| 亚洲精品影视一区二区三区av| 久久久久久久久久久免费av| 亚洲五月天丁香| 三级男女做爰猛烈吃奶摸视频| 精品久久久久久久末码| 欧美最新免费一区二区三区| 18禁在线无遮挡免费观看视频| .国产精品久久| 亚洲va在线va天堂va国产| 精品国产露脸久久av麻豆 | 亚洲精品日韩av片在线观看| 久久精品国产99精品国产亚洲性色| 久久99蜜桃精品久久| 99久国产av精品| 国产一区二区在线观看日韩| 亚洲国产成人一精品久久久| 婷婷色综合大香蕉| 亚洲av电影不卡..在线观看| 国产一区二区在线观看日韩| 国产91av在线免费观看| 久久这里只有精品中国| 日韩欧美国产在线观看| 亚洲综合色惰| 男女那种视频在线观看| 国产av不卡久久|