金浩宇,霍 宏,方 濤

(上海交通大學(xué) 電子信息與電氣工程學(xué)院,上海 200240)

0 引 言

圖模式匹配是指在圖數(shù)據(jù)中搜索與待查詢模式圖相同或相似的子圖的一類算法,是實(shí)現(xiàn)圖數(shù)據(jù)高效率查詢的重要手段,已經(jīng)應(yīng)用于眾多的領(lǐng)域。例如社交網(wǎng)絡(luò)分析[1]、知識(shí)分析[2]等。現(xiàn)有的圖模式匹配方法大多僅適用于靜態(tài)圖,不適用于在現(xiàn)實(shí)世界中廣泛存在的時(shí)態(tài)圖[3-4],即圖數(shù)據(jù)中的兩個(gè)頂點(diǎn)之間的邊具有時(shí)間屬性,其記錄了兩個(gè)頂點(diǎn)之間關(guān)系的開始與結(jié)束時(shí)間。圖1(a)給出了一個(gè)任務(wù)合作時(shí)序圖,圖中每個(gè)頂點(diǎn)表示一個(gè)人,頂點(diǎn)標(biāo)簽A,B,C,D,E表示不同的職業(yè),頂點(diǎn)之間的有向邊表示兩個(gè)人之間交接任務(wù)的方向,每條邊上都有一個(gè)時(shí)間區(qū)間(s,f)表示任務(wù)交接的開始時(shí)間s與結(jié)束時(shí)間f。

圖1 任務(wù)合作時(shí)序圖

假設(shè)有一個(gè)任務(wù)合作模式圖QT,如圖1(b)所示,QT中每條邊ei都具有一個(gè)時(shí)序優(yōu)先級(jí),時(shí)序優(yōu)先級(jí)規(guī)定了低優(yōu)先級(jí)邊的開始時(shí)間一定要晚于高優(yōu)先級(jí)邊的結(jié)束時(shí)間,即模式圖QT隱含著一種時(shí)序約束,該文稱其為時(shí)序模式圖,其中A先與B交接任務(wù),然后A在接收了B和E的交接信息后,再與C進(jìn)行交接,最后C與D完成任務(wù)交接?，F(xiàn)要在如圖1(a)所示的任務(wù)合作時(shí)序圖上查詢與QT相同或相似的子圖。如果采用靜態(tài)的圖模擬匹配方法,可以得到的一個(gè)匹配結(jié)果的邊集合為{e1,e2,e3,e4,e6,e7},顯然,由于沒有考慮邊具有的時(shí)序?qū)傩?邊e7并不滿足模式圖QT中的時(shí)序約束,而正確的匹配結(jié)果如圖1(c)所示。除了時(shí)序約束外,觀察圖1(b),不難發(fā)現(xiàn)模式圖QT中還存在環(huán)路,如A→B→A等,而現(xiàn)有的時(shí)態(tài)圖模式匹配方法無法處理模式圖中的環(huán)路。因此,需要研究適合于時(shí)態(tài)圖并能處理環(huán)路的時(shí)序模式圖匹配方法。

針對(duì)時(shí)序圖特有的時(shí)序?qū)傩约骖櫰渫負(fù)浣Y(jié)構(gòu),提出了時(shí)序優(yōu)先級(jí)約束的時(shí)序模式圖強(qiáng)模擬匹配算法,該算法在匹配過程中,不僅對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行檢查,還將各條邊的時(shí)序優(yōu)先級(jí)作為局部約束,并設(shè)置了冗余頂點(diǎn)過濾規(guī)則來縮小搜索范圍,以及對(duì)時(shí)序檢查的隊(duì)列順序進(jìn)行優(yōu)化使得算法能夠提前剪枝,減少了計(jì)算復(fù)雜度,所提出的方法兼具子圖同構(gòu)和圖模擬的優(yōu)勢(shì),實(shí)現(xiàn)了既準(zhǔn)確又高效的圖匹配。在三個(gè)時(shí)序數(shù)據(jù)集上的大量實(shí)驗(yàn)表明,相比傳統(tǒng)的強(qiáng)模擬算法,所提算法能夠有效過濾錯(cuò)誤結(jié)果,并且在不同規(guī)模的數(shù)據(jù)圖上均具有良好的性能表現(xiàn)。

1 相關(guān)工作

1.1 近似匹配

