亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

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

        李 源,劉金生,趙會群,孫 晶

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

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

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

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

        本研究首先證明了時序圖中查詢(θ,τ)持續(xù)性k-核子圖是NP-難問題。為解決這一問題,本文提出通過全局和局部兩種思路設(shè)計(jì)的算法,分別命名為S-Global和S-Center算法。其中S-Global算法從全局角度出發(fā),不斷刪除不滿足條件的節(jié)點(diǎn),最后得到一個極大的(θ,τ)持續(xù)性k-核圖。在此過程中,將通過提出的削減規(guī)則減少搜索空間。另一個算法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)是無需遍歷整個時序圖。在四個真實(shí)世界網(wǎng)絡(luò)中的大量實(shí)驗(yàn),驗(yàn)證了提出算法的高效性。其中S-Global算法更適用于時序圖較為稠密的場景,而S-Center算法則適用于稀疏圖場景。

        1 相關(guān)工作

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

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

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

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

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

        2.1 滑動窗口模型的使用

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

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

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

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

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

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

        值得注意的是,當(dāng)時序圖結(jié)構(gòu)發(fā)生改變時,一個節(jié)點(diǎn)的有效壽命及壽命長度也要隨之改變。例如圖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 問題定義及分析

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

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

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

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

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

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

        3 搜索算法

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

        3.1 S-Global算法

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

        算法1是本算法的詳細(xì)細(xì)節(jié)。其中R是最終要找到的極大結(jié)果子圖集合,De是每次枚舉過程中要刪除的節(jié)點(diǎn)集合,Safe是安全節(jié)點(diǎn)集合(第1行)。當(dāng)?shù)玫揭粋€候選節(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ū)⒁粋€節(jié)點(diǎn)u加入進(jìn)De準(zhǔn)備刪除(第5行),對于剩余的子圖,先判斷其有效壽命是否大于τ(第6行),若大于τ,則這個子圖中的極大k-核圖就是一個極大結(jié)果,將其代入R并停止遞歸(第12行)。否則,繼續(xù)向后按順序?qū)之后的節(jié)點(diǎn)進(jìn)行遞歸判斷(第17行)。當(dāng)一個節(jié)點(diǎn)完成遞歸之后,保留這個節(jié)點(diǎn)作為安全節(jié)點(diǎn)進(jìn)入節(jié)點(diǎn)集Safe(第18行)。注意,每次更新子圖時都要對度數(shù)時序矩陣J進(jìn)行更新(第11和19行)所有遞歸判斷完成后,將R內(nèi)的所有子圖輸出作為結(jié)果(第4行)。

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

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

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

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

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

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

        3.2 S-Center算法

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

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

        在枚舉過程中,同樣有3個枚舉約簡規(guī)則來減少枚舉操作的次數(shù):

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

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

        規(guī)則6當(dāng)枚舉到一個節(jié)點(diǎn)v時,記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加入子圖,此時壽命為[0,3]∪[9,14],下一次枚舉的節(jié)點(diǎn)v6加入子圖之后壽命長度小于5。根據(jù)枚舉約簡規(guī)則4,v6節(jié)點(diǎn)無需進(jìn)入子圖。然后將下一個節(jié)點(diǎn)v1加入子圖。此時子圖內(nèi)的節(jié)點(diǎn){v2,v3,v1,v0}。能構(gòu)成一個(2,5)持續(xù)性3-核圖,將其記錄進(jìn)入R。當(dāng)所有枚舉操作完成后,得出唯一的極大結(jié)果{v2,v3,v1,v0}。

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

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

        3.3 兩種搜索算法的比較

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

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

        本章中通過一些真實(shí)的數(shù)據(jù)源驗(yàn)證算法的有效性及運(yùn)行效率,并通過一些對比實(shí)驗(yàn)說明參數(shù)對算法性能的影響。兩種算法都由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個不同的真實(shí)世界的時序圖數(shù)據(jù)源進(jìn)行研究。數(shù)據(jù)源的詳細(xì)情況見表1。其中,|V|、|E|、|E′|、|T|和dmax分別是時序圖中的節(jié)點(diǎn)數(shù),時序邊數(shù),靜態(tài)投影邊數(shù),時間戳范圍和節(jié)點(diǎn)的最大靜態(tài)投影度數(shù)。HS2013是從sociopatterns網(wǎng)站上下載的面對面交互網(wǎng)絡(luò),時間戳單位為h。LKML和ENRON是從konect網(wǎng)站上下載的時序社交網(wǎng)絡(luò),單位是月。DBLP是DBLP計(jì)算機(jī)科學(xué)文獻(xiàn)庫中的作家協(xié)作網(wǎng)絡(luò),單位是年。

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

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

        本文中的兩個算法都涉及到了三個參數(shù)θ、τ、k。其中θ、τ作為時序參數(shù)用于確定滑動窗口的長度和子圖的最短持續(xù)時間,k用于確定子圖的結(jié)構(gòu)內(nèi)聚性。本文中的實(shí)驗(yàn)部分將每個數(shù)據(jù)源需要的3個參數(shù)各變化3次,且每一組參數(shù)都取5個不同的查詢節(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 時間約束對算法性能的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        5 結(jié)語

        本文研究了時序圖中的稠密子圖搜索這一新穎的問題。本研究利用(θ,τ)持續(xù)性k-核子圖這一模型定義了時序圖中的一種稠密子圖概念,在去除干擾節(jié)點(diǎn)后的候選節(jié)點(diǎn)集,也就是削減后的時序圖中,設(shè)計(jì)了兩種算法,從兩種不同的角度枚舉這個時序圖中的節(jié)點(diǎn)集合,來找出能夠組成一個(θ,τ)持續(xù)性k-核圖的極大節(jié)點(diǎn)集作為搜索結(jié)果。在枚舉過程中,通過一些高效的削減規(guī)則來大幅度減少枚舉的執(zhí)行次數(shù)增強(qiáng)算法的效率。最后,本文通過實(shí)驗(yàn)在四個時序圖中驗(yàn)證了提出算法的高效性和有效性,并給出了兩種算法應(yī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ù)源的期刊評價研究
        基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
        基于太陽影子定位枚舉法模型的研究
        基于真值發(fā)現(xiàn)的沖突數(shù)據(jù)源質(zhì)量評價算法
        不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)
        分布式異構(gòu)數(shù)據(jù)源標(biāo)準(zhǔn)化查詢設(shè)計(jì)與實(shí)現(xiàn)
        久久精品国产99久久久| 亚洲精品国产二区三区在线| 国产亚洲一区二区三区夜夜骚| 偷拍一区二区三区黄片| 亚洲国产成人久久精品不卡| 国产美女精品视频线免费播放软件 | 女人一级特黄大片国产精品| 女优av性天堂网男人天堂| 白嫩人妻少妇偷人精品| 久久精品国产亚洲av无码娇色| 又爆又大又粗又硬又黄的a片| 无码高潮久久一级一级喷水| 国产精品老女人亚洲av无| 国产一区二区三区av天堂| 亚洲春色在线视频| 国产精品视频一区国模私拍| 国产精品一区区三区六区t区| 极品夫妻一区二区三区| 97在线视频人妻无码| 麻豆精品久久久久久久99蜜桃| 亚洲线精品一区二区三区八戒| 在线看不卡的国产视频| 精品少妇一区二区三区免费| 影视av久久久噜噜噜噜噜三级| 亚洲精品久久久久久| 国产爆乳美女娇喘呻吟久久| 日韩精品一区二区三区影音视频| 永久免费毛片在线播放| 亚洲色在线v中文字幕| 亚洲av日韩片在线观看| 91青青草手机在线视频| 91中文人妻熟女乱又乱| 国产操逼视频| 亚洲欧美中文v日韩v在线| 在线亚洲精品免费视频| 精品亚洲一区二区三区四| 麻豆成人精品国产免费| 国产精品美女AV免费观看| 91久久精品一二三区色| 老熟女的中文字幕欲望| 亚洲第一av导航av尤物|