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

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

1 引言

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

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

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

2 準(zhǔn)備知識(shí)

2.1 符號(hào)介紹與問(wèn)題定義

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

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

本文使用的具體符號(hào)及其含義如表1所示。

Table 1 Notations and their meanings

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

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

(1)

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

(2)

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

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

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

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

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

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

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

Figure 1 Construction process of structure-attribute bipartite graph

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

假設(shè)從任意節(jié)點(diǎn)vi∈V開(kāi)始跳轉(zhuǎn)，通過(guò)擲硬幣的方式來(lái)進(jìn)行跳轉(zhuǎn)，如果硬幣正面朝上，則依照屬性圖的拓?fù)浣Y(jié)構(gòu)跳轉(zhuǎn)到相鄰的節(jié)點(diǎn)上：

(3)

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

(4)

(5)

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

S=DvQDaQT

(6)

(7)

由于傳統(tǒng)的隨機(jī)游走中的轉(zhuǎn)移矩陣僅包含拓?fù)浣Y(jié)構(gòu)的轉(zhuǎn)移概率，要在結(jié)構(gòu)-屬性二部圖上進(jìn)行結(jié)構(gòu)-屬性隨機(jī)游走需要將屬性信息添加到轉(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è)：通過(guò)擲硬幣的方式模擬從網(wǎng)絡(luò)中的任意節(jié)點(diǎn)進(jìn)行跳轉(zhuǎn)時(shí)的選擇過(guò)程。每一次擲硬幣的行為之間相互獨(dú)立；從節(jié)點(diǎn)跳轉(zhuǎn)到屬性，再由屬性跳轉(zhuǎn)到節(jié)點(diǎn)，這2個(gè)跳轉(zhuǎn)過(guò)程也相互獨(dú)立。以下給出概率轉(zhuǎn)移矩陣R的跳轉(zhuǎn)機(jī)制的證明：

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

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

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

□

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

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

定義3(融合結(jié)構(gòu)-屬性的隨機(jī)游走) 融合結(jié)構(gòu)-屬性的隨機(jī)游走是對(duì)傳統(tǒng)隨機(jī)游走的改進(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é)點(diǎn)度數(shù)總和與外部未探測(cè)區(qū)域度數(shù)總和之間的最小值來(lái)作為界定社區(qū)內(nèi)聚性優(yōu)劣的閾值。電導(dǎo)值越小，則說(shuō)明局部社區(qū)與外部連接越稀疏，且內(nèi)部連接越緊密，因此找到的局部社區(qū)自然也就越準(zhǔn)確。綜上所述，采用電導(dǎo)值衡量社區(qū)的內(nèi)聚性和分離性是準(zhǔn)確且有效的。雖然該方法有效地通過(guò)結(jié)構(gòu)信息解決了局部社區(qū)的定位問(wèn)題，但是該方法僅考慮到結(jié)構(gòu)上的內(nèi)聚性，直接應(yīng)用到屬性網(wǎng)絡(luò)會(huì)因?yàn)槿鄙賹傩孕畔⒌闹味鴮?dǎo)致局部社區(qū)的不準(zhǔn)確性。因此，本文提出融合屬性的電導(dǎo)值的計(jì)算方法如下所示：

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

(11)

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

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

(12)

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

(13)

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

(14)

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

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

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

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

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

步驟1構(gòu)建鄰接矩陣An×n，節(jié)點(diǎn)-屬性關(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通過(guò)Nodelist[i]/vol[i]的大小對(duì)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并返回。

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

該方法的時(shí)間復(fù)雜度分為執(zhí)行隨機(jī)游走部分和社區(qū)搜索部分。第1部分的時(shí)間復(fù)雜度為O(iterations)，第2部分的時(shí)間復(fù)雜度為O(n+n),其一，因?yàn)橐Y選節(jié)點(diǎn)的重要性分?jǐn)?shù)值，故而要執(zhí)行n次；其二，因?yàn)樾枰闅vNodelist，將其中每個(gè)節(jié)點(diǎn)加入社區(qū)來(lái)計(jì)算電導(dǎo)值，且Nodelist的最大長(zhǎng)度為n，故而要執(zhí)行n次。該方法總體需要的時(shí)間復(fù)雜度是O(iterations+2n)。

4 實(shí)驗(yàn)結(jié)果及分析

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

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

本文在真實(shí)和人工數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn)以評(píng)估本文方法的有效性。真實(shí)數(shù)據(jù)集包括Cora和Citeseer。這2個(gè)數(shù)據(jù)集都是經(jīng)典的引文網(wǎng)絡(luò)數(shù)據(jù)集。其中節(jié)點(diǎn)代表的是論文，邊代表的是論文之間的引用關(guān)系，節(jié)點(diǎn)上的屬性是與論文相對(duì)應(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ù)符號(hào)的含義如表3所示。其中參數(shù)的設(shè)置如下：

Table 3 LFR parameters and their meanings

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

4.2 實(shí)驗(yàn)設(shè)置

4.2.1 評(píng)價(jià)指標(biāo)

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

(15)

(16)

(17)

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

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

(18)

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

4.2.2 對(duì)比方法

實(shí)驗(yàn)的主要對(duì)比方法有2類，包括本文方法的變種和其他方法。

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

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

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

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

4.3.1 參數(shù)對(duì)實(shí)驗(yàn)的影響

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

Figure 2 Influence of β on SAR-AC performance

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

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

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

Table 4 Influence of conductance on each method performance

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

圖3展示了4種方法的結(jié)果社區(qū)的CMF-S值，該值越大則說(shuō)明社區(qū)的屬性內(nèi)聚性越高。從圖3中可以看到,SAR-AC的效果最好，而SAR-C由于劃分社區(qū)時(shí)忽略了屬性信息而導(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é)通過(guò)SAR-AC與RWR-C和ACQ的比較來(lái)驗(yàn)證本文方法的有效性。表5列出了3種方法在3個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，其中粗體字表示最佳性能。

Table 5 Comparison with other methods

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

4.4 案例分析

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

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

5 結(jié)束語(yǔ)

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