李 舉，馬慧芳,2，李青青，宿 云

(1.西北師范大學(xué)計算機科學(xué)與工程學(xué)院，甘肅 蘭州 730070;2.桂林電子科技大學(xué)廣西可信軟件重點實驗室,廣西 桂林 541004)

1 引言

屬性網(wǎng)絡(luò)是真實世界關(guān)系的自然表示形式，本質(zhì)上是攜帶屬性信息的節(jié)點借助特定關(guān)系相互連接形成的圖。已有研究發(fā)現(xiàn)：現(xiàn)實世界的網(wǎng)絡(luò)中存在明顯的“社區(qū)”特性，即社區(qū)結(jié)構(gòu)滿足社區(qū)內(nèi)連接盡可能稠密且屬性相似，而社區(qū)間連接則盡可能稀疏且屬性盡可能相異[1,2]。近年來，面向?qū)傩跃W(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)引起了廣泛關(guān)注，這類方法往往需要利用異構(gòu)數(shù)據(jù)信息間的互補特性，是圖挖掘研究中最重要的問題之一[3-5]。隨著圖規(guī)模的不斷增大與現(xiàn)實世界應(yīng)用場景的不斷豐富，用戶往往不需要對整個圖進行劃分，而僅需要提供樣例節(jié)點表征興趣從而定位局部社區(qū)，這使得基于用戶個性化要求的社區(qū)搜索任務(wù)備受關(guān)注[6]。尋找用于屬性網(wǎng)絡(luò)的有效、可行的社區(qū)搜索方法是一個很重要的課題，其難點在于如何利用屬性探索更符合社區(qū)語義主題的密集子圖。 例如，在科學(xué)家合作網(wǎng)絡(luò)中，以某個科學(xué)家作為查詢節(jié)點執(zhí)行社區(qū)搜索任務(wù)，挖掘出的關(guān)系子圖是與該科學(xué)家有相同研究領(lǐng)域且合作密切的同事，此類語義的社區(qū)可以為以該科學(xué)家為中心的科研討論提供成員推薦建議。若邀請的同事彼此熟識(結(jié)構(gòu)相似)且具有相似科研興趣(屬性相似)，那么就有更大的可能性成功組織該討論。再比如在社交網(wǎng)絡(luò)中，以某個用戶作為查詢節(jié)點的社區(qū)發(fā)現(xiàn)可以定位該用戶的潛在朋友。如果推薦的潛在用戶與查詢用戶興趣相似度大，則很有可能挖掘到查詢用戶的潛在朋友。這種類型的社區(qū)搜索對于諸如推薦系統(tǒng)等實際應(yīng)用具有重要意義。

基于隨機游走的改進方法因為能夠找到與查詢節(jié)點緊密相連的社區(qū)而被廣泛應(yīng)用。代表性工作包括：Tong等人[7]提出了重啟隨機游走RWR(Random Walk with Restart)，該方法通過改進傳統(tǒng)的隨機游走方法，得到了針對查詢節(jié)點的其他節(jié)點的重要性排名向量，該向量能較好地提高社區(qū)搜索結(jié)果的質(zhì)量。然而這種方法忽略了對節(jié)點的屬性信息的分析，使得社區(qū)搜索結(jié)果的可解釋性欠佳。越來越多的社區(qū)搜索改進方法將屬性信息納入到搜索過程中來改善其在屬性圖上的表現(xiàn)。這類方法[8 - 11]通常通過節(jié)點的屬性信息來計算節(jié)點相似度，之后基于屬性相似度和特定的拓撲結(jié)構(gòu)2類約束從查詢節(jié)點擴展社區(qū)。例如：ACQ(Attributed Community Query)[12]是一種基于社區(qū)擴展方法的屬性社區(qū)搜索算法，其主要是通過將k-core作為結(jié)構(gòu)性約束來找到與查詢節(jié)點屬性相關(guān)度高的社區(qū)。Andersen等人[13]提出一種基于PageRank-Nibble的方法完成社區(qū)搜索任務(wù)并證明了其可行性，該方法通過最小化電導(dǎo)值探索社區(qū)。電導(dǎo)值由將局部社區(qū)與外界的連邊數(shù)比上局部社區(qū)度數(shù)和外部社區(qū)度數(shù)兩者之中的最小值得到。模塊度被作為圖中所有社區(qū)的劃分基準，因此著眼于圖中整體社區(qū)劃分的優(yōu)劣，忽略了單個社區(qū)的好壞。電導(dǎo)值是對單個社區(qū)的密集程度進行評定，不考慮對整個圖的影響，因此借助電導(dǎo)值能夠發(fā)現(xiàn)更具有代表性的個性化社區(qū)。

