復雜屬性條件下基于Spark的clique社區搜索算法

佘 鑫，何震瀛

（1.復旦大學 軟件學院，上海 200441；2.復旦大學 計算機科學技術學院，上海 200441）

0 概述

社區搜索有利于對網絡進行分析，具有重要的應用價值。在網絡中，節點表示實體，邊表示實體之間的關系［1］。社區結構作為網絡的重要組成部分，是內部節點連接緊密的子圖［2］。例如：在Facebook中，社區可由具有朋友關系的用戶組成［3］；在萬維網中，社區可以是一些具有相似主題的網站［4］；在蛋白質-蛋白質相互作用網絡［5］和代謝網絡［6］中，社區可以用于生物功能模塊發現；在企業社會化網絡中，社區可用于分析企業團體的拓撲特征和功能特性［7］。

早期的社區搜索算法僅考慮網絡拓撲結構，即給定一組節點，從網絡中尋找包含這組節點的社區。常見的社區結構有clique［5］、k-core［8-10］、k-truss［11］等。文獻［5］利用clique 結構來尋找網絡中的重疊社區。文獻［9］提出了尋找包含給定節點集的k-core 社區問題及對應算法。文獻［10］提出了復雜條件下的k-core 社區搜索方法，旨在找到滿足給定復雜條件的k-core 社區，但該方法使用由節點變量組成的布爾表達式定義復雜條件，在搜索過程中僅考慮網絡拓撲結構，不適用于節點包含屬性信息的網絡。文獻［11］給出了k-truss 的社區定義。文獻［12］提出了尋找包含給定節點的k-truss 社區問題，并設計了基于TCP-Index 的搜索算法。

近年來的社區搜索算法研究出現了同時考慮網絡拓撲結構和節點屬性的情況。文獻［13］提出基于k-core 結構在屬性圖上進行社區搜索，旨在尋找內部節點間共享盡可能多的屬性的社區。文獻［14］在給定節點集和屬性集的情況下，設計了一個屬性評價函數來度量屬性在社區內部的流行程度，進而尋找基于屬性的k-truss 社區。文獻［15］提出了尋找包含給定屬性集的最小且緊密的k-truss 社區的問題。文獻［16］提出了以關鍵字為中心的社區搜索問題，通過定義屬性間的距離來度量子圖中的屬性緊密度，進而尋找滿足要求的最大k-core 社區。文獻［17］建立內聚屬性社區搜索模型以尋找結構和屬性緊密度高的社區。文獻［18］提出了屬性多樣化的社區搜索問題，提出了屬性多樣化模型和基于k-core 的剪枝算法。

上述社區搜索算法可以尋找包含給定屬性集的社區，但仍難以滿足實際應用的復雜需求。本文將包含給定屬性集的這類條件之外的屬性條件稱為復雜屬性條件（如包含屬性集中任意一個屬性、包含某些屬性而不包含另一些屬性等），進而提出復雜屬性條件下的clique 社區搜索問題。

clique 社區搜索問題難以在多項式時間內被解決，枚舉極大clique 的問題已被證明是NP-Hard的［19］，該問題具有指數級別的復雜度其中，n為網絡圖的節點數目。文獻［20］提出的經典BK 算法是后續算法的基礎。文獻［19］提出了一個運行速度更快的算法，但是總體復雜度仍然與BK 算法接近。文獻［21］提出了一種在大型網絡中枚舉clique的近似算法，該算法基于隨機的方式實現，但是沒有提供clique 枚舉的準確計數。文獻［22］提出了一種誤差小于2%的clique 計數的近似算法，但該算法在大型網絡中無法擴展。

目前多數解決clique 問題的算法都是在單機環境下運行的，很少有分布式環境下的解決方案。文獻［23］提出了一種分布式解決方案，該解決方案使用結合MapReduce 框架的多路聯接來枚舉clique，但是該方案存在嚴重的I/O 性能瓶頸，并且在大型網絡中的效果較差。文獻［24］提出了基于Spark 的利用多階段分區策略來尋找最大clique 的算法，但該算法無法擴展至存在復雜屬性條件的情況。

