華佳林，于 劍

1.北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044

2.交通數(shù)據(jù)分析與挖掘北京市重點實驗室，北京 100044

1 引言

聚類[1]是數(shù)據(jù)挖掘和機器學(xué)習(xí)中一個重要的問題，它根據(jù)某些標(biāo)準(zhǔn)將沒有標(biāo)定的數(shù)據(jù)分割到不同的類中。通常要進(jìn)行聚類的數(shù)據(jù)以兩種形式呈現(xiàn)[2]：特征向量或相似（相異）性矩陣。大多數(shù)的聚類算法采用特征向量作為輸入，這種類型的聚類算法已有大量的文獻(xiàn)進(jìn)行研究[3]。這些研究主要集中在特征提取[4-7]和聚類方法[8-13]上，它們通常需要事先知道某些重要的參數(shù)，比如聚類的個數(shù)。

關(guān)聯(lián)聚類[14]是另外一種形式的聚類問題，算法輸入是一個有符號圖，圖中節(jié)點表示數(shù)據(jù)，節(jié)點之間由有符號邊連接，即正邊和負(fù)邊。這種有符號圖能夠很好地表達(dá)現(xiàn)實世界中的很多場景，比如對象之間的相似/不相似、朋友/敵人、喜歡/不喜歡等。數(shù)據(jù)之間的邊可以加上一個權(quán)重來表示正或負(fù)關(guān)系的程度。關(guān)聯(lián)聚類的目的是使得在同一個類中的點盡可能由正邊連接，而不同類中的點盡可能由負(fù)邊連接。在關(guān)聯(lián)聚類中不事先設(shè)定聚類的個數(shù)，而是完全由數(shù)據(jù)的內(nèi)在結(jié)構(gòu)所決定。

本文的主要貢獻(xiàn)如下:

（1）提出了一種基于滴水原理的大規(guī)模有符號圖收縮的方法（correlation clustering based on drop of water principle，CCDWP），基于該方法所得到的新的有符號圖能極大地降低問題的規(guī)模。

（2）基于新的有符號圖提出了一個關(guān)聯(lián)聚類算法，算法基于圖的內(nèi)在結(jié)構(gòu)，使用整數(shù)線性規(guī)化來對局部的點進(jìn)行劃分。

（3）提出的算法既保證了結(jié)果的精確性，又能夠處理大規(guī)模有符號圖。

（4）應(yīng)用不同數(shù)據(jù)集的實驗結(jié)果表明了本文提出的關(guān)聯(lián)聚類算法的有效性。

2 相關(guān)工作

對于圖中點的劃分通常在社交媒體數(shù)據(jù)挖掘中被定義為社區(qū)發(fā)現(xiàn)而進(jìn)行研究。通常的社區(qū)發(fā)現(xiàn)任務(wù)要處理的圖并不考慮邊的符號，對于結(jié)果的要求是社區(qū)（聚類）內(nèi)部邊的密度較大，社區(qū)之間邊的密度較小。

關(guān)聯(lián)聚類的任務(wù)包括兩種情況：第一種追求最大一致性，所謂的一致性指類內(nèi)正邊和類間負(fù)邊；第二種追求最小不一致性，所謂的不一致性指類內(nèi)負(fù)邊和類間正邊。無論哪種情況都被證明是NP-hard問題[14]。通常的方法基于求解最小不一致性。

對于關(guān)聯(lián)聚類的求解，一個自然的方法是將其表示成整數(shù)線性規(guī)化（integer linear programming，ILP）問題：