綜上所述，以社區(qū)擴展為策略的有效屬性網(wǎng)絡(luò)社區(qū)搜索方法已經(jīng)被深入研究，而基于隨機游走的屬性網(wǎng)絡(luò)社區(qū)搜索的方法依舊稀少。這是因為在屬性網(wǎng)絡(luò)上進行隨機游走有以下挑戰(zhàn)：(1)如何將屬性信息融合到隨機游走的過程中；(2)如何利用隨機游走得到的重要性得分向量查找社區(qū)。針對以上2個挑戰(zhàn)，本文提出了融合結(jié)構(gòu)-屬性交互二部圖的隨機游走的社區(qū)搜索方法SAR-AC(Structure Attribute Random walk-Attribute Conductance)和適用于屬性圖社區(qū)搜索的電導(dǎo)值。首先，設(shè)計了由屬性圖構(gòu)造結(jié)構(gòu)-屬性交互二部圖的方法；其次，給出了融合結(jié)構(gòu)信息和屬性信息的轉(zhuǎn)移矩陣的構(gòu)造方法和融合屬性的跳轉(zhuǎn)機制；再次，通過優(yōu)化傳統(tǒng)的電導(dǎo)函數(shù)將其應(yīng)用在了屬性圖的社區(qū)搜索任務(wù)中；最后，通過充分的實驗表明了本文提出的局部社區(qū)搜索方法的可行性和融合屬性信息的電導(dǎo)值對社區(qū)搜索的有效性。

2 準備知識

2.1 符號介紹與問題定義

設(shè)G=(V,E,F)表示屬性網(wǎng)絡(luò)，其中V={v1,v2,…,vn}表示節(jié)點集合，E?V×V表示邊集，F(xiàn)={f1,f2,…,fm}表示屬性集。矩陣An×n為結(jié)構(gòu)鄰接關(guān)系矩陣，若節(jié)點vi與節(jié)點vj有邊，則Aij=1,否則Aij=0。矩陣Qn×m表示節(jié)點-屬性關(guān)系矩陣，若節(jié)點vi具有屬性fj，則Qij=1,否則Qij=0，Qi是節(jié)點vi的屬性向量。設(shè)G對應(yīng)的真實社區(qū)集合為C={C1,C2,…,Cd}，Ci表示某特定社區(qū)，且Ci∩Cj=?，C1∪…∪Cd=V。

給定查詢節(jié)點vi，社區(qū)搜索的目標是查找包含查詢節(jié)點vi的社區(qū)Ci。設(shè)D表示社區(qū)搜索算法返回的社區(qū)，D中的節(jié)點應(yīng)具有緊密的結(jié)構(gòu)鏈接性，且節(jié)點屬性應(yīng)與查詢節(jié)點包含的屬性高度相關(guān)。算法的有效性可由Ci與D之間的相似性評價。

本文使用的具體符號及其含義如表1所示。

Table 1 Notations and their meanings

2.2 重啟隨機游走與電導(dǎo)值

重啟隨機游走方法是在傳統(tǒng)隨機游走方法基礎(chǔ)上的改進。步行者從圖中的某個節(jié)點出發(fā)，每一步跳轉(zhuǎn)面臨2個選擇，隨機跳轉(zhuǎn)到相鄰節(jié)點，或者返回開始節(jié)點。經(jīng)過迭代到達平穩(wěn)，平穩(wěn)后得到的概率分布可被看作是受開始節(jié)點影響的重要性分布。具體地，重啟隨機游走公式定義如式(1)所示：

(1)

電導(dǎo)是測定圖中一組頂點的緊密程度的常見指標。傳統(tǒng)的電導(dǎo)度量定義如式(2)所示：

(2)

其中，|φ(D)|表示社區(qū)D與外部連接的邊數(shù)，vol(D)表示社區(qū)D中節(jié)點的度數(shù)和，vol(V)-vol(D)表示圖中去除社區(qū)中節(jié)點的剩余節(jié)點的度數(shù)和。

