基于最小描述長度的圖分割變化檢測改進算法

魏長寶，姚汝賢

（黃淮學院信息工程學院，河南駐馬店463000）

·圖形圖像處理·

基于最小描述長度的圖分割變化檢測改進算法

魏長寶，姚汝賢

（黃淮學院信息工程學院，河南駐馬店463000）

圖分割變化檢測（GPCD）可檢測出可能導致網絡社區發生變化的重要事件。針對現有的檢測算法未考慮圖形分割結構動態特點的不足，利用概率樹表示圖分割結構的概率模型，將GPCD問題轉化為基于最小描述長度的樹變化檢測問題，并提出一種求解GPCD問題的Tree算法。仿真實驗結果表明，與GraphScope基準算法相比，該算法檢測圖分割結構變化時的虛警率較低，并具有較高的檢測精度。

圖分割變化檢測；最小描述長度；概率樹；變化成本；虛警率

中文引用格式：魏長寶，姚汝賢.基于最小描述長度的圖分割變化檢測改進算法［J］.計算機工程，2015，41（7）：274?279，284.

英文引用格式：Wei Changbao，Yao Ruxian.Improved Algorithm of Graph Partitioning Change Detection Based on M inimum Description Length［J］.Computer Engineering，2015，41（7）：274?279，284.

1 概述

圖分割技術［1?3］（也稱圖聚合問題）是一種按照某種標準將圖分成若干子模塊的方法。圖分割可以使得分割后各子模塊中節點聯系更緊密，模塊間聯系更低。該技術在蛋白質網絡、網絡數據挖掘等許多領域都有廣泛應用。本文主要研究如何對二分圖時間序列的圖分割結構變化進行檢測。將該檢測問題稱為圖分割變化檢測（Graph Partitioning Change Detection，GPCD）問題。根據鏈路關系，圖分割結構可看成圖節點的聚類結構。這一圖分割過程將會導致多個網絡社區。因此，它有助于社區結構變化檢測及圖分割結構變化檢測，而社區結構變化往往對應于真實世界中的重要世界，因此研究GPCD問題具有重要意義［4?5］。

文獻［6?7］基于最小描述長度（MDL）原則，從無損數據壓縮角度為選擇最優分割提供了一種準則。該準則認為，如果有種分割策略，進行圖形編碼時所需總碼長及相對數據量最小，則該分割策略即為最優分割。為此，文獻［8?9］提出基于MDL的靜態二分圖分割方法和普通圖分割方法。對于動態圖分割，文獻［10］提出 GraphScope圖形變化檢測算法。該方法根據MDL準則將二分圖分割為一組子圖，以便使數據的碼長及圖形分割碼長之和最小，通過進行分割是否發生變化的假設性檢驗來實現圖形分割結構的變化檢測。GraphScope是GPCD問題的有效求解算法，但是存在如下缺陷：（1）初始圖必須是節點分割的直積，圖形分割結構的表示非常有限，本文將這一現象稱為基于直積的分割策略。當描述具有分層特征的圖分割結構時會出現大量參數，比如進行一次分割后，對每個被分割的子圖還需再一次分割，依次類推。（2）沒有考慮圖形分割結構的動態特點。實際上，該方法也沒有考慮分割轉換概率模型。因此，圖形變化的成本被忽略，導致出現虛警。

為此，本文提出針對GPCD問題的一種新的求解算法TREE，主要工作如下：（1）基于樹進行圖分割：TREE算法利用基于樹的概率模型來表示圖形分割結構，本文稱其為基于樹的分割方法，GPCD問題可轉化為樹結構的變化檢測問題。與基于直積的分割方法相比，基于樹的分割問題可使本文使用較少參數來表示分層分割圖。（2）GPCD問題的動態模型選擇：通過引入圖分割之間的轉換概率，以考慮基于樹的圖分割的動態特性。于是，圖分割變化成本可定義為轉換概率的碼長。然后，本文將動態模型選擇（DMS）理論［11］應用于圖分割序列選擇過程中，即通過選擇一組圖分割，可使數據的碼長與變化成本之和最小。因此，根據數據擬合和變化復雜度間的平衡情況確定最優序列。

2 圖形分割變化檢測

假設圖形序列為：

其中，每個二分圖Gt（t＝1，2，…）有m個發送節點和n個接收節點。更準確地說，每個Gt可表示為一個m×n矩陣，第（i，j）個元素gij表示第i個發送方至第j個接收方的鏈接。本文假設m和n固定。下面分析如何將圖形序列Ψ分割為如下一組圖形子序列：

其中，每個Ψs表示從ts至ts+1-1的一個圖形序列：