近似匹配放松了圖匹配條件,成為廣泛采用的一種圖模式匹配方法,主要包括圖模擬[5]、雙向模擬[6]、強(qiáng)模擬[7]、受限模擬[8]、量化模擬[9-10]等。圖模擬要求匹配每個(gè)節(jié)點(diǎn)以及其子節(jié)點(diǎn)。雙向模擬在圖模擬的基礎(chǔ)上還要匹配父節(jié)點(diǎn)。強(qiáng)模擬在雙向模擬基礎(chǔ)上還需考慮匹配子圖的局部特性。受限模擬是指在模式圖上對(duì)跳躍次數(shù)進(jìn)行了限制。量化模擬關(guān)注了圖上的具有計(jì)數(shù)量詞的表達(dá)模式。上述的近似匹配方法都只考慮了圖的拓?fù)浣Y(jié)構(gòu),而忽略了圖上的時(shí)間信息,無法用來解決在時(shí)態(tài)圖上的匹配問題。

1.2 時(shí)態(tài)圖及其圖模式匹配

時(shí)態(tài)圖主要用于對(duì)實(shí)體及其之間涉及的時(shí)態(tài)關(guān)系進(jìn)行建模,是在靜態(tài)圖的基礎(chǔ)上演變的一種新型圖數(shù)據(jù)[11]。目前,關(guān)于時(shí)態(tài)圖的研究主要包括可達(dá)性查詢[12]、最小生成樹[13]、最短時(shí)態(tài)路徑[14]等。

時(shí)態(tài)圖上的圖模式匹配問題的研究才剛剛起步,Xu等[15]研究了時(shí)態(tài)圖同構(gòu)匹配,提出了時(shí)間約束的模式圖匹配算法(Time-Constrained Graph Pattern Matching,TCGPM),但同構(gòu)匹配要求匹配到與查詢模式圖完全相同的子圖,過于嚴(yán)格。Song等[16]研究了圖流上的事件模式匹配,將時(shí)間窗口概念引入了子圖匹配并提出了DDST(Degree-Preserving Dual Simulation with Timing Constraints)算法,且基于標(biāo)簽過濾與度約束的思想提出了兩個(gè)優(yōu)化算法DDST-SIGNATURE和COLORING以提升算法的運(yùn)行效率,但是這些算法將給定時(shí)間窗口的時(shí)態(tài)圖快照作為靜態(tài)圖處理,容易導(dǎo)致遺漏部分結(jié)果。Ma等[17]根據(jù)受限模擬和時(shí)態(tài)路徑定義了時(shí)態(tài)圖上的圖模式匹配并基于連接的方式枚舉匹配結(jié)果,但是這種方法的匹配條件過于寬松,并且不允許模式圖中出現(xiàn)環(huán)路。

2 模式圖匹配與時(shí)序模式圖匹配的形式化描述

雙向模擬和強(qiáng)模擬是經(jīng)典的模式圖匹配算法,兩者的形式化描述如下：

定義1 雙向模擬。給定一個(gè)模式圖Q=(Vq,Eq,Lq)和一個(gè)數(shù)據(jù)圖G=(V,E,L),如果存在一個(gè)二元匹配關(guān)系S?Vq×V且滿足下列條件,則說G通過雙向模擬匹配Q：

(1)每一對(duì)(u,v)∈S,u和v都有相同的標(biāo)簽;

(2)對(duì)每個(gè)v∈Vq,存在u∈V滿足(u,v)∈S且每一條邊e'(v,v1)∈Eq都存在一條邊e(u,u1)∈E使得(u1,v1)∈S;

(3)對(duì)每個(gè)v∈Vq,存在u∈V滿足(u,v)∈S且每一條邊e'(v2,v)∈Eq都存在一條邊e(u2,u)∈E使得(u2,v2)∈S。

定義2 強(qiáng)模擬。給定一個(gè)模式圖Q=(Vq,Eq,Lq)和一個(gè)數(shù)據(jù)圖G=(V,E,L),若在G中存在一個(gè)頂點(diǎn)v和一個(gè)連通子圖Gs(Vs,Es)滿足以下條件,則說G通過強(qiáng)模擬匹配Q：

(1)Q對(duì)Gs滿足雙向模擬匹配,且有最大二元匹配關(guān)系S,即Q在G上的任意二元匹配關(guān)系SA都有SA?S。