3 融合結(jié)構(gòu)-屬性的社區(qū)搜索方法

盡管傳統(tǒng)的重啟隨機游走在普通網(wǎng)絡(luò)上的社區(qū)搜索效果良好，但在屬性圖上的社區(qū)搜索結(jié)果卻差強人意。屬性作為屬性圖中描述節(jié)點的關(guān)鍵信息，在包含屬性的社區(qū)搜索過程中需要著重考慮。因此在執(zhí)行重啟隨機游走前，需要將屬性信息融入概率轉(zhuǎn)移矩陣中并且利用屬性信息優(yōu)化電導(dǎo)值，以精確地定位社區(qū)。本節(jié)首先介紹了結(jié)構(gòu)-屬性交互二部圖并給出了在二部圖上的跳轉(zhuǎn)機制和轉(zhuǎn)移矩陣，其目的是將屬性信息融入到隨機游走的過程中；之后提出了基于融合結(jié)構(gòu)-屬性的隨機游走和融合屬性信息的電導(dǎo)值的社區(qū)搜索方法SAR-AC。

3.1 結(jié)構(gòu)-屬性交互二部圖

為了能夠在隨機游走的過程中加入屬性信息，需要重構(gòu)跳轉(zhuǎn)機制及其轉(zhuǎn)移矩陣。將節(jié)點與屬性的鏈接關(guān)系構(gòu)成的圖視為結(jié)構(gòu)-屬性交互二部圖。首先，將給定網(wǎng)絡(luò)中的節(jié)點和屬性分為2個類別的節(jié)點；其次，將節(jié)點與其對應(yīng)的屬性節(jié)點連邊。具體定義如下：

定義1(結(jié)構(gòu)-屬性交互二部圖)SAG=(V∪F,ESAG)，其中ESAG?V×F。則節(jié)點-屬性關(guān)系矩陣Qn×m即對應(yīng)于該二部圖的鄰接矩陣Qn×m。對于?vi∈V，?fj∈F,若節(jié)點vi與屬性fj存在連邊(即節(jié)點vi邊包含屬性fj),則Qij=1，否則Qij=0。

結(jié)構(gòu)-屬性交互二部圖能夠直觀地展示節(jié)點與屬性的關(guān)系，如圖1所示，為結(jié)構(gòu)-屬性二部圖的構(gòu)造過程。帶有數(shù)字標號的圓形代表節(jié)點，灰色條形中的f1～f4代表節(jié)點所附著的屬性。由屬性圖可知節(jié)點1上附著的屬性是f2，f3，f4。由定義1，節(jié)點1和f2，f3，f4應(yīng)有連邊。將屬性圖中的節(jié)點與其包含的屬性相連即可構(gòu)造出結(jié)構(gòu)-屬性二部圖。

Figure 1 Construction process of structure-attribute bipartite graph

傳統(tǒng)的隨機游走機制在轉(zhuǎn)移矩陣中僅包含拓撲結(jié)構(gòu)上的轉(zhuǎn)移概率，而本文將屬性信息納入了轉(zhuǎn)移矩陣中，這使得步行者不僅僅在節(jié)點之間跳轉(zhuǎn)，還可能存在“節(jié)點-屬性-節(jié)點”的跳轉(zhuǎn)方式。值得注意的是，在“節(jié)點-屬性-節(jié)點”的跳轉(zhuǎn)方式上，起始節(jié)點可能最終會跳轉(zhuǎn)到其非鄰居節(jié)點上。這是由于這2個節(jié)點都擁有相同的屬性，可能屬于同一社區(qū)，因此這種跳轉(zhuǎn)是合理的。如圖1所示，以節(jié)點1為起始節(jié)點進行跳轉(zhuǎn)，通過擲硬幣的方式來介紹跳轉(zhuǎn)機制。如果硬幣正面朝上，則由節(jié)點1跳轉(zhuǎn)到節(jié)點2；如果硬幣反面朝上，則由節(jié)點1跳轉(zhuǎn)到f4,再由f4跳轉(zhuǎn)到節(jié)點3。

假設(shè)從任意節(jié)點vi∈V開始跳轉(zhuǎn)，通過擲硬幣的方式來進行跳轉(zhuǎn)，如果硬幣正面朝上，則依照屬性圖的拓撲結(jié)構(gòu)跳轉(zhuǎn)到相鄰的節(jié)點上：