本文提出基于Spark 適用于復雜屬性條件的clique 社區搜索算法。利用布爾表達式形式化地定義復雜屬性條件，進而基于clique 結構給出復雜屬性條件下clique 社區搜索問題的定義，并說明該問題的復雜性。通過使用Spark 并行計算框架，根據考慮網絡結構和內容屬性的先后順序，分別提出結構優先的社區搜索算法SF 和屬性優先的社區搜索算法AF。同時考慮到SF 算法未充分利用屬性信息和AF算法屬性計數成本較高的問題，結合網絡結構和內容屬性，進一步提出融合屬性和結構的社區搜索算法AS。

1 復雜屬性條件下的clique 社區搜索問題

傳統的屬性社區搜索問題都是以屬性集的形式作為輸入，旨在尋找包含給定屬性集的社區，但是無法適用于以下兩種情況：一種是不包含給定的若干屬性的情況；另一種是至少包含給定的若干屬性中一個的情況。本節首先基于布爾表達式形式化地定義復雜屬性條件，然后提出復雜屬性條件下的clique社區搜索問題定義并給出問題示例，最后說明該問題的復雜性。

1.1 問題定義

布爾表達式由邏輯運算符和布爾變量組成［10］。布爾變量的取值為真（1）和假（0），邏輯運算符包括與（∧）、或（∨）、非（﹁）。確定式中每個布爾變量的取值并結合邏輯運算符即可判斷整個布爾表達式的真假。因此，本文利用布爾表達式形式化地定義復雜屬性條件。

對于一個社區C，給定布爾變量A（對應屬性A）。如果社區包含屬性A，那么該屬性對應的布爾變量為真；反之，如果社區不包含屬性A，那么該屬性對應的布爾變量為假。將這樣的布爾變量稱為屬性變量，利用屬性變量和邏輯運算符組成的布爾表達式，可以完成復雜屬性條件的形式化定義。

定義1簡單屬性條件

1）單個屬性變量A 是簡單屬性條件；

2）如果屬性變量A 和B 是簡單屬性條件，那么A∧B 是簡單屬性條件；

3）當且僅當有限次地應用條件1）、2）所得到的布爾表達式稱為簡單屬性條件。

定義2屬性條件

1）單個屬性變量A 是屬性條件；

2）如果A 是屬性條件，那么﹁A 是屬性條件；

3）如果A 和B 是屬性條件，那么A ∧B、A ∨B 是屬性條件；

4）當且僅當有限次地應用條件1）～3）所得到的布爾表達式稱為屬性條件。

定義3復雜屬性條件

將滿足定義2 但不滿足定義1 的布爾表達式稱為復雜屬性條件。

定義4單項屬性條件

對于一個屬性條件，如果有且僅有一組屬性變量的取值能滿足該條件，那么稱其為單項屬性條件。

定義5clique 社區

給定一個網絡圖G=（V，E），其中：V 為節點集；E 為邊集。圖G 中的clique 社區C 滿足：對于任意節點u∈C，v∈C（u≠v），存在一條邊（u，v）∈E。圖G 中如果不存在一個clique 社區C’使C ?C’，那么稱clique 社區C 為圖G 中的一個極大clique 社區。

定義6復雜屬性條件下的clique 社區搜索問題

給定一個網絡圖G=（V，E），其中：V 為節點集；節點數n=|V（G）|；E 為邊集；邊數m=|E（G）|。用T表示圖G的屬性集，用attr（v）表示節點v的屬性集，v∈V，attr（v）?T。對于任意屬性A ∈T，用VA表示包含屬性A的節點集，即VA={v ∈V|A ∈attr(v)}。輸入復雜屬性條件Q，尋找滿足以下條件的社區C：1）C ?V；2）C 是連通的，且為極大clique 社區；3）復雜屬性條件Q 在給定社區C 的情況下為真。

