動態空間網絡中的黑洞模式挖掘算法*

譚勝昔，賈金萍，趙 斌，吉根林

(南京師范大學計算機科學與技術學院,江蘇 南京 210023)

1 引言

隨著全球定位技術、無線通訊技術的持續發展，以及移動終端設備的廣泛普及，大規模移動數據的獲取已經成為可能。按照數據來源的不同，常見的移動數據包括手機終端定位與通訊記錄、公交刷卡記錄、GPS的軌跡數據、社交網絡簽到數據等[1]。此類數據記錄了空間、時間、方向、速度和POI(Point of Interest)等方面的信息。這為人類移動模式研究帶來了前所未有的機遇和挑戰。通過分析和挖掘移動數據可以為現代城市的交通管理、疾病防控、城市規劃和旅游推薦等應用領域提供有力的方法指導和決策支持。

人類移動模式研究[2 - 5]是移動數據挖掘中的一個熱點問題，其研究任務是發現移動對象群體的運動模式和活動規律，如城市人群的通勤活動、游行集會和交通擁堵等。按照研究類型的不同，人類移動模式研究分為面向群體的研究和面向地理空間的研究[6]。典型的面向群體的移動模式包括成群模式(Flock)[7]、護航模式(Convoy)[8]、蜂群模式(Swarm)[9]和聚合模式(Gathering)[10]等。此類研究從運動形態的視角出發分析與挖掘群體移動的規律性，可以發現具有相同運動形態的移動對象群體。但是，挖掘方法中不涉及地理空間信息，因而無法發現地理空間中區域間的移動模式。面向地理空間的研究從地理空間的視角研究人類移動模式，彌補了這一不足。2014年，Kim等人[11]利用空間上聚集的地鐵站點研究區域間的移動交互模式。Chen等人[12]采用出租車的OD(Origin to Destination)數據研究城市中功能區域間的移動交互模式。Liang等人[13]在ACM 頂級會議SIGSPATIAL上提出了基于空間網絡模型的黑洞模式，研究地理空間中人類群體的聚集移動模式，并將此研究工作定義為空間網絡中的子圖發現問題。

黑洞模式的研究工作是人類移動模式研究的標志性成果，但在移動模式的演化建模方面存在局限性。黑洞模式定義在空間網絡模型上，該網絡含有地理空間的結點(路口、拐點等)及其連接的邊，但不包含任何時間信息，因而無法反映移動群體在地理空間中隨時間的分布變化，對于在地理空間中移動對象群體的運動演化趨勢研究存在局限性。以“上海踩踏事件”[14]為例，在外灘附近的道路網絡中人群經過一段逐漸匯聚的過程形成了廣場區域的大規模擁堵。現有的黑洞模式通過空間網絡的子圖發現方法可以發現路網中人群聚集的街區，但無法對地理空間中移動群體的持續變化狀態進行建模，因而也就無法跟蹤、發現人群的匯聚趨勢，甚至預測可能引發的潛在踩踏風險。

基于上述分析，本文將研究具有時間演化特性的黑洞模式。新模式在保留原定義的群體規模性和空間區域性的同時，將增加時間演化特性，使之有效反映移動對象群體在空間網絡中隨時間變化的分布情況，這將有助于揭示地理空間中群體性的移動規律。但是，具有時間演化特性的黑洞模式挖掘研究會面臨2方面挑戰。

(1)定義新的空間網絡模型。原有的黑洞模式是基于空間網絡模型定義的，而該網絡模型中包含地理空間和網絡流量2方面信息。新黑洞模式需要增加時間演化性，這就要求空間網絡中包含隨時間變化的流量信息，即需要提出動態的空間網絡模型。

(2)在動態空間網絡中如何提升黑洞模式的挖掘效率。Liang等人[13]將黑洞模式挖掘定義為空間網絡中的子圖發現問題,經過證明,此問題是NP完全問題。而當前研究的動態空間網絡流量數據隨時間變化不斷增加、持續累積，數據規模巨大，因而從動態空間網絡中挖掘黑洞模式依然需要巨大的計算代價。

為了應對上述挑戰，本文提出具有時間演化特性的動態空間網絡模型，基于此模型定義新的黑洞模式，并提出相應的挖掘算法。本文提出的動態空間網絡將邊權重屬性定義為權重的時間序列，用以反映群體移動行為在空間網絡上隨時間的流量變化。相應地，本文提出的黑洞模式在滿足群體規模和空間區域2方面要求的前提下，還需要滿足流量變化的約束要求。為了提升模式挖掘算法的效率，本文設計了基于時空劃分的候選模式剪枝算法，有效降低了挖掘算法在時空維中的搜索代價。最后，基于真實數據的實驗結果表明了本文提出的黑洞模式及其挖掘算法的有效性和可行性。