(3)

如果硬幣反面朝上，依照給定的結(jié)構(gòu)-屬性交互二部圖以一定概率隨機跳轉(zhuǎn)到節(jié)點上附著的屬性集中的任意節(jié)點。然后再任意跳轉(zhuǎn)到包含這個屬性的節(jié)點上。

(4)

(5)

在硬幣反面朝上的情況中，“節(jié)點-屬性-節(jié)點”的跳轉(zhuǎn)滿足式(6)定義的結(jié)構(gòu)-屬性二部圖轉(zhuǎn)移矩陣Sn×n：

S=DvQDaQT

(6)

(7)

由于傳統(tǒng)的隨機游走中的轉(zhuǎn)移矩陣僅包含拓撲結(jié)構(gòu)的轉(zhuǎn)移概率，要在結(jié)構(gòu)-屬性二部圖上進行結(jié)構(gòu)-屬性隨機游走需要將屬性信息添加到轉(zhuǎn)移矩陣中，其定義如下：

定義2(屬性-結(jié)構(gòu)轉(zhuǎn)移矩陣R) 基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)所構(gòu)成的概率轉(zhuǎn)移矩陣和融合結(jié)構(gòu)和屬性的2階段的概率轉(zhuǎn)移矩陣構(gòu)成屬性-結(jié)構(gòu)轉(zhuǎn)移矩陣R，構(gòu)造方法如式(8)和式(9)所示：

(8)

(9)

假設(shè)：通過擲硬幣的方式模擬從網(wǎng)絡(luò)中的任意節(jié)點進行跳轉(zhuǎn)時的選擇過程。每一次擲硬幣的行為之間相互獨立；從節(jié)點跳轉(zhuǎn)到屬性，再由屬性跳轉(zhuǎn)到節(jié)點，這2個跳轉(zhuǎn)過程也相互獨立。以下給出概率轉(zhuǎn)移矩陣R的跳轉(zhuǎn)機制的證明：

證明若硬幣正面朝上，則以β概率在拓撲結(jié)構(gòu)網(wǎng)絡(luò)上進行跳轉(zhuǎn)：

若硬幣反面朝上，則以1-β的概率在結(jié)構(gòu)-屬性二部圖上進行跳轉(zhuǎn)：

則從節(jié)點vi跳轉(zhuǎn)到vj的概率為：

□

3.2 結(jié)構(gòu)-屬性二部圖的社區(qū)搜索方法

缺失屬性信息是基于傳統(tǒng)隨機游走的社區(qū)搜索在屬性圖上效果不理想的根本原因，因此如何將屬性信息的作用在隨機游走中發(fā)揮出來是一個值得研究的問題?；谠诮Y(jié)構(gòu)-屬性交互二部圖上的跳轉(zhuǎn)機制和轉(zhuǎn)移矩陣，本節(jié)首先給出了融合結(jié)構(gòu)-屬性的隨機游走定義，之后給出了融合結(jié)構(gòu)和屬性的并行電導(dǎo)，最后提出了結(jié)構(gòu)-屬性二部圖的社區(qū)搜索方法。

定義3(融合結(jié)構(gòu)-屬性的隨機游走) 融合結(jié)構(gòu)-屬性的隨機游走是對傳統(tǒng)隨機游走的改進，將屬性信息和結(jié)構(gòu)信息融合成為轉(zhuǎn)移矩陣Rn×n，具體的公式定義如下：

rt+1=α×R×rt+(1-α)×q

(10)

為了能夠找到社區(qū)內(nèi)部連接緊密、外部連接稀疏的社區(qū)，Andersen等人[13]采取最小化電導(dǎo)值的方法確定社區(qū)。傳統(tǒng)的電導(dǎo)函數(shù)(2.2節(jié))利用社區(qū)與外部連接邊數(shù)比上社區(qū)節(jié)點度數(shù)總和與外部未探測區(qū)域度數(shù)總和之間的最小值來作為界定社區(qū)內(nèi)聚性優(yōu)劣的閾值。電導(dǎo)值越小，則說明局部社區(qū)與外部連接越稀疏，且內(nèi)部連接越緊密，因此找到的局部社區(qū)自然也就越準確。綜上所述，采用電導(dǎo)值衡量社區(qū)的內(nèi)聚性和分離性是準確且有效的。雖然該方法有效地通過結(jié)構(gòu)信息解決了局部社區(qū)的定位問題，但是該方法僅考慮到結(jié)構(gòu)上的內(nèi)聚性，直接應(yīng)用到屬性網(wǎng)絡(luò)會因為缺少屬性信息的支撐而導(dǎo)致局部社區(qū)的不準確性。因此，本文提出融合屬性的電導(dǎo)值的計算方法如下所示：

