具有對偶約束的半監督重疊社區發現方法

許小媛，李海波，于本成，劉 芳

(1.江蘇開放大學信息工程學院，江蘇 南京 210017； 2.中國礦業大學計算機科學與技術學院，江蘇 徐州 221116)

0 引 言

在機器學習領域，許多應用不能完全精準地區分有監督學習和無監督學習[1]，所提供的背景知識亦十分有限。監督通常采用成對約束的形式，這種約束描述了數據對象之間的關系，已被用于指導和提高聚類算法的有效性,半監督學習的概念擴展到了網絡分析領域。社區發現等任務可能受益于引入來自單個領域專家或群智的有限監督，這類知識通常被編碼為約束，表明一對節點應始終分配給同一社區或始終不分配給同一個社區。通過這些知識，可以潛在地發現在分析大型或嘈雜網絡時難以識別的節點社區。

最初社區發現的研究工作集中在開發產生不相交群的算法，其中的每一個節點屬于一個社區[2]。然而，在許多實際網絡中，節點將自然地屬于多個社區。無論是在線社交網絡還是離線社交網絡，都可以觀察到無處不在的重疊，其中個人屬于高度重疊的社交群體[3]。最近，已有重疊社區的發現算法應用于這些真實網絡[2，4]。與此相反，在半監督的重疊社區發現方面，繼續側重于那些相互獨立的情況。

本文提出一種基于貪心策略的局部擴展[5]半監督社區查找方法，并將其稱為基于對偶約束的局部擴展(半監督重疊社區發現)算法PC-GCE(Pairwise Constrained Greedy Clique Expansion)。在進程的初始化階段和子社區擴展過程中引入必須鏈接和不可能鏈接的約束。對基準合成網絡的實驗評估表明，引入相對較小的約束數可以提高正確發現這些網絡中潛在社區的能力。

1 相關工作

1.1 社區發現

發現非重疊社區。在此背景下，算法可以大致分為3種類型。1)層次算法?；诰W絡拓撲結構構建社區樹。這些算法可以是2種類型之一：分裂算法[6]或凝聚算法[7]。2)基于模塊化的算法。對已知的模塊化目標函數進行優化，并發現網絡[8]中的社區。3)其他算法。這類算法包括基于標簽傳播方法的算法，利用拉普拉斯矩陣或標準矩陣特征向量的譜算法，以及基于統計模型[9]的方法。

發現重疊社區。在此背景下，現有的算法可以分為4大類。1)節點種子和局部擴展算法。這種算法從一個節點或一組節點開始檢測社區，然后使用質量函數將它們擴展到一個社區。OSLOM[10]就是這種算法的一個例子，它使用一個統計函數來計算節點值，并將其擴展到一個社區。另一個例子是MOSES[11]，它是一個基于統計模型的算法，使用目標函數作為貪心策略的優化技術。2)集群擴張算法。這種方法使用一組稱為clique(集群)的全鏈接節點作為展開的起點。CFinder[1]和貪心集群擴張算法(GCE)[12]就是這種算法的例子。3)鏈接聚類。這類算法通過分割鏈接而不是節點[13-16]來檢測一致性。4)標簽傳播。該策略根據相鄰節點的相似性將每個節點劃分為一個社區。COPRA算法[11]就是一個例子。

1.2 半監督學習

通過已有的幾種形式的先驗知識來指導社區的決策過程。最廣泛使用的是成對約束(必須鏈接或不能鏈接)，其含義表示2個節點必須在同一個社區中，或者必須在不同的社區中。這種約束已經在幾種算法中實現，包括基于模塊的方法[17]、光譜分析方法[5,12]和基于矩陣分解的方法[18-19]。其他算法利用節點標簽作為先驗知識，代替約束，改進了社區檢測[20]的過程。在文獻[21-22]中，作者提出了一種根據節點標簽和負信息的半監督標簽傳播算法。

在這一領域，絕大多數半監督算法的目標是檢測不相交的社區，而許多現實世界的網絡是包含重疊社區的。據筆者所知，在尋找重疊社區方面人們所做的工作很少。在文獻[8]中，使用了一小組稱為種子的節點，將這些節點與社區的親緣關系作為先驗知識來推斷網絡中其他節點的親緣關系。以下，本文重點討論半監督社區尋找適合于包含重疊社區網絡的應用程序的問題。

2 算法使用

2.1 貪心集群擴張算法(GCE)

GCE[16]社區搜索算法首先將最大的群體作為種子，然后通過優化局部適應度函數，貪心地將這些種子擴展為更大的群體。給定網絡G，用戶指定的最小小圈子大小為k，最小社區距離為ε，GCE算法包括以下步驟：