ts稱為變化點，Ψs稱為一個分段（s＝1，2，…）。將圖 G的分割看成圖 G分解為一組連接子圖｛G（u）｝的過程，其中G＝∪uG（u）。可得GPCD問題定義如下：已知一個圖形序列Ψ＝G1，G2，…，根據G1，G2，…的分割序列來檢測出Ψ中的變化點及其相應變化。

3 基于樹的GPCD問題

3.1 基于樹分割的概率模型

本文利用二分樹來實現基于樹的分割表示。在二分樹中，每個樹節點關聯一組發送節點和接收節點。為了區分樹中節點和圖中節點，將前者稱為樹節點，將后者稱為節點。對每個樹節點，其子樹節點的分配有2種情況。情況1：2個子樹節點的發送節點集合相同，但是接收節點集合分離。情況2：2個子樹節點的接收節點集合相同，但是發送節點集合分離。

例如，如果圖 G的矩陣表示如式（1）所示，則圖G可由圖1中的二分樹確定。首先接收方節點集合可分為｛1，2｝和｛3，4｝，然后對于具有前一集合的子樹節點，接收節點集合可分為｛1，2｝和｛3，4｝。

圖1 基于樹的分割過程

已知樹M，設u＝（urow，ucol）表示樹M中葉子u的行節點和列節點組成的元組。設G（u）表示u的相應子圖。此時，可以獲得一種基于數的分割G＝∪uG（u）。

設Mt表示 Gt的對應樹，二分樹序列可表示如下：

Ψ的分割問題轉化為Θ的分割問題（如圖2所示），本文將Θ的分割表示為 Θ ＝｛Θ1，Θ2，…｝。 對每個s，任意M，M′∈Θs有M＝M′。如果Gt∈Ψs，則Mt∈Θs。也就是說，一個分段只對應于一個樹。

圖2 基于樹的圖分割變化檢測

設M表示圖G相應的二分樹。M的概率分布定義可表示如下：對樹M中的葉子u，Gr，c（u）表示u相應子圖中第r行第c列的元素。假設根據參數為λ（u）的泊松分布生成 Gr，c（u），并將其表示為

3.2 動態模型選擇

假設已知圖形序列Ψ＝G1，G2，…，GT（T：數據規模）及基于樹的分割序列Θ＝M1，M2，…，MT，其中Mi會隨著時間而變化。假設每個碼字不是另一碼字的前輟，在此前提下考慮ψ和Θ的編碼問題。本文引入動態模型選擇（DMS）準則［8］來衡量已知 ψ時Θ的質量。將其定義為對ψ和Θ進行編碼所需要的總碼長L（Ψ；Θ）。

其中，M0已知；式（3）右側第1項表示Ψ相對于Θ的碼長；第2項表示Θ本身碼長。DMS可看成是將傳統的基于MDL的靜態模型選擇拓展為一種模型序列選擇［11］。

3.3 基于樹的圖形分割編碼方法

下面分析計算式（3）右側第1和第2項。Mt已知時Gt的碼長可計算為歸一化最大似然（NML）碼長，該碼長定義為歸一化最大似然的負對數，如下式所示：

其中，leaf（Mt）表示Mt的一組葉節點；Gt（u）表示第u個葉節點的子圖。設 Gt：r，c（u）表示 Gt（u）的第（r，c）個元素。設urow和ucol分別表示樹節點u的行節點集合和列節點集合。于是，PNML表示歸一化最大似然分布，定義如下：

式（5）右側的分母難以進行解析計算，根據Rissanen方程［12］進行近似計算：設I（λ）表示定義為的Fisher信息矩陣，Gt的隨機復雜性有如下等式：

其中，a表示最小整數，λ＾∈［0，2a］且lb×a＝lb a+ lblb a+…+lb b表示對a編碼時需要的碼長，此時對所有正項求和，且lb b≈2.865 064。如果數據范圍無限，則Fisher信息發散，因此本文將其限制在范圍［0，2a］內以便使整數有限。 將式（6）代入式（4），可得：

3.4 樹轉換的編碼方法

下面給出式（3）中第 2項的計算方法。設α（＞0）表示一維參數。設No（Mt）表示Mt中葉節點的數量，N1（Mt）表示 Mt中內部樹節點的數量，且：

用int（Mt）表示Mt的內部樹節點集合，mu表示在樹節點u處可被分割的樹節點數量。轉換概率定義如下（對t≥1）：

該轉換定義表明，樹節點不發生變化的概率為1-α，發生變化的概率為α。在后一種情況下，根據概率選擇 Mt。因此，樹轉換的碼長為：

此時，每次轉換時樹編碼方法與 Rissanen方法［12］吻合，于是有：

