基于屬性相似性的極大團?

周翠蓮

（昆明理工大學信息工程與自動化學院 昆明 650500）

基于屬性相似性的極大團?

周翠蓮

（昆明理工大學信息工程與自動化學院 昆明 650500）

極大團枚舉是圖論中一個基本問題，且在生活中具有廣泛的應用。但一直以來，關于極大團的研究主要集中在圖的拓撲結構上，而較少關注頂點上的信息。論文定義一種結合圖的結構和屬性相似性的極大團，SA-clique，并提出了它的應用場景。針對該SA-clique查詢，論文提出一種其充分利用等價點剪枝策略有效求解算法SCQuery。通過實驗證明該算法具有較高的效率。

極大團；屬性信息；相似性

1 引言

一直以來，極大團枚舉一直是學術界的研究熱點問題之一，特別是大數據時代的到來，它在各個領域都發揮著重要的作用。例如，在社交網絡分析［1］、行為和認知網絡中的結構學習［2］和恐怖模式的發現［3］、金融網絡中的統計分析［4］、動態網絡圖聚類［5］，以及在生物計算領域中蛋白質相互作用的發現［6］等等。

當然，隨著數據信息的急劇增長，也帶來了一系列的挑戰。處理的圖數據不僅結構關系更多，頂點上的屬性信息也越來復雜。傳統的極大團算法往往只考慮圖的結構特性而忽略了圖的頂點信息。如圖1社交關系網絡中，圖中頂點r代表用戶，頂點r上的屬性P是收藏過的網頁，邊代表用戶之間的好友關系。圖1有兩個3-clique，分別是Q1=(r1，r2，r3)，Q2=(r4，r5，r6)。從結構上分析 Q1和Q2都是團，團中的頂點具有強連通性，而從頂點屬性上看，Q2比Q1擁有的相同屬性更多，Q1有的相同屬性是空，而Q2擁有兩個相同屬性P4、P5。表明了現實生活中Q2中的用戶比Q1擁有更多的相似性（具體根據屬性內容決定），關系更緊密，且易從Q2推斷出用戶之間隱藏的關聯信息，比如相似愛好等。

為了更好地解決上述問題，本文提出SA-clique，能夠很好地解釋圖的結構關系和屬性信息。SA-clique是一種結合圖的結構特性和頂點屬性的極大團，它將圖的拓撲結構和頂點上包含的屬性信息緊密關聯起來，即此時的SA-clique既滿足圖的拓撲結構上的強連通性又滿足頂點屬性的相似性。圖1中，從圖的結構特征和頂點屬性上看，Q2和Q3都是團，但Q2中的頂點之間共同屬性值更多。而Q2就是要描述的SA-clique作為一種基于頂點的屬性相似性的極大團查詢，SA-clique枚舉進一步豐富了圖查詢問題。為了有效查詢極大緊密團，本文提出一種利用等價點剪枝策略算法SCQuery。在搜索過程不斷縮小候選集大小，提高算法效率。

圖1 社交關系網絡

本文將具體闡述SA-clique的概念，和具體的應用場景，并提出一種等價點剪枝策略的極大緊密團查詢算法SCQuery。通過實驗結果進一步分析參數c和算法運行時間的關系，算法的效率問題。

2 相關工作

極大團枚舉工作一直是學術界關注的熱點，其研究成果也很多。Tomita等［4］很早就提出枚舉極大團的時間復雜度的問題，并證明在給定一個具有n個結點和m條邊的圖中，最壞情況下枚舉出極大團的時間復雜度是O(3n/3)，因為在n個頂點的圖中，至多存在3n/3個極大團。接著Jeffrey等［5］在Tomita基礎上又證明能在多項式時間內枚舉出極大團。

上述較早的文獻都只關注了圖的結構特性，而忽視了圖的屬性信息。近些年來，隨著圖數據的急劇增長，包含的屬性信息也愈復雜化，具有重要的研究意義。Zhou等［6］提出基于圖結構和屬性上的圖聚類算法SA-Cluster，將屬性轉化成一種附加的結構，使得屬性和結構統一，最終將原圖劃分為K簇并且同一簇中結點屬性值盡可能相同。孫煥良等［7］提出Top-k屬性差異的q-clique查詢，該查詢旨在發現圖中屬性差異較大的極大團。

而本文提出的基于頻繁屬性集的極大緊密團，是結合結構特征和頂點屬性兩個方面進行的，旨在發現圖中頂點屬性集盡量相似的極大團，這個相似性本文使用固定參數c去控制，從而使得同一團內的頂點不光從結構上保持強連通性，從頂點屬性上也能保持盡量相同。和文獻［6］Top-k屬性差異的q-clique查詢極大團比較，文獻［7］查詢旨在發現圖中屬性差異較大的極大團，而SA-clique是發現圖中屬性值盡量相同的極大團，所以SA-clique頂點屬性上更為一致，具有更高的相似性。而文獻［11］是將屬性轉化成圖中的結點，使得屬性和結構統一，再使用統一度量方式劃分，保證同一簇里面的結點屬性值盡量相似，這里盡量相似具有不確定性，因為它沒有一個指標去控制。而本文SA-clique不僅能夠使得同一極大團中的屬性值盡量相似，還通過閾值保證了相同屬性值的相似性。