其中，w+ij和w-ij分別表示邊(i,j)的正權(quán)重或負(fù)權(quán)重；xij=0表示將點i和j指派到同一個類中，xij=1表示將點i和j指派到不同的類中。約束條件xij+xjk≥xik是為了防止結(jié)果中出現(xiàn)不一致的情況，比如xij=xjk=0,xik=1。但是ILP通常只能處理一兩百個點的網(wǎng)絡(luò)，面對更大的網(wǎng)絡(luò)時，時間的消耗讓人難以接受。很多研究將ILP中的變量xij∈{0,1}松弛到[0,1]中，從而轉(zhuǎn)化成線性規(guī)化（linear programming，LP）問題。對于新的變量的不同處理方式產(chǎn)生了不同的關(guān)聯(lián)聚類算法[15-18]。文獻(xiàn)[17-18]將xij看成是點之間的距離。文獻(xiàn)[17]將距離小于閾值的兩個點指派到同一個類中；而文獻(xiàn)[18]每次從任意一個點出發(fā)構(gòu)造了一個球，凡是被球所包圍的點都與球心在同一個類中（稱為Ball-algorithm）。而文獻(xiàn)[16]將關(guān)聯(lián)聚類問題和聚類集成問題看成是同一個問題來進(jìn)行研究，同時基于文獻(xiàn)[17]繼續(xù)研究如何取得更好的閾值。而文獻(xiàn)[15]則將1-xij看成點i和j在同一個類中的概率，當(dāng)這個概率大于0.5時將對應(yīng)的兩個點指派到同一個類中（稱為Pivot-algorithm）。Ball-algorithm和Pivot-algorithm是經(jīng)典的關(guān)聯(lián)聚類算法。文獻(xiàn)[21]首先使用Fusion-Move的方法收縮有符號圖，在降低數(shù)據(jù)的規(guī)模后再使用傳統(tǒng)的關(guān)聯(lián)聚類算法（文中使用Pivot-algorithm）處理新的規(guī)模更小的圖。文獻(xiàn)[22]證明了關(guān)聯(lián)聚類問題如果按照最小不一致性來求解時與Multicut問題等價。

由于表達(dá)式（1）中的變量xij不是直接的類標(biāo)，有些約束并沒有考慮在其中，比如xii=0,導(dǎo)致基于LP的關(guān)聯(lián)聚類算法得到的結(jié)果往往精度不高。因此在文獻(xiàn)[17,19-20]中半正定優(yōu)化（semi-definite positive，SDP）被引入來求解關(guān)聯(lián)聚類問題。變量xij被重新定義為對應(yīng)兩個點的類標(biāo)向量的內(nèi)積。所謂的類標(biāo)向量，比如第i個點的類標(biāo)向量表示點i被指派到第k個類中，而xij=ind(i)?ind(j)。顯然矩陣X=(xij)是半正定的。文獻(xiàn)[19-20]構(gòu)建下列半正定模型：

分水嶺（watersheds）算法最早被用來進(jìn)行梯度圖像的分割。對于一個梯度圖像根據(jù)滴水原理（drop of water principle）可以構(gòu)造出圖像的分水嶺，一個積水盆地（catchment basin）即是圖像的一個分割。

本文提出的關(guān)聯(lián)聚類算法借用分水嶺算法的思路，首先對符號圖中的點按照正度從高到低進(jìn)行排序，每次對度最高的點按照正權(quán)重降低最慢尋找路徑，將每個路徑中的點合并成一個新的點，從而收縮圖的規(guī)模。在收縮的圖上選出重要的點，利用ILP來判斷這些點和周圍點之間的合并或分割關(guān)系，從而最終得到聚類結(jié)果。

3 基于滴水原理的符號圖收縮

下面主要介紹如何借鑒滴水原理的思路來收縮大規(guī)模有符號圖。

3.1 滴水原理基本定義

滴水原理在機器學(xué)習(xí)中常被用來進(jìn)行圖像分割處理。所謂的滴水原理是指當(dāng)水從高處往下滴落時會沿著滴落速度最快的路徑下落。在基于分水嶺的圖像分割中，滴落路徑構(gòu)成分水嶺，從而對圖像進(jìn)行分割。

3.2 基于滴水原理的有符號圖收縮

在關(guān)聯(lián)聚類中，圖中的點從聚類的意義上看重要性并不一致，其中的正度比較大的點更容易形成聚類，這些點從某種意義上可以看成聚類的原型（prototypes），因此本文從重要的點（即正度比較大的點，記為i）開始，首先將與i有正邊連接的點（記為j）看作候選點，如果邊(i,j)的權(quán)重是點j所有的邊中權(quán)重最大的，則將i與j合并，找出所有這樣的j（記為j1,j2,…,jk），這些點都與i合并成一個新的點（新點還是記為i）。記I={i,j1,j2,…,jk}，任何兩個端點都在I中的邊直接刪除，而一個點在I中另一個不在其中的邊都合并成與i相連的邊，邊的權(quán)重是原來邊的權(quán)重相加。作者先前研究過按這種方式減小有符號圖的規(guī)模的關(guān)聯(lián)聚類算法并取得了不錯的效果，現(xiàn)在將進(jìn)一步減小圖的規(guī)模。