2 問題定義

在地理空間中的人群聚集行為具有時間持續性、空間區域性和群體規模性。結合上述特性，本節提出動態空間網絡和黑洞模式的定義，并且提出動態空間網絡中的黑洞模式挖掘問題。

定義1(動態空間網絡) 1個動態空間網絡記作G=(V,E)，與G相關的時間區間記作T，V={v1,…,vn}表示頂點集合，E={e1,…,em}表示邊的集合，T={t1,…,tk}表示由單位時間段構成的序列，ti表示T中的第i個單位時間段，|T|為時間序列中單位時間段的個數。任意邊e∈E的流量屬性表示為時間序列形式，記作{f(e,t1),…,f(e,tk)}。

定義2(進/出流量) 邊e的進流量指在單位時間段內進入e的移動對象數量，記作fin(e,t)=∑e′∈(E-e)f(e′,e,t)，其中f(e′,e,t)表示在時間段t內從邊e′進入邊e的移動對象數。同理，邊e的出流量記作fout(e,t)=∑e′∈(E-e)f(e,e′,t)。令邊集E′為E的1個子集，則E′的入流量表示在單位時間段內從其他邊進入邊集E′的移動對象總數，記作fin(E′,t)=∑e∈E′,e′∈(E-E′)f(e′,e,t)。同理，E′的出流量記作fout(E′,t)=∑e∈E′,e′∈(E-E′)f(e,e′,t)。

定義3(凈流量) 凈流量表示在單位時間段內進入邊或邊集流量的凈值。如果進流量小于出流量，則凈流量為負值。邊e在單位時間段t內的凈流量記作fa(e,t)=fin(e,t)-fout(e,t)。同理，邊集E的凈流量記作fa(E,t)=fin(E,t)-fout(E,t)。

定義4(黑洞模式) 用S=(V,E)表示G的1個子圖，其中S.V和S.E分別為G.V和G.E的子集，任意邊e∈S.E的權重序列為{fa(e,ts),…,fa(e,te)},T′={ts,ts+1,…,te}是T的子序列，表示黑洞模式S持續的時間,ts和te分別表示模式的起止單位時間段。S的凈流量記作S.fa=∑t∈T′fa(S.E,t)。若S滿足下列條件，則稱S是1個黑洞模式：

(1)S滿足連通性；

(2)|T′|≥θ；

(3)MBB(S)

(4)S.fa/|T′|≥δ。

其中，θ稱作模式的時間閾值，它規定了聚集事件的持續過程需要滿足一定時長；d稱作空間閾值，它規定對聚集事件的識別在空間上需要足夠精確，其中MBB指子圖在空間上最小外包矩形的對角線長度；δ稱作流量閾值，它規定所檢測的聚集事件需要滿足一定的群體流量規模，且對于持續時間較長的聚集事件，其流量規模也應較大。

問題定義給定1個動態空間網絡G、時間閾值θ、空間閾值d和流量閾值δ，黑洞模式挖掘算法的目標是找到G中符合上述定義的黑洞模式集合BH={S1,S2,…,Sn}，其中BH滿足下列條件：

(1)對于?Si∈BH，1≤i≤n,S滿足定義4；

(2)對于?Si∈(G-BH)，Si不滿足定義4；

(3)?Sa,Sb∈BH(Sa≠Sb)，Sa.E∩Sb.E≠?和Sa.T′∩Sb.T′≠?不能同時成立。

實際上，同一聚集事件在網絡中可能對應多種子圖組合，列舉出所有的子圖會造成挖掘結果的高度冗余，不利于結果分析與展示。此外，黑洞模式挖掘本質上是1種基于密度的子圖搜索問題，這被證明是1個NP完全問題[15]。如果列舉所有的候選子圖并對其逐一驗證，該方法的計算復雜度為指數級。因此，在動態空間網絡中，放棄挖掘黑洞模式的準確結果，而選擇挖掘黑洞模式的近似結果是較為合理的。

3 算法設計

3.1 黑洞模式挖掘算法框架

黑洞模式挖掘的基本框架包含2部分：動態空間網絡構建和黑洞模式挖掘，如圖1所示。