以 從DBLP（http：//dblp.uni-trier.de/db/）中抽取的論文合作網絡（使用clique）為例，如圖1 所示。在該網絡中，節點表示作者，邊表示作者間的合作關系，每個作者有若干屬性標簽，如作者的研究領域Data Mining、Data Security、Big Data Analytics 等。此時需要組建一個具有Data Mining 和Data Security背景且合作緊密的團隊。對于尋找一個滿足何種條件的clique 社區這一問題，從社區的角度來解釋，此問題即為需要在給定學術合作網絡中找到包含屬性Data Mining 和Data Security 的社區。圖1 中包含的極 大clique 社區有3個，分別是｛v1，v2，v4，v6｝、｛v3，v4，v5，v6，v7，v8｝和｛v7，v8，v9，v10，v11｝，其中，滿足包含屬性Data Mining 和Data Security 這一條件的極大clique 社區為｛v3，v4，v5，v6，v7，v8｝。

圖1 復雜屬性條件下的社區搜索示例Fig.1 Example of community search under complex attribute condition

1.2 復雜性

極大clique 的枚舉問題是NP-Hard 的［12］，該問題的復雜度為其中，n為圖的節點數目。假設考慮最簡單的屬性條件，即求包含單個屬性的極大clique，那么就相當于是要求出所有極大clique，然后再判斷是否包含該屬性。這樣極大clique 的枚舉問題，即復雜屬性條件下的clique 社區搜索問題是NP-Hard 的。

2 復雜屬性條件下的clique 社區搜索算法

本節提出結構優先的社區搜索算法SF和屬性優先的社區搜索算法AF。在此基礎上，結合圖的結構特征和內容屬性，提出融合屬性和結構的社區搜索算法AS。

2.1 結構優先的社區搜索算法

結構優先的社區搜索算法SF 設計思想為：首先枚舉出圖中所有的極大clique，然后判斷每一個極大clique是否符合給定的屬性條件，若不符合，則刪除不符合屬性條件的節點，反之則保留該極大clique，最后選出所有滿足屬性條件的極大clique。但該算法由于在計算過程中需要枚舉出圖上所有的極大clique，因此時間開銷很大，已被證明是NP-Hard 的。因為復雜屬性條件下的社區搜索結果與輸入的屬性條件有很大關系，一般情況下不會涉及到全體結果，所以沒有必要枚舉出所有的極大clique。因此，本文結合屬性信息提出屬性優先的社區搜索算法。

2.2 屬性優先的社區搜索算法

本文基于Spark 并行計算框架提出屬性優先的社區搜索算法AF，其偽代碼如算法1 所示。該算法根據復雜屬性條件對每一個點進行屬性計數，進而利用Spark GraphX 提供的操作進行圖分割，最終找到所有滿足條件的社區。

算法1屬性優先的社區搜索算法AF

AF 算法的主要步驟如下：

步驟1讀取數據加載圖。

首先給定文件路徑從HDFS 中讀取數據集，生成點集合對象VertexArray 和邊集合對象EdgeArray，然后通過Spark 的parallelize 算子生成VertexRDD 和EdgeRDD，最后 使用Spark GraphX 的Graph 方法構造出圖G。

步驟2獲取圖的輔助信息。

在步驟1 得到的圖G 基礎上，調用Spark GraphX中的aggregateMessages方法獲取NeighborVertexRDD。aggregateMessages 操作的對象是triplet，其結構為一個五元組，包含源頂點號、目的頂點號、源頂點屬性、目的頂點屬性和邊的屬性。triplet 中的操作包含sendMsg和mergeMsg 這2 個階段。在sendMsg 階段，源頂點和目的頂點之間會互相發送各自的編號和屬性；而在mergeMsg 階段，會將每個頂點收集起來的編號和屬性進行合并。最終，返回NeighborVertexRDD。

