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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

0 引言（Introduction）

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

1 相關(guān)研究（Related work）

1.1 二分圖中的常用模型

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

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

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

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

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

2 常用符號(hào)和基礎(chǔ)定義（Frequently used notationsand basic definition）

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

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

3 基礎(chǔ)搜索算法（Basic search algorithm）

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

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

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

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

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

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

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

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

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

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

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

二跳鄰居的定義如下。

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

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

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

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

4.2 算法設(shè)計(jì)

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

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

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

4.3 算法運(yùn)行實(shí)例

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

5 實(shí)驗(yàn)（Experiments）

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

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

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

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

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

5.2 算法運(yùn)行時(shí)間分析

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

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

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

5.3 算法剪枝效果分析

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

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

6 結(jié)論（Conclusion）

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

作者簡(jiǎn)介：

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

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

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