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

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

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

0 引言（Introduction）

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

1 相關研究（Related work）

1.1 二分圖中的常用模型

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

1.2 二分圖中的biclique計數(shù)問題研究

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

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

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

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

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

本文中經(jīng)常使用的定義如下。

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

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

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

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

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

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

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

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

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

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

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

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

二跳鄰居的定義如下。

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

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

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

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

4.2 算法設計

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

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

PBlisting子程序是實現(xiàn)枚舉過程的具體算法，需要傳入3個參數(shù)：集合W 用來存放u 的二跳鄰居，集合CommonN 存放L 中所有節(jié)點的共同鄰居，雙向隊列L 存放當前候選的所有節(jié)點。當雙向隊列L 中的節(jié)點數(shù)量為α 時，判斷當前集合CommonN 中的節(jié)點數(shù)量以及優(yōu)先級隊列C 的大小，如果集合CommonN 中的節(jié)點數(shù)量大于min，同時優(yōu)先級隊列C 中maximal α-biclique數(shù)量等于n，那么將優(yōu)先級隊列C 中V 節(jié)點數(shù)量最少的maximal α-biclique 彈出，將新的maximalα-biclique加入優(yōu)先級隊列C 中，并且更新參數(shù)閾值min。如果優(yōu)先級隊列C 中maximal α-biclique數(shù)量小于n，那么同樣將新的maximal α-biclique插入優(yōu)先級隊列C，并且若插入后優(yōu)先級隊列C 中maximal α-biclique的數(shù)量等于n，則更新閾值min，最后返回（第14～21行）。如果L 中節(jié)點的數(shù)量小于α，同樣根據(jù)節(jié)點的順序，每次選擇集合W 中順序最高的節(jié)點添加到雙向隊列L 中，直到程序結(jié)束?；诠餐従铀阉鞯乃惴▊未a如算法2所示。

4.3 算法運行實例

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

5 實驗（Experiments）

5.1 實驗環(huán)境和數(shù)據(jù)集

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

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

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

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

5.2 算法運行時間分析

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

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

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

5.3 算法剪枝效果分析

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

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

6 結(jié)論（Conclusion）

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

作者簡介：

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

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

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