其中，n（Mt-1）表示Mt-1中樹的變化總量。

3.5 基于樹的GPCD問題

下面介紹本文提出的TREE算法，該算法的總體流程如下：

（1）通過分割和融合操作來構建一個樹序列：本文利用圖序列來構建樹序列。樹序列包括多個子序列，每個子序列稱為一個段。假設在同一分段內的所有樹相同，且對不同的時間分段，一個段中的樹與相鄰段中的樹不同。為了構建每個段中的樹，對節點進行分配，對樹進行分割或修剪操作以使隨機復雜性最小。具體內容見算法1～算法3。

算法1 節點分配

已知：圖形子序列Ψs，對葉節點u，有一組行節點：u1row，u2row

步驟1 設置R＝u1row∪u2row。

步驟2 設置x（∈R）為一個列節點，設置R←R-｛x｝

步驟3 計算：

步驟4 計算 KL（λx，λ1），KL（λx，λ2），其中，表示參數λ1和λ2時泊松分布間的Kullback?Leibler散度。

步驟5 如果 KL（λx，λ1）＜KL（λx，λ2）且 x∈u2row，則u1row←u1row∪｛x｝，u2row←u2row-｛x｝，否則如果KL（λx，λ2）＜KL（λx，λ1）且 x∈u1row，則 u2row←u2row∪｛x｝，u1row←u1row-｛x｝，否則保持不變。

步驟6 如果R＝?，則終止，否則執行步驟2。

（2）對樹序列進行最優分段：為了使總碼長最小，根據式（3）DMS準則對樹序列進行分段。按照如下方法確定一個變化點序列。對已知分段Ψ，Ψ的隨機復雜度（SC）定義為：

其中，Mt表示Gt的樹。設SCs表示最后一個分段Ψs的隨機復雜性，SCs+t表示Ψs∪Gt的隨機復雜性，SCt表示Gt的隨機復雜性，表示從一個段到另一個段的轉換概率估計。將式（3）DMS準則應用到樹序列的分割中。于是發現，如果：

則可將時間t看成是一個變化點，否則不將其看成變化點。此時：

鑒于兩者間的時間差異，通過式（3）DMS準則和式（9）可推出式（12）。此外，Gt的變化點指數可定義為：

該指數可衡量在時間t進行分割時碼長的下降情況。本文定義，只要下式成立則t即是一個變化點。

TREE的時間復雜度為O（mn（lb mn）T），其中，m表示列的數量；n表示行的數量；T表示數據規模。這是因為每個樹進行分割和融合的計算復雜度為O（mn），樹的最大規模為O（lb mn），TREE算法運行時與T呈線性關系。

算法2 樹分割

已知：u：雙支樹的一個葉節點

步驟1 對葉節點u，生成新的葉節點u1，u2，并設置u1row＝urow，u2row＝?。

步驟2 SC1＝SC（u1）+SC（u2）。

步驟3 對x∈u1row，計算將x從u1移動到u2時所生成的樹的SC，并將其記為SC2。

步驟4 如果 SC2＜SC1，則 u1row←u1row-｛x｝，且u2row←u2row∪｛x｝。

步驟5 對所有 x（∈u1row），重復步驟 2～步驟4。

步驟6 對u1，u2，運行算法1。

步驟7 如果SC（u1）+SC（u2）-lb P0+?（u）＜SC（u）-lb P1，則分割列節點。

算法3 樹融合

已知：u：樹的根，q：隊列

步驟1 q＝｛u｝。

步驟2 u′←q.dequeue，d：u′的深度。

步驟3 設u1，u2是u′的子樹節點。

計算：

SC1＝SC（u′）-lbP1

SC2＝SC（u1）+SC（u2）-lbP0+l（u）

步驟4 如果SC1＜SC2，則修剪u1，u2，否則q.enqueue（u1，u2）。

步驟5 重復步驟2～步驟4直到q＝?。

4 基于直積的GPCD算法

GraphScope算法是一種典型的基于硬聚類的GPCD算法。它首先分別對接收節點和發送節點進行聚類，然后生成一個圖形分割作為發送節點和接收節點聚類的直積。文中將這種分割稱為基于直積的分割。例如，假設發送節點集合為｛A，B，C，D｝，接收節點的集合為｛1，2，3，4｝。當為接收節點生成｛A，B｝和｛C，D｝2個聚類，并為接收節點生成｛1，2｝和｛3，4｝2個聚類時，生成的分割策略有4個區域分割成為它們的直積，如圖3所示。

圖3 基于直積的分割

GraphScope算法使用多種啟發式策略來構建基于直積的分割，此時總碼長在所有可能的分割中局部最小。

