融合結(jié)構(gòu)-屬性交互二部圖隨機游走的社區(qū)搜索方法*

李 舉，馬慧芳,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)用場景的不斷豐富，用戶往往不需要對整個圖進(jìn)行劃分，而僅需要提供樣例節(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)用具有重要意義。

基于隨機游走的改進(jìn)方法因為能夠找到與查詢節(jié)點緊密相連的社區(qū)而被廣泛應(yīng)用。代表性工作包括：Tong等人[7]提出了重啟隨機游走RWR(Random Walk with Restart)，該方法通過改進(jìn)傳統(tǒng)的隨機游走方法，得到了針對查詢節(jié)點的其他節(jié)點的重要性排名向量，該向量能較好地提高社區(qū)搜索結(jié)果的質(zhì)量。然而這種方法忽略了對節(jié)點的屬性信息的分析，使得社區(qū)搜索結(jié)果的可解釋性欠佳。越來越多的社區(qū)搜索改進(jìn)方法將屬性信息納入到搜索過程中來改善其在屬性圖上的表現(xiàn)。這類方法[8 - 11]通常通過節(jié)點的屬性信息來計算節(jié)點相似度，之后基于屬性相似度和特定的拓?fù)浣Y(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ū)的劃分基準(zhǔn)，因此著眼于圖中整體社區(qū)劃分的優(yōu)劣，忽略了單個社區(qū)的好壞。電導(dǎo)值是對單個社區(qū)的密集程度進(jìn)行評定，不考慮對整個圖的影響，因此借助電導(dǎo)值能夠發(fā)現(xiàn)更具有代表性的個性化社區(qū)。

綜上所述，以社區(qū)擴展為策略的有效屬性網(wǎng)絡(luò)社區(qū)搜索方法已經(jīng)被深入研究，而基于隨機游走的屬性網(wǎng)絡(luò)社區(qū)搜索的方法依舊稀少。這是因為在屬性網(wǎng)絡(luò)上進(jìn)行隨機游走有以下挑戰(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 準(zhǔn)備知識

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ū)搜索的目標(biāo)是查找包含查詢節(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ǔ)上的改進(jìn)。步行者從圖中的某個節(jié)點出發(fā)，每一步跳轉(zhuǎn)面臨2個選擇，隨機跳轉(zhuǎn)到相鄰節(jié)點，或者返回開始節(jié)點。經(jīng)過迭代到達(dá)平穩(wěn)，平穩(wěn)后得到的概率分布可被看作是受開始節(jié)點影響的重要性分布。具體地，重啟隨機游走公式定義如式(1)所示：

(1)

電導(dǎo)是測定圖中一組頂點的緊密程度的常見指標(biā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ù)字標(biāo)號的圓形代表節(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)移矩陣中僅包含拓?fù)浣Y(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é)點進(jìn)行跳轉(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)，通過擲硬幣的方式來進(jìn)行跳轉(zhuǎn)，如果硬幣正面朝上，則依照屬性圖的拓?fù)浣Y(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)移矩陣僅包含拓?fù)浣Y(jié)構(gòu)的轉(zhuǎn)移概率，要在結(jié)構(gòu)-屬性二部圖上進(jìn)行結(jié)構(gòu)-屬性隨機游走需要將屬性信息添加到轉(zhuǎn)移矩陣中，其定義如下：

定義2(屬性-結(jié)構(gòu)轉(zhuǎn)移矩陣R) 基于網(wǎng)絡(luò)拓?fù)浣Y(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é)點進(jìn)行跳轉(zhuǎn)時的選擇過程。每一次擲硬幣的行為之間相互獨立；從節(jié)點跳轉(zhuǎn)到屬性，再由屬性跳轉(zhuǎn)到節(jié)點，這2個跳轉(zhuǎn)過程也相互獨立。以下給出概率轉(zhuǎn)移矩陣R的跳轉(zhuǎn)機制的證明：

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

