• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      大規(guī)模時(shí)序圖中持續(xù)性稠密子圖搜索算法研究

      2022-02-24 12:32:40劉金生趙會(huì)群
      關(guān)鍵詞:枚舉子圖數(shù)據(jù)源

      李 源,劉金生,趙會(huì)群,孫 晶

      北方工業(yè)大學(xué) 信息學(xué)院,北京 100144

      時(shí)序圖是一個(gè)隨時(shí)間不斷變化的圖結(jié)構(gòu),其中邊上的時(shí)間戳代表該邊出現(xiàn)的時(shí)間。這一模型具有很多現(xiàn)實(shí)應(yīng)用。例如,社交網(wǎng)絡(luò)[1-2]、作家協(xié)作網(wǎng)絡(luò)[3]、生物信息網(wǎng)絡(luò)[4]等。稠密子圖挖掘問(wèn)題(cohesive subgraph mining,CSM)作為圖計(jì)算的基礎(chǔ)研究問(wèn)題之一,近幾年被越來(lái)越多的學(xué)者在時(shí)序圖上進(jìn)行深入研究。一般來(lái)講,CSM分為不考慮查詢節(jié)點(diǎn)的稠密子圖檢測(cè)問(wèn)題(cohesive subgraph detection,CSD)和考慮查詢節(jié)點(diǎn)的稠密子圖搜索問(wèn)題(cohesive subgraph search,CSS)兩類。時(shí)序圖上的CSD問(wèn)題已經(jīng)被學(xué)者們廣泛研究。但是,當(dāng)時(shí)序圖規(guī)模過(guò)大時(shí),發(fā)現(xiàn)時(shí)序圖中所有的稠密子圖將變得不切實(shí)際。為此,本文將主要研究在時(shí)序圖中長(zhǎng)期被忽視的CSS問(wèn)題。該問(wèn)題的描述如下:給定一個(gè)特定的查詢節(jié)點(diǎn),找到包含該查詢節(jié)點(diǎn),且滿足一定時(shí)間和結(jié)構(gòu)約束條件的子圖。由于查詢節(jié)點(diǎn)的引入,這一問(wèn)題將具有更強(qiáng)的現(xiàn)實(shí)意義。

      在真實(shí)的時(shí)序網(wǎng)絡(luò)中找到在一段時(shí)間內(nèi)持續(xù)出現(xiàn)的稠密子圖通常是很有意義的[5]。為此,本研究采用(θ,τ)持續(xù)性k-核子圖模型。其中,參數(shù)θ表示判定持續(xù)性的最大間隔。即,將連續(xù)出現(xiàn)兩次時(shí)間間隔小于θ的子圖視為不間斷的。參數(shù)τ用于表示最短持續(xù)時(shí)間約束,即子圖不間斷的時(shí)間至少應(yīng)為τ。參數(shù)k用于結(jié)果子圖的結(jié)構(gòu)約束,即子圖中所有節(jié)點(diǎn)都至少有k個(gè)鄰居。從后文實(shí)驗(yàn)可以看出,參數(shù)θ和τ根據(jù)實(shí)際應(yīng)用場(chǎng)景而變化。當(dāng)時(shí)序圖變化較為頻繁時(shí),θ應(yīng)取值較??;當(dāng)時(shí)序圖變化不頻繁時(shí),θ取值可以適當(dāng)增大。τ值可以根據(jù)實(shí)際需要定義,一般來(lái)說(shuō),τ值較大時(shí),問(wèn)題的時(shí)間約束更加嚴(yán)格,查詢結(jié)果個(gè)數(shù)會(huì)更少。本文將研究大規(guī)模時(shí)序圖中,找到一個(gè)包含特定查詢節(jié)點(diǎn)且滿足該模型的時(shí)序子圖。例如,圖1中包含兩個(gè)(2,3)持續(xù)性3-核子圖,分別是H0={v0,v1,v2,v3}和H1={v0,v4,v5,v6}。

      圖1 一個(gè)時(shí)序圖的實(shí)例Fig.1 Example of temporal graph

      本研究首先證明了時(shí)序圖中查詢(θ,τ)持續(xù)性k-核子圖是NP-難問(wèn)題。為解決這一問(wèn)題,本文提出通過(guò)全局和局部?jī)煞N思路設(shè)計(jì)的算法,分別命名為S-Global和S-Center算法。其中S-Global算法從全局角度出發(fā),不斷刪除不滿足條件的節(jié)點(diǎn),最后得到一個(gè)極大的(θ,τ)持續(xù)性k-核圖。在此過(guò)程中,將通過(guò)提出的削減規(guī)則減少搜索空間。另一個(gè)算法S-Center從查詢節(jié)點(diǎn)出發(fā),以查詢節(jié)點(diǎn)為中心將其他節(jié)點(diǎn)分層,不斷地在候選結(jié)果的鄰接點(diǎn)中找到正確的節(jié)點(diǎn)加入子圖,直到找到目標(biāo)結(jié)果。這種方式的優(yōu)點(diǎn)是無(wú)需遍歷整個(gè)時(shí)序圖。在四個(gè)真實(shí)世界網(wǎng)絡(luò)中的大量實(shí)驗(yàn),驗(yàn)證了提出算法的高效性。其中S-Global算法更適用于時(shí)序圖較為稠密的場(chǎng)景,而S-Center算法則適用于稀疏圖場(chǎng)景。

      1 相關(guān)工作

      時(shí)序圖上的稠密子圖檢測(cè)問(wèn)題已經(jīng)被學(xué)者們廣泛研究。吳歡歡等人提出了一種時(shí)序圖上的(k,h)-核模型,即子圖中每個(gè)頂點(diǎn)至少有k個(gè)鄰接點(diǎn)和h條時(shí)序邊[6]。馬帥等人提出一種算法,在加權(quán)時(shí)序圖中通過(guò)時(shí)間快照計(jì)算權(quán)值找到一個(gè)時(shí)間段內(nèi)的密集連接子圖[7]。瑟莫茲團(tuán)隊(duì)的工作是在時(shí)序圖的所有時(shí)間快照上找到一個(gè)持久的密集子圖[8]。黃欣等人基于k-truss模型,提出了一種基于TCP索引找到包含最大k的查詢頂點(diǎn)的k-truss的方法[9]。

      在不同類型的圖結(jié)構(gòu)中,稠密子圖的搜索問(wèn)題同樣已經(jīng)被深入研究。例如,基于靜態(tài)屬性圖中,文獻(xiàn)[10]提出了一種基于k-核的方法,以找到包含查詢節(jié)點(diǎn)的稠密子圖。在加權(quán)的屬性圖中,文獻(xiàn)[11]提出了一種方法來(lái)找到權(quán)值較高的內(nèi)聚子圖。在地理社交網(wǎng)絡(luò)中,文獻(xiàn)[12]提出了一種基于位置信息找到圖中稠密子圖的方法。然而,時(shí)序圖中稠密子圖搜索問(wèn)題則尚未被充分研究。

      2 問(wèn)題定義及相關(guān)概念

      本文用G(V,E)表示一個(gè)無(wú)向時(shí)序圖。其中,V和E分別代表節(jié)點(diǎn)集和邊集。用n=|V|和m=|E|分別表示節(jié)點(diǎn)數(shù)量和邊的數(shù)量。每一條時(shí)序邊e∈E是一個(gè)三元組(u,v,t)。其中u和v都是V中的節(jié)點(diǎn),并在t時(shí)刻上產(chǎn)生聯(lián)系。這里假設(shè)所有時(shí)間都是整數(shù)。注意,若t i≠t j,(u,v,t i)和(u,v,t j)將會(huì)是兩條不同的時(shí)序邊。對(duì)于V的一個(gè)子集S,用G[S]表示它的誘導(dǎo)子圖,且E(S)={(u,v,t)|u,v∈S,(u,v,t)∈E}表示G[]S中的邊集。用N G(u)={(v,t)|(u,v,t)∈E}表示u在G中的時(shí)序鄰居集合。最后,用G′(V′,E′,T C)來(lái)表示一個(gè)時(shí)序圖G在一個(gè)時(shí)間段T C=[t i,t j]的靜態(tài)投影圖。例如圖2是圖1在時(shí)間段[4,6]上的靜態(tài)投影圖。

      圖2 圖1在[4,6]上的靜態(tài)投影圖Fig.2 Static projection of Fig.1 in[4,6]

      2.1 滑動(dòng)窗口模型的使用

      在靜態(tài)圖中,k-核圖通常是結(jié)構(gòu)內(nèi)聚的。其中,每個(gè)節(jié)點(diǎn)都至少有k個(gè)鄰居[13-15]。在時(shí)序圖中,這種內(nèi)聚子圖通常需要持續(xù)存在一段時(shí)間才是有意義的。本研究中用(θ,τ)持續(xù)性k-核圖定義時(shí)序圖中的一個(gè)持續(xù)出現(xiàn)的內(nèi)聚子圖,并用滑動(dòng)窗口模型找到這種內(nèi)聚子圖。其中θ將作為滑動(dòng)窗口的長(zhǎng)度。τ將成為一個(gè)時(shí)序子圖通過(guò)滑動(dòng)窗口計(jì)算的最小有效壽命,后文中會(huì)有詳細(xì)定義。接下來(lái)將給出在滑動(dòng)窗口模型的基礎(chǔ)上一個(gè)節(jié)點(diǎn)的有效壽命定義。

      定義1(節(jié)點(diǎn)有效壽命)給定一個(gè)時(shí)序圖G(V,E),節(jié)點(diǎn)u∈V,參數(shù)θ,k。節(jié)點(diǎn)u的有效壽命被定義為:當(dāng)u的度數(shù)在θ長(zhǎng)度的滑動(dòng)窗口內(nèi)大于k時(shí),滑動(dòng)窗口的移動(dòng)覆蓋區(qū)間。

      例如,當(dāng)核數(shù)k=3,滑動(dòng)窗口長(zhǎng)度θ=2時(shí),v3的在整個(gè)時(shí)序圖中有效壽命有三段,分別是[0,2]、[4,6]和[9,14]。即滑動(dòng)窗口在這些時(shí)間區(qū)內(nèi)滑動(dòng)時(shí),v3在滑動(dòng)窗口內(nèi)的度數(shù)都大于3。

      由于在實(shí)際應(yīng)用中,相同時(shí)間長(zhǎng)度的情況下,連續(xù)不斷的有效壽命比斷斷續(xù)續(xù)的有效壽命更加具有實(shí)際意義。所以在本研究中重新定義一個(gè)節(jié)點(diǎn)的有效壽命長(zhǎng)度。

      定義2(節(jié)點(diǎn)有效壽命長(zhǎng)度)時(shí)序圖G中的一個(gè)節(jié)點(diǎn)u通過(guò)θ長(zhǎng)度的滑動(dòng)窗口得到的有效壽命后,其長(zhǎng)度δG(u)的計(jì)算方式為:

      其中,r表示節(jié)點(diǎn)u的有效壽命中不連續(xù)的極大有效壽命段的數(shù)量,t sp、t ep分別表示第p個(gè)極大有效壽命段的開(kāi)始和結(jié)束時(shí)間。例如圖1中,當(dāng)k=3,θ=2時(shí),v3在整個(gè)時(shí)序圖內(nèi)的有效壽命δG(v)3=(2-0)+(6-4)+(14-9)-2×2=5。

      值得注意的是,當(dāng)時(shí)序圖結(jié)構(gòu)發(fā)生改變時(shí),一個(gè)節(jié)點(diǎn)的有效壽命及壽命長(zhǎng)度也要隨之改變。例如圖1中,若只考慮子圖H0={v0,v1,v2,v3},則節(jié)點(diǎn)v3的壽命將變?yōu)閮啥?,分別是[0,2]和[9,14]。其有效壽命δH0(v)3=(2-0)+(14-9)-1×2=5。

      2.2 問(wèn)題定義及分析

      接下來(lái)基于以上定義,將給出(θ,τ)持續(xù)性k-核圖模型的定義和本研究的問(wèn)題定義。

      定義3((θ,τ)持續(xù)性k-核圖)給定一個(gè)時(shí)序圖G(V,E),參數(shù)θ、τ、k。在θ長(zhǎng)度的滑動(dòng)窗口模型中,若對(duì)于?v∈V,δG(u)>τ,則G是一個(gè)(θ,τ)持續(xù)性k-核圖。

      定義4((θ,τ)持續(xù)性k-核子圖搜索問(wèn)題)給定一個(gè)時(shí)序圖G(V,E),參數(shù)θ、τ、k和一個(gè)查詢節(jié)點(diǎn)q。找到一個(gè)G中的一個(gè)誘導(dǎo)子圖G[]S滿足如下條件:(1)q∈S。(2)G[]S是一個(gè)(θ,τ)持續(xù)性k-核圖。(3)G[S]不會(huì)被其他滿足條件(1)和(2)的誘導(dǎo)子圖完全包含。

      接下來(lái),定理1證明了(θ,τ)持續(xù)性k-核圖搜索問(wèn)題為NP-難的。

      定理1時(shí)序圖中包含查詢節(jié)點(diǎn)的(θ,τ)持續(xù)性k-核圖搜索問(wèn)題是一個(gè)NP-難問(wèn)題。

      證明 此處可將(θ,τ)持續(xù)性k-核子圖搜索問(wèn)題轉(zhuǎn)化為包含查詢節(jié)點(diǎn)的子圖檢測(cè)問(wèn)題。在得到一個(gè)時(shí)序圖G之后,新建一個(gè)虛擬節(jié)點(diǎn)q作為查詢節(jié)點(diǎn)。令q與圖G中所有節(jié)點(diǎn)在G中出現(xiàn)的每一個(gè)時(shí)間戳上都有一條時(shí)序邊相連,將這個(gè)新構(gòu)造的虛擬圖(G∪q)記為G*。根據(jù)構(gòu)造條件,G*中的任何(θ,τ)持續(xù)性k-核子圖都包含q,因此G*上的搜索問(wèn)題就轉(zhuǎn)化為G中(θ,τ)持續(xù)性k-核圖檢測(cè)問(wèn)題,而這一問(wèn)題已經(jīng)被證明是NP-難的[6],所以本研究的問(wèn)題同樣是NP-難的。

      3 搜索算法

      在搜索算法開(kāi)始之前,需要對(duì)時(shí)序圖進(jìn)行預(yù)處理以對(duì)時(shí)序圖進(jìn)行初步削減,隨后在削減后的時(shí)序圖中進(jìn)行搜索算法找到目標(biāo)子圖。首先通過(guò)滑動(dòng)窗口模型算法構(gòu)建一個(gè)θ長(zhǎng)度的窗口,并令其在時(shí)序圖的時(shí)間戳范圍內(nèi)滑動(dòng),以窗口右端作為窗口的位置,記錄滑動(dòng)窗口在每一個(gè)時(shí)間戳上,每一個(gè)節(jié)點(diǎn)在窗口內(nèi)的度數(shù),以此構(gòu)成一個(gè)度數(shù)時(shí)序矩陣J。其中J[i][j]表示節(jié)點(diǎn)v i在滑動(dòng)窗口走到時(shí)間戳t=j時(shí)的度數(shù)。在得到查詢節(jié)點(diǎn)q,參數(shù)k、θ、τ之后,可以通過(guò)矩陣J,得出所有節(jié)點(diǎn)的有效壽命,刪除那些與查詢節(jié)點(diǎn)的壽命交集小于τ的節(jié)點(diǎn),將剩余節(jié)點(diǎn)計(jì)入候選節(jié)點(diǎn)集Ca,Ca中將可能包含一個(gè)(θ,τ)持續(xù)性k-核圖。接下來(lái),本章中提出兩種基于枚舉的算法找到這個(gè)子圖。

      3.1 S-Global算法

      在預(yù)處理部分得到候選節(jié)點(diǎn)集Ca之后,本算法從全局的角度出發(fā),即從所有候選節(jié)點(diǎn)與查詢節(jié)點(diǎn)構(gòu)成的子圖開(kāi)始,在每一次的枚舉中找出一個(gè)待刪除的節(jié)點(diǎn)集合,然后判斷剩余的節(jié)點(diǎn)集合能否構(gòu)成一個(gè)符合要求的結(jié)果。

      算法1是本算法的詳細(xì)細(xì)節(jié)。其中R是最終要找到的極大結(jié)果子圖集合,De是每次枚舉過(guò)程中要?jiǎng)h除的節(jié)點(diǎn)集合,Safe是安全節(jié)點(diǎn)集合(第1行)。當(dāng)?shù)玫揭粋€(gè)候選節(jié)點(diǎn)集之后首先將Ca中的所有節(jié)點(diǎn)按其靜態(tài)投影度數(shù)排序(第2行)。在第一次遞歸中需要判斷Ca是否滿足(θ,τ)持續(xù)性k-核圖的條件,若滿足,則Ca構(gòu)成的誘導(dǎo)子圖就是圖G中的極大結(jié)果(第3行)。若不滿足,則進(jìn)入之后的遞歸操作。每一次按照順序?qū)⒁粋€(gè)節(jié)點(diǎn)u加入進(jìn)De準(zhǔn)備刪除(第5行),對(duì)于剩余的子圖,先判斷其有效壽命是否大于τ(第6行),若大于τ,則這個(gè)子圖中的極大k-核圖就是一個(gè)極大結(jié)果,將其代入R并停止遞歸(第12行)。否則,繼續(xù)向后按順序?qū)之后的節(jié)點(diǎn)進(jìn)行遞歸判斷(第17行)。當(dāng)一個(gè)節(jié)點(diǎn)完成遞歸之后,保留這個(gè)節(jié)點(diǎn)作為安全節(jié)點(diǎn)進(jìn)入節(jié)點(diǎn)集Safe(第18行)。注意,每次更新子圖時(shí)都要對(duì)度數(shù)時(shí)序矩陣J進(jìn)行更新(第11和19行)所有遞歸判斷完成后,將R內(nèi)的所有子圖輸出作為結(jié)果(第4行)。

      為了減少枚舉,也就是遞歸判斷的次數(shù),本算法中使用了三個(gè)枚舉約簡(jiǎn)規(guī)則:

      規(guī)則1當(dāng)枚舉到一個(gè)節(jié)點(diǎn)u時(shí),若剩余子圖的有效壽命已經(jīng)大于τ,則無(wú)需枚舉u之后的節(jié)點(diǎn)。

      規(guī)則2當(dāng)枚舉到一個(gè)節(jié)點(diǎn)u時(shí),如果存在某個(gè)Safe中的節(jié)點(diǎn)不滿足k-核條件,則本次枚舉失效。

      規(guī)則3在枚舉一個(gè)節(jié)點(diǎn)u之前,若Safe集合構(gòu)成的子圖壽命小于τ,則u及u之后的節(jié)點(diǎn)都無(wú)需枚舉。

      以圖1為例,假設(shè)q=v0,θ=2,τ=5,k=3,最初Safe={v0},Ca={v2,v3,v6,v1,v4,v5}。顯然q與Ca內(nèi)的節(jié)點(diǎn)不能直接構(gòu)成一個(gè)(θ,τ)持續(xù)性k-核圖。將v2加入De。此時(shí)由于G[Ca/De]的有效壽命小于τ,根據(jù)枚舉約簡(jiǎn)規(guī)則1繼續(xù)將Ca內(nèi)v2后面的節(jié)點(diǎn)加入De中,直到De={v6,v4,v5},Ca/De={v2,v3,v1}。此時(shí)G[Ca/De]的有效壽命為[0,2]∪[9,14],有效壽命長(zhǎng)度是6,大于τ,與此同時(shí),G[(Ca/De)∪q]的靜態(tài)投影是一個(gè)k-核圖,則將這個(gè)子圖保存至R中。當(dāng)所有枚舉操作完成后,得到本例的唯一結(jié)果子圖{v2,v3,v1,v0}。

      由于本算法涉及到枚舉操作,枚舉Ca中節(jié)點(diǎn)的所有組合,所以本算法的時(shí)間復(fù)雜度為O(2nCa),n Ca是Ca中的節(jié)點(diǎn)個(gè)數(shù)。但由于枚舉約簡(jiǎn)規(guī)則的存在,算法的實(shí)際運(yùn)行時(shí)間將遠(yuǎn)遠(yuǎn)小于2n Ca。

      3.2 S-Center算法

      在S-Global算法中,由于需要遍歷整個(gè)Ca構(gòu)成的子圖,當(dāng)Ca內(nèi)節(jié)點(diǎn)數(shù)量較多時(shí),這一枚舉算法將產(chǎn)生較大的時(shí)間開(kāi)銷。本節(jié)中提出的S-Center算法將從查詢節(jié)點(diǎn)出發(fā),每次枚舉其鄰域中的一個(gè)節(jié)點(diǎn)進(jìn)入子圖,直到找到一個(gè)極大的(θ,τ)持續(xù)性k-核圖。在進(jìn)行該算法之前,首先要將Ca中的所有節(jié)點(diǎn)進(jìn)行分層,令查詢節(jié)點(diǎn)在第0層,其余所有節(jié)點(diǎn)的層數(shù)是其到查詢節(jié)點(diǎn)的最短距離。隨后在算法中,與S-Global中的枚舉方式類似,在對(duì)Ca中的節(jié)點(diǎn)排序之后,每一次枚舉一個(gè)節(jié)點(diǎn)進(jìn)入待查子圖中,但不同的是,在一個(gè)節(jié)點(diǎn)進(jìn)入子圖后,隨后枚舉的節(jié)點(diǎn)只有這個(gè)節(jié)點(diǎn)下一層的節(jié)點(diǎn)與同層該節(jié)點(diǎn)之后的其他節(jié)點(diǎn)。

      算法2描述了S-Center算法的詳細(xì)過(guò)程。此處用到的兩個(gè)集合分別是結(jié)果子圖集合R和當(dāng)前的待查子圖節(jié)點(diǎn)集Sub(第1行)。在得到候選節(jié)點(diǎn)集Ca后,為節(jié)點(diǎn)分層并排序,同時(shí)記錄每一層中節(jié)點(diǎn)個(gè)數(shù)(第2~4行),然后開(kāi)始在q的鄰域中進(jìn)行枚舉(第5、6行)。在每一次枚舉操作中,如果當(dāng)前枚舉的節(jié)點(diǎn)u加入子圖后子圖的有效壽命仍然大于τ,則這個(gè)節(jié)點(diǎn)可以加入Sub中(第8、9行)。此時(shí)若G[Sub]的靜態(tài)投影是一個(gè)k-核圖,則說(shuō)明G[ ]Sub是一個(gè)(θ,τ)持續(xù)性k-核圖。更新R中的結(jié)果以維護(hù)極大結(jié)果集合(第10~13行)。然后繼續(xù)進(jìn)行枚舉操作(第14~20行)。

      在枚舉過(guò)程中,同樣有3個(gè)枚舉約簡(jiǎn)規(guī)則來(lái)減少枚舉操作的次數(shù):

      規(guī)則4當(dāng)枚舉到一個(gè)節(jié)點(diǎn)u時(shí),若這個(gè)節(jié)點(diǎn)進(jìn)入待查子圖后子圖的有效壽命小于τ,則節(jié)點(diǎn)u無(wú)需加入子圖。

      規(guī)則5當(dāng)一個(gè)節(jié)點(diǎn)v加入待查子圖后,如果子圖中存在一個(gè)與v隔層的節(jié)點(diǎn)度數(shù)仍然小于k,則本次枚舉失效。

      規(guī)則6當(dāng)枚舉到一個(gè)節(jié)點(diǎn)v時(shí),記m′為當(dāng)前子圖中v上一層節(jié)點(diǎn)的最小度數(shù),n′為與v同層節(jié)點(diǎn)中未進(jìn)入子圖的數(shù)量。若m′+n′

      同樣,以圖1為例,假設(shè)q=v0,θ=2,τ=5,k=3,由于圖中所有節(jié)點(diǎn)都在同一層中,所以Ca={v2,v3,v6,v1,v4,v5}。最初待查子圖內(nèi)只有v0,壽命為[0,7]∪[9,14]。然后將v2加入子圖,壽命為[0,3]∪[7,14]。下一次將v3加入子圖,此時(shí)壽命為[0,3]∪[9,14],下一次枚舉的節(jié)點(diǎn)v6加入子圖之后壽命長(zhǎng)度小于5。根據(jù)枚舉約簡(jiǎn)規(guī)則4,v6節(jié)點(diǎn)無(wú)需進(jìn)入子圖。然后將下一個(gè)節(jié)點(diǎn)v1加入子圖。此時(shí)子圖內(nèi)的節(jié)點(diǎn){v2,v3,v1,v0}。能構(gòu)成一個(gè)(2,5)持續(xù)性3-核圖,將其記錄進(jìn)入R。當(dāng)所有枚舉操作完成后,得出唯一的極大結(jié)果{v2,v3,v1,v0}。

      由于S-Center同樣是一個(gè)基于枚舉的算法,所以這個(gè)算法的時(shí)間復(fù)雜度依然是O(2nCa),但由于三個(gè)枚舉約簡(jiǎn)規(guī)則的存在,這個(gè)算法的實(shí)際運(yùn)行時(shí)間同樣遠(yuǎn)遠(yuǎn)小于2nCa。而且S-Center無(wú)需全局遍歷Ca中的所有節(jié)點(diǎn),這進(jìn)一步的提高了效率。

      在本算法中,每次遞歸都從待查子圖的鄰域中枚舉一個(gè)節(jié)點(diǎn),并且找到一個(gè)查詢結(jié)果后,算法不會(huì)停止,而是繼續(xù)進(jìn)行遞歸操作找到一個(gè)極大結(jié)果。因此在不考慮約簡(jiǎn)規(guī)則的情況下,這一算法始終可以找到一個(gè)精確的極大結(jié)果。而約簡(jiǎn)規(guī)則只會(huì)刪除那些一定不在查詢結(jié)果的枚舉集合。所以S-Center算法在查詢節(jié)點(diǎn)有效時(shí),始終可以找到一個(gè)精確的極大結(jié)果。

      3.3 兩種搜索算法的比較

      本節(jié)中給出兩種算法的時(shí)間復(fù)雜度。兩種算法都采用了枚舉的思路,對(duì)于S-Global算法來(lái)說(shuō),每次枚舉的節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)集合,而候選節(jié)點(diǎn)中剩余的節(jié)點(diǎn)作為待查子圖。那么當(dāng)待查子圖內(nèi)節(jié)點(diǎn)數(shù)小于k+1時(shí),這個(gè)子圖一定不會(huì)是查詢結(jié)果,則這一算法的實(shí)際運(yùn)行時(shí)間復(fù)雜度為:顯然,當(dāng)候選子圖G[ ]Ca與結(jié)果子圖相差不多時(shí),這一算法將更快地得到結(jié)果。該種情況一般在查詢節(jié)點(diǎn)有效壽命較長(zhǎng),時(shí)序圖更加稠密時(shí)發(fā)生。對(duì)于S-Center算法來(lái)說(shuō),算法中枚舉的節(jié)點(diǎn)集的誘導(dǎo)子圖本身就是待查子圖。顯然,這一算法的時(shí)間復(fù)雜度與G[Ca]內(nèi)節(jié)點(diǎn)的層數(shù)有關(guān)。當(dāng)G[Ca]內(nèi)所有節(jié)點(diǎn)的層數(shù)相同時(shí),枚舉算法將會(huì)遍歷候選字圖中的所有節(jié)點(diǎn),其最壞時(shí)間復(fù)雜度為O(2nCa)。當(dāng)節(jié)點(diǎn)分層較多時(shí),由于枚舉到某一節(jié)點(diǎn)時(shí),隔層以上的節(jié)點(diǎn)將不會(huì)被枚舉。假設(shè)候選節(jié)點(diǎn)集共分為s層,則此時(shí)算法的實(shí)際時(shí)間復(fù)雜度為。其中N i是G[Ca]第i層節(jié)點(diǎn)的數(shù)量。顯然,當(dāng)G[Ca]分層較多時(shí),這一算法將更快得到結(jié)果。該種情況一般出現(xiàn)于查詢節(jié)點(diǎn)有效壽命較短,時(shí)序圖較為稀疏的條件下。

      4 實(shí)驗(yàn)

      本章中通過(guò)一些真實(shí)的數(shù)據(jù)源驗(yàn)證算法的有效性及運(yùn)行效率,并通過(guò)一些對(duì)比實(shí)驗(yàn)說(shuō)明參數(shù)對(duì)算法性能的影響。兩種算法都由C++編寫,運(yùn)行環(huán)境為Windows Server 2012 R2操作系統(tǒng),Inter?Xeon?Platinum 8163,2.49 GHz CPU和16 GB內(nèi)存。

      4.1 數(shù)據(jù)集

      本文中取4個(gè)不同的真實(shí)世界的時(shí)序圖數(shù)據(jù)源進(jìn)行研究。數(shù)據(jù)源的詳細(xì)情況見(jiàn)表1。其中,|V|、|E|、|E′|、|T|和dmax分別是時(shí)序圖中的節(jié)點(diǎn)數(shù),時(shí)序邊數(shù),靜態(tài)投影邊數(shù),時(shí)間戳范圍和節(jié)點(diǎn)的最大靜態(tài)投影度數(shù)。HS2013是從sociopatterns網(wǎng)站上下載的面對(duì)面交互網(wǎng)絡(luò),時(shí)間戳單位為h。LKML和ENRON是從konect網(wǎng)站上下載的時(shí)序社交網(wǎng)絡(luò),單位是月。DBLP是DBLP計(jì)算機(jī)科學(xué)文獻(xiàn)庫(kù)中的作家協(xié)作網(wǎng)絡(luò),單位是年。

      表1 時(shí)序圖數(shù)據(jù)集的參數(shù)Table 1 Parameters of temporal graph datasets

      4.2 參數(shù)設(shè)定

      本文中的兩個(gè)算法都涉及到了三個(gè)參數(shù)θ、τ、k。其中θ、τ作為時(shí)序參數(shù)用于確定滑動(dòng)窗口的長(zhǎng)度和子圖的最短持續(xù)時(shí)間,k用于確定子圖的結(jié)構(gòu)內(nèi)聚性。本文中的實(shí)驗(yàn)部分將每個(gè)數(shù)據(jù)源需要的3個(gè)參數(shù)各變化3次,且每一組參數(shù)都取5個(gè)不同的查詢節(jié)點(diǎn)進(jìn)行5次實(shí)驗(yàn),并記錄其運(yùn)行結(jié)果的平均值作為實(shí)驗(yàn)結(jié)果。具體的取值情況如表2所示。

      表2 不同數(shù)據(jù)源上的實(shí)驗(yàn)參數(shù)Table 2 Experimental parameters in different datasets

      4.3 時(shí)間約束對(duì)算法性能的影響

      本節(jié)中固定每組數(shù)據(jù)源的參數(shù)k,然后分別固定參數(shù)θ和τ并改變另一個(gè)參數(shù),以確定這兩個(gè)參數(shù)對(duì)算法性能的影響。圖3中的4幅圖為變化參數(shù)θ時(shí)兩種算法及預(yù)處理過(guò)程在4個(gè)數(shù)據(jù)源上的運(yùn)行時(shí)間。通過(guò)這4幅圖可以得出,當(dāng)θ越大時(shí),算法的運(yùn)行時(shí)間越長(zhǎng)。這是因?yàn)楫?dāng)θ變大時(shí),同一條時(shí)序邊會(huì)計(jì)入更多的滑動(dòng)窗口中。圖4的4幅圖為變化參數(shù)τ時(shí)兩種算法在4個(gè)數(shù)據(jù)源上的運(yùn)行時(shí)間。由于當(dāng)τ變大時(shí),更多的時(shí)序邊不滿足有效壽命的約束條件,所以算法的運(yùn)行時(shí)間會(huì)變短。值得一提的是,S-global算法有時(shí)會(huì)出現(xiàn)運(yùn)行速度過(guò)小的情況,例如圖3(d)、圖4(b)和圖4(d)。這是因?yàn)橛行r(shí)候G[Ca]本身就能構(gòu)成一個(gè)(θ,τ)持續(xù)性k-核圖,在S-Global算法中無(wú)需進(jìn)行更多的枚舉操作,這大大降低了算法的運(yùn)行時(shí)間。

      圖3 變化參數(shù)θ時(shí)的運(yùn)行時(shí)間Fig.3 Run time when varyingθ

      圖4 變化參數(shù)τ時(shí)的運(yùn)行時(shí)間Fig.4 Run time when varyingτ

      4.4 結(jié)構(gòu)約束對(duì)算法性能的影響

      本實(shí)驗(yàn)中將固定θ、τ,改變參數(shù)k并觀察其對(duì)算法運(yùn)行時(shí)間的影響。圖5顯示了本實(shí)驗(yàn)的結(jié)果。實(shí)驗(yàn)結(jié)果表明,k值變大時(shí),兩個(gè)算法的運(yùn)行時(shí)間都變短。這是因?yàn)椋?dāng)k值變大時(shí),滿足結(jié)構(gòu)約束的節(jié)點(diǎn)變得更少,也就是說(shuō),候選節(jié)點(diǎn)集Ca中的節(jié)點(diǎn)邊更少。同時(shí)實(shí)驗(yàn)中發(fā)現(xiàn),算法的運(yùn)行時(shí)間與Ca的規(guī)模與結(jié)果子圖規(guī)模的關(guān)系密切相關(guān),當(dāng)Ca規(guī)模與結(jié)果子圖規(guī)模相差較大時(shí),S-Center的運(yùn)行速度較快,反之,S-Global的運(yùn)行速度較快。

      圖5 變化參數(shù)k時(shí)程序的運(yùn)行時(shí)間Fig.5 Run time when varying k

      4.5 枚舉削減規(guī)則對(duì)運(yùn)行效率的影響

      本實(shí)驗(yàn)記錄了兩種算法在運(yùn)行過(guò)程中枚舉操作的執(zhí)行次數(shù),同時(shí)記錄了不同參數(shù)下每組實(shí)驗(yàn)的候選節(jié)點(diǎn)集Ca的情況,以此可以估算出不考慮枚舉削減規(guī)則時(shí)的預(yù)計(jì)枚舉次數(shù)。表3展示了本次實(shí)驗(yàn)的詳細(xì)結(jié)果。其中n Ca表示候選節(jié)點(diǎn)集Ca的節(jié)點(diǎn)個(gè)數(shù),l Ca表示候選節(jié)點(diǎn)集的分層數(shù),PGlobal、PCenter分別表示S-Global算法和S-Center算法運(yùn)行時(shí)的枚舉次數(shù)。從表中可以看出,兩種算法中的枚舉削減規(guī)則都能夠極大地減少枚舉次數(shù)。在Ca與查詢結(jié)果非常接近時(shí),S-Global算法的枚舉次數(shù)將大幅減少,反之,Ca與查詢結(jié)果相差較大時(shí),S-Center算法更具優(yōu)勢(shì)。

      表3 枚舉次數(shù)統(tǒng)計(jì)Table 3 Statistics of enumeration times

      4.6 算法的內(nèi)存開(kāi)銷

      本實(shí)驗(yàn)考察了兩種算法在4個(gè)數(shù)據(jù)集上的內(nèi)存開(kāi)銷情況。表4記錄了本實(shí)驗(yàn)中不同數(shù)據(jù)源在不同參數(shù)情況下的平均內(nèi)存開(kāi)銷。表內(nèi)的第一列為數(shù)據(jù)源本身占用的內(nèi)存大小。從結(jié)果中可以看出,兩種算法的內(nèi)存開(kāi)銷幾乎相同,原因是兩種算法均采用了基于深度優(yōu)先包含枚舉的策略。同時(shí),發(fā)現(xiàn)兩種算法參數(shù)變化對(duì)內(nèi)存開(kāi)銷影響較小,原因是(1)在不同參數(shù)下,經(jīng)過(guò)預(yù)處理后得到的候選節(jié)點(diǎn)集Ca的規(guī)模通常很小,該結(jié)論能夠通過(guò)表3中的n Ca數(shù)量得到驗(yàn)證。(2)由于兩種算法均采用基于深度優(yōu)先的枚舉策略,在搜索過(guò)程中只需保存枚舉中當(dāng)前搜索分支的中間結(jié)果,而且由于兩種算法均采用了削減規(guī)則,樹(shù)中搜索分支不會(huì)過(guò)深。為此,即使n Ca大小有所不同,內(nèi)存開(kāi)銷影響也不大。因此從理論上證明兩種算法參數(shù)變化幾乎不影響內(nèi)存開(kāi)銷。多次不同的實(shí)驗(yàn)也驗(yàn)證了該結(jié)論。此外,ENORN數(shù)據(jù)源上的內(nèi)存開(kāi)銷遠(yuǎn)遠(yuǎn)大于其數(shù)據(jù)源,因?yàn)镋NORN數(shù)據(jù)源的時(shí)間戳范圍跨度很大。

      表4 不同數(shù)據(jù)源上的內(nèi)存開(kāi)銷Table 4 Memory overhead on different datasets MB

      4.7 時(shí)間約束對(duì)結(jié)果質(zhì)量的影響

      本實(shí)驗(yàn)中將固定每組數(shù)據(jù)源的k值,然后分別固定參數(shù)θ和τ并改變另一個(gè)參數(shù),以記錄時(shí)間約束對(duì)結(jié)果質(zhì)量的影響。對(duì)于每一組實(shí)驗(yàn)得到的結(jié)果子圖,用一個(gè)系數(shù)表示子圖的稠密程度。其中m′表示子圖內(nèi)的靜態(tài)邊數(shù),n表示子圖內(nèi)的節(jié)點(diǎn)數(shù)。顯然D值越大,結(jié)果子圖越稠密。表5中的4張表展示了參數(shù)θ對(duì)查詢結(jié)果的影響??梢钥闯?,θ的大小與結(jié)果內(nèi)子圖的節(jié)點(diǎn)數(shù)量和邊數(shù)量都呈正相關(guān),因?yàn)橥粭l邊會(huì)被包含在更多的滑動(dòng)窗口中,節(jié)點(diǎn)的有效壽命會(huì)變長(zhǎng)。但當(dāng)子圖內(nèi)節(jié)點(diǎn)數(shù)量突然增多時(shí),子圖的密度會(huì)有所降低。因?yàn)閮煞N算法都旨在找到數(shù)據(jù)源中的極大結(jié)果,且k值是固定的。表6中的4張子表展示了參數(shù)τ對(duì)查詢結(jié)果的影響。顯然,τ的大小與結(jié)果內(nèi)子圖的節(jié)點(diǎn)數(shù)量和邊數(shù)量都呈負(fù)相關(guān),且與表4結(jié)論類似,子圖內(nèi)節(jié)點(diǎn)數(shù)量突然減少時(shí),子圖的密度會(huì)有所增加。

      表5 參數(shù)θ對(duì)查詢結(jié)果的影響Table 5 Effect of parameterθon query results

      表6 參數(shù)τ對(duì)查詢結(jié)果的影響Table 6 Effect of parameterτon query results

      5 結(jié)語(yǔ)

      本文研究了時(shí)序圖中的稠密子圖搜索這一新穎的問(wèn)題。本研究利用(θ,τ)持續(xù)性k-核子圖這一模型定義了時(shí)序圖中的一種稠密子圖概念,在去除干擾節(jié)點(diǎn)后的候選節(jié)點(diǎn)集,也就是削減后的時(shí)序圖中,設(shè)計(jì)了兩種算法,從兩種不同的角度枚舉這個(gè)時(shí)序圖中的節(jié)點(diǎn)集合,來(lái)找出能夠組成一個(gè)(θ,τ)持續(xù)性k-核圖的極大節(jié)點(diǎn)集作為搜索結(jié)果。在枚舉過(guò)程中,通過(guò)一些高效的削減規(guī)則來(lái)大幅度減少枚舉的執(zhí)行次數(shù)增強(qiáng)算法的效率。最后,本文通過(guò)實(shí)驗(yàn)在四個(gè)時(shí)序圖中驗(yàn)證了提出算法的高效性和有效性,并給出了兩種算法應(yīng)用于不同場(chǎng)景的建議。

      猜你喜歡
      枚舉子圖數(shù)據(jù)源
      基于理解性教學(xué)的信息技術(shù)教學(xué)案例研究
      速讀·上旬(2022年2期)2022-04-10 16:42:14
      一種高效的概率圖上Top-K極大團(tuán)枚舉算法
      臨界完全圖Ramsey數(shù)
      Web 大數(shù)據(jù)系統(tǒng)數(shù)據(jù)源選擇*
      基于不同網(wǎng)絡(luò)數(shù)據(jù)源的期刊評(píng)價(jià)研究
      基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
      基于太陽(yáng)影子定位枚舉法模型的研究
      基于真值發(fā)現(xiàn)的沖突數(shù)據(jù)源質(zhì)量評(píng)價(jià)算法
      不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)
      分布式異構(gòu)數(shù)據(jù)源標(biāo)準(zhǔn)化查詢?cè)O(shè)計(jì)與實(shí)現(xiàn)
      鹤山市| 岗巴县| 房山区| 海丰县| 家居| 涞水县| 满洲里市| 平和县| 沽源县| 克山县| 清镇市| 犍为县| 方山县| 五大连池市| 黎平县| 瑞安市| 澄江县| 新泰市| 诏安县| 来宾市| 舟山市| 个旧市| 武城县| 青田县| 镇沅| 青神县| 商都县| 卢氏县| 凤凰县| 贵阳市| 南皮县| 永吉县| 友谊县| 平潭县| 上饶市| 罗甸县| 泰和县| 利津县| 巴彦淖尔市| 成都市| 内黄县|