3 SA-clique模型

定義1（屬性圖） G=(V，E，A)表示一個屬性圖，其中V是無向圖G的頂點集，E?V×V是圖G的邊集，用A表示圖中每個頂點的相關屬性；對于圖G中?v∈V，A(v)表示該頂點的屬性集合，它為一個列表{a1，a2，a3，…，an} ，其中 ai為頂點 v 的一個屬性值。本文使用二元變量表明該屬性值存在的狀態，0表示不存在，1表示存在。

例子1 以圖1為例，圖中每個頂點代表一位用戶，具有“網頁列表”的屬性，圖中邊表示彼此具有好友關系。頂點r1的屬性集合表示為A(r1)={P1，P2}。

定義2（頂點間相似性） 給定圖G=(V，E，A)，圖中具有二元變量屬性值的頂點 r1，r2，且(r1，r2)∈E，則其頂點間的相似性定義成：

其中，其中s是頂點r1值為1而頂點r2值為1的數目。易知，極大團的density一直為1。所以極大團的相似性取決于頂點屬性的相似性。

例子2 以圖1為例，例如圖中團Q=(r1，r2，r3)的頂點集為{r1，r2，r3} ，它的頂點相似性是

定義3（SA-clique） 給定圖 G=(V，E，A)和給定參數c，若圖中頂點集V′頂點間的相似滿足c，且?V″?V∩V′?V″，使得頂點V″導出的子圖上的頂點屬性相似性滿足c，即similarity(V'')≥c，則稱V′為圖G上的SA-clique。

例子3 以圖1為例，自定義c=1，由于頂點集V′={r1，r2} ，有 similarity(V′)=1≥c，又頂點集V′是圖G上的團，則稱V′是圖G上的緊密團。又V″={r1，r2，r3} 的支持度都不滿足 c ，所以V′又是圖G上的SA-clique。

定義4（等價點） 給定圖 G=(V，E，A)，若?A(v1)?A(v2)和 e=(v1，v2)，則稱 v2是 v1的等價點。

定理1：如果V′是圖G上的SA-clique，那么V′任何子集也是相似的。