1)找到種子，這些種子都是G中具有至少k個節點的最大團體。

2)選擇最大的未擴展種子，并通過使用社區適應度函數FS貪婪地將其擴展到候選社區C′，直到添加任何節點不會增加適應度值。

3)測試C′與所有先前接受的社區之間的距離。如果C′與現有社區C之間的距離小于給定的閾值ε，則認為C和C′無限接近，因此舍棄C′，否則，保留C′。

4)重復步驟2和步驟3，直到不再有種子。

GCE定義了適應度函數[14]來擴展每個種子，函數描述了給定社區S中節點k的入度和出度，公式如下：

(1)

其中，參數α通常采用[0.9,1.5]范圍內的值?？梢允褂眠m應度函數FS總結貪心策略的擴展步驟如下：

1)對于給定種子S邊界中的每個節點v，計算v的適應度值。例如，如果將節點v添加到S，則S的社區適應度將改變。

2)選擇具有最大適應度值的節點vmax。

3)如果適應度值vmax為正，則將節點v插入S并返回步驟1，否則，終止并返回S。

為了在GCE算法的步驟4中丟棄近似重復的社區，本文提出使用基于重疊的2個社區之間的距離度量：

(2)

鑒于2個社區S和S′中，公式(2)的測量包括較小社區中的節點，忽略了較大社區的節點。對于給定的一組社區集合，離給定社區S的距離小于給定的閾值的所有社區都被判定為S的重疊社區。

2.2 社區檢測中的成對約束

給定包含一組節點v的網絡，半監督的成對約束通常采用2種可能的形式：

1)必然連接(must-link)約束指定2個節點屬于同一簇類。令CML為must-link約束集，對于?vi,vj∈v，當i≠j，(vi,vj)∈CML表示必須將2個節點vi和vj分配給同一社區。

2)不可能連接(cannot-link)約束指定2個節點必須屬于不同簇類。令CCL為cannot-link約束集，對于?vi,vj∈v，當i≠j，(vi,vj)∈CCL表示必須將2個節點vi和vj分配給不同社區。

3)選擇這種約束形式最簡單的方法是隨機選擇一對節點(vi,vj)，并查詢權威數據判斷應該采用must-link還是cannot-link約束。重復該過程以選擇所需數量的約束或直到部分監督預算用完。在非重疊的社區查找中，must-link約束具有傳遞屬性，其中第3個must-link關系可以從其他2個關聯的must-link約束對推斷出來。所以，如果(vi,vj)∈CML，且有(vj,vk)∈CML，那么也可以推斷出(vi,vk)∈CML。如圖1所示，在非重疊的情況下，傳遞屬性允許從2個現有的must-link約束推斷出第3個must-link約束。

圖1 非重疊社區

但是，這并不會自動適用于重疊的情況，其中存在2種可能的情況。由于傳遞屬性不再成立，將約束納入重疊社區則更具挑戰性。

圖2 重疊社區

如圖2所示，具體來說，如果(vi,vj)∈CML，且(vj,vk)∈CML那么(vi,vk)有2種可能的情況，要么(vi,vk)∈CML，要么(vi,vk)∈CCL。這是因為重疊節點vj具備節點vi和vk的must-link約束，但這2個節點分屬于2個不同的社區。但也有可能，這3個節點實際上是位于同一社區中。除非在算法中明確(vi,vk)是must-link約束還是cannot-link約束，否則無法有效區分這2種情況。網絡若具有高度重疊的社區，那么這種有問題的情況將更頻繁地發生。如果單純地試圖將成對約束結合起來，而不考慮這種情況，那么在社區發現的過程中，即使增加約束，社區發現的結果并不令人滿意。

要解決此問題，在選擇成對約束之后，需要檢測從任意2個must-link鏈接對中派生出的cannot-link對，并將其插入到cannot-link集中。但是，這將顯著增加無鏈接約束的集合。例如，如果只想提供5個成對約束，每個約束如圖3所示，插入所需的cannot-link對將使cannot-link集的大小加倍。在下一節中，將介紹解決此問題的方法。

圖3 擴展5個約束對的情況

2.3 半監督的GCE

本文提出的方法是有限的監督下的重疊社區發現，稱為成對約束GCE或對偶約束GCE (PC-GCE)方法。該方法由2個階段組成：第1個階段包括選擇和預處理約束，解決了重疊社區中must-link約束缺乏傳遞性的問題；第2個階段為GCE算法提供約束，以便在社區檢測過程中處理這些約束。具體描述如下：

