魏長寶，姚汝賢

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

·圖形圖像處理·

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

魏長寶，姚汝賢

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

圖分割變化檢測（GPCD）可檢測出可能導(dǎo)致網(wǎng)絡(luò)社區(qū)發(fā)生變化的重要事件。針對現(xiàn)有的檢測算法未考慮圖形分割結(jié)構(gòu)動態(tài)特點(diǎn)的不足，利用概率樹表示圖分割結(jié)構(gòu)的概率模型，將GPCD問題轉(zhuǎn)化為基于最小描述長度的樹變化檢測問題，并提出一種求解GPCD問題的Tree算法。仿真實(shí)驗(yàn)結(jié)果表明，與GraphScope基準(zhǔn)算法相比，該算法檢測圖分割結(jié)構(gòu)變化時(shí)的虛警率較低，并具有較高的檢測精度。

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

中文引用格式：魏長寶，姚汝賢.基于最小描述長度的圖分割變化檢測改進(jìn)算法［J］.計(jì)算機(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 概述

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

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

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

2 圖形分割變化檢測

假設(shè)圖形序列為：

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

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

ts稱為變化點(diǎn)，Ψs稱為一個(gè)分段（s＝1，2，…）。將圖 G的分割看成圖 G分解為一組連接子圖｛G（u）｝的過程，其中G＝∪uG（u）?？傻肎PCD問題定義如下：已知一個(gè)圖形序列Ψ＝G1，G2，…，根據(jù)G1，G2，…的分割序列來檢測出Ψ中的變化點(diǎn)及其相應(yīng)變化。

3 基于樹的GPCD問題

3.1 基于樹分割的概率模型

本文利用二分樹來實(shí)現(xiàn)基于樹的分割表示。在二分樹中，每個(gè)樹節(jié)點(diǎn)關(guān)聯(lián)一組發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)。為了區(qū)分樹中節(jié)點(diǎn)和圖中節(jié)點(diǎn)，將前者稱為樹節(jié)點(diǎn)，將后者稱為節(jié)點(diǎn)。對每個(gè)樹節(jié)點(diǎn)，其子樹節(jié)點(diǎn)的分配有2種情況。情況1：2個(gè)子樹節(jié)點(diǎn)的發(fā)送節(jié)點(diǎn)集合相同，但是接收節(jié)點(diǎn)集合分離。情況2：2個(gè)子樹節(jié)點(diǎn)的接收節(jié)點(diǎn)集合相同，但是發(fā)送節(jié)點(diǎn)集合分離。

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

圖1 基于樹的分割過程

已知樹M，設(shè)u＝（urow，ucol）表示樹M中葉子u的行節(jié)點(diǎn)和列節(jié)點(diǎn)組成的元組。設(shè)G（u）表示u的相應(yīng)子圖。此時(shí)，可以獲得一種基于數(shù)的分割G＝∪uG（u）。

設(shè)Mt表示 Gt的對應(yīng)樹，二分樹序列可表示如下：

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

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

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

3.2 動態(tài)模型選擇

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

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

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

下面分析計(jì)算式（3）右側(cè)第1和第2項(xiàng)。Mt已知時(shí)Gt的碼長可計(jì)算為歸一化最大似然（NML）碼長，該碼長定義為歸一化最大似然的負(fù)對數(shù)，如下式所示：

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

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

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

3.4 樹轉(zhuǎn)換的編碼方法

下面給出式（3）中第 2項(xiàng)的計(jì)算方法。設(shè)α（＞0）表示一維參數(shù)。設(shè)No（Mt）表示Mt中葉節(jié)點(diǎn)的數(shù)量，N1（Mt）表示 Mt中內(nèi)部樹節(jié)點(diǎn)的數(shù)量，且：

用int（Mt）表示Mt的內(nèi)部樹節(jié)點(diǎn)集合，mu表示在樹節(jié)點(diǎn)u處可被分割的樹節(jié)點(diǎn)數(shù)量。轉(zhuǎn)換概率定義如下（對t≥1）：

該轉(zhuǎn)換定義表明，樹節(jié)點(diǎn)不發(fā)生變化的概率為1-α，發(fā)生變化的概率為α。在后一種情況下，根據(jù)概率選擇 Mt。因此，樹轉(zhuǎn)換的碼長為：