GraphScope的計算復雜度為O（mnT（k?+1?）），其中，k?表示列聚類數量；1?表示行聚類數量。

5 仿真實驗

5.1 基于人工數據集的實驗

利用人工數據集來比較TREE和GraphScope算法。設置接收節點和發送節點數量均為20個，并準備4個數據集，每個數據集有30個數據。根據Θ1生成t＝1～10之間的數據，根據Θ2生成t＝11～20間的數據，根據Θ3生成t＝21～30間的數據。變化點為tc＝11和21。

生成數據集1，2，3，4，其分割結構變化如圖4～圖7所示。

圖4 數據集1分割結構變化

圖5 數據集2分割結構變化

圖6 數據集3分割結構變化

圖7 數據集4分割結構變化

矩陣中的數據表明各分段的數量。使用效益和虛警率（FAR）2個指標來衡量GPCD的性能。假設x表示被檢測出來的變化點，tc表示真實點，x的效益定義為：

其中，T表示已知正數。當且僅當x與tc吻合時值為1，當增加時線性降為0。如果警報點大于T且離真實點很遠，則認為警報丟失。FAR表示所有警報中不是變化點的警報比例。進行50次實驗取均值。

表1給出了不同算法在4個數據集上的效益和虛警率比較結果。本文在計算效益時設置T＝3。

表1 數據集1～數據集4的效益和FAR

對數據集1，2種算法的效益值均較高，TREE的FAR值遠低于GraphScope。這是因為直積方法無法有效表示真實的分割，導致GraphScope的FAR高于TREE。對數據集2，由于與數據集1同樣的原因，GraphScope算法的FAR較高。然而，即使對數據集2，基于樹的方法無法有效表示真實分割，TREE的FAR仍然遠低于 GraphScope。對數據集 3，GraphScope的FAR低于TREE。這是因為直積方法非常有效地表示了真實分割，TREE方法需要更多的參數才能表示真實分割。在實踐中這種情況比較罕見。從以上結果可以看出，除了直積可以有效表示真實分割的少部分情況外，TREE的性能優于GraphScope。

表2給出了不同算法在數據集1～數據集4上的內存占用量比較結果。實驗環境為：CPU為酷睿3.4 GHz，內存容量為4 GB，W indows 7操作系統（64位）。從表2可以看到，TREE算法在4種數據集上的表現都要優于GraphScope算法。仔細分析其原因可知，這主要是因為GraphScope算法在描述具有分層特征的圖分割結構時會出現大量參數，需要多次分割以保證檢測的準確性，所以占用了較多的系統資源。而本文方法利用基于樹的概率模型來表示圖分割結構，并將動態模型選擇（DMS）理論應用于圖形分割序列選擇過程中，與GraphScope算法相比，可以用較少參數來表示分層分割圖，因此取得了更好的系統性能。

表2 不同算法的內存占用量比較 MB

5.2 基于真實數據集的實驗

利用日本內務交通省、統計局、政策規劃和統計研究及培訓學院總干事提供的人口流動數據［14］進行實驗。這一數據對公眾開放，給出了2005年4月-2011年11月間日本所有縣市每月人口流動情況。發送節點是人口流出的縣市，接收節點是人口流入的縣市。從發送節點到接收節點之間鏈路的數值表示一個月內從發送節點到接收節點間的流動人口數量。時間點總數為81，發送節點和接收節點總數均為47個。

圖8和圖9給出了2種算法的運行結果。每個圖中的橫坐標顯示了 2005年4月開始的時間。圖8、圖9中的縱坐標表示變化點評分。在2種情況下，當縱坐標數值超過0時即可檢測出變化點。2種算法均可檢測出t＝71時的變化（從紅色broken線可以看出）。該變化對應于2011年日本遠東大地震導致的人口遷移。2011年5月檢測出來的變化對應于日本政府宣布日本部分地區輻射水平顯著升高時。2種算法還檢測出了2011年6月和8月的變化，這2次變化對應于日本政府宣布2011年6月-8月間的人口流動。雖然TREE和GraphScope可以成功檢測出重要真實事件的變化，但是GraphScope發布的與任何事件均無關聯的虛警數量高于TREE。這表明TREE的穩定性優于GraphScope。

圖8 TREE算法運行結果

圖9 GraphScope算法運行結果

6 結束語