Figure 1 Framework of black hole pattern mining algorithm圖1 黑洞模式挖掘算法框架

(1)動態空間網絡構建。

首先從路網數據中提取路段和路口數據，根據其拓撲關系生成空間網絡。接著對軌跡數據和空間網絡數據進行路網匹配，確定軌跡數據與路網中路段的對應關系，從而統計在不同時間段內各路段的流量信息，生成對應邊上的動態權重，最終完成動態空間網絡的構建。

(2)黑洞模式挖掘。

該部分負責對動態空間網絡數據進行挖掘，生成黑洞模式結果集。算法在時空維上將網絡劃分為若干時空區間，并采用剪枝算法將部分流量稀疏無法形成黑洞的區間予以排除，從而降低算法計算代價，最終在候選的時空區間內搜索黑洞模式。為了避免結果集的冗余，在搜索黑洞模式的同時，更新動態空間網絡數據以及候選時空區間，防止對網絡的重復搜索。

3.2 動態空間網絡構建

本文將城市路段作為空間網絡中的空間實體，將路段與路段之間的鄰接關系對應為空間網絡中實體的拓撲關系。原始的路網數據為空間矢量數據，不具備空間網絡的圖結構性質。因此，首先需要對路網數據進行預處理，從中提取路段和路口的信息，包括標識和空間位置屬性，并根據其鄰接關系構建空間網絡。

動態空間網絡的構建需要計算路段上隨時間變化的流量值。而軌跡數據是移動對象在二維空間中運動形成的位置點序列，和城市道路空間沒有直接的映射關系。因此，為了能夠計算動態空間網絡邊的權重序列，需要通過路網匹配操作[16]，將原始軌跡數據中的位置點對應到各路段上，接著對不同時刻下路段上的移動對象數進行統計，生成各邊上的權重序列。

性質1給定路段e和時間段t，假設在t的開始時刻路段e上的移動對象數為p，在結束時刻e上的移動對象數為q，則路段e在時間段t內的凈流量fa(e,t)=q-p。

證明根據凈流量定義，有q=p+fin(e,t)-fout(e,t)，變換可得q-p=fin(e,t)-fout(e,t)=fa(e,t)。故性質1得證。

□

根據定義，凈流量的計算需要統計各移動對象在不同路段上的進出情況，計算量較大。而由性質1，在計算單位時間段內路段上的凈流量時，只需要直接計算起止時刻該路段上的移動對象數的差值即可，從而避免了凈流量統計的高代價計算。

模式挖掘的過程中需要頻繁訪問動態空間網絡數據。然而隨著數據的不斷累積，動態空間網絡數據的規模不斷增大，這導致模式挖掘過程中無法將數據全部加載在內存中，而只能將數據保存在磁盤上，造成數據訪問效率低下。為了加快數據的查詢效率，提高算法性能，本文針對存放在磁盤上的動態空間網絡數據設計相應的索引。如圖2所示，利用空間網格索引將各邊分配到對應的網格單元，以提高對邊數據的空間查詢效率。對索引中的每一條邊存儲其拓撲關系和時空屬性，用鄰接表記錄其鄰邊集合，sp和ep分別表示其起止端點的空間信息，st和et指其動態權重的起止單位時間段信息。數據以邊為單位存儲在磁盤上，每一個數據單元記錄該邊的權重序列，并將其磁盤偏移量記錄在索引中，方便快速尋址。

Figure 2 Index of dynamic spatial network data圖2 動態空間網絡數據索引

3.3 黑洞模式挖掘算法

黑洞模式挖掘本質上是一種圖數據中的子圖發現問題，其時間復雜度隨著數據規模的增大呈指數級增長。由于動態空間網絡數據隨著時間增長不斷累積，其數據量在時間維度上規模巨大，若不經優化，直接對其展開黑洞模式的挖掘將耗費大量的時間。黑洞模式對應了網絡中流量相對密集的子圖結構。現實中移動對象分布的不均勻性導致網絡中的流量分布也是不均勻的，由此網絡中部分流量稀疏的時空區間必然無法形成黑洞模式，可直接予以排除，不需要參與黑洞的檢測。因此，為了壓縮模式挖掘的搜索空間，本文在空間和時間2個維度將動態空間網絡劃分為若干時空區間，并篩選出流量相對密集的時空區間作為候選參與黑洞模式的檢測。黑洞模式算法偽代碼如算法1所示。

算法1黑洞模式挖掘算法