此時(shí)，每次轉(zhuǎn)換時(shí)樹編碼方法與 Rissanen方法［12］吻合，于是有：

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

3.5 基于樹的GPCD問題

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

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

算法1 節(jié)點(diǎn)分配

已知：圖形子序列Ψs，對葉節(jié)點(diǎn)u，有一組行節(jié)點(diǎn)：u1row，u2row

步驟1 設(shè)置R＝u1row∪u2row。

步驟2 設(shè)置x（∈R）為一個(gè)列節(jié)點(diǎn)，設(shè)置R←R-｛x｝

步驟3 計(jì)算：

步驟4 計(jì)算 KL（λx，λ1），KL（λx，λ2），其中，表示參數(shù)λ1和λ2時(shí)泊松分布間的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＝?，則終止，否則執(zhí)行步驟2。

（2）對樹序列進(jìn)行最優(yōu)分段：為了使總碼長最小，根據(jù)式（3）DMS準(zhǔn)則對樹序列進(jìn)行分段。按照如下方法確定一個(gè)變化點(diǎn)序列。對已知分段Ψ，Ψ的隨機(jī)復(fù)雜度（SC）定義為：

其中，Mt表示Gt的樹。設(shè)SCs表示最后一個(gè)分段Ψs的隨機(jī)復(fù)雜性，SCs+t表示Ψs∪Gt的隨機(jī)復(fù)雜性，SCt表示Gt的隨機(jī)復(fù)雜性，表示從一個(gè)段到另一個(gè)段的轉(zhuǎn)換概率估計(jì)。將式（3）DMS準(zhǔn)則應(yīng)用到樹序列的分割中。于是發(fā)現(xiàn)，如果：

則可將時(shí)間t看成是一個(gè)變化點(diǎn)，否則不將其看成變化點(diǎn)。此時(shí)：

鑒于兩者間的時(shí)間差異，通過式（3）DMS準(zhǔn)則和式（9）可推出式（12）。此外，Gt的變化點(diǎn)指數(shù)可定義為：

該指數(shù)可衡量在時(shí)間t進(jìn)行分割時(shí)碼長的下降情況。本文定義，只要下式成立則t即是一個(gè)變化點(diǎn)。

TREE的時(shí)間復(fù)雜度為O（mn（lb mn）T），其中，m表示列的數(shù)量；n表示行的數(shù)量；T表示數(shù)據(jù)規(guī)模。這是因?yàn)槊總€(gè)樹進(jìn)行分割和融合的計(jì)算復(fù)雜度為O（mn），樹的最大規(guī)模為O（lb mn），TREE算法運(yùn)行時(shí)與T呈線性關(guān)系。

算法2 樹分割

已知：u：雙支樹的一個(gè)葉節(jié)點(diǎn)

步驟1 對葉節(jié)點(diǎn)u，生成新的葉節(jié)點(diǎn)u1，u2，并設(shè)置u1row＝urow，u2row＝?。

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

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

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

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

步驟6 對u1，u2，運(yùn)行算法1。

步驟7 如果SC（u1）+SC（u2）-lb P0+?（u）＜SC（u）-lb P1，則分割列節(jié)點(diǎn)。

算法3 樹融合

已知：u：樹的根，q：隊(duì)列

步驟1 q＝｛u｝。

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

步驟3 設(shè)u1，u2是u′的子樹節(jié)點(diǎn)。

計(jì)算：

SC1＝SC（u′）-lbP1

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

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

步驟5 重復(fù)步驟2～步驟4直到q＝?。

4 基于直積的GPCD算法

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

圖3 基于直積的分割

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

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

5 仿真實(shí)驗(yàn)

5.1 基于人工數(shù)據(jù)集的實(shí)驗(yàn)

利用人工數(shù)據(jù)集來比較TREE和GraphScope算法。設(shè)置接收節(jié)點(diǎn)和發(fā)送節(jié)點(diǎn)數(shù)量均為20個(gè)，并準(zhǔn)備4個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集有30個(gè)數(shù)據(jù)。根據(jù)Θ1生成t＝1～10之間的數(shù)據(jù)，根據(jù)Θ2生成t＝11～20間的數(shù)據(jù)，根據(jù)Θ3生成t＝21～30間的數(shù)據(jù)。變化點(diǎn)為tc＝11和21。