步驟3簡化復雜屬性條件。

在進行實際社區搜索時，輸入的屬性變量數目通常比較少，因此，可以通過枚舉屬性變量取值的形式來找到滿足復雜屬性條件的所有取值集合。用1和0 分別代表屬性是否存在于社區中。例如：滿足條件A ∧﹁B ∧C 的屬性變量組合為A=1，B=0，C=1。如果輸入的屬性變量數目較多，那么可以采用求解可滿足性問題的快速算法，如GRASP 算法［25］。

在得到滿足復雜屬性條件的所有取值集合后，可以得到與該條件等價的主析取范式。例如：對于復雜屬性條件(A ∨﹁B)∧C，可以先枚舉出A=1，B=0，C=1、A=1，B=1，C=1 和A=0，B=0，C=1 這3 種取值組合使條件的結果為真，進而該條件可以化簡為3 個合取式的析取式，即(A ∧﹁B ∧C)∨(A ∧B ∧C)∨(﹁A ∧﹁B ∧C)，然后對每個合取式進行一次單項屬性條件社區搜索，最后將每次得到的結果合并去重得到最終結果。

此外，化簡得到的主析取范式還可能存在冗余的情況，如(A ∧B ∧C)∨(﹁A ∧B ∧C)，由于屬性變量A 對結果不會產生任何影響，消除冗余后可以得到B ∧C，因此利用奎因-麥克拉斯基（QM）算法［26］消除這一類的冗余，從而減少搜索的開銷。

步驟4根據單項屬性條件進行搜索。

枚舉出所有的可能取值以后，根據每一組的取值進行社區搜索，即單項屬性條件社區搜索。根據每個單項屬性條件是否存在邏輯非運算符，把屬性分為必要屬性和禁止屬性，即如果單項屬性條件中的屬性變量取1 時為真，那么其對應的屬性為必要屬性；反之，如果單項屬性條件中的屬性變量取0 時為真，那么其對應的屬性為禁止屬性。對于一個單項屬性條件P，記P.RAS（Required Attribute Set）為其必要屬性集，記P.FAS（Forbidden Attribute Set）為其禁止屬性集。例如，對于單項屬性條件A ∧﹁B ∧C ∧﹁D，其必要屬性集P.RAS=｛A，C｝，禁止屬性集P.FAS=｛B，D｝。

單項屬性條件社區搜索過程如下：

1）根據單項屬性條件對圖中的每個節點進行屬性計數。屬性計數規則為：若節點包含當前單項屬性條件的禁止屬性，則該節點的屬性計數直接為-1，并且忽略該節點的其他屬性；若節點不包含當前單項屬性條件的禁止屬性，則該節點的屬性計數為當前單項屬性條件的必要屬性集和該節點的屬性集的交集的屬性數目。上述過程通過在圖G 和NeighborVertexRDD 上的outerJoinVertices 操作和mapVertices 操作實現。

2）為每個節點構造子圖，調用Spark GraphX 的aggregateMessages 方法生成子圖。在sendMsg 階段，對于相鄰的2 個節點，屬性計數較小的節點將發送其編號和屬性到屬性計數較大的節點，如果2 個節點的屬性計數相等，那么編號較小的節點將發送其編號和屬性到編號較大的節點；在mergeMsg 階段，每個節點合并收到的消息，與發送消息的鄰居節點形成一個子圖。

3）在每個節點生成的子圖中尋找滿足單項屬性條件的極大clique。

步驟5合并社區結果。

在得到每個單項屬性條件的社區搜索結果后，將其合并就能夠得到最終的復雜屬性條件社區搜索結果。

2.3 融合屬性和結構的社區搜索算法