證明：對于 ?X?V′，由于 V′是圖G上的SA-clique，即有 similarity(V')≥c。因為包含V′的頂點必包含X，所以有similarity(X)≥c成立，即頂點集X是相似的。

定理2：如果頂點集Y在圖G中是非相似的，那么Y的任何超集是非相似的。

證明：反證法。如果?X?Y，且頂點集 X是相似的，根據定理1，Y也是相似。與已知Y為非相似的相矛盾。所以Y的任何超集在圖G上都是非相似的。

定理3：如果v1是相似的，存在v2是v1的等價點，那么v2也是相似的，它們的頂點集合也是相似的。

證明：存在 similarity(v1)≥c，由于 v2是v1的等價 點 ，即 ?A(v1)?A(v2) 且 e=(v1，v2) ，即similarity(v2)≥c ，similarity(v1，v2)=s/|A(r1)∪ A(r2)|=s/|A(r1)|=similarity(v1)≥c，similarity(v1，v2)≥c，所以v2也是相似的，它們的頂點集合也是相似的。

4 算法

在極大緊密團搜索過程中，可以充分利用定理3的性質來縮小候選集的大小，提高算法的效率。假設x是已選頂點集，A(x)是x的屬性集合，而y是候選集中的任意一個頂點，若存在y是x的等價點，則根據定理3知，y和x的頂點集合也是相似的。因此將頂點y從候選集合中刪除，直接合并到已選節點集中。例如圖1社交網絡關系圖，r5，r6彼此之前是等價關系，在搜索過程中，若其中任一頂點是緊密的，則其它也是緊密的，這極大的降低了算法的運算時間。

算法SCQuery具體執行過程如算法1所示。

算法 1：SCQuery（CAND，c，m_Q）

輸入：候選集合cand，初始化為G的頂點集V

給定參數c

當前已選集合snodes

輸出：存儲極大緊密團集合mc

1. if cand=?

2. if snodesQ?mc

3. mc←snodes

4. return

5. if snodes！=?

6. calculate候選集合cand中的等價點

7. 將等價點從cand中刪除，加入snodes

8. while cand！=?

8. if cand∈mc return

9. Q=cand中相似性最大的頂點

12. cand=cand-Q

13. if similarity（snodes，Q）≥c）

14. snodes add Q

15. candq=cand∩Q的鄰居節點

16. SCQuery（candq，c，snodes）

步驟1～4描述當前的候選集cand為空時，表明SA-clique已經出現，此時步驟2判斷該極大緊密團是否被發現，如沒有則加入到SA-clique集合中，搜索結束。若候選集不為空，需對當前的候選集繼續搜索，首先判斷候選集存在與已選集合等價關系的等價點，將它們直接從候選集cand中刪除，加入已選集合中。步驟8～16描述了非等價點的處理，如候選集已經SA-clique則停止搜索，否則從cand任選一頂點賦值給Q，計算已選集合snodes在加入Q后是否相似，若相似，將Q加入snodes中，根據極大團的結構特性計算新的候選集合。否則，返回步驟8，繼續向下搜索。SCQuery的時間復雜度O（n2）。

5 實驗分析

5.1 實驗環境

本文的算法采用C++實現，實驗平臺是C++開發工具Visual Studio 2010和圖分析庫SNAP（Stanford Network Analysis Platform）。所有實驗都是在一臺PC機上運行的，PC機的配置如下：處理器Intel雙核，3.0GHz，內存4GB，Windows7操作系統。

5.2 實驗數據

本文實驗使用DBLP數據集。從數據集中抽取出作者發表論文信息，建立作者合作關系圖，圖中頂點作者，邊代表作者之間存在合著文獻的關系，頂點上的屬性是作者論文列表。

5.3 算法效率分析

本文通過設置不同的參數進行實驗對比，比較算法的效率。

通過實驗結果對比圖可以發現，圖2（a）隨著圖的大小不斷增大，算法的運行時間是不斷提高的，這是因為要處理的計算量越來越大。而通過圖2（b）發現，相似性和算法效率成反比，參數c設置的越大反而算法的運行時間越短。因為實際上在作者合作關系網絡中，作家合著的文獻數是較低的，當參數c的值越高，滿足SA-clique的候選集越少。

圖2 DBLP-Papers數據集實驗結果對比

6 結語

本文提出了一種結合圖的結構特征和頂點上的屬性相似性的極大團SA-clique：圖的結構和頂點屬性滿足一定的緊密性和相似性的。例如圖1枚 舉 出 的 SA-cliqueQ2=(r4，r5，r6) 、比 極 大 團Q1=(r1，r2，r3)成員之間交往的更頻繁和緊密，表明了SA-clique具有重要的實用價值。為了有效枚舉SA-clique，本文提出一種等價點剪枝策略算法SCE-PE，在搜索過程中不僅利用圖的結構特性和Apriori性質減去不能形成極大團的枝，同時利用等價點剪枝策略，減小候選集大小提高算法性能。最后本文利用DBLP-Papers對算法效率進行測試。實驗表明SCQuery能夠有效的枚舉出SA-clique。

［1］Wasserman，Faust.Social Network Analysis：Methods and Applications［J］.American Ethnologist，1997，24（1）：219-220.

［2］H.R.Bernard，P.D.Killworth.Informant Accuracy in Social Network Data iv：A Comparison of Clique-Level Structure in Behavioral and Cognitive Network data［J］.Social Networks，2（3）：191-218，1979.

［3］N.M.Berry，T.H.Ko，T.Moy，J.Smrcka，J.Turnley.Emergent Clique Formation in Terrorist Recruitment［J］.In The AAAI-04 Workshop on Agent Organizations：Theory and Practice，2004.

［4］Boginski V.Statistical Analysis of Financial Networks［J］.Computational Statistics&Data Analysis，2005，48（2）：431-443.

［5］V.Stix.Finding all Maximal Cliques in Dynamic Graphs［J］.Computational Optimization and Applications，2004，27：173-186.

［6］F.N.Abu-Khzam.On the Relative Efficiency of Maximal Clique Enumeration Algorithms，with Applications to High-through Put Computational Biology［C］//In International Conference on Research Trends in Science and Technology，2005.

［7］ Tomita，E.，Tanaka，A.，Takahashi.The Worst-case Time Complexity for Generating all Maximal Cliques and Computational Experiments［J］.Theory.Compute.Sci.，2006，363（1）：28-42.

［8］Chang L，Yu J X，Qin L.Fast Maximal Cliques Enumeration in Sparse Graphs［J］.Algorithmica，2013，66（1）：173-186.

［9］Zhou Yang.Cheng Hong，Yu Jeffrey Xu.Graph Clustering Based on Structural//Attribute Similarities［C］//Proceedings of the VLDB Endowment，2009，2（1）：718-729.

［10］ Sun Huangliang，Lu Zhi.Top-k Attribute Difference q-clique Queries in Graph Data［J］.Chinese Journal of Computes，2012，11：2265-2274.

Maximal Clique Based on Attribute Similarities

ZHOU Cuilian
（Faculty of Information Engineering and Automation，Kunming University of Science and Technology，Kunming 650500）

Maximal clique enumeration is a fundamental problem in graph theory and widely applied to various fields However，many existing graph clustering methods mainly focus on the topological structure，but largely ignore the vertex properties.In this paper，a novel maximal clique，SA-clique，based on both structural and attribute through a attribute similarities measure is proposed，and its application scenarios is present.Meanwhile，an efficient algorithm SCQuery is proposed，which takes full advantage of the equivalent pruning strategy.The efficiency of the algorithm is proved by experiments.

maximal clique，attribute，similarities

TP391

10.3969/j.issn.1672-9722.2017.11.028

Class Number TP391

2017年5月4日，

2017年6月18日

周翠蓮，女，碩士，研究方向：數據挖掘和圖挖掘。