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

    基于最小割圖分割的社區(qū)發(fā)現(xiàn)算法

    2017-07-18 10:53:41王亞珅黃河燕
    中文信息學報 2017年3期
    關(guān)鍵詞:最大化節(jié)點社區(qū)

    王亞珅,黃河燕,馮 沖

    (北京理工大學 計算機學院北京市海量語言信息處理與云計算應用工程技術(shù)研究中心,北京 100081)

    基于最小割圖分割的社區(qū)發(fā)現(xiàn)算法

    王亞珅,黃河燕,馮 沖

    (北京理工大學 計算機學院北京市海量語言信息處理與云計算應用工程技術(shù)研究中心,北京 100081)

    該文證明了模塊度最大化問題可以被轉(zhuǎn)換成為原網(wǎng)絡(luò)上的最小割圖分割問題,并且基于該證明提出了一種高效的社區(qū)發(fā)現(xiàn)算法。同時,該文創(chuàng)新性地將模塊度理論與當今比較流行的統(tǒng)計推理模型相結(jié)合: 首先,這些統(tǒng)計推理模型被轉(zhuǎn)化為模塊度最大化問題中的零模型;其次,統(tǒng)計推理模型中的目標函數(shù)被修改并應用于本文的最優(yōu)化算法中。實驗結(jié)果顯示,無論是在真實世界網(wǎng)絡(luò)還是在人工生成網(wǎng)絡(luò)中,該文提出的算法均具有高效和穩(wěn)定的發(fā)現(xiàn)社區(qū)的能力。

    社區(qū)發(fā)現(xiàn);模塊度;最小割圖分割

    1 引言

    作為網(wǎng)絡(luò)的一種常見屬性,社區(qū)結(jié)構(gòu)(community structure)是一種對網(wǎng)絡(luò)節(jié)點的分割,其中,同一個社區(qū)中的節(jié)點聯(lián)系緊密,而隸屬于不同社區(qū)的節(jié)點之間聯(lián)系則相對松散[1-2],社區(qū)發(fā)現(xiàn)(community detection)已經(jīng)在諸多領(lǐng)域體現(xiàn)出其應用價值[3-5]。為了解決社區(qū)發(fā)現(xiàn)問題,我們首先討論社區(qū)(community)的定義,學界目前存在很多全局化的社區(qū)定義,這些定義均將社區(qū)結(jié)構(gòu)視為整個網(wǎng)絡(luò)的一個屬性[6]。

    (1) 最為直觀的社區(qū)定義與連接不同社區(qū)邊的數(shù)量(在有權(quán)網(wǎng)絡(luò)中,則為連接邊的加權(quán)和)有關(guān),這個數(shù)量通常被稱為割規(guī)模(cut size),旨在最小化割規(guī)模的問題一般被稱為“最小割圖分割(minimum-cut graph partitioning)”問題。

    (2) 另一種社區(qū)的定義則是基于被廣泛使用的模塊度(modularity)概念[1,7]。模塊度衡量一個給定的圖分割與一個期望隨機圖(又稱為“零模型”)的圖分割之間的差異,旨在最大化模塊度的問題一般被稱為“模塊度最大化(modularity maximization)”問題。

    本文研究的核心內(nèi)容是,探索模塊度最大化問題和最小割圖分割問題的內(nèi)在關(guān)系。目前,學界對此類問題的相關(guān)研究較少。文獻[8]針對生成一個特定網(wǎng)絡(luò)的似然函數(shù)最大化問題,證明了統(tǒng)計推理模型可以映射成為最小割圖分割問題。本文的研究正是受文獻[8]啟發(fā),但是我們重點關(guān)注的是模塊度最大化問題,證明模塊度最大化問題可以被轉(zhuǎn)化成為原網(wǎng)絡(luò)上的最小割圖分割問題,并應用多層次圖分割的Kernighan-Lin算法[9]來解決上述最小割圖分割問題。

    本文另外一個貢獻在于,創(chuàng)新性地將模塊度理論和統(tǒng)計推理算法(例如隨機塊模型[10-11]及其度修正變體[12])相結(jié)合。統(tǒng)計推理算法首先假設(shè)了一些用于產(chǎn)生社區(qū)結(jié)構(gòu)的潛在概率模型,進而估計模型的參數(shù)。實際上,基于模塊度的算法和此類基于統(tǒng)計推理模型的算法均可以視為最優(yōu)化問題,因此我們嘗試證明二者之間的聯(lián)系。所以,統(tǒng)計推理模型在本文提出的算法中扮演著重要角色:

    (1) 在證明過程中,統(tǒng)計推理模型可以被轉(zhuǎn)化成為模塊度最大化問題中的零模型(null model)[12]。

    (2) 統(tǒng)計推理算法的核心思想是通過最大化似然函數(shù)(likelihood)來產(chǎn)生一個合理的目標函數(shù),因此,我們修改這個目標函數(shù)以應用于我們的最優(yōu)化策略中。

    簡言之,本文提出的算法首先通過執(zhí)行多層次最小割圖分割算法,得到一個包含眾多社區(qū)結(jié)構(gòu)的候選集合;然后使用度修正隨機塊模型的目標函數(shù),從候選集合中選擇目標函數(shù)值最大的社區(qū)結(jié)構(gòu)作為最終結(jié)果。據(jù)悉,我們首創(chuàng)性地探尋模塊度理論、統(tǒng)計推理模型和傳統(tǒng)圖聚類/圖分割算法三者之間的內(nèi)在聯(lián)系,雖然本文算法在時間復雜度方面依然有很大提升空間(文獻[8]也面臨同樣挑戰(zhàn)),但是本文算法在真實世界網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)的實驗中均得到了很高的準確率和穩(wěn)定性。

    本文的內(nèi)容組織如下: 第二節(jié)將總結(jié)相關(guān)工作;第三節(jié)重點分析度修正隨機塊模型的原理;在第四節(jié)中,我們將詳細分析模塊度最大化算法和最小割圖分割算法之間的關(guān)系,并提出我們的算法;第五節(jié)和第六節(jié)將闡述實驗和相關(guān)結(jié)果及結(jié)論。

    2 相關(guān)工作

    作為聚類質(zhì)量的評價指標,模塊度被文獻[1]引入到社區(qū)發(fā)現(xiàn)研究中,并憑借其直觀高效的特點,逐漸成為社區(qū)發(fā)現(xiàn)研究的常用度量方式。文獻[7]提出的貪婪的基于模塊度的社區(qū)發(fā)現(xiàn)算法CNM,已成為當今使用最為普遍的算法。該算法從嵌套的堆棧中迭代地選擇和合并能夠產(chǎn)生最大模塊度增益的最優(yōu)節(jié)點對,直至沒有此類節(jié)點對能夠提高模塊度為止。此后,作為CNM的變體,一系列針對有權(quán)重網(wǎng)絡(luò)和有向網(wǎng)絡(luò)的計算模塊度的算法相繼被提出;此外,基于其他理論的諸多算法也被提出,例如計算網(wǎng)絡(luò)圖的Laplacian特征向量的算法[13]等。近年來,包括隨機塊模型[10]及其度修正變體[11]在內(nèi)的統(tǒng)計推理算法,憑借其優(yōu)良的性能吸引著越來越多的研究興趣。

    不難發(fā)現(xiàn),社區(qū)發(fā)現(xiàn)與圖分割/圖聚類有著密切關(guān)系,但是二者之間依然存在著一定差異[6]。圖分割是人工智能領(lǐng)域被深入研究的課題[14-16],旨在將網(wǎng)絡(luò)中的節(jié)點劃分成一些指定規(guī)模(并不要求規(guī)模相等)的分組,并且確保分組之間連接邊的數(shù)量最小。其中有兩類算法占據(jù)著主導地位: 基于網(wǎng)絡(luò)圖Laplacian特征向量的譜二分析法,以及使用貪婪策略不斷優(yōu)化社區(qū)外部連接邊和內(nèi)部連接邊進而不斷改善初始劃分的Kernighan-Lin算法[16]及其多層次變體[9](見圖1)。目前,學界已有不少利用(歸一化)最小割圖分割算法進行社區(qū)發(fā)現(xiàn)的研究[17],但是對于模塊度最大化與最小割圖分割的關(guān)系的研究尚屬少數(shù)[18]。文獻[18]意在證明歸一化模塊度最大化問題可以轉(zhuǎn)換為RatioCut譜聚類問題,但是無法精確證明二者之間的等價關(guān)系。

    3 度修正的隨機塊模型

    原始的隨機塊模型是一個用于網(wǎng)絡(luò)社區(qū)的產(chǎn)生式模型,但是由于忽略了節(jié)點度的多樣性,導致其很難被應用于真實世界網(wǎng)絡(luò)。為了解決上述問題,度修正隨機塊模型(degree-corrected stochastic block model)[12]為每個節(jié)點i添加了一個參數(shù)θi用于控制節(jié)點i的度的期望值,這使其能夠適應任何度分布。

    對于網(wǎng)絡(luò)G(V,E),V和E分別表示該網(wǎng)絡(luò)全部n個節(jié)點的集合和全部m條邊的集合,k表示社區(qū)的數(shù)量。Aij表示G(V,E)的鄰接矩陣的元素,其值等同于節(jié)點i和節(jié)點j之間邊的數(shù)量,且Aii=0。ωrs是一個k×k維對稱矩陣的元素,控制著社區(qū)r和社區(qū)s之間的連接邊。我們將Aij的期望值設(shè)定為θiθjωgigj[12],其中g(shù)i表示節(jié)點i所隸屬的社區(qū)。綜上所述,生成網(wǎng)絡(luò)G(V,E)的似然度函數(shù)為式(1)。

    其中,ki是節(jié)點i的度;κs是社區(qū)s所有節(jié)點度的總和;mrs是連接社區(qū)r和社區(qū)s的邊的數(shù)量,其定義如式(3)所示。

    其中,δgigj是KroneckerDelta。將θ和ω的值帶入式(1),經(jīng)過適當改寫,我們便得到了只依賴于社區(qū)結(jié)構(gòu)輪廓的似然函數(shù),并取對數(shù)得

    因為統(tǒng)計推理算法通常被用作評估社區(qū)發(fā)現(xiàn)算法的基準算法,所以我們不妨利用式(4)作為判別社區(qū)劃分是否合理的目標函數(shù)

    4 基于最小割圖分割的社區(qū)發(fā)現(xiàn)算法

    文獻[1]所定義的模塊度概念,被廣為認可和使用,而近來來關(guān)于社區(qū)發(fā)現(xiàn)的研究也大多集中在模塊度最大化問題。本章將證明,模塊度最大化問題可以被轉(zhuǎn)化成原網(wǎng)絡(luò)最小割圖分割問題。

    給定以下條件:

    (1) 一個擁有n個節(jié)點和m條邊的網(wǎng)絡(luò)G(V,E),V和E分別代表上文所定義的節(jié)點集合和邊集合;

    (2) 包含k個社區(qū)的一個劃分P=P1,…,Pk;

    (3) 一個在原網(wǎng)絡(luò)節(jié)點集合V上的隨機網(wǎng)絡(luò)分布為G。

    隨機網(wǎng)絡(luò)分布G有很多選擇方式[19],具體如下。

    (1)Erd?s-Renyi模型: 原始的隨機塊模型與Erd?s和Renyi提出的隨機圖模型[20]有密切的內(nèi)在聯(lián)系[12],但是這個模型極易產(chǎn)生不符合實際的網(wǎng)絡(luò)(度分布服從泊松分布),甚至產(chǎn)生沒有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)。

    (2)Chung-Lu模型: 為了避免上述問題,模塊度經(jīng)常使用另外一種固定度期望序列使之與被觀察網(wǎng)絡(luò)一致的模型來定義。這種意義下,度修正的隨機塊模型與Chung和Lu所研究的模型[21]有關(guān)。

    為了簡化描述,我們定義

    為劃分P所對應的割規(guī)模。我們首先考慮最簡單的情況——二分問題(即k=2),式(6)可以被改寫成

    對于式(8)中隨機網(wǎng)絡(luò)分布G的選定,我們將分別考察原始隨機塊模型及其度修正變體。

    4.1 將原始隨機塊模型作為G的情況

    重寫式(8)得

    如果我們使用w12來表示社區(qū)1和社區(qū)2之間的邊的數(shù)量期望值,那么

    考慮到

    其中,n1和n2分別表示社區(qū)1和社區(qū)2中節(jié)點的數(shù)量,則

    因此模塊度最大化問題可以被進一步重寫為

    至此,式(6)所代表的原始問題,已經(jīng)被轉(zhuǎn)化成了計算公式(15)。

    4.2 將度修正的隨機塊模型作為G的情況

    去掉式(8)中的常數(shù)項m,我們可以得到

    在度修正隨機塊模型中,我們有

    其中,w11和w22分別表示社區(qū)1和社區(qū)2內(nèi)部邊數(shù)量的期望值。并且有

    相似地,可得

    至此,式(6)所代表的原始問題,已經(jīng)被轉(zhuǎn)化成了計算式(21)。

    式(21)與式(15)十分相似,原始的模塊度最大化問題也被映射成為一個帶有附加項的最小割圖分割問題。所以,綜合考慮式(15)和式(21),本文首先固定隨機網(wǎng)絡(luò)分布G,執(zhí)行以社區(qū)結(jié)構(gòu)為自變量的最小化;然后,固定社區(qū)結(jié)構(gòu),執(zhí)行以G為自變量的最小化。

    我們可以執(zhí)行下述在社區(qū)發(fā)現(xiàn)研究中常用的貪婪策略[7]來完成對社區(qū)規(guī)模n1和n2的選擇。假設(shè)我們并不區(qū)分社區(qū)的類別,即我們只需要將所有節(jié)點劃分進兩個不同的社區(qū),而并不關(guān)心某個節(jié)點具體屬于哪個社區(qū)。如果網(wǎng)絡(luò)中節(jié)點總數(shù)n是偶數(shù),那么有n/2+1種對兩個社區(qū)的規(guī)模的選擇方式: 一種極端的選擇方式將所有節(jié)點放入某一個社區(qū)中,另一種極端的選擇方式將所有節(jié)點均分到兩個社區(qū)中,其他的選擇方式介于上述兩種極端選擇方式之間。相似地,如果n是奇數(shù),則會有(n+1)/2種對兩個社區(qū)規(guī)模的選擇方式。上述所有選擇構(gòu)成一個單一參數(shù)(參數(shù)為社區(qū)規(guī)模)的候選集合;對于每個選擇均對應一個標準的最小割圖分割問題,因此很多啟發(fā)式算法[14-16]可以應用于此,本文使用多層次的Kernighan-Lin算法[9]解決該最小割圖分割問題,并得到相應候選解(即候選的社區(qū)結(jié)構(gòu))。此時,因為這里使模塊度全局最大的候選解應同樣滿足使式(4)取得最大值,所以我們將每個候選解帶入式(4)并計算,從計算得到的目標值中選擇最大值對應的候選解作為最終結(jié)果。上述將網(wǎng)絡(luò)劃分為兩個社區(qū)的算法可以很簡單地擴展到多社區(qū)劃分的情況,方法如下: 我們首先使用上述算法將網(wǎng)絡(luò)分成兩個網(wǎng)絡(luò),然后遞歸地將各個子網(wǎng)絡(luò)繼續(xù)劃分成兩個社區(qū),以此類推[13];對于某個子圖,如果其任何劃分都不增加整個網(wǎng)絡(luò)的模塊度,那么這個子圖將被保留成為一個社區(qū)而不再被繼續(xù)分割。

    基于文獻[9]中的分析,本文提出的算法將包含n個節(jié)點和m條邊的網(wǎng)絡(luò)劃分成兩個社區(qū)的時間復雜度為O(n2);當劃分為k個社區(qū)的時候,只需要執(zhí)行d次上述計算即可,其中d是樹狀圖的深度(在二分樹中,log2k≤d≤k)。因為本文提出的算法是一個創(chuàng)新性的嘗試和證明,所以與現(xiàn)有算法(如算法[7])相比,其計算時間并不具備優(yōu)勢,依然有很大改進空間(這種降低時間復雜度的挑戰(zhàn)同樣也是文獻[8]所面臨的)。因此在降低時間復雜度方面對算法進行改進,將是未來工作的方向之一;但是實驗結(jié)果顯示,該算法對于發(fā)現(xiàn)社區(qū)結(jié)構(gòu)具有很高的準確率。

    5 實驗和結(jié)果分析

    本節(jié)中,我們在真實世界網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)上,分別測試本文算法(記為MC)的性能并與其他算法進行比較,實驗證明其取得了良好的實驗結(jié)果。其中,真實世界網(wǎng)絡(luò)可以體現(xiàn)算法在現(xiàn)實條件下的性能,而人工生成網(wǎng)絡(luò)可以在已知社區(qū)結(jié)構(gòu)設(shè)定和受控條件下測試算法發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的能力。本文實驗部分修改和應用基于多層次圖分割策略的圖分割工具包METIS-5.1.0*http://glaros.dtc.umn.edu/gkhome/metis/metis/download,主要采用的度量方法是歸一化互信息(normalizedmutualinformation,NMI)[22]及其變體(variantnormalizedmutualinformation,VNMI)。

    本文實驗所使用的網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)均已知,這使得我們可以度量被算法所正確劃分的節(jié)點的數(shù)量。所以,本文重點關(guān)注: 真實的社區(qū)結(jié)構(gòu)和算法所產(chǎn)生的社區(qū)結(jié)構(gòu)之間的差異。將上述兩種社區(qū)結(jié)構(gòu)均視為隨機變量(分別記為A和B),NMI定義如下:

    5.1 真實世界網(wǎng)絡(luò)實驗

    我們將本文算法應用在了一系列不同規(guī)模的真實世界網(wǎng)絡(luò),算法均產(chǎn)生了與先驗知識一致的社區(qū)結(jié)構(gòu)。這里,我們重點介紹其中三個真實世界網(wǎng)絡(luò)的實驗細節(jié)。

    第一個實驗網(wǎng)絡(luò)是“KarateClub”網(wǎng)絡(luò)[23],該網(wǎng)絡(luò)表示一所美國大學中擁有34個成員的空手道俱樂部中的人際關(guān)系交互情況。由于一次爭吵,這個俱樂部的成員被劃分成為兩個部分,因此這個網(wǎng)絡(luò)為二分算法提供了良好的實驗素材。圖2展示了本文算法在“KarateClub”網(wǎng)絡(luò)上的實驗結(jié)果。結(jié)果顯示,本文算法準確地識別出了已知社區(qū)結(jié)構(gòu),除了錯分位于兩個社區(qū)邊界的編號為10的節(jié)點——該節(jié)點在很多其他的算法中也經(jīng)常被錯誤分類[12],主要因為該節(jié)點連接到兩個社區(qū)的邊的數(shù)量相同。第二個實驗網(wǎng)絡(luò)是“BottlenoseDolphins”網(wǎng)絡(luò)。圖3 展示了本文算法在 “BottlenoseDolphins”網(wǎng)絡(luò)的實驗結(jié)果。該網(wǎng)絡(luò)包含了位于新西蘭的62只海豚,是通過觀察它們之間交互的頻繁程度而建立的網(wǎng)絡(luò)[24]。本文算法首先將這個網(wǎng)絡(luò)分成兩個大的子網(wǎng)絡(luò),其中較大的一個隨后又被分成兩個較小的子網(wǎng)絡(luò)。

    圖2 “Karate Club”網(wǎng)絡(luò)實驗結(jié)果

    圖3 “Bottlenose Dolphins”網(wǎng)絡(luò)實驗結(jié)果

    第三個網(wǎng)絡(luò)是“AmericanPoliticalBlogs”網(wǎng)絡(luò)。“AmericanPoliticalBlogs”網(wǎng)絡(luò)[25]由2004年美國總統(tǒng)大選期間政治類博客及其鏈接信息組成,這些博客中的前758個是支持共和黨的,而剩下的732個博客是支持民主黨的。表1顯示,本文算法應用于全部1 490個節(jié)點的情況下,NMI值只有0.500 502(錯分164個節(jié)點);但是如果去掉原圖中225個孤立節(jié)點而只考慮原圖的聯(lián)系密切的主要部分節(jié)點(1 265個節(jié)點)及其連接,NMI值上升到0.720 525,這與文獻[12]的實驗結(jié)果十分接近。

    表1 “American Political Blogs”網(wǎng)絡(luò)實驗結(jié)果

    5.2 人工生成網(wǎng)絡(luò)實驗

    為了與其他(基準)算法進行比較,我們將本文算法分別應用到基于度修正隨機塊模型(DCM)[12]和Lancichinetti-Fortunato-Radicchi(LFR)基準[26]所產(chǎn)生的人工生成網(wǎng)絡(luò)上。

    5.2.1 DCM人工生成網(wǎng)絡(luò)實驗

    效仿文獻[12],本文按照如下的定義來選擇ωrs,從而產(chǎn)生基于DCM的人工生成網(wǎng)絡(luò)。

    在第一組DCM人工生成網(wǎng)絡(luò)實驗中,每個網(wǎng)絡(luò)均含有100 000個節(jié)點,以及兩個等規(guī)模的社區(qū),并且每個社區(qū)的度的平均期望值均為20。在選定社區(qū)結(jié)構(gòu)、所有節(jié)點度的期望值(公式(2)中的θi)和ωrs的取值之后,我們按照如下方法來生成網(wǎng)絡(luò): 首先對于每對社區(qū)r和s,產(chǎn)生一個服從泊松分布(均值為ωrs)的邊的數(shù)量值,然后根據(jù)θi將所有邊附著在節(jié)點i上。本文提出的MC、原始隨機塊模型(記為SBM)和度修正隨機塊模型(記為DCM)被應用在第一組實驗網(wǎng)絡(luò)上進行性能對比。對于SBM和DCM這兩個模型,我們均采用隨機設(shè)定(后綴為R)和種植設(shè)定(后綴為P)分別進行初始化,分別進行10次獨立運行,并從中選擇最好的結(jié)果展示出來。

    圖4將NMI值作為參數(shù)λ的函數(shù)值,每個數(shù)據(jù)點代表了在100個等條件生成網(wǎng)絡(luò)上的平均值。圖4(a)顯示,隨著λ從0開始逐漸增長,雖然因為此時的網(wǎng)絡(luò)還處于比較隨機的狀態(tài),所有的算法均未能產(chǎn)生比較合理的社區(qū)結(jié)構(gòu),但是本文算法性能優(yōu)于其他算法,一方面是因為最小割圖分割思想有效地將社區(qū)發(fā)現(xiàn)問題還原到了圖論問題的本質(zhì),另一方面是因為本文算法引入的窮舉策略,能夠遍歷當前參數(shù)設(shè)定條件下所有可能的社區(qū)劃分。值得注意的是,本文的算法為每個候選社區(qū)結(jié)構(gòu)均計算“目標值”[見式(4)],但是只有擁有最大“目標值”的社區(qū)結(jié)構(gòu)才會被選中成為最終結(jié)果,所以在最終結(jié)果的NMI值和所有候選的社區(qū)結(jié)構(gòu)中最大的NMI值之間存在一個“間距”: 通過實驗我們發(fā)現(xiàn),當λ的取值接近于0的時候,上述“間距”比較大;而當λ繼續(xù)增加,“間距”開始下降。這種現(xiàn)象很直觀地解釋了以下問題: 當網(wǎng)絡(luò)中社區(qū)劃分越明確,傳統(tǒng)圖分割算法對于社區(qū)劃分結(jié)果的置信度越高;同時,這種“間距”下降,也證明了本文引入度修正隨機塊模型的似然函數(shù)的有效性。此外,當λ超過中值,MC和DCM的曲線基本重合,說明我們的結(jié)果達到了當前最優(yōu)的基準效果。而對于未進行度修正的SBM,即使λ的取值已經(jīng)超過中值,也依然未能產(chǎn)生合理的社區(qū)結(jié)構(gòu)。

    另外一組基于DCM人工生成網(wǎng)絡(luò)的實驗采用的生成網(wǎng)絡(luò)更加復雜和貼近現(xiàn)實網(wǎng)絡(luò)。社區(qū)規(guī)模與度的平均期望值與上一組實驗相同,不同之處在于,本組實驗設(shè)定社區(qū)1的度分布服從冪律分布——復雜網(wǎng)絡(luò)的顯著特征之一,并且取冪指數(shù)γ=2.8;設(shè)定社區(qū)2的度分布為均值為20的泊松分布。圖4(b)證明了本文算法具有良好的穩(wěn)定性:MC在λ很小的情況(即網(wǎng)絡(luò)社區(qū)劃分不明確,甚至是幾乎隨機的網(wǎng)絡(luò))下依然能夠體現(xiàn)出不錯的性能。這是因為MC能夠僅僅依靠節(jié)點的度信息對絕大部分節(jié)點進行分類。相反地,在λ≤0.2的情況下,DCM的正確率幾乎為0,僅略微優(yōu)于原始的SBM。當λ處于插值的中值階段(0.5≤λ≤0.7)時,DCM性能優(yōu)于本文提出的MC,但是在λ取其他值時,MC依然優(yōu)于DCM。換言之,當每條邊都有幾乎相同概率從隨機網(wǎng)絡(luò)和種植網(wǎng)絡(luò)中選擇的時候,DCM準確率的提升速度要快于MC的準確率。特別地,本組實驗社區(qū)1中更為接近現(xiàn)實復雜網(wǎng)絡(luò)中度的冪律分布,使SBM的性能遠差于其在上一組實驗的性能,這是因為SBM產(chǎn)生的網(wǎng)絡(luò)中,節(jié)點的度服從泊松分布,而泊松分布不符合真實世界網(wǎng)絡(luò),因此SBM無法有效擬合觀測網(wǎng)絡(luò)。比較上述兩組DCM人工生成網(wǎng)絡(luò)實驗,我們不難發(fā)現(xiàn),現(xiàn)實網(wǎng)絡(luò)更有助于本文算法發(fā)揮其性能優(yōu)勢。

    圖4 基于DCM的人工合成網(wǎng)絡(luò)的實驗

    5.2.2LFR人工生成網(wǎng)絡(luò)實驗

    為了測試算法在一系列大跨度、寬范圍的結(jié)構(gòu)化網(wǎng)絡(luò)特征下的性能,我們使用LFR基準網(wǎng)絡(luò)進行實驗。LFR綜合考慮了度和社區(qū)規(guī)模的多樣性,是社區(qū)發(fā)現(xiàn)研究領(lǐng)域經(jīng)常被使用的比較符合現(xiàn)實網(wǎng)絡(luò)特征的基準網(wǎng)絡(luò)。

    本文主要討論下述三個主要的用于生成網(wǎng)絡(luò)的參數(shù),對不同算法的性能影響: (a)聚合參數(shù)μ,類似于上述DCM人工生成網(wǎng)絡(luò)實驗中的參數(shù)λ;(b)節(jié)點度的平均值〈k〉;(c)網(wǎng)絡(luò)所包含的節(jié)點總數(shù)N。

    首先,本文與文獻[28]進行對比實驗。我們使用相同的實驗網(wǎng)絡(luò)設(shè)定,實驗包括兩種不同的網(wǎng)絡(luò)規(guī)模(1 000個節(jié)點和5 000個節(jié)點),度的平均值為20。圖5(a)呈現(xiàn)了本文算法的實驗曲線,每個數(shù)據(jù)點均代表100個等條件網(wǎng)絡(luò)實驗結(jié)果的平均值。其中,后綴S和B分別表示較小的社區(qū)規(guī)模(每個社區(qū)包含10~50個節(jié)點)和較大的社區(qū)規(guī)模(每個社區(qū)包含20~100個節(jié)點)。通過實驗結(jié)果對比,本文算法比文獻[28]所分析的算法更有競爭力;相似地,當μ由0.6增長為0.7的時候,曲線出現(xiàn)了快速下降。

    圖5(b)和圖5(c)分別展示了節(jié)點度平均值〈k〉和節(jié)點總數(shù)N對算法性能的影響。通過實驗我們發(fā)現(xiàn),節(jié)點數(shù)量對于算法性能的影響有限;然而節(jié)點度平均值卻對準確率有著顯著影響,在節(jié)點度的變化過程中,幾乎所有算法都遭受過NMI值的巨大損失,而大部分算法的NMI值在度平均值取值約為25的時候達到峰值。

    圖5 基于LFR的人工生成網(wǎng)絡(luò)的實驗

    6 總結(jié)

    社區(qū)發(fā)現(xiàn)長久以來一直吸引著學者們的研究興趣,諸如基于模塊度算法、統(tǒng)計推理模型算法和基于傳統(tǒng)圖聚類/圖分割算法等不同類型算法被相繼提出。我們始終認為,在這些不同的理論之間一定存在某些內(nèi)在聯(lián)系。所以,本文進行了一個創(chuàng)新性的嘗試,旨在探索并發(fā)現(xiàn)這些理論之間的潛在聯(lián)系。本文證明了模塊度最大化問題可以被轉(zhuǎn)化成在原網(wǎng)絡(luò)上的最小割圖分割問題,因此所有高效的最小割圖分割算法均可以被應用于本文提出的算法中。此外,本文將模塊化理論和當今比較流行的統(tǒng)計推理模型進行充分結(jié)合,將后者轉(zhuǎn)化成為模塊度最大化問題中的零模型,并將其目標函數(shù)應用在我們的最優(yōu)化策略中?;谏鲜鲎C明和討論,本文提出了一種新的基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法。

    我們在不同規(guī)模(節(jié)點數(shù)量級最高達到百萬級)的真實世界網(wǎng)絡(luò)和人工生成網(wǎng)絡(luò)上測試了本文提出的算法。實驗結(jié)果顯示,本文算法在發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的能力方面具備高效性和穩(wěn)定性;尤其是在諸如冪律分布此類有著強烈不均衡度分布的網(wǎng)絡(luò)中,本文算法依然表現(xiàn)出良好的性能。除了“大規(guī)?!碧匦?,現(xiàn)實社交網(wǎng)絡(luò)的另一個重要特征就是“動態(tài)”特性。因此,我們的后續(xù)研究將重點關(guān)注解決在線或者動態(tài)社區(qū)發(fā)現(xiàn)問題;同樣,我們將會繼續(xù)完善本文算法,以進一步降低其時間復雜度。

    [1]NewmanMEJ,GirvanM.Findingandevaluatingcommunitystructureinnetworks[J].PhysicalReviewE, 2004, 69(2): 026113.

    [2]Fortunato,S.Communitydetectioningraphs[J].PhysicsReports. 2010, 486(3): 75-174.

    [3]ZhouTC,MaH,LyuMR,etal.User-Rec:auserrecommendationframeworkinsocialtaggingsystems[C]//Proceedingsof24thAAAIConferenceonArtificialIntelligence.Atlanta,USA:AAAIPress, 2010: 1486-1491.

    [4]WengJ,LeeBS.EventDetectioninTwitter[C]//Proceedingsof5thInternationalAAAIConferenceonWeblogsandSocialMedia.Barcelona,Spain:AAAIPress, 2011: 401-408.

    [5] 靳延安,李瑞軒,文坤梅,等. 社會標注及其在信息檢索中的應用研究綜述[J]. 中文信息學報,2010,(4): 52-62.

    [6]PapadopoulosS,KompatsiarisY,VakaliA,etal.CommunitydetectioninSocialMedia[J].DataMiningandKnowledgeDiscovery, 2011, 24(3): 515-554.

    [7]ClausetA,NewmanM,MooreC.Findingcommunitystructureinverylargenetworks[J].PhysicalReviewE, 2004, 70(6): 066111.

    [8]NewmanMEJ.Communitydetectionandgraphpartitioning[J].EPL(EurophysicsLetters), 2013, 103(2): 28003.

    [9]KarypisG,KumarV.Afastandhighqualitymultilevelschemeforpartitioningirregulargraphs[J].SIAMJournalonScientificComputing, 1998, 20(1): 359-392.

    [10]CondonA,KarpRM.Algorithmsforgraphpartitioningontheplantedpartitionmodel[J].RandomStructuresandAlgorithms, 2001, 18(2): 116-140.

    [11]AiroldiEM,BleiDM,FienbergSE,etal.Mixedmembershipstochasticblockmodels[J].TheJournalofMachineLearningResearch, 2008, 9: 1981-2014.

    [12]KarrerB,NewmanMEJ.Stochasticblockmodelsandcommunitystructureinnetworks[J].PhysicalReviewE, 2011, 83(1): 016107.

    [13]NewmanMEJ.Findingcommunitystructureinnetworksusingtheeigenvectorsofmatrices[J].PhysicalReviewE, 2006, 74(3): 036104.

    [14]FjallstromP.Algorithmsforgraphpartitioning:asurvey[J].LinkopingElectronicArticlesinComputerandInformationScience, 1998, 3(10) 123-128.

    [15]FiedlerM.Algebraicconnectivityofgraphs[J].CzechoslovakMathematicalJournal, 1973, 23 (98): 298-305.

    [16]KernighanBW,LinS.Anefficientheuristicprocedureforpartitioninggraphs[J].BellSystemTechnicalJournal, 1970, 49: 291-307.

    [17]FlakeGW,TarjanRE,TsioutsiouliklisK.Graphclusteringandminimumcuttrees[J].InternetMathematics, 2004, 1(4): 385-408.

    [18]WhiteS,SmythP.Aspectralapproachtofindcommunitiesingraphs[C]//ProceedingsofSIAMConf.onDataMining. 2005: 76-84.

    [19] 馬力,焦李成,白琳,等. 基于小世界模型的復合關(guān)鍵詞提取方法研究[J]. 中文信息學報,2009,(3): 121-128.

    [20]Erd?sP,RenyiA.Onrandomgraphs[J].Publ.Math, 1959, (6): 290-297.

    [21]ChungF,LuL.Connectedcomponentsinrandomgraphswithgivenexpecteddegreesequences[J].AnnalsofCombinatorics, 2002, 6(2): 125-145.

    [22]FredALN,JainAK.Robustdataclustering[C]//2003IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.Madison,Wisconsin,USA:IEEEPress, 2003:II-128-133.

    [23]ZacharyWW.Aninformationflowmodelforconflictandfissioninsmallgroups[J].JournalofAnthropologicalResearch, 1977, 33(4): 452-473.

    [24]LusseauD,SchneiderK,BoisseauOJ,etal.ThebottlenosedolphincommunityofDoubtfulSoundfeaturesalargeproportionoflong-lastingassociations[J].BehavioralEcologyandSociobiology, 2003, 54(4): 396-405.

    [25]AdamicLA,GlanceN.Thepoliticalblogosphereandthe2004U.S.election[C]//Proceedingsof3rdInternationalWorkshoponLinkDiscovery.NewYork,NewYork,USA:ACMPress, 2005: 36-43.

    [26]LancichinettiA,FortunatoS,RadicchiF.Benchmarkgraphsfortestingcommunitydetectionalgorithms[J].PhysicalReviewE, 2008, (78): 046110.

    [27]ChungF,LuL.Theaveragedistancesinrandomgraphswithgivenexpecteddegrees[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica, 2002, 99(25): 15879-15882.

    [28]LancichinettiA,FortunatoS.Communitydetectionalgorithms:Acomparativeanalysis[J].PhysicalReviewE, 2009, 80: 056117.

    CommunityDetectionBasedonMinimum-CutGraphPartitioning

    WANG Yashen, HUANG Heyan, FENG Chong

    (Beijing Engineering Research Center of High Volume Language Information Processing and Cloud Computing Application, School of Computer, Beijing Institute of Technology, Beijing 100081, China)

    This article demonstrated that modularity maximization issue could be transformed into minimum-cut graph partitioning problem, and proposed an efficient algorithm for detecting community structure. Meanwhile, we combined the modularity theory with popular statistical inference method in two aspects: (i) transforming such statistical model into null model in modularity maximization; (ii) adapting the objective function of statistical inference method for our optimization. The experiments we conducted show that the proposed algorithm is highly effective and stable in discovering community structure from both real-world networks and synthetic networks.

    community detection; modularity; minimum-cut graph partitioning

    王亞珅(1989—),博士研究生,主要研究領(lǐng)域為短文本話題發(fā)現(xiàn)和信息檢索。

    黃河燕(1963—),通信作者,教授、博士生導師,主要研究領(lǐng)域為語言信息智能處理、社交網(wǎng)絡(luò)、文本大數(shù)據(jù)分析處理及云計算。

    馮沖(1977—),副研究員,主要研究領(lǐng)域為機器翻譯、信息抽取、網(wǎng)絡(luò)輿情和社會計算。

    1003-0077(2017)03-0213-10

    2015-04-07定稿日期: 2015-08-27

    國家高技術(shù)研究發(fā)展計劃(863計劃)(2015AA015404)

    TP391

    : A

    猜你喜歡
    最大化節(jié)點社區(qū)
    CM節(jié)點控制在船舶上的應用
    Analysis of the characteristics of electronic equipment usage distance for common users
    社區(qū)大作戰(zhàn)
    幼兒園(2021年6期)2021-07-28 07:42:08
    勉縣:力求黨建“引領(lǐng)力”的最大化
    當代陜西(2021年1期)2021-02-01 07:18:12
    基于AutoCAD的門窗節(jié)點圖快速構(gòu)建
    Advantages and Disadvantages of Studying Abroad
    3D打印社區(qū)
    劉佳炎:回國創(chuàng)業(yè)讓人生價值最大化
    華人時刊(2019年15期)2019-11-26 00:55:44
    在社區(qū)推行“互助式”治理
    當代陜西(2019年16期)2019-09-25 07:28:38
    戴夫:我更愿意把公益性做到最大化
    日韩 亚洲 欧美在线| 国产黄片美女视频| 亚洲人成网站在线播| 少妇人妻精品综合一区二区| 性色avwww在线观看| 国产精品熟女久久久久浪| 亚洲婷婷狠狠爱综合网| 久久6这里有精品| 91久久精品国产一区二区三区| 伦理电影免费视频| 亚洲一级一片aⅴ在线观看| 成人黄色视频免费在线看| 国产 一区精品| 日韩中字成人| 免费观看a级毛片全部| 亚洲精品日韩在线中文字幕| 国产黄色免费在线视频| 蜜臀久久99精品久久宅男| 最黄视频免费看| av福利片在线| 国内揄拍国产精品人妻在线| 又大又黄又爽视频免费| 少妇人妻一区二区三区视频| 深夜a级毛片| 亚洲欧美成人综合另类久久久| 99热国产这里只有精品6| 一区在线观看完整版| 五月伊人婷婷丁香| 国产 一区精品| 少妇人妻 视频| 美女国产视频在线观看| 22中文网久久字幕| 成人毛片a级毛片在线播放| 久久鲁丝午夜福利片| 亚洲欧美日韩东京热| www.av在线官网国产| 不卡视频在线观看欧美| 国产毛片在线视频| 亚洲性久久影院| 免费大片黄手机在线观看| 性高湖久久久久久久久免费观看| 亚洲中文av在线| 久久女婷五月综合色啪小说| 精品国产一区二区三区久久久樱花| 亚洲经典国产精华液单| 大香蕉久久网| 日韩熟女老妇一区二区性免费视频| 大香蕉久久网| 老司机影院毛片| 高清午夜精品一区二区三区| 亚洲国产精品一区二区三区在线| 制服丝袜香蕉在线| 国产成人精品无人区| 国产免费一级a男人的天堂| 日韩人妻高清精品专区| 亚洲精品乱码久久久久久按摩| 久久久午夜欧美精品| 日本午夜av视频| 亚洲av成人精品一二三区| 日韩大片免费观看网站| 国产男人的电影天堂91| 国产亚洲欧美精品永久| 色哟哟·www| 综合色丁香网| 啦啦啦中文免费视频观看日本| 最近中文字幕高清免费大全6| av在线播放精品| 大片免费播放器 马上看| 最近手机中文字幕大全| 国产黄色视频一区二区在线观看| 97精品久久久久久久久久精品| 亚洲色图综合在线观看| 久久99精品国语久久久| 九九久久精品国产亚洲av麻豆| 在线观看三级黄色| 又粗又硬又长又爽又黄的视频| 一边亲一边摸免费视频| 国产精品国产三级国产av玫瑰| 最近最新中文字幕免费大全7| 亚洲av.av天堂| 精品久久久久久久久av| 国产日韩一区二区三区精品不卡 | 欧美成人午夜免费资源| 亚洲av成人精品一区久久| 蜜桃在线观看..| 欧美激情极品国产一区二区三区 | 99九九线精品视频在线观看视频| 日韩成人av中文字幕在线观看| 久久6这里有精品| 精品卡一卡二卡四卡免费| 一本一本综合久久| 欧美3d第一页| 高清毛片免费看| 亚洲丝袜综合中文字幕| 亚洲欧美日韩东京热| 两个人的视频大全免费| 少妇人妻一区二区三区视频| 亚洲精品色激情综合| 桃花免费在线播放| 男女国产视频网站| 一区二区三区四区激情视频| 一本久久精品| 亚洲成人一二三区av| 十八禁高潮呻吟视频 | 成人国产麻豆网| 中文精品一卡2卡3卡4更新| 亚洲欧洲精品一区二区精品久久久 | 最新的欧美精品一区二区| 观看av在线不卡| 黑人高潮一二区| 又粗又硬又长又爽又黄的视频| 人人澡人人妻人| 美女cb高潮喷水在线观看| 99热6这里只有精品| 亚洲成人一二三区av| 精品亚洲乱码少妇综合久久| 欧美97在线视频| av黄色大香蕉| 亚洲va在线va天堂va国产| 女性生殖器流出的白浆| 少妇人妻精品综合一区二区| 美女xxoo啪啪120秒动态图| 制服丝袜香蕉在线| 少妇丰满av| 欧美人与善性xxx| 国产精品一区二区三区四区免费观看| 成人毛片60女人毛片免费| 国产一区二区在线观看日韩| 国产精品欧美亚洲77777| 日本爱情动作片www.在线观看| 老司机亚洲免费影院| 久久久久久久大尺度免费视频| 一级爰片在线观看| 免费看不卡的av| 国产精品一区二区在线观看99| 亚洲精品日韩在线中文字幕| 99热国产这里只有精品6| 亚洲一级一片aⅴ在线观看| 中国国产av一级| 久久国内精品自在自线图片| 久久精品夜色国产| 97在线人人人人妻| 欧美精品高潮呻吟av久久| 欧美+日韩+精品| 亚洲av日韩在线播放| 国产熟女午夜一区二区三区 | 欧美精品国产亚洲| 一级毛片久久久久久久久女| 国产在视频线精品| 色视频www国产| 熟妇人妻不卡中文字幕| 男女无遮挡免费网站观看| 黄色一级大片看看| 汤姆久久久久久久影院中文字幕| 欧美bdsm另类| 亚洲精品国产成人久久av| 大香蕉97超碰在线| 精品亚洲乱码少妇综合久久| 国产探花极品一区二区| 成人毛片60女人毛片免费| 日韩制服骚丝袜av| 国产男女内射视频| 91久久精品国产一区二区成人| 丝袜脚勾引网站| 中文字幕免费在线视频6| 又黄又爽又刺激的免费视频.| 国产精品99久久久久久久久| 交换朋友夫妻互换小说| 少妇丰满av| 亚洲中文av在线| 国产熟女欧美一区二区| 一区二区三区精品91| 一本色道久久久久久精品综合| 久久青草综合色| 国产精品国产三级国产专区5o| 久久精品熟女亚洲av麻豆精品| 免费av不卡在线播放| 观看av在线不卡| av天堂久久9| av国产久精品久网站免费入址| 乱系列少妇在线播放| 精品亚洲成国产av| 国产欧美亚洲国产| 街头女战士在线观看网站| 夫妻午夜视频| 春色校园在线视频观看| 亚洲人成网站在线播| 午夜免费男女啪啪视频观看| 亚洲一区二区三区欧美精品| 自拍欧美九色日韩亚洲蝌蚪91 | 在线播放无遮挡| 精品熟女少妇av免费看| 日韩制服骚丝袜av| 嫩草影院新地址| 久久精品国产亚洲网站| 精品久久久噜噜| 久久久国产精品麻豆| av免费观看日本| 久久ye,这里只有精品| 国产精品99久久99久久久不卡 | 夜夜骑夜夜射夜夜干| 18禁动态无遮挡网站| av视频免费观看在线观看| 国产av码专区亚洲av| 九九久久精品国产亚洲av麻豆| 一区二区三区四区激情视频| 国产无遮挡羞羞视频在线观看| 赤兔流量卡办理| 在线看a的网站| 亚洲精品乱久久久久久| 男男h啪啪无遮挡| 国产亚洲一区二区精品| 精品视频人人做人人爽| 欧美激情极品国产一区二区三区 | 久久精品国产鲁丝片午夜精品| 黄色一级大片看看| 国产极品天堂在线| 七月丁香在线播放| 少妇猛男粗大的猛烈进出视频| 久久人人爽人人片av| 人妻 亚洲 视频| 大话2 男鬼变身卡| 99热网站在线观看| 热re99久久国产66热| 欧美日韩亚洲高清精品| 伦精品一区二区三区| 日本与韩国留学比较| 日韩av免费高清视频| 97在线视频观看| 婷婷色综合www| 99热这里只有精品一区| 国产精品人妻久久久久久| 午夜福利网站1000一区二区三区| 久久久久视频综合| 亚洲综合精品二区| 18禁动态无遮挡网站| 亚洲久久久国产精品| 久久久久久久久久久久大奶| 我的女老师完整版在线观看| av国产精品久久久久影院| 国产日韩欧美视频二区| 在线观看免费视频网站a站| 大话2 男鬼变身卡| 精品久久久久久电影网| 六月丁香七月| 欧美 日韩 精品 国产| 91精品一卡2卡3卡4卡| 天天操日日干夜夜撸| 爱豆传媒免费全集在线观看| 亚洲欧美清纯卡通| 欧美成人午夜免费资源| 性高湖久久久久久久久免费观看| 成人黄色视频免费在线看| 9色porny在线观看| 一级黄片播放器| av在线老鸭窝| 老司机影院毛片| 国产一区二区在线观看av| 日本av手机在线免费观看| 妹子高潮喷水视频| 亚洲精华国产精华液的使用体验| 久久久亚洲精品成人影院| 九色成人免费人妻av| 好男人视频免费观看在线| 国产深夜福利视频在线观看| av有码第一页| 免费播放大片免费观看视频在线观看| 免费大片18禁| 国产一级毛片在线| 免费看光身美女| 国产黄频视频在线观看| 亚洲av电影在线观看一区二区三区| 久久久久网色| 青春草视频在线免费观看| av.在线天堂| 亚洲av.av天堂| 最后的刺客免费高清国语| 国产乱人偷精品视频| av天堂中文字幕网| 亚洲伊人久久精品综合| 成人无遮挡网站| 九九爱精品视频在线观看| 女性生殖器流出的白浆| a级毛片在线看网站| 激情五月婷婷亚洲| 99热全是精品| 久久亚洲国产成人精品v| 日韩av不卡免费在线播放| 97在线视频观看| 久久久久精品性色| 精品视频人人做人人爽| 少妇人妻 视频| 我要看日韩黄色一级片| 大香蕉97超碰在线| av在线老鸭窝| 老司机影院毛片| 十分钟在线观看高清视频www | 美女视频免费永久观看网站| 欧美+日韩+精品| 免费人妻精品一区二区三区视频| 中国国产av一级| 一级av片app| av有码第一页| www.色视频.com| 人妻人人澡人人爽人人| videos熟女内射| 国产精品一区二区性色av| 国产国拍精品亚洲av在线观看| 大香蕉97超碰在线| 成人综合一区亚洲| 天天操日日干夜夜撸| 狂野欧美激情性xxxx在线观看| a级毛色黄片| 色5月婷婷丁香| 精品国产乱码久久久久久小说| 亚洲高清免费不卡视频| 亚洲不卡免费看| 久久久久久久久久人人人人人人| 桃花免费在线播放| 亚洲精品日本国产第一区| 精品一品国产午夜福利视频| 男人舔奶头视频| 中国国产av一级| 亚洲av不卡在线观看| 国产黄片美女视频| 国产精品国产三级国产av玫瑰| 久久久久精品性色| 色5月婷婷丁香| 99热国产这里只有精品6| 亚洲国产最新在线播放| 国产亚洲av片在线观看秒播厂| 男女免费视频国产| 国产男女内射视频| 久久精品久久久久久久性| 国产成人freesex在线| 欧美精品一区二区免费开放| 高清不卡的av网站| 三上悠亚av全集在线观看 | 久久人人爽av亚洲精品天堂| 女的被弄到高潮叫床怎么办| 成人亚洲精品一区在线观看| 亚洲一级一片aⅴ在线观看| 日韩亚洲欧美综合| 在线观看一区二区三区激情| 欧美精品一区二区大全| 亚洲情色 制服丝袜| 亚洲av不卡在线观看| 99视频精品全部免费 在线| 免费不卡的大黄色大毛片视频在线观看| av不卡在线播放| 秋霞伦理黄片| 在线观看免费日韩欧美大片 | 在线观看美女被高潮喷水网站| 亚洲国产成人一精品久久久| 国产高清不卡午夜福利| 亚洲精品色激情综合| 亚洲欧美日韩另类电影网站| a级片在线免费高清观看视频| 国产精品福利在线免费观看| 一区二区三区四区激情视频| 黑人巨大精品欧美一区二区蜜桃 | 51国产日韩欧美| 亚洲在久久综合| 草草在线视频免费看| 一级毛片我不卡| 男人添女人高潮全过程视频| 自拍偷自拍亚洲精品老妇| 久久韩国三级中文字幕| 国产一区有黄有色的免费视频| 中文天堂在线官网| 偷拍熟女少妇极品色| 极品少妇高潮喷水抽搐| av网站免费在线观看视频| 在线观看国产h片| 国产精品蜜桃在线观看| 国产精品久久久久久久电影| av一本久久久久| 亚洲精品456在线播放app| 精品国产露脸久久av麻豆| 多毛熟女@视频| 一级av片app| 精品熟女少妇av免费看| 美女xxoo啪啪120秒动态图| 国产精品国产三级国产专区5o| 夫妻性生交免费视频一级片| √禁漫天堂资源中文www| 亚洲国产欧美日韩在线播放 | 国产免费一区二区三区四区乱码| 亚洲av成人精品一区久久| 国产精品偷伦视频观看了| 亚洲国产最新在线播放| av专区在线播放| 日韩不卡一区二区三区视频在线| 国产精品99久久99久久久不卡 | 妹子高潮喷水视频| 亚洲成色77777| 噜噜噜噜噜久久久久久91| 中文在线观看免费www的网站| 亚洲激情五月婷婷啪啪| 久久 成人 亚洲| 国产av一区二区精品久久| 亚洲国产av新网站| 99热全是精品| 国产黄片美女视频| a级毛片免费高清观看在线播放| 久久久久久久国产电影| 亚洲av欧美aⅴ国产| av国产久精品久网站免费入址| 成年女人在线观看亚洲视频| 日韩伦理黄色片| 久久久久网色| 黄色一级大片看看| 丰满乱子伦码专区| 亚洲国产成人一精品久久久| 国产免费福利视频在线观看| 一级二级三级毛片免费看| 精品人妻一区二区三区麻豆| 只有这里有精品99| 亚洲综合精品二区| 亚洲国产精品999| 国产精品人妻久久久影院| 免费黄网站久久成人精品| 男女边摸边吃奶| 日日摸夜夜添夜夜爱| 国产av一区二区精品久久| 我的女老师完整版在线观看| 最近2019中文字幕mv第一页| 亚洲真实伦在线观看| 亚洲va在线va天堂va国产| 国产又色又爽无遮挡免| 亚洲一级一片aⅴ在线观看| 另类精品久久| 国产免费福利视频在线观看| 大片免费播放器 马上看| 精品少妇黑人巨大在线播放| 国产精品三级大全| 国产日韩欧美亚洲二区| 欧美bdsm另类| 三级国产精品片| av网站免费在线观看视频| 亚洲精品国产av成人精品| 女性生殖器流出的白浆| 国产精品一区二区在线不卡| 国产色婷婷99| 亚洲国产精品专区欧美| 亚洲成人一二三区av| 男人舔奶头视频| 老司机影院成人| 美女脱内裤让男人舔精品视频| 校园人妻丝袜中文字幕| 亚洲精品一二三| 久久久精品94久久精品| 黄色欧美视频在线观看| 哪个播放器可以免费观看大片| 妹子高潮喷水视频| 国内揄拍国产精品人妻在线| 久久久久久久亚洲中文字幕| a级毛片免费高清观看在线播放| 在线播放无遮挡| 免费观看无遮挡的男女| 天堂中文最新版在线下载| 狂野欧美白嫩少妇大欣赏| 国产精品福利在线免费观看| 久久精品国产亚洲av天美| 各种免费的搞黄视频| 国产高清不卡午夜福利| 少妇裸体淫交视频免费看高清| 看十八女毛片水多多多| 老司机亚洲免费影院| freevideosex欧美| 国产欧美日韩一区二区三区在线 | av国产久精品久网站免费入址| 成年美女黄网站色视频大全免费 | 97超碰精品成人国产| 国产av国产精品国产| 人体艺术视频欧美日本| 水蜜桃什么品种好| 一区在线观看完整版| 亚洲国产精品国产精品| 精品久久国产蜜桃| 日本黄色日本黄色录像| 日韩免费高清中文字幕av| 久久免费观看电影| 亚洲国产欧美日韩在线播放 | 秋霞伦理黄片| 久久精品久久精品一区二区三区| 插逼视频在线观看| 久久人人爽人人片av| 99热国产这里只有精品6| tube8黄色片| a级毛片免费高清观看在线播放| 欧美日本中文国产一区发布| 婷婷色综合www| 亚洲av国产av综合av卡| 蜜桃久久精品国产亚洲av| 黑人高潮一二区| 在线播放无遮挡| 国产黄片视频在线免费观看| 天堂中文最新版在线下载| 日韩一区二区三区影片| 精品一区二区免费观看| 青春草视频在线免费观看| 欧美日韩视频高清一区二区三区二| 欧美日韩综合久久久久久| 久久久久精品性色| 观看av在线不卡| 国产精品麻豆人妻色哟哟久久| 成人特级av手机在线观看| 女人久久www免费人成看片| 在现免费观看毛片| 日本与韩国留学比较| 国产日韩欧美亚洲二区| 亚洲欧洲精品一区二区精品久久久 | 成年人午夜在线观看视频| 亚洲欧美精品专区久久| 又爽又黄a免费视频| 激情五月婷婷亚洲| 黄色日韩在线| 中文字幕精品免费在线观看视频 | 欧美xxⅹ黑人| 热re99久久精品国产66热6| 亚洲国产精品专区欧美| 欧美高清成人免费视频www| 久久韩国三级中文字幕| 久久免费观看电影| 纯流量卡能插随身wifi吗| 在线观看三级黄色| 99re6热这里在线精品视频| 美女cb高潮喷水在线观看| 国产精品成人在线| 国产高清三级在线| 9色porny在线观看| 插逼视频在线观看| 日本黄色片子视频| 亚州av有码| 在线精品无人区一区二区三| 大香蕉97超碰在线| 一区在线观看完整版| 欧美一级a爱片免费观看看| 午夜免费鲁丝| 国产精品一区二区性色av| 欧美成人精品欧美一级黄| 亚洲国产欧美在线一区| 精品少妇黑人巨大在线播放| 国产老妇伦熟女老妇高清| 国产一区二区三区av在线| 一个人免费看片子| 9色porny在线观看| 天堂中文最新版在线下载| 美女视频免费永久观看网站| 国产成人精品婷婷| 亚洲中文av在线| 亚洲欧美一区二区三区国产| 精品久久久久久电影网| 午夜免费男女啪啪视频观看| 成人无遮挡网站| 国产精品偷伦视频观看了| 久久久a久久爽久久v久久| 9色porny在线观看| 亚洲欧美一区二区三区黑人 | 精品午夜福利在线看| 内射极品少妇av片p| 热99国产精品久久久久久7| 深夜a级毛片| 在线观看一区二区三区激情| 久久精品久久精品一区二区三区| av网站免费在线观看视频| 高清毛片免费看| 国产亚洲最大av| 精品国产露脸久久av麻豆| 国产亚洲一区二区精品| 亚洲国产欧美在线一区| 亚洲中文av在线| 久久人人爽人人片av| 最近最新中文字幕免费大全7| 99国产精品免费福利视频| 色婷婷久久久亚洲欧美| 久久精品国产自在天天线| 日韩欧美一区视频在线观看 | 中文天堂在线官网| 99久久人妻综合| 国产精品女同一区二区软件| 黑丝袜美女国产一区| 另类精品久久| 一边亲一边摸免费视频| av有码第一页| 三级国产精品片| 桃花免费在线播放| 国产一区二区三区综合在线观看 | 亚洲国产最新在线播放| 黄片无遮挡物在线观看| 国产日韩欧美在线精品| 毛片一级片免费看久久久久| 一区二区三区精品91| 欧美97在线视频| 热re99久久国产66热| 日本与韩国留学比较| 久久精品熟女亚洲av麻豆精品| 亚洲婷婷狠狠爱综合网| 如日韩欧美国产精品一区二区三区 | 男人狂女人下面高潮的视频| 日韩av免费高清视频| 久久久国产精品麻豆| 久久99热6这里只有精品| 久久人人爽人人爽人人片va| 黄色日韩在线| a级毛色黄片| 久久久国产一区二区| 色网站视频免费| 国产精品久久久久久久久免| 国国产精品蜜臀av免费| 日本免费在线观看一区| 如何舔出高潮| 伦理电影免费视频| 精品国产一区二区三区久久久樱花|