輸入：動態空間網絡G，時間區間T，時間閾值θ，空間閾值d，流量閾值δ。

輸出：黑洞模式集合BH。

1.BH←?;

2.GS←SpatialPart(G,d);/*空間維劃分后生成候選區域集合*/

3. for eachg∈GSdo

4.TS←TemporalPart(T,θ);/*進行時間段劃分，得到不同時間段的候選區域*/

5.FilterByF(TS);//初步過濾算法

6.FilterByH(TS);/*結合流量持續性要求進一步過濾算法*/

7. whileTS≠? do

8.Ti,j←MaxUB(TS);//上界最大候選

9.BH′←BHExpansion(g,Ti,j);/*搜索黑洞模式*/

10.BH←BH∪BH′;

11.Update(g,TS);//更新候選區間

12. end while

13. end for

首先討論在空間維上的劃分方式。由于黑洞模式挖掘最終將在候選時空區間內進行，因此對搜索空間的劃分需要確保劃分邊界不會影響挖掘結果的完整性。受傳統黑洞模式研究工作的啟發，本文利用網格結構對動態空間網絡進行空間維的劃分。如圖3所示，假設模式的空間閾值為d，用邊長為d的方格對網絡進行空間維上的劃分，gab表示行列號分別為a和b的方格，gab.E表示方格內的邊集合，則有如下性質。

性質2給定一個黑洞模式S和方格gab，若S.E∩gab.E≠?，則必有S.E?AR(gab)，其中AR(gab)定義為由滿足|i-a|≤1,|j-b|≤1的所有方格gij組成的區域，稱作網格gab的鄰域，鄰域內的邊集記為AR(gab).E。

Figure 3 Schematic diagram of spatial division圖3 空間劃分示意圖

性質2表明，針對任意方格內網絡數據的黑洞模式挖掘，其搜索邊界是方格對應的鄰域。因而，通過空間維的數據劃分，挖掘任務被分解為各網格及其鄰域內的黑洞模式挖掘問題。以針對方格g的黑洞模式挖掘為例，如圖4a所示，挖掘算法的搜索空間在空間維上是AR(g)，在時間維上是T。由于黑洞模式的持續時長并不固定，因此需要在T時域上搜索滿足閾值的任意長度的黑洞模式，令Ti,j={ti,ti+1,…,tj}，如圖4b中矩陣所示，假設模式的時間閾值為θ，則{Ti,j|1≤i≤j≤k,j-i≥θ}是所有需要搜索的候選時間區間。

Figure 4 Searching space of black hole pattern mining圖4 黑洞模式挖掘搜索空間

隨著數據的積累，動態空間網絡數據在時間維上的規模較大，導致算法搜索空間擴大。由于現實中同一地區內不可能長時間保持人流量的高速增長，因此AR(g)中網絡的凈流量在T上通常是稀疏的。對于某些流量值過于稀疏而不可能形成黑洞模式的時間區間，考慮通過適當的篩選手段予以排除。下文以候選時間區間Ti,j={ti,ti+1,…,tj}為例，討論在不同流量規模下的取舍。

性質3子圖S的凈流量等于對應邊集在其時域內的凈流量之和，即S.fa=∑t∈S.T′,e∈S.Efa(e,t)。

證明根據定義2和定義3可作如下推導:

S.fa=∑t∈S.T′fa(S.E,t)=

∑t∈S.T′(fin(S.E,t)-fout(S.E,t))=

∑t∈S.T′(∑e∈S.Efin(e,t)-∑e∈S.Efout(e,t))=

∑t∈S.T′(∑e∈S.E(fin(e,t)-fout(e,t)))=

∑t∈S.T′(∑e∈S.Efa(e,t))=

∑t∈S.T′,e∈S.Efa(e,t)

故性質3得證。

□

綜上所述，對于方格g中的任意候選時間區間Ti,j而言，Fi,j和Hi,j分別為其子圖凈流量的2個上界，Fi,j誤差較大但方便計算，Hi,j過濾效果更好但計算代價較高。因此，考慮先利用Fi,j篩選如圖4b中所有的候選時間區間 ，再利用Hi,j對經過初步篩選的候選時間區間作進一步的篩選。經過時間區間的篩選，最終對剩下的候選時間區間采用下文中的搜索算法挖掘滿足閾值要求的黑洞模式。