融合屬性和結構的社區搜索算法AS 是基于AF算法的第4 步進行改進的。該算法同時考慮了圖的內容屬性和結構特征，并且可以根據不同的單項屬性條件采取不同的搜索策略，利用屬性的搜索成本和擴展成本進行局部優化，從而加快搜索過程。

簡化后的復雜屬性條件是由若干單項屬性條件組成的析取式，單項屬性條件一般會包含必要屬性和禁止屬性，因此，一個單項屬性條件會出現以下3 種情況：1）只包含必要屬性；2）既包含必要屬性又包含禁止屬性；3）只包含禁止屬性。

首先考慮第1 種情況，即只包含必要屬性。在clique 問題中，每個clique 的求解可以分為2 個步驟：

1）找到初始擴展節點。從該節點開始擴展，至少能夠找到一個極大clique。

2）擴展社區。以初始擴展節點的鄰居節點為候選集，不斷添加新節點到初始擴展節點所在集合，形成最終的極大clique。

在通常情況下，社區搜索問題中用戶輸入的屬性條件涉及到屬性數目比較少，同時，網絡圖中的節點包含的屬性有限，并且包含同一個屬性的節點數目不會太多。因此，結合必要屬性必須被包含在社區結果中這一情況，提出屬性的搜索成本的概念。

定義7屬性的搜索成本

給定圖G=（V，E）及其屬性集T，對于任意屬性A ∈T，其屬性搜索成本COST（A）為包含屬性A的節點數目與圖中節點數目的比值，即COST（A）=|VA|/|V |。

根據必要屬性的搜索成本可知包含某個屬性的節點數目。因為包含該屬性的節點數目越少，以其作為擴展節點時就越能避免考慮不必要的節點。因此，選擇具有最小搜索成本屬性的節點作為初始擴展節點。

在擴展社區的過程中，需要考慮的問題是將何類節點添加到社區結果中。例如，假設當前屬性條件為A ∧B ∧C，在擴展社區時，候選集為{V1，V2，V3}，其中，節點V1包含屬性A、D，節點V2包含屬性A、B，節點V3包含屬性B、C，那么在這一輪擴展社區時，包含屬性A的節點有2個，包含屬性B 的節點有2個，包含屬性C 的節點有1 個，因為被包含在更少節點的屬性是更稀缺的，該屬性更可能在后續擴展過程中消失，所以選擇被包含在更少節點的屬性作為這一輪擴展社區的屬性，進而包含該屬性的節點作為本輪的擴展節點。因此，提出了屬性的擴展成本概念。

定義8屬性的擴展成本

給定圖G=（V，E）及其屬性集T，當前擴展時的單項屬性條件為P，對于任意屬性A∈P.RAS，屬性A 的擴展成本為候選集中包含屬性A 的節點數與候選集中節點數的比值，即EXPAND（A，R）=|VA∩R|/|R|，其中，R 為當前擴展時的候選集。

在擴展社區的過程中，依次選擇包含具有最小擴展成本的屬性的一個節點加入到包含初始擴展節點的集合中，完成后續擴展，由此可以得到融合屬性和結構的社區搜索算法，如算法2 所示。

算法2融合屬性和結構的社區搜索算法AS

在選定初始擴展節點后，以初始擴展節點進行擴展，進而得到局部的clique。clique 局部擴展算法FindClique如算法3所示。

算法3clique 局部擴展算法FindClique

下面考慮第2 種情況，即屬性條件中既包含必要屬性又包含禁止屬性的情況。在這種情況下，使用必要屬性進行社區搜索，使用禁止屬性進行節點過濾。根據過濾操作的作用先后順序，可以分為3 種策略：預先搜索策略，預先過濾策略和搜索時過濾策略。

1）預先搜索策略即先搜索后過濾的策略。具體過程如下：首先根據必要屬性進行社區搜索，得到若干包含必要屬性的社區；然后檢查每個社區的內部節點是否存在禁止屬性，若存在，則刪除包含禁止屬性的節點，若不存在，則保留該社區；最后檢查過濾后的社區是否符合clique 結構的定義，若符合則保留。