生成數(shù)據(jù)集1，2，3，4，其分割結(jié)構(gòu)變化如圖4～圖7所示。

圖4 數(shù)據(jù)集1分割結(jié)構(gòu)變化

圖5 數(shù)據(jù)集2分割結(jié)構(gòu)變化

圖6 數(shù)據(jù)集3分割結(jié)構(gòu)變化

圖7 數(shù)據(jù)集4分割結(jié)構(gòu)變化

矩陣中的數(shù)據(jù)表明各分段的數(shù)量。使用效益和虛警率（FAR）2個(gè)指標(biāo)來衡量GPCD的性能。假設(shè)x表示被檢測出來的變化點(diǎn)，tc表示真實(shí)點(diǎn)，x的效益定義為：

其中，T表示已知正數(shù)。當(dāng)且僅當(dāng)x與tc吻合時(shí)值為1，當(dāng)增加時(shí)線性降為0。如果警報(bào)點(diǎn)大于T且離真實(shí)點(diǎn)很遠(yuǎn)，則認(rèn)為警報(bào)丟失。FAR表示所有警報(bào)中不是變化點(diǎn)的警報(bào)比例。進(jìn)行50次實(shí)驗(yàn)取均值。

表1給出了不同算法在4個(gè)數(shù)據(jù)集上的效益和虛警率比較結(jié)果。本文在計(jì)算效益時(shí)設(shè)置T＝3。

表1 數(shù)據(jù)集1～數(shù)據(jù)集4的效益和FAR

對數(shù)據(jù)集1，2種算法的效益值均較高，TREE的FAR值遠(yuǎn)低于GraphScope。這是因?yàn)橹狈e方法無法有效表示真實(shí)的分割，導(dǎo)致GraphScope的FAR高于TREE。對數(shù)據(jù)集2，由于與數(shù)據(jù)集1同樣的原因，GraphScope算法的FAR較高。然而，即使對數(shù)據(jù)集2，基于樹的方法無法有效表示真實(shí)分割，TREE的FAR仍然遠(yuǎn)低于 GraphScope。對數(shù)據(jù)集 3，GraphScope的FAR低于TREE。這是因?yàn)橹狈e方法非常有效地表示了真實(shí)分割，TREE方法需要更多的參數(shù)才能表示真實(shí)分割。在實(shí)踐中這種情況比較罕見。從以上結(jié)果可以看出，除了直積可以有效表示真實(shí)分割的少部分情況外，TREE的性能優(yōu)于GraphScope。

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

表2 不同算法的內(nèi)存占用量比較 MB

5.2 基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)

利用日本內(nèi)務(wù)交通省、統(tǒng)計(jì)局、政策規(guī)劃和統(tǒng)計(jì)研究及培訓(xùn)學(xué)院總干事提供的人口流動數(shù)據(jù)［14］進(jìn)行實(shí)驗(yàn)。這一數(shù)據(jù)對公眾開放，給出了2005年4月-2011年11月間日本所有縣市每月人口流動情況。發(fā)送節(jié)點(diǎn)是人口流出的縣市，接收節(jié)點(diǎn)是人口流入的縣市。從發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)之間鏈路的數(shù)值表示一個(gè)月內(nèi)從發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)間的流動人口數(shù)量。時(shí)間點(diǎn)總數(shù)為81，發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)總數(shù)均為47個(gè)。

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

圖8 TREE算法運(yùn)行結(jié)果

圖9 GraphScope算法運(yùn)行結(jié)果

6 結(jié)束語

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

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

［2］ 汪云飛，畢篤彥，孫 毅，等.一種采用雙勢阱策略的小直徑圖分割方法［J］.計(jì)算機(jī)應(yīng)用與軟件，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，F(xiàn)eige 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，F(xiàn)aloutsos 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，F(xiàn)lemming 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

河南省科技攻關(guān)計(jì)劃基金資助項(xiàng)目（122102210430）。

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

2014?12?24

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