由于動態空間網絡中流量的物理含義相同，故黑洞模式的搜索可繼續沿用傳統黑洞模式的啟發式搜索策略[13]。每次從候選集中選擇流量上界最大的時間區間Ti,j展開搜索。首先對方格中的每條邊e計算Ti,j時間區間內的凈流量和fa(e,Ti,j)。取方格g內凈流量和最大的1條邊構成初始子圖S，其中S.T′=Ti,j，隨后采用迭代的方式對子圖進行擴張。在每次迭代中，取當前子圖S的鄰邊作為候選邊集合，對候選邊集合中的每1條邊e進行打分，取分值最高的邊擴展當前子圖，打分策略如下所示：

其中，Δ指的是S在加入邊e之后對角線的變化值，即Δ=MBB(S+e)-MBB(S)，為了便于描述，其中S+e為S中加入邊e后生成的新子圖的簡單表示。得分為-∞或MBB(S+e)超出空間閾值的邊不予擴展，當沒有候選邊可用于擴展時，迭代結束。若此時的子圖S滿足S.fa/|S.T′|≥δ，則將其作為結果輸出，同時將S所涉及的邊從候選數據集中刪除，防止重復檢測，同時刷新候選時間區間流量值。按上述算法重復搜索黑洞模式，直到候選集為空。

4 實驗與分析

4.1 實驗設置

為了驗證基于動態空間網絡的黑洞模式及其挖掘算法的有效性和高效性，本文使用真實的GPS軌跡數據和路網數據進行實驗。實驗環境為Windows 10操作系統，處理器為Intel Core i5，主頻3.20 GHz，內存12 GB，硬盤容量500 GB，硬盤轉速為7 200轉/秒。

實驗數據為上海市路網數據和出租車軌跡數據。路網由286 591條路段和262 764個路口構成。軌跡數據是2015年4月2日上海市13 518輛出租車形成的時空軌跡。基于2類數據構建出動態空間網絡，數據大小為18.5 GB。

4.2 評價方法

實驗將從模式定義的有效性和挖掘算法的效率2個方面對基于動態空間網絡的黑洞模式挖掘算法進行評估。

在有效性方面，本文以空間網絡的黑洞模式挖掘算法[12]為比較對象。將空間網絡的黑洞模式簡稱為BH-SN(Black Hole in Spatial Network)，將本文提出的基于動態空間網絡的黑洞模式簡稱為BH-DSN(Black Hole in Dynamic Spatial Network)。由于2種模式在群體規模性和空間區域性方面的約束要求相同，因而本文從挖掘結果的重合情況及其時長2方面進行對比。如果2種挖掘算法的結果重合數量越多，則說明BH-DSN和BH-SN一樣有效，如果在高重合的情況下BH-DSN比BH-SN得到更多的結果，則說明BH-DSN比BH-SN更有效。另一方面，比較重合結果的時長情況，即相同參數設置下BH-DSN結果的時間區間與BH-SN結果的時間區間存在包含、分離和相交3種情況。如果在重合結果中，BH-DSN模式的時間區間包含BH-SN模式的時間區間比較多，則說明BH-DSN模式挖掘算法能發現時長更完整的聚集過程。

在算法效率實驗部分，主要對比基于網格劃分的黑洞模式挖掘算法BHPM(Black Hole Pattern Mining)和對搜索空間進行剪枝的改進算法BHPM*兩者的性能。效率實驗分2組進行：第1組實驗比較兩者在不同規模數據集下的運行時間；第2組實驗比較了2個算法在不同參數下的運行時間，包括BH-DSN模式定義中的時間閾值、空間閾值和流量閾值3個參數。

4.3 算法有效性

有效性分析的參數設置如下。BH-DSN的參數設置為：時間閾值θ=3，空間閾值d=150 m，流量閾值δ=5，動態空間網絡的流量匯總時間間隔為1/2/3/4/5 min(分5組進行)。由于BH-SN模式基于流量匯總時間段內的靜態流量進行定義，為了保證公平性，其流量閾值為θ*δ=15，空間閾值同為150 m，空間網絡的流量匯總時間間隔為3/6/9/12/15 min。輸入數據的規模為4月2日一整天的數據集。在上述時間間隔設置下，2種模式的檢測結果均對應最小持續時長為3/6/9/12/15 min的聚集事件，且根據定義，2種模式所檢測到的聚集事件在單位時空區間內的流量值是相同的，即檢測的目標是對等的。

