基于屬性相似性的極大團(tuán)?

周翠蓮

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

基于屬性相似性的極大團(tuán)?

周翠蓮

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

極大團(tuán)枚舉是圖論中一個基本問題，且在生活中具有廣泛的應(yīng)用。但一直以來，關(guān)于極大團(tuán)的研究主要集中在圖的拓?fù)浣Y(jié)構(gòu)上，而較少關(guān)注頂點(diǎn)上的信息。論文定義一種結(jié)合圖的結(jié)構(gòu)和屬性相似性的極大團(tuán)，SA-clique，并提出了它的應(yīng)用場景。針對該SA-clique查詢，論文提出一種其充分利用等價點(diǎn)剪枝策略有效求解算法SCQuery。通過實(shí)驗(yàn)證明該算法具有較高的效率。

極大團(tuán)；屬性信息；相似性

1 引言

一直以來，極大團(tuán)枚舉一直是學(xué)術(shù)界的研究熱點(diǎn)問題之一，特別是大數(shù)據(jù)時代的到來，它在各個領(lǐng)域都發(fā)揮著重要的作用。例如，在社交網(wǎng)絡(luò)分析［1］、行為和認(rèn)知網(wǎng)絡(luò)中的結(jié)構(gòu)學(xué)習(xí)［2］和恐怖模式的發(fā)現(xiàn)［3］、金融網(wǎng)絡(luò)中的統(tǒng)計(jì)分析［4］、動態(tài)網(wǎng)絡(luò)圖聚類［5］，以及在生物計(jì)算領(lǐng)域中蛋白質(zhì)相互作用的發(fā)現(xiàn)［6］等等。

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

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

圖1 社交關(guān)系網(wǎng)絡(luò)

本文將具體闡述SA-clique的概念，和具體的應(yīng)用場景，并提出一種等價點(diǎn)剪枝策略的極大緊密團(tuán)查詢算法SCQuery。通過實(shí)驗(yàn)結(jié)果進(jìn)一步分析參數(shù)c和算法運(yùn)行時間的關(guān)系，算法的效率問題。

2 相關(guān)工作

極大團(tuán)枚舉工作一直是學(xué)術(shù)界關(guān)注的熱點(diǎn)，其研究成果也很多。Tomita等［4］很早就提出枚舉極大團(tuán)的時間復(fù)雜度的問題，并證明在給定一個具有n個結(jié)點(diǎn)和m條邊的圖中，最壞情況下枚舉出極大團(tuán)的時間復(fù)雜度是O(3n/3)，因?yàn)樵趎個頂點(diǎn)的圖中，至多存在3n/3個極大團(tuán)。接著Jeffrey等［5］在Tomita基礎(chǔ)上又證明能在多項(xiàng)式時間內(nèi)枚舉出極大團(tuán)。

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

而本文提出的基于頻繁屬性集的極大緊密團(tuán)，是結(jié)合結(jié)構(gòu)特征和頂點(diǎn)屬性兩個方面進(jìn)行的，旨在發(fā)現(xiàn)圖中頂點(diǎn)屬性集盡量相似的極大團(tuán)，這個相似性本文使用固定參數(shù)c去控制，從而使得同一團(tuán)內(nèi)的頂點(diǎn)不光從結(jié)構(gòu)上保持強(qiáng)連通性，從頂點(diǎn)屬性上也能保持盡量相同。和文獻(xiàn)［6］Top-k屬性差異的q-clique查詢極大團(tuán)比較，文獻(xiàn)［7］查詢旨在發(fā)現(xiàn)圖中屬性差異較大的極大團(tuán)，而SA-clique是發(fā)現(xiàn)圖中屬性值盡量相同的極大團(tuán)，所以SA-clique頂點(diǎn)屬性上更為一致，具有更高的相似性。而文獻(xiàn)［11］是將屬性轉(zhuǎn)化成圖中的結(jié)點(diǎn)，使得屬性和結(jié)構(gòu)統(tǒng)一，再使用統(tǒng)一度量方式劃分，保證同一簇里面的結(jié)點(diǎn)屬性值盡量相似，這里盡量相似具有不確定性，因?yàn)樗鼪]有一個指標(biāo)去控制。而本文SA-clique不僅能夠使得同一極大團(tuán)中的屬性值盡量相似，還通過閾值保證了相同屬性值的相似性。

3 SA-clique模型

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

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

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

其中，其中s是頂點(diǎn)r1值為1而頂點(diǎn)r2值為1的數(shù)目。易知，極大團(tuán)的density一直為1。所以極大團(tuán)的相似性取決于頂點(diǎn)屬性的相似性。

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

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

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

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

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

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

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

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

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

證明：存在 similarity(v1)≥c，由于 v2是v1的等價 點(diǎn) ，即 ?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也是相似的，它們的頂點(diǎn)集合也是相似的。

4 算法

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

算法SCQuery具體執(zhí)行過程如算法1所示。

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

輸入：候選集合cand，初始化為G的頂點(diǎn)集V

給定參數(shù)c

當(dāng)前已選集合snodes

輸出：存儲極大緊密團(tuán)集合mc

1. if cand=?

2. if snodesQ?mc

3. mc←snodes

4. return

5. if snodes！=?

6. calculate候選集合cand中的等價點(diǎn)

7. 將等價點(diǎn)從cand中刪除，加入snodes

8. while cand！=?

8. if cand∈mc return

9. Q=cand中相似性最大的頂點(diǎn)

12. cand=cand-Q

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

14. snodes add Q

15. candq=cand∩Q的鄰居節(jié)點(diǎn)

16. SCQuery（candq，c，snodes）

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

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)環(huán)境

本文的算法采用C++實(shí)現(xiàn)，實(shí)驗(yàn)平臺是C++開發(fā)工具Visual Studio 2010和圖分析庫SNAP（Stanford Network Analysis Platform）。所有實(shí)驗(yàn)都是在一臺PC機(jī)上運(yùn)行的，PC機(jī)的配置如下：處理器Intel雙核，3.0GHz，內(nèi)存4GB，Windows7操作系統(tǒng)。

5.2 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)使用DBLP數(shù)據(jù)集。從數(shù)據(jù)集中抽取出作者發(fā)表論文信息，建立作者合作關(guān)系圖，圖中頂點(diǎn)作者，邊代表作者之間存在合著文獻(xiàn)的關(guān)系，頂點(diǎn)上的屬性是作者論文列表。

5.3 算法效率分析

本文通過設(shè)置不同的參數(shù)進(jìn)行實(shí)驗(yàn)對比，比較算法的效率。

通過實(shí)驗(yàn)結(jié)果對比圖可以發(fā)現(xiàn)，圖2（a）隨著圖的大小不斷增大，算法的運(yùn)行時間是不斷提高的，這是因?yàn)橐幚淼挠?jì)算量越來越大。而通過圖2（b）發(fā)現(xiàn)，相似性和算法效率成反比，參數(shù)c設(shè)置的越大反而算法的運(yùn)行時間越短。因?yàn)閷?shí)際上在作者合作關(guān)系網(wǎng)絡(luò)中，作家合著的文獻(xiàn)數(shù)是較低的，當(dāng)參數(shù)c的值越高，滿足SA-clique的候選集越少。

圖2 DBLP-Papers數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對比

6 結(jié)語

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

［1］Wasserman，F(xiàn)aust.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日

周翠蓮，女，碩士，研究方向：數(shù)據(jù)挖掘和圖挖掘。