本文主要研究了圖分割變化檢測問題，提出一種基于樹聚類的GPCD求解算法TREE。該算法將傳統的基于直積的方法（GraphScope）拓展至分割結構，具有分層特點。根據MDL準則，從動態模型選擇角度設計本文算法，并與GraphScope算法進行比較，結果表明，對多種圖形分割結構，TREE算法的GPCD性能優于GraphScope算法。下一步研究工作的重點是針對有權圖分割時不能很好解決子圖內部耦合度不高的問題，使用可以同時優化子圖內部頂點耦合度和子圖之間頂點耦合度的Ncut準則，提出基于散列技術的圖分割改進算法。

［1］ 文政穎，于海鵬.基于多Gamma分布模型的 SAR圖像直方圖分割算法［J］.計算機工程與設計，2014，35（6）：2104?2108.

［2］ 汪云飛，畢篤彥，孫 毅，等.一種采用雙勢阱策略的小直徑圖分割方法［J］.計算機應用與軟件，2013，30（4）：275?278.

［3］ Stanton I，Kliot G.Stream ing Graph Partitioning for Large Distributed Graphs［C］／／Proceedings of the 18th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining.New York，USA：ACM Press，2012：1222?1230.

［4］ Bansal N，Feige U，K rauthgamer R，et al.M in?max Graph Partitioning and Small Set Expansion［J］.SIAM Journal on Computing，2014，43（2）：872?904.

［5］ Nishimura J，Ugander J.Restreaming Graph Partitioning：Simple Versatile Algorithms for Advanced Balanc?ing［C］／／Proceeding s of the 19th ACM SIGKDD International Conference on Know ledge Discovery and Data Mining.Chicago，USA：ACM Press，2013：1106?1114.

［6］ López?Ruiz R，Sanudo J，Romera E，et al.Statistical Complexity and Fisher?shannon Information：Applica?tions［M］.Berlin，Germany：Springer，2011.

［7］ Silva T C，Zhao L.Stochastic Competitive Learning in Complex Networks［J］.IEEE Transactions on Neural Networks and Learning Systems，2012，23（3）：385?398.

［8］ Chakrabarti D，Papadim itriou S，Modha D S，et al.Fully Automatic Cross?associations［C］／／Proceedings of the 10th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining.New York，USA：ACM Press，2012：79?88.

［9］ Chakrabarti D.Autopart：Parameter?free Graph Partitioning and Outlier Detection［C］／／Proceedings of PKDD’04. Berlin，Germany：Springer，2004：112?124.

［10］ Sun J，Faloutsos C，Papadim itriou S，et al.Graphscope：Parameter?free M ining of Large Time?evolving Graphs［C］／／Proceedings of the 13th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining.San Jose，USA：ACM Press，2007：687?696.

［11］ Yamanishi K，Maruyama Y.Dynam ic Model Selection w ith Its Applications to Novelty Detection［J］.IEEE Transactions on Information Theory，2013，53（6）：2180?2189.

［12］ Rissanen J.Fisher Information and Stochastic Comple?xity［J］.IEEE Transactions on Information Theory，2012，42（1）：40?47.

［13］ Haldar JP，Hernando D，Liang Z P.Compressed?sensing MRIw ith Random Encoding［J］.IEEE Transactions on Medical Imaging，2011，30（4）：893?903.

［14］ Jonsen ID，Flemming JM，Myers R A.Robust State?space Modeling of Animal Movement Data［J］.Ecology，2005，86（11）：2874?2880.

編輯 索書志

Im proved Algorithm of Graph Partitioning Change Detection Based on M inimum Description Length

WEIChangbao，YAO Ruxian
（School of Information Engineering，Huanghuai University，Zhumadian 463000，China）

Graph Partitioning Change Detection（GPCD）problem is important in that it leads to discovery of important eventswhich cause changes of network communities.Aim ing at the disadvantages that the existing detecting algorithms do not consider dynamic graph partitioning structures，itemploys probabilistic trees to represent probabilisticmodels of graph partitioning structures，and reduces GPCD into the issue of detecting changes of trees on the basis of the M inimum Description Length（MDL） principle，and proposes Tree algorithm for solving the GPCD problem.Simulation experimental results show that the algorithm realizes significantly less False Alarm Rate（FAR）for change detection than the baselinemethod called GraphScope.And it is able to detect changesmore accurately than GraphScope.

Graph Partitioning Change Detection（GPCD）；M inimum Description Length（MDL）；probabilistic tree；cost of change；False Alarm Rate（FAR）

1000?3428（2015）07?0274?06

A

TP393

10.3969／j.issn.1000?3428.2015.07.052

河南省科技攻關計劃基金資助項目（122102210430）。

魏長寶（1972-），男，副教授、碩士，主研方向：圖像處理，智能信息處理；姚汝賢，副教授、碩士。

2014?12?24

2015?02?07E?mail：82671778＠qq.com