屬性相似度矩陣Pn×n，Pij表示的是節(jié)點vi和節(jié)點vj的相似度值。采用Jaccard計算任意2個節(jié)點的屬性相似度，具體計算如式(11)所示:

(11)

其中,⊙表示2個向量做元素乘積計算，即相應(yīng)位置相乘?！琎i‖0表示向量Qi的0-范數(shù),即向量中非零元素的個數(shù)。

融合結(jié)構(gòu)和屬性信息的并行割定義如式(12)所示：

(12)

由并行割的定義可得知結(jié)合結(jié)構(gòu)和屬性的并行電導(dǎo)公式如式(13)所示：

(13)

為了能夠合理地定位社區(qū)，首先將迭代后的得分向量r中的每一個分數(shù)值除以其對應(yīng)節(jié)點的度得到rank(vi)并進行降序排列，計算公式如式(14)所示：

(14)

假設(shè)得到的排列為rank(v1),rank(v2),…,rank(vk),定義掃描集合大小為從1到k的集合：Vj={v1,v2,…,vj},1≤j≤k。掃描所有的集合，并為每個集合計算電導(dǎo)值，最后將電導(dǎo)值最小的集合作為結(jié)果社區(qū)D返回。

融合結(jié)構(gòu)-屬性交互二部圖隨機游走的社區(qū)搜索方法大致包括以下步驟，首先通過輸入的屬性圖構(gòu)造結(jié)構(gòu)-屬性二部圖；之后通過融合結(jié)構(gòu)-屬性的隨機游走機制得到查詢節(jié)點的得分向量；最后通過最小化融合結(jié)構(gòu)和屬性信息的電導(dǎo)公式找到結(jié)果社區(qū)。本文方法的流程如算法1所示。

算法1結(jié)構(gòu)-屬性二部圖社區(qū)搜索方法

輸入:屬性網(wǎng)絡(luò)G=(V,E,F)，查詢節(jié)點q，重要性調(diào)節(jié)參數(shù)α，β,最大迭代次數(shù)iterations，相似度閾值λ。

輸出:結(jié)果社區(qū)D。

步驟1構(gòu)建鄰接矩陣An×n，節(jié)點-屬性關(guān)系矩陣Qn×m,初始化Nodelist為空集，初始化G[Vi]為空集；

步驟4利用式(6)構(gòu)造結(jié)構(gòu)-屬性二部圖轉(zhuǎn)移矩陣Sn×n；

步驟5利用式(8)構(gòu)造融合結(jié)構(gòu)和屬性信息的轉(zhuǎn)移矩陣Rn×n；

步驟6whilet

rt+1=α×R×rt+(1-α)×q;

t=t+1；

rt=rt+1;}

endwhile

步驟7 fori←0 tondo

ifr[i] >λ

Nodelist←r[i]

endif

endfor

步驟8通過Nodelist[i]/vol[i]的大小對Nodelist進行降序排序；

步驟9 fori=startpostoNodelist.lengthdo

G[Vi]←Nodelist[0]～Nodelist[i];

記錄Con(G[Vi]);

endfor

步驟10將Con(G[Vi])值最小的G[Vi]作為結(jié)果社區(qū)D并返回。