基于滴水原理的有符號圖收縮來自這樣的一個直覺：從度較大的點出發(fā)，尋找一個正權(quán)重變化最小的路徑，則路徑上的點以極大的可能性屬于同一個類。因此繼續(xù)從j出發(fā)，尋找與j有正邊連接的點（記為l），如果l與j之間的邊的權(quán)重是l的所有正邊中權(quán)重最大的，則將l也加入集合I；接下來繼續(xù)從l出發(fā)按照上面的邏輯繼續(xù)往下尋找合適的點并入I，直到不能繼續(xù)往下搜索則終止。本文以一個隨機產(chǎn)生的有符號圖來說明。如圖1所示，圖1（a）是原始的有符號圖，圖中實線表示正邊，虛線表示負(fù)邊，邊上的數(shù)字表示權(quán)重，邊的粗細(xì)與權(quán)重匹配。進(jìn)行簡單的統(tǒng)計就可以知道圖中的點4、15和24是比較重要的點，這幾個點以極大的概率稱為類原型。首先從4開始遍歷，可以看到點3、5、8、9和12與4之間的邊是其最大權(quán)重正邊，因此I={3,4,5,8,9,12}。繼續(xù)從I中的點出發(fā)，比如從3開始，發(fā)現(xiàn)2與3之間的邊是2的所有正邊中權(quán)重最大的邊，因此將2并入集合I，對I中其他點進(jìn)行類似的處理，最終可以得到I={1,2,3,4,5,6,7,8,9,10,11,12,13}。接下來分別從15和24出發(fā)進(jìn)行類似的操作，最終形成圖1（b）中所示的3個分割，每個分割是新的有符號圖中的一個點，這3個點之間是合并還是分割可以轉(zhuǎn)化成式（1）所示的ILP問題而獲得最佳解，從而形成最終的聚類結(jié)果。上面從點i出發(fā)構(gòu)造集合I的過程實際上就是從點i出發(fā)沿正邊尋找權(quán)重變化最小的路徑，然后將這條路徑上的所有點合并成一個點，這個過程類似于滴水時的情形。

4 基于滴水原理的關(guān)聯(lián)聚類算法

下面給出詳細(xì)的算法過程。

算法1基于滴水原理的關(guān)聯(lián)聚類算法（CCDWP）

輸入：有符號圖G=(V,E,W)，其中V是頂點集合，E是邊集合，W是邊的權(quán)重集合。

輸出：聚類結(jié)果。

（1）對圖中點按照正邊度進(jìn)行排序，對于正度最高的點i1，將所有與i1有正邊連接且該正邊是其所有邊中權(quán)重最大的點與i1合并，產(chǎn)生集合I1。

（2）對集合I1中除i1之外的點沿正邊尋找權(quán)重變化最小的路徑，將這些路徑中的點合并變成圖中一個新的點，將原來的邊進(jìn)行合并產(chǎn)生新的邊，兩個端點都在I1中的邊直接刪除。

（3）將所有I1中的點、所有內(nèi)部的邊及所有一個端點在I1中的邊及其對應(yīng)的另一個端點從原來的圖中刪除，對剩下的圖繼續(xù)執(zhí)行（1）和（2），直到不能找到新的點。

（4）記Θ={I1,I2,…,IN}為按照（1）~（3）所找到的N個集合，則可以得到一個收縮的有符號圖G′=(V′,E′,W′)，其中

（5）每次從Θ中的一個集合出發(fā)，比如Ij，尋找所有Ij的鄰居，然后按照式（1）來計算它們之間合并與否，對于不能合并的點將其作為一個新的類原型加入Θ中。繼續(xù)這個過程直到所有的點都已處理完畢，這樣得到的Θ即為最終的聚類結(jié)果。

在算法CCDWP中有幾個地方需要聲明：第一是在第（4）步中得到了N個集合，每個集合都看作是一個類原型，但是要注意的是N并不是人們認(rèn)為的類個數(shù)，因為可能存在多原型的情形。另外在第（5）步中要使用到ILP，其效率比較低，通常只能處理規(guī)模為幾百個點的圖。因此如果Ij的鄰居比較多，可能會產(chǎn)生超出ILP處理能力的情況。在實驗中發(fā)現(xiàn)，大多數(shù)情形下鄰居個數(shù)不會超出ILP的處理范圍，而如果超出了ILP的處理范圍的話也很容易處理，只需要設(shè)置一個閾值T（比如取T=200），當(dāng)鄰居數(shù)超過T的時候，將這些鄰居與Ij之間的邊的權(quán)重從大到小進(jìn)行排序，ILP只處理前T個鄰居，至于其他點則在以后的優(yōu)化中再進(jìn)行處理。這樣做對于最終的聚類結(jié)果并不會產(chǎn)生影響，而僅僅是稍微降低了算法的速度。