若硬幣反面朝上，則以1-β的概率在結(jié)構(gòu)-屬性二部圖上進(jìn)行跳轉(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)隨機游走的改進(jìn)，將屬性信息和結(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ū)自然也就越準(zhǔn)確。綜上所述，采用電導(dǎo)值衡量社區(qū)的內(nèi)聚性和分離性是準(zhǔn)確且有效的。雖然該方法有效地通過結(jié)構(gòu)信息解決了局部社區(qū)的定位問題，但是該方法僅考慮到結(jié)構(gòu)上的內(nèi)聚性，直接應(yīng)用到屬性網(wǎng)絡(luò)會因為缺少屬性信息的支撐而導(dǎo)致局部社區(qū)的不準(zhǔn)確性。因此，本文提出融合屬性的電導(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中的每一個分?jǐn)?shù)值除以其對應(yīng)節(jié)點的度得到rank(vi)并進(jìn)行降序排列，計算公式如式(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進(jìn)行降序排序；

步驟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是初步準(zhǔn)備工作。步驟5中的β取值0.5為最優(yōu)，這是因為在構(gòu)造轉(zhuǎn)移矩陣Rn×n時，需要通過β來衡量結(jié)構(gòu)信息和屬性信息的重要性，而結(jié)構(gòu)信息和屬性信息占比過少或過多都會使得結(jié)果社區(qū)不準(zhǔn)確，在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首先將得分向量中的每一個分?jǐn)?shù)值通過式(14)計算其對應(yīng)的排名，其中vol(vi)表示第i個節(jié)點的度；之后將rank(vi)的值大小進(jìn)行降序排列；然后按照次序?qū)⒎謹(jǐn)?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é)點的重要性分?jǐn)?shù)值，故而要執(zhí)行n次；其二，因為需要遍歷Nodelist，將其中每個節(jié)點加入社區(qū)來計算電導(dǎo)值，且Nodelist的最大長度為n，故而要執(zhí)行n次。該方法總體需要的時間復(fù)雜度是O(iterations+2n)。

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

為了驗證本文方法的有效性，設(shè)計實驗進(jìn)行驗證。首先介紹實驗所需的數(shù)據(jù)集；其次在實驗設(shè)置中給出本文方法評價指標(biāo)并介紹對比方法；最后對實驗結(jié)果進(jìn)行分析，并結(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ù)集上進(jìn)行了大量的實驗以評估本文方法的有效性。真實數(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ū)之間的屬性有差異。為了提高實驗的準(zhǔn)確度，在以上4個數(shù)據(jù)集上的每一個真實局部社區(qū)都隨機采樣50個節(jié)點作為查詢節(jié)點，分別對50個查詢節(jié)點所得到的評價標(biāo)準(zhǔn)取平均值作為最終結(jié)果。

4.2 實驗設(shè)置

4.2.1 評價指標(biāo)

為了衡量方法的有效性，采用召回率(recall)，精確率(precision)和F1-socre作為評價指標(biāo)，具體定義如式(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個評價指標(biāo)的取值都在0～1，且數(shù)值越大代表著方法的性能越佳。

文獻(xiàn)[12]提出了衡量局部社區(qū)中屬性內(nèi)聚性的評價指標(biāo)CMF(Community Member Frequency) 來衡量屬性社區(qū)中的屬性內(nèi)聚性。本文定義改進(jìn)后的屬性內(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é)點進(jìn)行排名并得到掃描集合，最后分別采用傳統(tǒng)電導(dǎo)值(RWR-C)和融合屬性的電導(dǎo)值(RWR-AC)對集合的電導(dǎo)值進(jìn)行計算，將電導(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種搜索標(biāo)準(zhǔn)對社區(qū)搜索的準(zhǔn)確度，將本文方法與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ū)搜索的需要。而本文方法將屬性信息融合到隨機游走起到了顯著的改進(jìn)作用。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)移矩陣；然后通過改進(jìn)后的重啟隨機游走得到查詢節(jié)點的得分向量；最后基于融合屬性的電導(dǎo)率定位查詢節(jié)點所在的社區(qū)。通過在4個數(shù)據(jù)集上的實驗表明了本文方法的有效性。