具體來說，步驟1～步驟5是初步準備工作。步驟5中的β取值0.5為最優(yōu)，這是因為在構(gòu)造轉(zhuǎn)移矩陣Rn×n時，需要通過β來衡量結(jié)構(gòu)信息和屬性信息的重要性，而結(jié)構(gòu)信息和屬性信息占比過少或過多都會使得結(jié)果社區(qū)不準確，在4.3.1節(jié)中的實驗中可以看出β取0.5時，結(jié)果最優(yōu)。步驟6是融合結(jié)構(gòu)-屬性的隨機游走。步驟7篩選出了高得分的節(jié)點，λ的最優(yōu)取值隨著數(shù)據(jù)集的不同而不同，其中r[i]是指第i個節(jié)點的得分值。步驟7～步驟10首先將得分向量中的每一個分數(shù)值通過式(14)計算其對應(yīng)的排名，其中vol(vi)表示第i個節(jié)點的度；之后將rank(vi)的值大小進行降序排列；然后按照次序?qū)⒎謹?shù)值變動的節(jié)點依次加入到局部社區(qū)中并計算其對應(yīng)的電導(dǎo)值；最后將電導(dǎo)值最小的局部社區(qū)作為結(jié)果社區(qū)返回。

該方法的時間復(fù)雜度分為執(zhí)行隨機游走部分和社區(qū)搜索部分。第1部分的時間復(fù)雜度為O(iterations)，第2部分的時間復(fù)雜度為O(n+n),其一，因為要篩選節(jié)點的重要性分數(shù)值，故而要執(zhí)行n次；其二，因為需要遍歷Nodelist，將其中每個節(jié)點加入社區(qū)來計算電導(dǎo)值，且Nodelist的最大長度為n，故而要執(zhí)行n次。該方法總體需要的時間復(fù)雜度是O(iterations+2n)。

4 實驗結(jié)果及分析

為了驗證本文方法的有效性，設(shè)計實驗進行驗證。首先介紹實驗所需的數(shù)據(jù)集；其次在實驗設(shè)置中給出本文方法評價指標并介紹對比方法；最后對實驗結(jié)果進行分析，并結(jié)合案例分析闡釋本文方法的有效性。實驗環(huán)境采用內(nèi)存為16 GB，CPU為Intel i7-8750H Core 2.67 GHz,GPU為NVIDIA RTX2070，操作系統(tǒng)為Windows 10的計算機。所有代碼都是使用Python 3.7實現(xiàn)。

4.1 實驗數(shù)據(jù)集

本文在真實和人工數(shù)據(jù)集上進行了大量的實驗以評估本文方法的有效性。真實數(shù)據(jù)集包括Cora和Citeseer。這2個數(shù)據(jù)集都是經(jīng)典的引文網(wǎng)絡(luò)數(shù)據(jù)集。其中節(jié)點代表的是論文，邊代表的是論文之間的引用關(guān)系，節(jié)點上的屬性是與論文相對應(yīng)的關(guān)鍵詞，根據(jù)關(guān)鍵詞的不同可將論文分類到不同社區(qū)。具體描述如表2所示。

Table 2 Statistics of real-world datasets

人工數(shù)據(jù)集是使用LFR benchmark生成的LFR-1和LFR-2。參數(shù)符號的含義如表3所示。其中參數(shù)的設(shè)置如下：

Table 3 LFR parameters and their meanings

在人工數(shù)據(jù)集的每個真實社區(qū)中，為節(jié)點隨機地附著相似的屬性，且保證2個社區(qū)之間的屬性有差異。為了提高實驗的準確度，在以上4個數(shù)據(jù)集上的每一個真實局部社區(qū)都隨機采樣50個節(jié)點作為查詢節(jié)點，分別對50個查詢節(jié)點所得到的評價標準取平均值作為最終結(jié)果。

4.2 實驗設(shè)置

4.2.1 評價指標

為了衡量方法的有效性，采用召回率(recall)，精確率(precision)和F1-socre作為評價指標，具體定義如式(15)～式(17)所示：

(15)

(16)

(17)

其中，CT表示的是查詢節(jié)點所屬的真實社區(qū)，CF代表的是本文方法檢測出的社區(qū)。recall指的是方法返回的正確的社區(qū)節(jié)點的個數(shù)占真實社區(qū)節(jié)點個數(shù)的比例。precision指的是方法返回的正確的社區(qū)節(jié)點的個數(shù)占其返回節(jié)點總數(shù)的比例。F1-score是召回率和精確率的調(diào)和平均數(shù)。以上3個評價指標的取值都在0～1，且數(shù)值越大代表著方法的性能越佳。

文獻[12]提出了衡量局部社區(qū)中屬性內(nèi)聚性的評價指標CMF(Community Member Frequency) 來衡量屬性社區(qū)中的屬性內(nèi)聚性。本文定義改進后的屬性內(nèi)聚性CMF-S(CMF-Single)如式(18)所示：