Fig.1 Original signed graph and three clusters圖1 原始的符號圖和形成的3個類

接下來以一個實例來詳細(xì)說明算法的過程。在圖2（a）所示的圖中根據(jù)點的正度從高到底排序可以得到3個重要的點4、15和24。因此分布從這3個點出發(fā)按照滴水原理尋找正權(quán)重變化最小的路徑。分別可以找到如下所示的路徑：即圖2（b）中陰影所示的部分。在這個過程中要注意選中的點所對應(yīng)的邊一定是權(quán)重最大的邊，比如在路徑4→3→2中，路徑在點2即停止而沒有再走下去，因為邊（1,2）對應(yīng)的邊不是點1所有的邊中權(quán)重最大的邊，所以即使最后的結(jié)果是1和2同屬一個類，但是為保證算法精度而不會將1納入。這樣就得到3個小的團體，將其作為3個類原型，將這些團體中的點合并成一個點，點的標(biāo)示分別是4、15、24，將每個團體內(nèi)部的邊直接取消，外部的邊進(jìn)行合并，從而得到一個收縮的新的有符號圖，如圖2（c）所示?？梢钥吹叫碌膱D較原來的圖的規(guī)模大為縮小。接下來基于新的圖繼續(xù)進(jìn)行處理。對于剩下的點，比如點1，發(fā)現(xiàn)其與33、4和15有連接，這些點之間的合并或分割的關(guān)系可以表示成式（1）的ILP問題，由于問題規(guī)模很小，可以快速進(jìn)行求解。最終得到如圖2（d）所示的聚類結(jié)果。

Fig.2 Procedure of CCDWP圖2CCDWP算法過程

5 實驗與結(jié)果

本文在人工數(shù)據(jù)和真實數(shù)據(jù)上測試算法CCDWP的有效性，并將CCDWP與Ball-algorithm[18]、Pivotalgorithm[15]、FusionCC[21]算法進(jìn)行對比測試。

5.1 人工數(shù)據(jù)實驗

首先設(shè)計了一個生成人工有符號圖數(shù)據(jù)的算法，如算法2所示。

算法2產(chǎn)生有符號圖

輸入：點個數(shù)ND，類個數(shù)k，類內(nèi)正邊概率p，類內(nèi)負(fù)邊概率w，類間正邊概率e，類間負(fù)邊概率q。

輸出：有符號圖。

隨機產(chǎn)生ND個點，并隨機分配到k個類中。

在實驗中讓產(chǎn)生的邊的權(quán)重分布在-5到5之間，然后在同種參數(shù)下產(chǎn)生10個隨機數(shù)據(jù)運行4個算法，記錄每次每個算法所產(chǎn)生的不一致性的數(shù)量。實驗結(jié)果如圖3所示。圖中縱坐標(biāo)表示算法結(jié)果的不一致性數(shù)量D，值越小表示算法越優(yōu)。橫坐標(biāo)中的10個點表示10個隨機產(chǎn)生的人工有符號圖。圖3（a）、（b）、（c）和（d）分別是在60個點、100個點、150個點和200個點的設(shè)置下產(chǎn)生的隨機圖。Ball-algorithm和Pivot-algorithm這兩個傳統(tǒng)的關(guān)聯(lián)聚類算法，在人工數(shù)據(jù)上的實驗結(jié)果與先前的研究結(jié)果一致：Ballalgorithm的結(jié)果要劣于Pivot-algorithm。FusionCC算法也是一種基于收縮的算法，毋庸置疑的是它的效果確實較以前的算法有很大的提高，但對于收縮之后所產(chǎn)生的新圖其仍然是使用傳統(tǒng)的關(guān)聯(lián)聚類算法，比如Pivot-algorithm，也就是基于將ILP松弛為LP的優(yōu)化方法。而CCDWP算法則謹(jǐn)慎地將圖更大規(guī)模地進(jìn)行收縮，對于收縮之后的圖采取局部ILP優(yōu)化的方法求解結(jié)果，算法沒有采用降低算法精度的松弛方法，因此算法的效果要更優(yōu)越，實驗結(jié)果完全證明了這一點。在圖3（a）中，圖的規(guī)模較小，因此FusionCC和CCDWP算法對于圖的收縮空間較小，同時ILP和LP的效果也相差不大?？梢钥吹剑?0個隨機圖中有4個FusionCC的不一致性數(shù)量小于CCDWP，有4個CCDWP的不一致性數(shù)量小于FusionCC，另外兩個則幾乎一致。但是隨著圖的規(guī)模的增大，CCDWP算法中圖收縮方法的優(yōu)越性則越來越明顯，同時局部的ILP比LP也更精確，因此在圖3（b）、（c）和（d）中CCDWP算法都求得了最小的不一致性數(shù)量。

