二分圖中高效計算top-n maximal α-biclique的方法研究

關鍵詞：（1，α）-core;maximal α-biclique;共同鄰居;節點順序

中圖分類號：TP391 文獻標志碼：A

0 引言（Introduction）

二分圖是社交網絡中一個備受關注的研究領域[1]，通常被用于兩種不同類型的實體及兩類實體之間的聯系建模。當前的研究主要聚焦于根據給定查詢用戶及查詢參數，輸出符合查詢條件的稠密子圖[2-3]，或者通過直接遍歷子圖獲得整個二分圖上所有的稠密子圖[4]。但是，當用戶只給定某一類節點的組合數量，希望輸出另一類節點數量排序為前n 的子圖時，現有的研究不能很好地解決這個問題。針對上述問題，本文提出了兩種不同的搜索算法：基礎搜索算法和基于共同鄰居搜索算法。基礎搜索算法使用（1，α）-core剪枝方法簡化初始圖，該算法必須遍歷簡化圖中全部節點，才能獲得所有的maximal α-biclique。基于共同鄰居搜索算法，每次選擇順序最大的節點進行遍歷，并且只枚舉該節點的二跳鄰居，當已經獲得n 個maximal α-biclique時，根據當前最小閾值判斷是否提前結束算法。實驗結果表明，兩種算法都可以有效地解決上述問題，與基礎搜索算法相比，基于共同鄰居搜索算法的搜索效率提升了80%。

1 相關研究（Related work）

1.1 二分圖中的常用模型

LYU等[5]研究了大規模二分圖中進行最大biclique搜索的問題。他們設計了一種漸進式邊界框架，該框架通過將問題映射到二維空間進行分析，利用節點性質縮小子圖從而提高搜索效率，并通過阿里巴巴集團控股有限公司的真實數據集驗證了算法的有效性。LIU等[6]提出了一種基于索引的（α，β）-core分解算法，并介紹了實用的索引維護方法。該分解算法的運行時間復雜度為O（n），其中n 為節點數量，索引僅需要O（m）大小的空間存儲，其中m 為邊的數量。楊珍等[7]提出了基于加權二分圖的推薦方案，采用基于用戶和方案特征的評分方式組成用戶方案規則庫，使用協同過濾算法比較新用戶特征和規則庫中用戶特征的相似度，并選擇相似度高的進行推薦。

1.2 二分圖中的biclique計數問題研究

蝴蝶計數作為biclique計數問題的一個特例，近年來引起了許多研究者的關注。WANG等[8]首次提出了二分圖中蝴蝶計數的精確算法，該算法避免了枚舉所有的蝴蝶。首先，算法隨機選擇一層節點;其次，對于所選層中的每個節點u，計算它的二跳鄰居。對于u 的每個二跳鄰居w，計算出u 和w 之間的共同鄰居數量，就可以得到包含u 的蝴蝶數量。將所有節點的蝴蝶數量相加再除以2，就是蝴蝶的總數。ZHOU等[9]定義了不確定二分圖上的蝴蝶結構，提出了蝴蝶結構的計數問題，在基礎搜索算法的基礎上提出了改進算法。該改進算法在不增加內存成本的情況下，進一步使用啟發式策略減少程序的運行時間。在不需要獲得精確結果的情況下，可以通過抽樣方法獲得近似結果。YANG等[10]研究了二分圖中的bi-triangle計數問題，其中bi-triangle被定義為6-cycle。

1.3 二分圖中的biclique枚舉問題研究

一個與本文的研究密切相關的問題是二分圖中的maximal biclique枚舉。只有當一個biclique不被其他任何biclique包含，才被稱為maximal biclique。ABIDI等[11]發現基于樞軸的搜索空間修剪在集團枚舉中有效，于是他們提出了一種實現樞軸修剪的算法，并通過對節點進行離線排序，達到加快修剪的目的。SHAHAM 等[12]提出了一種使用蒙特卡洛子空間聚類方法尋找最大邊團的概率算法，并證明了該算法的有效性。CHEN等[13]證明了在實際應用的二分圖中可以快速地發現最大平衡二分團，并且針對小型稠密圖和大型稀疏圖分別提出不同的精確算法;針對典型的大型稀疏圖，他們還提出了一種將大型稀疏圖轉換為有限數量的稠密子圖的算法。

2 常用符號和基礎定義（Frequently used notationsand basic definition）

在二分圖中有許多常用的符號，這些符號會在本文中重復出現，為了不重復描述同一個符號，也便于查找符號對應的解釋，本文將常用符號和對應的解釋全部列于表1中。