(18)

其中，F(xiàn)N(q)是節(jié)點q攜帶的屬性集，fh是社區(qū)D中包含第h個屬性的節(jié)點個數(shù)。CMF-S的取值在0～1，其值越大說明社區(qū)的屬性內(nèi)聚性越好。

4.2.2 對比方法

實驗的主要對比方法有2類，包括本文方法的變種和其他方法。

為了比較融合屬性電導(dǎo)值和傳統(tǒng)電導(dǎo)值對結(jié)果社區(qū)質(zhì)量的影響，采用本文方法的變種方法SAR-C作為對比方法，該方法的隨機游走方法與本文相同，但基于傳統(tǒng)電導(dǎo)值獲取社區(qū)。

為了比較隨機游走方法對結(jié)果社區(qū)質(zhì)量的影響采用RWR-C和RWR-AC作為對比方法。這2種方法是在無屬性圖上的社區(qū)搜索方法，這2種方法首先通過重啟隨機游走RWR得到圖中節(jié)點的重要性排名，之后使用與本文相同的策略對節(jié)點進行排名并得到掃描集合，最后分別采用傳統(tǒng)電導(dǎo)值(RWR-C)和融合屬性的電導(dǎo)值(RWR-AC)對集合的電導(dǎo)值進行計算，將電導(dǎo)值最小的集合作為結(jié)果社區(qū)返回。

為了說明本文方法的有效性，采用ACQ[12]作為對比方法，該方法是一種在屬性圖上的社區(qū)搜索方法，返回同時滿足結(jié)構(gòu)內(nèi)聚性(即節(jié)點之間緊密連接)和關(guān)鍵詞內(nèi)聚性(即社區(qū)內(nèi)的節(jié)點共享相同的關(guān)鍵詞)的屬性社區(qū)。

4.3 實驗結(jié)果與相關(guān)分析

4.3.1 參數(shù)對實驗的影響

本節(jié)將探索重要性調(diào)節(jié)參數(shù)對社區(qū)結(jié)果的影響。采取固定一個參數(shù)，調(diào)節(jié)另一個參數(shù)數(shù)值的方法來得到參數(shù)對社區(qū)結(jié)果的影響。為了能夠有效地測試出參數(shù)對測試方法性能的影響，α取0.5。在真實和人工數(shù)據(jù)集上的實驗結(jié)果如圖2所示。

Figure 2 Influence of β on SAR-AC performance

從圖2可以看出，重要性參數(shù)會影響結(jié)果社區(qū)的性能。在2個數(shù)據(jù)集上的實驗結(jié)果表明，在屬性(或者結(jié)構(gòu)信息)占有極端小的比例時，SAR-AC的性能并不好，而在結(jié)構(gòu)和屬性信息各占一半的時候，SAR-AC的性能最好。這是因為SAR-AC在構(gòu)建轉(zhuǎn)移矩陣時同時考慮了結(jié)構(gòu)和屬性信息。如果結(jié)構(gòu)信息占比過高，則查找出的節(jié)點大多與查詢節(jié)點屬性相似度低，這導(dǎo)致結(jié)果社區(qū)在結(jié)構(gòu)上緊湊而在屬性上稀疏；如果屬性信息占比過高，又會導(dǎo)致查詢過于精確而使得查詢得到的節(jié)點較少，故而導(dǎo)致SAR-AC效果不好。由圖2可以看出，在2類信息的占比均接近一半時，SAR-AC的效果最佳，這也符合結(jié)構(gòu)信息和屬性信息在屬性社區(qū)搜索過程中互補的特征。

4.3.2 2種電導(dǎo)值的比較

本節(jié)揭示了融合屬性的電導(dǎo)值和傳統(tǒng)電導(dǎo)值在屬性圖上社區(qū)搜索中的差異。為了能夠清晰地辨識出2種搜索標準對社區(qū)搜索的準確度，將本文方法與SAR-C、RWR-C和RWR-AC的結(jié)果作對比，如表4所示。

Table 4 Influence of conductance on each method performance