Fig.3 Experiments on synthetic data圖3 人工數(shù)據(jù)實驗結(jié)果

5.2 真實數(shù)據(jù)實驗

本文在真實數(shù)據(jù)上繼續(xù)驗證CCDWP算法的效果。首先在兩個小的有符號網(wǎng)絡(luò)上驗證CCDWP算法，這兩個網(wǎng)絡(luò)分別是Gahuku-Gama Subtribes（GGS）網(wǎng)絡(luò)[23]和 Slovene Parliamentary Party（SPP）網(wǎng)絡(luò)[24]。GGS網(wǎng)絡(luò)表示的是16個部落之間的友好（正邊）或敵對（負(fù)邊）的關(guān)系。SPP網(wǎng)絡(luò)表示的是斯洛文尼亞國會政黨之間政治理念相似（正邊）或不相似（負(fù)邊）。CCDWP算法在這兩個數(shù)據(jù)集上得到的結(jié)果如圖4和圖5所示，以不同的顏色表示不同的聚類。顯而易見本文算法在GGS和SPP兩個數(shù)據(jù)集上都給出了擁有最小不一致性的結(jié)果。

Fig.4 Clustering result of GGS圖4GGS的聚類

Fig.5 Clustering result of SPP圖5 SPP的聚類結(jié)果

接下來繼續(xù)在更大規(guī)模的真實數(shù)據(jù)上驗證CCDWP算法。這些數(shù)據(jù)包括Epidermal Growth Factor Receptor pathway network（EGFR）[25]、Macrophage network（Macrophage）[26]、Yeast network（Yeast）[27]、Gene regulatory network of the Escherichia Coli（Ecoli）[28]、voting network of Wikipedia[32]，統(tǒng)計信息如表1所示，其中“#A”表示A的數(shù)量，比如#Vertice表示點的數(shù)量，E+和E-表示正邊和負(fù)邊。原始的Wikipedia數(shù)據(jù)是有向圖，將其轉(zhuǎn)化成無向圖并按照下面的公式計算邊的權(quán)重：

即如果原來i和j相互信任，則對應(yīng)的邊的權(quán)重為2，如果原來相互不信任，則對應(yīng)的邊的權(quán)重為-2，如果原來一個信任對方但對方不信任他，則權(quán)重為0，即沒有邊。

Table 1 Information of 5 real data sets表1 5個真實數(shù)據(jù)集信息

由于Ball-algorithm和Pivot-algorithm無法運行較大規(guī)模的數(shù)據(jù)，本文只對比測試了FusionCC算法和CCDWP算法，比較這兩個算法給出的結(jié)果的不一致性數(shù)量，如表2所示，其中“X”表示沒有結(jié)果。從真實數(shù)據(jù)的結(jié)果上看，兩個算法的效果與前面人工數(shù)據(jù)上的效果類似，即當(dāng)數(shù)據(jù)的規(guī)模不大，邊非常稀疏時，CCDWP算法與FusionCC算法各有所長，算法的效果在一定程度上與數(shù)據(jù)的結(jié)果有關(guān)系。在5個數(shù)據(jù)集中，本文算法在EGFR和Ecoli上取得了更好的效果，在Macrophage和Yeast上兩個算法取得的結(jié)果差別很小。而CCDWP算法最大的一個優(yōu)勢在于能夠處理大規(guī)模的數(shù)據(jù)集。在運行Wikipedia數(shù)據(jù)集時，由于圖的規(guī)模太大，即使在收縮之后的圖上面FusionCC算法仍然難以運行。CCDWP算法則不存在這樣的問題，仍然能夠執(zhí)行算法過程。

Table 2 Results of FusionCC and CCDWPin 5 real data sets表2FusionCC和CCDWP算法在5個真實數(shù)據(jù)集上的結(jié)果

6 總結(jié)

本文提出了一種基于滴水原理的關(guān)聯(lián)聚類算法CCDWP。CCDWP算法根據(jù)滴水原理來搜索有符號圖，將其中最有可能的路徑上的點進(jìn)行收縮，從而大大減小了數(shù)據(jù)規(guī)模并得到類原型。同時，本文通過巧妙地在局部執(zhí)行ILP，將可能的點逐步合并到類原型中得到聚類結(jié)果。實驗結(jié)果表明，本文提出的關(guān)聯(lián)聚類算法在準(zhǔn)確度和效率方面優(yōu)于許多已有的關(guān)聯(lián)聚類算法，因此本文算法是可行且高效的。