本文中經常使用的定義如下。

3 基礎搜索算法（Basic search algorithm）

針對當二分圖中一類節點的數量固定時，如何搜索另一類型節點數量排序為前n 的maximal α-biclique的問題，最簡單的解決方法就是直接枚舉二分圖中所有的maximal α-biclique，最后從結果集中找到V 節點數量最多的排序為前n 個的maximal α-biclique。但是，這種方法是極其耗費時間的，尤其是在二分圖非常大的情況下。因此，本文首先根據maximal α-biclique的性質進行剪枝，其次在經過剪枝之后的簡化圖中進行maximal α-biclique枚舉。剪枝條件和枚舉算法如下。

引理1：在二分圖G 中被包含在maximal α-biclique的節點一定被包含在（1，α）-core中。

證明：可以使用反證法證明。如果一個U 類型節點出現在maximal α-biclique中，那么該節點的鄰居數量一定大于1，如果這樣的節點不被包含在（1，α）-core中，那么與定義1相違背。同理，如果一個V 類型節點出現在maximal α-biclique中，那么該節點的鄰居數量一定大于α，如果這樣的節點不被包含在（1，α）-core中，那么也與定義1相違背。

基礎搜索算法首先從原始二分圖中獲得經過（1，α）-core剪枝的簡化圖（第1行）;其次將優先級隊列C 和已遍歷節點隊列Q 進行初始化（第2行）;再次對簡化圖中的U 類型中的每一個節點進行遞歸，找到符合要求的maximal α-biclique，同時將已經遍歷過的節點添加到隊列Q 中（第3～5行）;最后從優先級隊列C 中將前n 個結果返回（第6行）。

Enumeration子過程是用來枚舉maximal α-biclique的具體算法。調用Enumeration子過程時需要傳入4個參數。雙向隊列L 中存放已經選中的節點，數組C中存放可以添加到雙向隊列L 中的節點，集合R 中存放雙向隊列L 中所有節點的共同鄰居，整數index 則表示C 中下一個要被遍歷的節點下標。Enumeration算法首先會判定雙向隊列L 中節點的數量和C 中還未遍歷節點的數量之和是否小于α，如果判定成立，就直接返回，不再向下遞歸（第8～9行）。當判定成立時，當前選擇的節點集合不可能成為一個maximal α-biclique，當前枚舉過程可以提前結束。當判定不成立時，會繼續判斷當前雙向隊列L 中節點的數量是否等于α，如果成立，那么就把當前雙向隊列L 和集合R 中的節點添加到優先級隊列C 中，并且返回（第10～12行）。當雙向隊列L 中的節點數量小于α 時，從數組C中選出下標為index 的節點u'添加到雙向隊列L中，集合R中的節點更新為集合R中節點和u'鄰居節點的交集，并進行下一層的遞歸，當遞歸完成后，將雙向隊列L 和集合R中的節點恢復為此次遍歷之前的節點集合（第13～16行）;具體的算法過程如下。

引理2：基礎搜索算法可以正確地輸出top-n maximal α-biclique。

證明：為了證明算法返回的是正確的結果，需要證明在刪除不滿足要求的節點時，G總是包含最大（1，α）-core。顯然在第一行初始化G 時，它包含了最大（1，α）-core，而且在對U 中的節點進行遍歷時，也沒有刪除節點，所以可以確保所有的節點都被遍歷，不會遺漏任何一個maximal α-biclique。同時，隊列Q 會記錄遍歷過的節點，并在數組C中已將遍歷過的節點全部排除，不會出現同一個maximal α-biclique重復出現的情況。因此，引理2正確。

復雜度分析：給定一個二分圖G=（U，V，E），基礎搜索算法的時間復雜度是O（|U|α），其中Uc 為簡化后子圖包含的U類型節點。

4 基于共同鄰居的搜索算法（Search algorithmbased on common neighbors）

雖然基礎搜索算法可以成功計算出top-n maximal α-biclique，但是它仍有優化的空間。比如基礎搜索算法在數組CL 中存放的是Uc 中除了已經遍歷過的節點外的所有節點，但實際上對于Uc 中的一個節點u'，如果u'不是節點u 的二跳鄰居，那么u 和u'之間的共同鄰居數量一定為0，u 和u'一定無法滿足maximal α-biclique，因此會導致一些無效搜索過程。基于此觀察，本節介紹基于共同鄰居的搜索算法。