由表4可以看出，SAR-AC在2個數(shù)據(jù)集上的表現(xiàn)都優(yōu)于SAR-C。這是因為屬性社區(qū)是由節(jié)點之間的公共偏好和關(guān)系共同組成的，這意味著僅僅考慮結(jié)構(gòu)信息的社區(qū)搜索方法不能夠滿足屬性社區(qū)搜索的需要。而本文方法將屬性信息融合到隨機游走起到了顯著的改進作用。RWR-C和RWR-AC的召回率都較小且相同，這是由于RWR的轉(zhuǎn)移矩陣中沒有融合屬性信息，故而找到的正確節(jié)點較少。而引入融合電導(dǎo)值的RWR-AC的精確率有明顯升高，這是由于融合屬性的電導(dǎo)值有效過濾了那些與查詢節(jié)點屬性同質(zhì)性低的節(jié)點。

圖3展示了4種方法的結(jié)果社區(qū)的CMF-S值，該值越大則說明社區(qū)的屬性內(nèi)聚性越高。從圖3中可以看到,SAR-AC的效果最好，而SAR-C由于劃分社區(qū)時忽略了屬性信息而導(dǎo)致屬性內(nèi)聚性偏低。同樣地，RWR-AC考慮了屬性信息，因此屬性內(nèi)聚性略優(yōu)于RWR-C。

Figure 3 Comparison of the attributes cohesion in local community

4.3.3 與其它方法的比較

本節(jié)通過SAR-AC與RWR-C和ACQ的比較來驗證本文方法的有效性。表5列出了3種方法在3個數(shù)據(jù)集上的實驗結(jié)果，其中粗體字表示最佳性能。

Table 5 Comparison with other methods

從表5中可以看出，考慮了屬性信息的方法具有最佳性能，本文方法表現(xiàn)最佳。RWR-C是不考慮屬性信息的社區(qū)搜索方法；ACQ雖然考慮了節(jié)點的屬性信息，但是僅僅考慮了局部社區(qū)屬性同質(zhì)性最大的情況。SAR-AC既考慮了節(jié)點屬性信息，又匯聚了節(jié)點與屬性的跳轉(zhuǎn)關(guān)系。實驗結(jié)果不僅展現(xiàn)了本文方法的有效性，而且還說明了加入“節(jié)點-屬性-節(jié)點”跳轉(zhuǎn)機制對社區(qū)搜索效果的優(yōu)化作用。

4.4 案例分析

為了能夠更好地說明本文方法的有效性，本節(jié)比較了SAR-AC和SAR-C在數(shù)據(jù)集Cora上的社區(qū)搜索結(jié)果，結(jié)果如圖4所示。其中黑色節(jié)點是查詢節(jié)點，淺灰色節(jié)點集是查找到的局部社區(qū)，白色節(jié)點是其它社區(qū)節(jié)點，圖4a和圖4b的查詢節(jié)點是一樣的，因為大小問題，僅展示了全部結(jié)果圖的一部分。從圖4中可以看出，SAR-C和SAR-AC尋找的結(jié)果社區(qū)都大致符合局部社區(qū)的特征，然而SAR-C的結(jié)果社區(qū)包含數(shù)量較多的無關(guān)節(jié)點。從圖4b中可以看出，這些無關(guān)節(jié)點大多是邊界節(jié)點。該類節(jié)點與真實社區(qū)的屬性交互較稀疏，所以將其劃分到了結(jié)果社區(qū)中，但是這類節(jié)點與真實社區(qū)節(jié)點的屬性同質(zhì)性并不高，所以采用傳統(tǒng)的電導(dǎo)率方法無法將其與真實社區(qū)分割。但是，在圖4a中，融合屬性的電導(dǎo)值可以有效地過濾這些邊界節(jié)點。

Figure 4 Local communities discovered by SAR-AC and SAR-C

5 結(jié)束語

針對現(xiàn)有的基于隨機游走的社區(qū)搜索方法忽略了屬性信息的問題，本文提出了一種融合了結(jié)構(gòu)-屬性交互二部圖隨機游走的社區(qū)搜索方法。首先通過節(jié)點與屬性的關(guān)系構(gòu)造結(jié)構(gòu)-屬性交互二部圖，重構(gòu)轉(zhuǎn)移矩陣；然后通過改進后的重啟隨機游走得到查詢節(jié)點的得分向量；最后基于融合屬性的電導(dǎo)率定位查詢節(jié)點所在的社區(qū)。通過在4個數(shù)據(jù)集上的實驗表明了本文方法的有效性。