(2)Gs是S構(gòu)成的圖,即(a)有一個(gè)頂點(diǎn)w∈Vs當(dāng)且僅當(dāng)它存在于S。(b)有一條邊e(w,w')∈Es當(dāng)且僅當(dāng)在Q中存在一條邊e'(u,u')使得(u,w)∈S且(u',w')∈S。

時(shí)態(tài)圖的邊具有時(shí)間屬性,其形式化描述為：

定義3 時(shí)態(tài)圖。給定一個(gè)有向帶標(biāo)簽的圖GT=(V,E,L),其中V是頂點(diǎn)的集合;E∈V×V是有向時(shí)態(tài)邊的集合;L是一個(gè)標(biāo)簽函數(shù),可將每個(gè)頂點(diǎn)u∈V映射到其對(duì)應(yīng)的標(biāo)簽L(u)。假設(shè)圖中一條有向時(shí)態(tài)邊ei∈E連接了兩個(gè)頂點(diǎn)u,v∈V,可表示為一個(gè)四元組(u,v,si,fi),該四元組的含義為兩個(gè)頂點(diǎn)u和v的關(guān)系從時(shí)間點(diǎn)si開始到時(shí)間點(diǎn)fi結(jié)束。

時(shí)態(tài)圖的模式圖及其強(qiáng)模擬匹配算法的形式化描述如下：

定義4 時(shí)序模式圖。一個(gè)時(shí)序模式圖表示為QT=(Vq,Eq,Lq),其中Vq是頂點(diǎn)的集合,Lq是一個(gè)標(biāo)簽函數(shù),Eq∈Vq×Vq是有向時(shí)序優(yōu)先級(jí)邊的集合。一條有向時(shí)序優(yōu)先級(jí)邊ei∈Eq可表示為一個(gè)三元組(u,v,pi),其中pi為ei的時(shí)序優(yōu)先級(jí)。時(shí)序模式圖不關(guān)心具體的時(shí)間范圍,而是通過時(shí)序優(yōu)先級(jí)規(guī)定每條邊代表的事件發(fā)生的先后順序,時(shí)序優(yōu)先級(jí)低的事件必須在時(shí)序優(yōu)先級(jí)高的事件結(jié)束之后發(fā)生。

定義5 時(shí)序強(qiáng)模擬匹配。給定一個(gè)時(shí)序模式圖QT=(Vq,Eq,Lq)和一個(gè)時(shí)態(tài)數(shù)據(jù)圖GT=(V,E,L),如果滿足以下條件,則稱G通過時(shí)序強(qiáng)模擬匹配QT：

3 文中算法

該文提出的時(shí)序優(yōu)先級(jí)約束的時(shí)序模式圖強(qiáng)模擬匹配算法(Temporal Priority Constrained Graph Pattern Strong Simulation Matching,TPC-GPSSM)針對(duì)時(shí)序圖特有的時(shí)序特性,將各條邊的時(shí)序優(yōu)先級(jí)作為局部約束,在匹配過程中,能夠同時(shí)兼顧時(shí)序圖邊具有的時(shí)序優(yōu)先級(jí)及其拓?fù)浣Y(jié)構(gòu),也適用于帶環(huán)路的時(shí)序模式圖的匹配。

3.1 TPC-GPSSM算法

TPC-GPSSM算法主要先在時(shí)態(tài)圖上構(gòu)建球,然后在球上進(jìn)行時(shí)序優(yōu)先級(jí)約束的強(qiáng)模擬匹配。在時(shí)態(tài)圖上構(gòu)建球采用廣度優(yōu)先遍歷(Breath First Search,BFS)算法[18],以每個(gè)頂點(diǎn)為球心,構(gòu)造半徑為時(shí)序模式圖直徑的球,可將構(gòu)建好的每個(gè)球看作是時(shí)態(tài)圖的一個(gè)子圖。然后,將每個(gè)球與時(shí)序模式圖進(jìn)行雙向模擬匹配,在匹配過程中,一方面要計(jì)算每個(gè)球其所包含的二元匹配關(guān)系,并檢查時(shí)序優(yōu)先級(jí)約束,找到最大的二元匹配關(guān)系。另一方面,在匹配的同時(shí)還進(jìn)行拓?fù)浣Y(jié)構(gòu)檢查,以保證匹配的子圖與時(shí)序模式圖匹配。

算法1 TPC-GPSSM

輸入：時(shí)序模式圖QT=(Vq,Eq,Lq)及其直徑dq,時(shí)態(tài)圖GT=(V,E,L)

輸出：匹配結(jié)果集合S