階段1：選擇和預處理約束。在這個階段，可以將成對約束集視為一個新集，如果它們共享成對約束(must-link或cannot-link)，則在原始網絡的2個節點之間存在鄰接點。然后在must-link集涉及的節點中尋找所有可能的禁用三元組。給定3個節點A、B、C，當A連接到B和C時發生禁用三元組(或開放三元組)，但B和C之間不存在鄰接點。在預處理步驟中，尋找這樣的情況，比如判斷B和C之間是否存在must-link或cannot-link。為了控制約束集的大小，該方法“貪心”地對它進行擴展，直到達到預定義的最大尺寸。這個階段實現步驟如下(見圖4)：

1)選擇must-link和cannot-link的初始隨機集。

2)在must-link集中查找所有可能的禁止三元組，以便在數據庫中查詢它們之間的關系。

3)如果它們的關系是must-link，則將其插入到must-link集中，否則將其插入到cannot-link集中。

4)重復以上步驟，直到設置達到最大尺寸。

在該階段結束時，成對約束集即完成以用于GCE算法進行社區檢測。

階段2：成對約束的GCE(PC-GCE)。在社區檢測階段，只將cannot-link約束結合到現有的GCE算法中，實現步驟如下(見圖5)：

1)找到種子，這些種子都是網絡G中具有至少k個節點的最大團體。

2)選擇最大的未擴展種子，并通過使用社區適應度函數(公式(1))貪婪地將其擴展到候選社區C′，直到添加任何節點都不再增加適應度值。但是，在擴展過程中，不要添加任何節點，該節點與種子中的任何現有節點都是cannot-link。

3)檢查C′中所有節點對之間是否存在任何cannot-link約束。如果存在這樣的對，則計算2個節點相對于C′的適應度，并移除值較低的節點。

4)使用公式(2)測試社區C′與所有已接受社區之間的距離。如果C′與任何已接受社區C之間的距離<ε，則C′和C接近重疊，丟棄C′，否則，接受C′。

5)返回步驟2并重復該過程，直到沒有種子冗余。

在社區發現的過程中只采用cannot-link約束的原因是：由于種子擴展步驟的貪婪性質，將must-link約束納入此步驟會導致相當大社區數量變少。主要使用適應度函數作為將群集擴展到社區的局部優化技術已經實現了一些must-link關系，并且處理cannot-link集將主要檢測從2個鏈接的must-link對中派生的對。因此，使用算法處理的must-link集將是額外的對非信息性約束的處理，這會對算法產生噪聲并降低精度。

圖4 半監督GCE階段1涉及的4個步驟

圖5 半監督GCE階段2涉及的4個步驟

3 實驗結果及分析

本文通過在包含重疊社區的2組人工合成網絡上進行實驗來評估PC-GCE的性能。為了進行對比，將PC-GCE的結果與以下無監督重疊社區檢測算法進行比較：標準GCE[16]、OSLOM[13]、MOSES[5]和COPRA[11]。

3.1 實驗數據

實驗中使用的合成網絡是用廣泛使用的LFR基準網絡生成器[15]生成的，它可以生成具有類似真實網絡屬性的人工合成網絡，它也包含嵌入式地面真實社區。表1中列出了用于生成網絡的所有參數值。

表1 用于生成LFR合成網絡參數值

在實驗中，生成2組不同的網絡，分別包含小型社區和大型社區。小型社區有10～50個節點，而大社區有20～100個節點。每組由16個具有2個參數Om和On的不同組合的網絡組成，參數Om控制每個節點的社區數量，On控制重疊節點的數量。對于每組中的第一個網絡，所有節點屬于2個社區(Om=2)，然后對于每個連續網絡，該參數的值遞增1，直到Om=5。對于每個參數值Om，將重疊節點參數On增加25%，直到100%的節點屬于多個社區。

3.2 實驗步驟

為了比較不同算法在實驗中的性能，本文使用了標準歸一化互信息(NMI)測量重疊[14]。該算法度量在網絡中使用算法產生的社區與地面真實社區之間的一致性。若A值接近1表示高度一致，接近0表示算法社區并不比隨機產生的社區好。

進行了2個實驗。第一個實驗旨在測量所選社區檢測算法的當前性能，使用GCE算法所得的結果作為評估PC-GCE算法性能的基準。第二個實驗評估針對不同約束數，PC-GCE的性能，每個網絡中可能的約束對數量占總數的1%到5%。在該實驗中，隨機選擇初始約束對；然后重復20次以上并對NMI分數進行平均；最后，將PC-GCE獲得的結果與選定的基準算法進行比較。

3.3 實驗結果分析

實驗采用2步比較和評估結果。首先，將PC-GCE的準確性與標準GCE進行比較(如表2)。其次，比較了PC-GCE算法與其他基準算法的準確性(如表3)。