4.1 基于共同鄰居的搜索策略

二跳鄰居的定義如下。

定義4：二跳鄰居。在一個二分圖G=（U，V，E）中，如果節點u 和節點v 之間存在一條邊（u，v），同時節點v 和節點u'之間也存在一條邊（u'，v），那么稱u'是u 的二跳鄰居。

同時發現，本文的求解目標是top-n maximal α-biclique，因此只需要求解出排序為前n 個的maximal α-biclique即可，不需要枚舉出所有的maximal α-biclique，因此本文使用了節點順序的概念，如定義5。節點順序排名高的節點，優先進行遍歷。一個節點的節點順序越大，那么在該節點組成的maximal α-biclique中，V 中元素數量越多的可能性越高。

定義5：節點順序。給定一個二分圖G=（U，V，E），對于兩個節點u，u'∈U，如果節點u 的鄰居數量d（u，G）>d（u'，G）或者d（u，G）=d（u'，G）并且u.id<u'.id，那么u的節點順序高于u'的節點順序。

如果當前結果集中maximal α-biclique的數量已經到達n個，同時一個節點的共同鄰居數量小于或等于當前結果集中最小maximal α-biclique中V 的節點數量，那么要遍歷的U類型節點形成的maximal α-biclique就不會出現在結果集中。這個現象可以被用來搜索空間剪枝。

4.2 算法設計

根據以上觀察結果，本文設計了基于共同鄰居搜索算法，算法流程具體如下。

基于共同鄰居搜索算法的第一步和基礎搜索算法相同，都是先對原始圖進行（1，α）-core剪枝得到簡化圖（第1行），然后將優先級隊列C 初始化為空，同時將閾值min設置為0。min用來記錄當優先級隊列C 的大小為n 時，優先級隊列C 包含的各個maximal α-biclique中V 類型節點數量的最小值（第2行）。算法將所有節點的二跳鄰居存放到集合NN 中，并根據每個節點的度計算出節點的排序（第3～4行）。根據此節點的排序按逐漸降序的方式進行遍歷（第5～11行），如果當前節點的鄰居數量小于或等于閾值min，那么表示此節點包含的maximal α-biclique不可能優于當前已知結果，因此直接結束此次循環（第6～7行）。如果當前節點的二跳鄰居數量大于或等于α-1，那么對該節點可能形成的maximal α-biclique進行枚舉。當前節點遍歷完成后，需要更新集合NN ，防止枚舉相同的maximal α-biclique。

PBlisting子程序是實現枚舉過程的具體算法，需要傳入3個參數：集合W 用來存放u 的二跳鄰居，集合CommonN 存放L 中所有節點的共同鄰居，雙向隊列L 存放當前候選的所有節點。當雙向隊列L 中的節點數量為α 時，判斷當前集合CommonN 中的節點數量以及優先級隊列C 的大小，如果集合CommonN 中的節點數量大于min，同時優先級隊列C 中maximal α-biclique數量等于n，那么將優先級隊列C 中V 節點數量最少的maximal α-biclique 彈出，將新的maximalα-biclique加入優先級隊列C 中，并且更新參數閾值min。如果優先級隊列C 中maximal α-biclique數量小于n，那么同樣將新的maximal α-biclique插入優先級隊列C，并且若插入后優先級隊列C 中maximal α-biclique的數量等于n，則更新閾值min，最后返回（第14～21行）。如果L 中節點的數量小于α，同樣根據節點的順序，每次選擇集合W 中順序最高的節點添加到雙向隊列L 中，直到程序結束。基于共同鄰居搜索的算法偽代碼如算法2所示。

4.3 算法運行實例

使用圖2模擬基于共同鄰居搜索算法遍歷節點的過程。節點的遍歷順序和結果集的變化過程如表2所示，查詢參數同樣為α=2，n=2。

5 實驗（Experiments）

5.1 實驗環境和數據集

實驗環境：本研究在CSB、FI、MI和LA真實數據集上對本文提出的算法進行實驗評估，以驗證算法在不同數據集上的有效性。所有實驗都是在一臺配置為Intel i5 3.1 GHz CPU和16 GB內存的Windows機器上運行的。算法全部由Java語言編寫。

算法：使用基礎搜索算法和基于共同鄰居算法驗證top-nmaximal α-biclique。為了方便表述，以下使用BL和CN分別表示基礎搜索算法和基于共同鄰居搜索算法。

數據集：從不同領域選擇了4個真實數據集，這些數據集具有不同的數據屬性。所有的數據集都可以在Konect（www.konect.cc）上獲得，數據集的詳細信息如表3所示。