表1描述了2種模式挖掘結果的重合情況，重合數指BH-SN模式的挖掘結果和BH-DSN挖掘結果在空間上重合的數量，其中，若2種模式的MBB在空間上相交，則說明2者相互鄰近，判定為重合。從表1可以看出，在不同的匯總時間間隔下，BH-DSN模式的挖掘結果幾乎均能完全覆蓋BH-SN模式的挖掘結果，不僅如此，BH-DSN模式的挖掘結果在數量上更多，而根據定義，2者的挖掘目標是對等的，因此進一步，BH-DSN模式能檢測到更多BH-SN模式無法檢測到的聚集事件。之所以出現這樣的差異，是因為BH-SN針對空間網絡中的靜態流量進行定義，對于聚集事件的檢測效果取決于流量匯總的時間區間。例如，若某1聚集事件形成過程的前半段和后半段被劃分到不同的黑洞模式挖掘批次，則有可能因流量沒有達到閾值而無法被檢測。而BH-DSN模式基于動態流量而定義，檢測范圍覆蓋任意時間區間，且群體規模隨時間跨度的不同而調整，因此能對發生在任何時間區間內的聚集事件進行準確檢測。實驗結果表明，本文提出的黑洞模式能對區域中的聚集事件進行更有效的檢測。

Table 1 Repetition of mining results表1 挖掘結果重合情況

表2分析了2種模式重合結果的平均時長以及時間區間的包含情況。其中，包含(相交、相離)比例指BH-DSN模式的時間區間對BH-SN模式呈現包含(相交、相離)關系的數量占比。結果表明，BH-DSN模式挖掘結果的時間長度比BH-DSN模式的更長，且在時間區間上普遍包含BH-DSN模式的。這是由于BH-DSN模式的定義更加靈活，能對任意時長的聚集事件進行檢測，而傳統的BH-SN模式的檢測效果取決于空間網絡流量匯總的時間間隔。實驗結果表明，BH-DSN模式能對聚集事件的過程進行更完整的檢測。

Table 2 Comparison of mining time表2 挖掘時長對比

4.4 算法效率

本節對本文提出的算法進行效率方面的實驗分析。首先進行第1組實驗，分析在不同數據規模下BHPM和BHPM*的性能表現。單次實驗的輸入數據開始時間均為2015年4月2日上午6點，動態空間網格數據的流量匯總時間間隔均為1 min，通過設置不同的結束時間，可以控制輸入數據的規模大小。算法參數設置如下：時間閾值θ=3，空間閾值d=100 m，流量閾值δ=3。

從圖5可以看出，在數據規模相同的情況下，BHPM*算法的運行時間顯著低于不經過優化的BHPM算法，并且隨著數據規模的增大，2者的運行時間差異也越來越大。

Figure 5 Algorithm execution time varies with data scale圖5 算法執行時間隨數據規模的變化

第2組效率實驗對比2個算法在不同參數設置情況下的運行時間。實驗采用控制變量的方法進行，即在改變其中1項參數的情況下，保持另外2項參數不變，測試數據的規模均為2 h,流量匯總時間間隔為1 min。默認的參數設置如下：時間閾值θ=3，空間閾值d=100 m，流量閾值δ=3。

Figure 6 Algorithm execution time varies with time threshold圖6 算法執行時間隨時間閾值的變化

Figure 7 Algorithm execution time varies with space threshold圖7 算法執行時間隨空間閾值的變化

Figure 8 Algorithm execution time varies with flow threshold圖8 算法執行時間隨流量閾值的變化

圖6～圖8分別對比了算法執行時間在不同時間閾值、空間閾值和流量閾值下的變化情況。可以看出，相比于原始算法，BHPM*算法的性能有數量級的提升。其中，算法的執行時間隨著時間閾值和流量閾值的增大而縮短，這是因為這2個閾值的增大代表著對模式的時間和流量規模的要求提高，產生的候選集較少。同理，隨著空間閾值的提高，黑洞模式的候選集越多，算法執行時間隨之增加。

5 結束語

本文提出了一種基于動態空間網絡的黑洞模式，用于城市群體聚集事件的識別和檢測。該模式與現有研究相比，在時空維上表現出更加準確的識別效果。由于動態空間網絡數據隨時間不斷累積而規模巨大，為了提高模式挖掘效率，本文利用動態空間網絡流量分布不均的特點對黑洞模式挖掘搜索空間剪枝，提高算法性能。通過實驗分析驗證了基于動態空間網絡的黑洞模式在有效性方面的優勢，并通過對比黑洞模式挖掘算法及其改進算法的運行時間，驗證了本文提出的改進算法的優化效果。