從表2中可見，在大多數情況下，無論網絡中重疊節點的比例如何，PC-GCE都優于標準GCE算法。更具體地說，對于重疊節點分數的所有度量，隨著成對約束的百分比增加，PC-GCE的準確度也提高。另一方面，當將重疊節點On的比例從節點總數的25%增加到100%時，GCE的NMI下降到0的情況幾乎占總結果集的60%。又如，在小型社區網絡的情況下，對于Om=3時，GCE的NMI值從0.7636降到0，對于Om=4，NMI從0.6484降至0。對比一下，PC-GCE算法隨著On值的增加，準確度會適當降低，這表明PC-GCE在高度重疊的社區中優于標準GCE。但是，通常，2種算法在包含較小社區的網絡上都表現出更好的性能。

表2 小型和大型社區網絡中運用PC-GCE的NMI值(約束對占比0～5%)

大型社區網絡每個節點的社區數(Om)201%2%3%4%5%GCEPC-GCE重疊節點數(On)2500.96920.97040.97120.97220.97200.97245000.98500.99020.99230.99310.99540.99587500.94420.96500.97500.97840.98150.986010000.82090.86200.88430.88610.88950.8946301%2%3%4%5%GCEPC-GCE重疊節點數(On)2500.65400.67550.67600.67670.67720.67765000.62750.66600.68540.69320.70400.70867500.49520.56460.58660.59620.62240.624010000.25770.28880.30760.32500.33140.3494401%2%3%4%5%GCEPC-GCE重疊節點數(On)2500.55900.55960.56060.56160.56100.56225000.44000.46220.47520.48620.48860.49547500.10310.12800.15860.16640.17540.177410000.00000.01060.01100.01420.01520.0211501%2%3%4%5%GCEPC-GCE重疊節點數(On)2500.46660.46680.46720.46800.46860.46865000.19800.20820.23140.24880.25880.26927500.00000.06360.07840.07980.07620.081510000.00000.00000.00000.00020.00000.0000

從表3可以看出，PC-GCE算法在2種網絡中性能均優于COPRA算法。當考慮重疊節點數最小(即On=250)時，COPRA與PC-GCE幾乎相當。然而，隨著On值的增加，COPRA的性能下降到0，而PC-GCE的性能僅顯示略微下降。因此，可以得出結論，PC-GCE算法在高度重疊的社區網絡上優于COPRA。另一方面，PC-GCE在大型網絡上優于MOSES，但在小型網絡上表現出幾乎相似的性能。最后，在2種類型的網絡中，使OSLOM的NMI得分與PC-GCE的整體性能相當。

表3 小型和大型社區網絡中應用無監督算法的NMI值

小型社區網絡每個節點的社區數(Om)COPRA2345重疊節點數(On)2500.75360.61380.49500.35955000.56640.00000.00000.00007500.00000.00000.00000.000010000.00000.00000.00000.0000

小型社區網絡每個節點的社區數(Om)OSLOM2345重疊節點數(On)2500.97320.91460.79620.71685000.94350.84960.60200.31727500.92400.67890.22990.077710000.89520.37170.00980.0000

大型社區網絡每個節點的社區數(Om)MOSES2345重疊節點數(On)2500.61400.54480.45950.42445000.53380.44980.34950.31987500.47880.34350.17960.096010000.57400.19890.01910.0000

大型社區網絡每個節點的社區數(Om)COPRA2345重疊節點數(On)2500.71200.62350.48440.43775000.52160.00000.00000.00007500.00000.00000.00000.000010000.00000.00000.00000.0000

大型社區網絡每個節點的社區數(Om)OSLOM2345重疊節點數(On)2500.95240.86000.70760.64245000.90770.73750.46460.22857500.90250.49080.17800.072510000.86180.13820.00000.0000

4 結束語

本文探討了半監督策略在網絡中尋找重疊社區的潛力，提出了一種新的基于成對(對偶)約束的重疊社區檢測算法(PC-GCE)。大量實驗表明，基于對偶約束的GCE算法性能優于基于無約束的重疊社區發現算法，并且隨著成對約束數量的增加，其性能有所提高。這顯示了本文采用半監督策略尋找重疊社區的潛力。然而，在大多數網絡中，只有一小部分節點具有成對的信息約束。因此，使用成對約束的隨機選擇可能會產生負面影響，因為選擇非信息性節點會降低社區檢測過程的準確性。未來的工作將致力于應用主動學習的思想來選擇成對的信息約束，以及探討不正確的“噪聲”約束的影響及其對算法性能的影響。