:

[1]Alpaydin E.Introduction to machine learning[M].Cambridge:MIT Press,2014.

[2]Yu Jian.Generalized categorization axioms[J].CoRR abs/1503.09082,2015.

[3]Xu Rui,Wunsch D C.Survey of clustering algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678.

[4]Wold S,Esbensen K,Geladi P.Principal component analysis[J].Chemometrics&Intelligent Laboratory Systems,1987,2(1/3):37-52.

[5]Jain A K,Duin R P W,Mao Jianchang.Statistical pattern recognition:a review[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(1):4-37.

[6]Hyv?rinen A.Survey on independent component analysis[J].Neural Computing Surveys,1999,2(7):1527-1558.

[7]Young F W,Hamer R M.Multidimensional scaling:history,theory,and applications[M].Hillsdale:Lawrence Erlbaum Associates,1987.

[8]Jain A K,Dubes R C.Algorithms for clustering data[M].Upper Saddle River:Prentice-Hall,1988.

[9]Jain A K,Murty M N,Flynn P J.Data clustering:a review[J].ACM Computing Surveys,1999,31(3):264-323.

[10]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[11]Jain A K.Data clustering:50 years beyondK-means[J].Pattern Recognition Letters,2010,31(8):651-666.

[12]Luxburg V.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.

[13]Parsons L,Haque E,Liu Huan.Subspace clustering for high dimensional data:a review[J].ACM SIGKDD Explorations Newsletter,2004,6(1):90-105.

[14]Bansal N,Blum A,Chawla S.Correlation clustering[J].Machine Learning,2004,56(1/3):89-113.

[15]Ailon N,Charikar M,Newman A.Aggregating inconsistent information:ranking and clustering[J].Journal of the ACM,2008,55(5):23.

[16]Gionis A,Mannila H,Tsaparas P.Clustering aggregation[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):4.

[17]Charikar M,Guruswami V,WirthA.Clustering with qualitative information[C]//Proceedings of the 44th Symposium on Foundations of Computer Science,Cambridge,Oct 11-14,2003.Washington:IEEE Computer Society,2003:524-533.

[18]Demaine E E,Immorlica N.Correlation clustering with partial information[C]//LNCS 2764:Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problem and 7th International Workshop on Randomization and Approximation Techniques in Computer Science,Princeton,Aug 24-26,2003:1-13.

[19]Elsner M,Schudy W.Bounding and comparing methods for correlation clustering beyond ILP[C]//Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing,Boulder,2009.Stroudsburg:ACL,2009:19-27.

[20]Mathieu C,Schudy W.Correlation clustering with noisy input[C]//Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms,Austin,Jan 17-19,2010.Philadelphia:SIAM,2010:712-728.

[21]Beier T,Hamprecht F A,Kappes J H.Fusion moves for correlation clustering[C]//Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition,Bos-ton,Jun 7-12,2015.Washington:IEEE Computer Society,2015:3507-3516.

[22]Emanuel D,Fiat A.Correlation clustering—minimizing disagreements on arbitrary weighted graphs[C]//LNCS 2832:Proceedings of the 11th Annual European Symposium on Algorithms,Budapest,Sep 16-19,2003.Berlin,Heidelberg:Springer,2003:208-220.

[23]Read K E.Cultures of the central highlands,new guinea[J].Southwestern Journal ofAnthropology,1954,10(1):1-43.

[24]Doreian P,Mrvar A.A partitioning approach to structural balance[J].Social Networks,1996,18(2):149-168.

[25]Oda K,Matsuoka Y,Funahashi A,et al.A comprehensive pathway map of epidermal growth factor receptor signaling[J].Molecular Systems Biology,2005.

[26]Oda K,Kimura T,Matsuoka Y,et al.Molecular interaction map of a macrophage[J].AfCS Research Reports,2004,2(14):1-12.

[27]Milo R,Shen-Orr S,Itzkovitz S,et al.Network motifs:simple building blocks of complex networks[J].Science,2002,298:824-827.

[28]Salgado H,Gama-Castro S,Peralta-Gil M,et al.RegulonDB(version 5.0):Escherichia coli K-12 transcriptional regulatory network,operon organization,and growth conditions[J].NucleicAcids Research,2006,34(D):394-397.