參數設置：為了更好地評估本文提出的算法，本文將n 的參數范圍設置為10～100，每次增加30，同時α 的范圍設置為3～11，每次增加2。同時，如果沒有特殊說明，那么實驗中默認使用n=10，α=3作為參數。

5.2 算法運行時間分析

不同數據集上的實驗結果：BL和CN在不同數據集上的運行時間如圖3所示。從圖3中可以觀察到，在所有數據集上，CN的運行時間比BL的運行時間增加了接近一個數量級。這是因為CN剪去大量的無效分支，并能夠在已確信獲得所需結果的前提下提前終止算法的運行，從而節約了計算時間。當U 類型的節點增加時，BL的運行時間快速增加，但是CN運行時間增加緩慢，說明CN具有良好的剪枝效果。

參數n 變化的效果：表4展示了當查詢參數α=3時，BL和CN在4個數據集上隨著n 從10變化到100時的運行時間變化情況。從表4中可以觀察到，BL的運行時間沒有發生變化，這是因為BL每次都要獲取所有的3-biclique。CN的運行時間隨著n 的變大而增加，但是增加的幅度十分緩慢，這是因為當n 的值變大時，要返回的maximal 3-biclique數量更多，此時閾值可能變小，必須遍歷更多的節點，才可以獲得結果。

參數α 變化的效果：圖4展示了當n=10時，BL和CN在4個數據集上隨著α 從3變化到11的運行時間。從圖4中可以觀察到，CN在4個數據集中的運行時間沒有劇烈的變化且遠遠小于BL的運行時間。在CSB和FI中，BL的運行時間隨著α的增加呈現先增加后減小的變化趨勢。這是因為當α很大時，簡化圖就會變得比較小或者比較稀疏，此時BL可以很快地枚舉整個子圖。在MI和LA中，簡化圖雖然變小，但是仍有大量的節點需要遍歷，因此BL的運行時間隨著α的增加而增加。

5.3 算法剪枝效果分析

α變化的剪枝效果：表5展示了隨著α 的變化，BL和CN需要遍歷的節點數量。從第二列到第五列，每一列左邊和右邊的數字分別表示BL與CN需要遍歷的節點數量。從表5中可以觀察到，隨著α 變大，BL遍歷的節點數量逐漸減少。這是因為當α 變大時，使用（1，α）-core剪去U 類型節點的數量增加，U中剩余的節點數量變少，需要遍歷的節點也變少。然而在CN中，每次都選擇排序最大的節點枚舉，則越有可能成為結果的節點就會越早被遍歷到，當已經獲得數量為n 的maximal α-biclique后，就可以通過閾值判斷是否結束算法。

n 變化的剪枝效果：表6展示了當n 變化時，BL和CN需要遍歷的節點數量。從第二列到第四列，每一列左邊和右邊的數字分別表示BL和CN需要遍歷的節點數量。從表6中可以觀察到，當n 變大時，BL需要遍歷的節點數量是一樣的，n 變大時，經過（1，3）-core剪枝的簡化圖的大小沒有變化，BL每次都要遍歷所有的U 類型節點。CN需要遍歷的節點數量隨著n的變大而不變或增加，這是因為當n 變大時，閾值可能會變小，只有遍歷更多的節點，才能確定最終結果。

6 結論（Conclusion）

本文研究當二分圖中某一類節點的數量固定時，如何搜索包含另一類型節點數量排序為前n 的maximal α-biclique問題。首先，本文介紹了maximal α-biclique的定義。其次，提出了一種使用（1，α）-core剪枝的基礎搜索算法，并在該算法的基礎上利用共同鄰居概念提出了基于共同鄰居搜索算法。基于共同鄰居搜索算法每次選擇排序最大的節點遍歷，通過枚舉該節點的二跳鄰居減少搜索分支，并且根據已知結果的最小閾值，判斷是否能提前結束搜索過程，從而提高搜索效率。最后，本文通過理論分析和廣泛的實驗驗證了兩種算法的有效性，同時實驗結果表明，相比于基礎搜索算法，基于共同鄰居搜索算法的搜索效率提升了80%。

作者簡介：

唐東杭（1997-），男，碩士生。研究領域：數據挖掘，社交分析。

吳進高（1977-），男，本科，工程師。研究領域：數據挖掘，社交分析。本文通信作者。

徐建（1975-），男，博士，教授。研究領域：數據挖掘，社交分析。