1.S：=?,B：=?

2.for eachvinVdo

6.sim(v),sim(e')：=TemporalFilter(QT,sim(v),sim(e'))

7.Gs：=CheckTopology(QT,sim(v),sim(e'))

8.ifGs≠? then

9.S：=S∪Gs

10.returnS

算法2 DualSimMatch

輸出：候選頂點(diǎn)集合sim(v),候選邊集合sim(e')

1.for eachv∈Vqdo

2.sim(v)：={u|uis inG[v,dq] andLq(u)}

3.for eache(v,v1)∈Eqdo

4.sim(e')：={e|e(u,u1)is inG[v,dq],u∈sim(v),u1∈sim(v1)}

5.while there are changes do

6. for eachu∈sim(v) do

7. for eache(v,v') inEqdo

9.Removeuand edges containingufrom sim(v) and sim(e')

10. for eache(v',v) inEqdo

12.Removeuand edges containingufrom sim(v) and sim(e')

13.return sim(v),sim(e')

算法3 TemporalFilter

輸入：時(shí)序模式圖QT,候選頂點(diǎn)集合sim(v),候選邊集合sim(e')

輸出：候選頂點(diǎn)集合sim(v),候選邊集合sim(e')

1.while there are changes do

4. ifp1>p2ands1

7. Removeu,u1and all edges containingu,u1from sim(v) and sim(e')

8.return sim(v),sim(e')

算法4給出了拓?fù)浣Y(jié)構(gòu)檢查的偽代碼CheckTopology,主要功能是對(duì)球內(nèi)的子圖進(jìn)行檢查,去除在時(shí)序優(yōu)先級(jí)約束下因刪除時(shí)態(tài)邊而產(chǎn)生的不符合QT拓?fù)浣Y(jié)構(gòu)要求的頂點(diǎn)和邊。對(duì)頂點(diǎn)候選集sim(v)中的任意頂點(diǎn)u,首先檢查其后繼關(guān)系,后繼頂點(diǎn)集合為succ(u),后繼頂點(diǎn)候選集為sim(v'),若succ(u)∩sim(v')=?,則將該節(jié)點(diǎn)及其關(guān)聯(lián)的邊從候選集合中刪除;然后檢查其前驅(qū)關(guān)系,前驅(qū)頂點(diǎn)集合為pred(u),前驅(qū)頂點(diǎn)候選集為sim(v''),若pred(u)∩sim(v'')=?,則將相關(guān)頂點(diǎn)和邊刪除(見第1-5行)。若頂點(diǎn)和邊候選集均非空,則將其構(gòu)造成一個(gè)子圖Gs(見第6-8行)。

算法4 CheckTopology

輸入：時(shí)序模式圖QT,候選頂點(diǎn)集合sim(v),候選邊集合sim(e')

輸出：匹配子圖Gs

1.While there are changes do

2. for eachu∈sim(v) do

3. if succ(u)∩sim(v')=? or pred(u)∩sim(v'')=? then

4.sim(v)：=sim(v){u}

5.remove all edges containingufrom sim(e')

6.if sim(v),sim(e')≠? then

7. constructGsfrom sim(v),sim(e')

8.returnGs

TPC-GPSSM在球的建立過程花費(fèi)了很多時(shí)間,主要因?yàn)槊總€(gè)球包含了很多無用的拓?fù)浣Y(jié)構(gòu)信息,并且在時(shí)序檢查過程中存在重復(fù)檢查的問題。如果能減少每個(gè)球的計(jì)算量, 避免時(shí)序的重復(fù)檢查,將大大提升算法的效率。

3.2 TPC-GPSSM算法優(yōu)化方法

針對(duì)上文提及的TPC-GPSSM算法存在很多重復(fù)計(jì)算的問題,進(jìn)一步對(duì)球的建立過程、時(shí)態(tài)優(yōu)先級(jí)約束等方面進(jìn)行優(yōu)化,算法5給出了優(yōu)化后的TPC-GPSSM算法的偽代碼,主要包括：

第一,在球的建立過程中,TPC-GPSSM算法對(duì)數(shù)據(jù)圖中每個(gè)頂點(diǎn),都作為中心建立了球,然而其中大量的球并沒有包含能夠匹配模式圖的子圖,對(duì)這些球的計(jì)算浪費(fèi)了大量時(shí)間。在建球之前先進(jìn)行雙向模擬匹配(見第2行),能夠過濾掉大量的節(jié)點(diǎn)與邊,這樣既能減少需要建立的球的數(shù)量,也能使每個(gè)球包含的子圖規(guī)模減小。

第二,在對(duì)球心的選擇方面,只選擇與模式圖中距離最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)相匹配的節(jié)點(diǎn)(見第3-8行),如圖1(b)所示,E、D是模式圖中距離最遠(yuǎn)的兩個(gè)點(diǎn),以E對(duì)應(yīng)的頂點(diǎn)E2為球心建球得到的結(jié)果與以A1為球心建立球得到的結(jié)果相同,因此計(jì)算以A1為球心的球是冗余的。

第三,在時(shí)序優(yōu)先級(jí)約束過程中,先對(duì)模式圖中的邊根據(jù)時(shí)序優(yōu)先級(jí)進(jìn)行排序,從高優(yōu)先級(jí)的邊開始依次檢查,每一條邊只檢查與其相鄰的時(shí)序優(yōu)先級(jí)更高的邊的之間的時(shí)序關(guān)系,可避免重復(fù)時(shí)序檢查。

算法5 優(yōu)化后的TPC-GPSSM算法

輸入：時(shí)序模式圖QT=(Vq,Eq,Lq)及其直徑dq,時(shí)態(tài)圖GT=(V,E,L)

輸出：子圖集合S

1.S：=?,B：=?

3.vf1,vf2are the farthest two nodes inQ

4.for eachv∈sim(vf1) or sim(vf2) do

10. forpfrom the highest priority to the lowest priority do

11.simb(v),simb(e')：= TemporalFilter(QT,simb(v),simb(e))

12.Gs：=CheckTopology(QT,simb(v),simb(e))

13. ifGs≠? then

14.S：=S∪Gs

15.ReturnS

優(yōu)化后的TPC-GPSSM算法大幅減少了球的數(shù)量,同時(shí)避免了球之間因?yàn)榻患M(jìn)行的重復(fù)計(jì)算,且保證了對(duì)每條時(shí)序邊只檢查一次,解決了重復(fù)檢查的問題。

4 實(shí)驗(yàn)與結(jié)果分析

本章節(jié)對(duì)分別從算法有效性以及算法效率兩個(gè)維度來評(píng)估提出的算法,并對(duì)普通的強(qiáng)模擬匹配算法[19](General Strong Simulation,GSS)與TPC-GPSSM及優(yōu)化后的TPC-GPSSM算法進(jìn)了比較。實(shí)驗(yàn)采用三個(gè)時(shí)態(tài)數(shù)據(jù)集,分別是：(1)BMC[20],一個(gè)小學(xué)師生相互接觸時(shí)態(tài)網(wǎng);(2)Enron[21],一個(gè)電子郵件傳輸網(wǎng)絡(luò);(3)Wikitalk-Russian[22],一個(gè)Russian Wikipedia上的交流網(wǎng)絡(luò)。表1列出了這些數(shù)據(jù)集的詳細(xì)參數(shù),其中|V|、|E|、|T|、#labels分別是數(shù)據(jù)集的頂點(diǎn)數(shù)量、邊的數(shù)量、邊的平均時(shí)間區(qū)間、標(biāo)簽數(shù)量。

表1 數(shù)據(jù)集

模式圖由一個(gè)自行開發(fā)的模式圖生成器提供。給定模式圖的頂點(diǎn)數(shù)量和標(biāo)簽集合,模式圖生成器隨機(jī)生成包含不同時(shí)序優(yōu)先級(jí)數(shù)量的模式圖。實(shí)驗(yàn)對(duì)每個(gè)數(shù)據(jù)集分別生成了100個(gè)模式圖,對(duì)其平均結(jié)果進(jìn)行評(píng)估。

4.1 算法有效性實(shí)驗(yàn)

首先,對(duì)TPC-GPSSM算法的有效性進(jìn)行了實(shí)驗(yàn)驗(yàn)證。TPC-GPSSM算法相比傳統(tǒng)強(qiáng)模擬匹配算法,能夠有效地過濾不符合時(shí)態(tài)要求的邊。為了定量地描述算法有效性,定義了一個(gè)評(píng)價(jià)指標(biāo)——時(shí)態(tài)邊聚合度(Temporal Edge Closeness,TEC)。

給定一個(gè)時(shí)序模式圖QT=(Vq,Eq,Lq),以及一組作為匹配結(jié)果返回的子圖{M1,M2,…,Mn},TEC定義如下式：

其中,|EMj|是Mj中時(shí)態(tài)邊的數(shù)量,|Eq|是模式圖的邊數(shù)量,TEC的值越小說明對(duì)時(shí)態(tài)邊的過濾效果越明顯。對(duì)三個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果如圖2所示,實(shí)驗(yàn)改變時(shí)序模式圖頂點(diǎn)數(shù)量|Vq|從2到5,分別在三個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試。其中,GSS由于沒有考慮時(shí)態(tài)邊的順序,所以得到了最大的TEC值,而TPC-GPSSM及其改進(jìn)算法對(duì)不合模式圖需求的時(shí)態(tài)邊進(jìn)行了過濾,得到了更優(yōu)的TEC值。

圖2 不同數(shù)據(jù)集上匹配質(zhì)量的評(píng)價(jià)

4.2 算法效率實(shí)驗(yàn)

這里通過二個(gè)實(shí)驗(yàn),分別考察時(shí)序模式圖、不同時(shí)序優(yōu)先級(jí)數(shù)量對(duì)TPC-GPSSM算法效率和性能的影響。

(1)時(shí)序模式圖頂點(diǎn)數(shù)量|Vq|對(duì)算法效率的影響。設(shè)置了2到10不同大小的|Vq|,在三個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖3所示,可以觀察到,三種算法的匹配時(shí)間都隨著|Vq|的增大而增加,這是因?yàn)楫?dāng)|Vq|增大時(shí),需要匹配的節(jié)點(diǎn)和邊的數(shù)量也同時(shí)增加,這將增加計(jì)算的時(shí)間花銷。優(yōu)化后的TPC-GPSSM算法采用了先進(jìn)行雙向模擬匹配,再建立球進(jìn)行局部性檢查,使得球的數(shù)量大幅減少,取得了更加良好的性能表現(xiàn)。

圖3 時(shí)序模式圖大小對(duì)算法效率的影響

(2)不同時(shí)序優(yōu)先級(jí)數(shù)量對(duì)匹配結(jié)果的影響。實(shí)驗(yàn)中固定模式圖的|Vq|為10,改變其中的時(shí)序優(yōu)先級(jí)數(shù)量,實(shí)驗(yàn)結(jié)果如圖4所示。當(dāng)時(shí)序優(yōu)先級(jí)數(shù)量增加時(shí),意味著匹配條件更加嚴(yán)格,符合條件的子圖數(shù)量也隨之減少,而GSS不考慮時(shí)序關(guān)系,時(shí)序優(yōu)先級(jí)數(shù)量不影響它的匹配結(jié)果。

圖4 時(shí)序優(yōu)先級(jí)數(shù)量對(duì)匹配結(jié)果的影響

5 結(jié)束語

針對(duì)時(shí)態(tài)圖上的模式圖匹配,提出了一種時(shí)序優(yōu)先級(jí)約束的時(shí)序模式圖強(qiáng)模擬匹配算法(TPC-GPSSM),該算法將時(shí)序優(yōu)先級(jí)作為局部約束,在模式圖的匹配過程中考慮了時(shí)態(tài)圖中不同時(shí)態(tài)邊之間的時(shí)序優(yōu)先級(jí),并兼顧圖的拓?fù)浣Y(jié)構(gòu),通過設(shè)置冗余頂點(diǎn)過濾規(guī)則來縮小搜索范圍,優(yōu)化時(shí)序檢查的隊(duì)列順序,以達(dá)到提前剪枝、減少計(jì)算復(fù)雜度的目的。提出并利用時(shí)態(tài)邊聚合度作為評(píng)價(jià)指標(biāo),在三個(gè)時(shí)序數(shù)據(jù)集上的大量實(shí)驗(yàn)表明,相比普通的強(qiáng)模擬算法,所提算法能夠有效過濾錯(cuò)誤結(jié)果,并且在不同規(guī)模的數(shù)據(jù)圖上均具有良好的性能表現(xiàn)。該算法可應(yīng)用于涉及前后時(shí)序關(guān)系的場(chǎng)景,如任務(wù)交接分析、交通網(wǎng)絡(luò)分析等,特別是在任務(wù)交接中存在環(huán)路的情況下該算法也能進(jìn)行有效的處理。在下一步的工作中,一個(gè)方向是考慮不同時(shí)間窗口的約束,另一個(gè)方向是在分布式環(huán)境中開發(fā)更性能更高的算法。