2）預先過濾策略即先過濾后搜索的策略。具體過程如下：先根據禁止屬性刪除圖中所有包含禁止屬性的節點；再根據必要屬性進行社區搜索，這樣得到的社區結果不再包含禁止屬性，所以一定能夠滿足搜索條件。

3）搜索時過濾策略即根據必要屬性進行搜索，并且在搜索過程中避開包含禁止屬性的節點，直到找到滿足屬性條件的社區，且不再需要對社區結果進行檢查。

針對單項屬性條件同時包含必要屬性和禁止屬性的情況，在社區搜索的過程中需要做出選取何種搜索策略的決策。在刪除包含禁止屬性的節點前后，根據所有必要屬性中最小搜索成本的大小變化可以做出決策。現給定某個屬性條件，假設使用預先搜索策略時，所有必要屬性中的最小搜索成本為a，使用預先過濾策略時，所有必要屬性的搜索成本為b。如果a>b，那么采用預先過濾策略；如果a

還有一種特殊的情況是屬性條件中只包含禁止屬性的情況。這種情況由于沒有必要屬性，因此沒有根據屬性進行搜索的過程，只需要將包含禁止屬性的節點刪除后在剩余圖中枚舉出所有極大clique即可。

3 實驗結果與分析

在Spark集群上進行實驗，其中包括1個master節點和2個worker節點。硬件配置如下：Intel Xeon Silver 4280 CPU @ 2.10 GHz；64 GB 內存。軟件配置如下：Linux Ubuntu 18.04，JDK 1.8.0_151，Scala 2.11.12，Spark-2.4.5版本。

本文實驗中使用的數據集如表1 所示，其中包括loc-Gowalla、DBLP、Youtube 和SocPokec，這4 個數據集都來源于Stanford Large Network Dataset Collection（http：//snap.stanford.edu/data/）。

表1 實驗數據集Table 1 Datasets for experiment

實驗1對比不同屬性條件下SF、AF 和AS 算法的時間開銷。

設計6組不同的屬性條件，如表2所示，在DBLP和Youtube 數據集上測試3 種算法在各組屬性條件下的時間開銷。

表2 屬性條件Table 2 Attribute conditions

在DBLP 數據集上的實驗結果如圖2 所示，在Youtube 數據集上的實驗結果如圖3 所示。通過第1 組和第2 組屬性條件的對比實驗結果可以看出，屬性條件中的屬性數目越多，3 種算法的時間開銷越大，這表明算法時間開銷與屬性條件中涉及到的屬性數目呈正相關。通過第3 組和第4 組屬性條件的對比結果實驗結果可以看出，當屬性條件中涉及到的必要屬性數目和禁止屬性數目比較接近時，3 種算法的時間開銷也比較接近，這表明算法的時間開銷與涉及到的屬性總數目有關，如果涉及到的屬性總數目接近，那么算法的時間開銷也接近。通過第5 組和第6 組屬性條件的對比實驗結果可以看出：在只包含必要屬性的條件下，3 種算法的時間開銷與相同必要屬性數目的其他類似條件的時間開銷接近。在只包含禁止屬性的條件下，SF 算法和AF算法的時間開銷接近，這是由于缺少必要屬性，導致AF 算法在屬性層面失效。此外，AS 算法在只包含禁止屬性的條件下的時間開銷要比其他情況時間開銷稍大，這是由于刪除包含禁止屬性的節點需要額外時間，并且需要在剩余圖中進行全局搜索。

圖2 不同屬性條件下的時間開銷（DBLP）Fig.2 Time cost under different attribute conditions（DBLP）

圖3 不同屬性條件下的時間開銷（Youtube）Fig.3 Time cost under different attribute conditions（Youtube）

實驗2對比不同網絡規模下SF、AF 和AS 算法的時間開銷。

采用SocPokec 數據集（記為G4），由該數據集生成3 個G4 的子圖，分別是G1、G2 和G3，其中，G1 子圖的節點數是G4的1/4，G2子圖的節點數是G4的1/2，G3子圖的節點數是G4 的3/4，具體信息如表3 所示。

表3 SocPokec 及其子圖Table 3 SocPokec and its subgraphs

在本實驗中，屬性條件中搜索的屬性項數量為5，其中包含3 個必要屬性和2 個禁止屬性。實驗結果如圖4 所示，可以看出：在同一個網絡下，網絡規模越大，3 種算法的時間開銷就越大，且時間開銷隨著網絡規模的變化而線性變化；在4 種不同的網絡規模下，AS 算法的性能優于AF 算法，AF 算法的性能優于SF 算法。

圖4 不同網絡規模下3 種算法的時間開銷Fig.4 Time cost of three algorithms under different network scales

此外，進一步對比在不同網絡中SF、AF 和AS 算法的時間開銷。在實驗中，屬性條件中搜索的屬性項數量為5，其中包含3 個必要屬性和2 個禁止屬性。實驗結果如圖5 和圖6 所示，可以看出，在同一網絡數據集中，AS 算法的時間開銷小于AF 算法，AF 算法的時間開銷小于SF 算法，具體地，AS 算法速度比AF 算法快約1.5～2.5 倍，AF 算法 速度比SF 算法快約2～4 倍。

圖5 loc-Gowalla 和DBLP 上3 種算法的時間開銷Fig.5 Time cost of three algorithms on loc-Gowalla and DBLP

圖6 Youtube 和SocPokec 上3 種算法的時間開銷Fig.6 Time cost of three algorithms on Youtube and SocPokec

實驗3對比不同worker 節點數量下SF、AF 和AS 算法的時間開銷。

采用Docker虛擬化技術進行搭建，模擬3個worker節點數目不同的Spark 分布式集群，其中worker節點數目分別為2、4、8 和16。本實驗在loc-Gowalla 數據集上進行，屬性條件中搜索的屬性項數量為5，其中包含3個必要屬性和2 個禁止屬性。實驗結果如圖7 所示，可以看出，3 種算法的時間開銷隨著worker節點數目的增多而減小，但最終趨于穩定，這表明，在一定的范圍內，Spark分布式集群提供的計算資源越多，算法的性能就會越好。同時，在這3 種分布式環境下，AS 算法的性能均優于AF 算法，AF 算法的性能均優于SF 算法。

圖7 不同worker 節點數目下3 種算法的時間開銷Fig.7 The time cost of three algorithms under different number of worker nodes

上述實驗結果表明，融合屬性和結構信息的社區搜索算法的性能優于于其他2 種算法，且AS 和AF 算法的時間開銷都與給定的屬性條件相關，算法的時間開銷與網絡規模呈正線性相關，分布式環境提供的計算資源越多，算法的時間開銷越小，但最終將趨于穩定。

4 結束語

針對復雜屬性條件下clique 社區搜索問題求解復雜度高、屬性條件通用性差等問題，本文基于布爾表達式給出復雜屬性條件下的clique社區搜索問題定義，并說明該問題的復雜性。在此基礎上，結合Spark 并行計算框架分別提出結構優先的社區搜索算法和屬性優先的社區搜索算法，并對屬性優先的社區搜索算法進行改進，進一步提出融合屬性和結構的社區搜索算法。該算法在社區搜索過程中同時考慮圖的結構特征和節點的內容屬性，并結合3 種不同的搜索策略大幅減少需要訪問的節點數，從而加快搜索過程。在真實數據集中的實驗結果驗證了所提算法的正確性和有效性。下一步擬基于Spark GraphX 提出一套社區搜索的通用API，以解決復雜屬性條件下社區搜索的通用問題，而不僅限于clique 結構，同時還使算法能夠處理k-core、k-truss 和用戶自定義的結構。