李青青，馬慧芳，2，李 舉，李志欣，姜彥斌

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

1 引言

作為分析復(fù)雜系統(tǒng)本質(zhì)和功能的有力表示，圖可以建模各種復(fù)雜系統(tǒng)單元之間的交互關(guān)系.其中節(jié)點(diǎn)表示復(fù)雜系統(tǒng)單元，邊表示節(jié)點(diǎn)間潛在結(jié)構(gòu)和交互規(guī)則.此外，節(jié)點(diǎn)往往可以與大量屬性相關(guān)聯(lián)，描述節(jié)點(diǎn)的特定特征并提供與網(wǎng)絡(luò)拓?fù)湔坏挠袃r(jià)值的信息［1，2］.作為網(wǎng)絡(luò)分析中的一個(gè)基本問(wèn)題，社區(qū)搜索旨在挖掘與用戶(hù)給定查詢(xún)節(jié)點(diǎn)相關(guān)聯(lián)的局部社區(qū)［3］.與社區(qū)檢測(cè)［4］不同，社區(qū)搜索將個(gè)性化需求整合到社區(qū)搜索過(guò)程中在特定用戶(hù)挖掘［5］、蛋白分析網(wǎng)絡(luò)［6］等任務(wù)中具有廣泛的應(yīng)用前景.

傳統(tǒng)的社區(qū)搜索方法主要集中于普通圖（無(wú)屬性）［7～9］.隨著現(xiàn)實(shí)世界屬性信息的激增，屬性可作為輔助信息潛在的提高社區(qū)搜索的準(zhǔn)確性.早期的屬性社區(qū)搜索方法將屬性視為同等重要，旨在通過(guò)屬性相似性找到包含查詢(xún)節(jié)點(diǎn)的局部?jī)?nèi)聚社區(qū).如Leman等人［10］提出的基于屬性圖的無(wú)參數(shù)化方法，即PICS（Parameter-free Identification of Cohesive Subgroups），將所有屬性視為節(jié)點(diǎn)來(lái)挖掘局部社區(qū).Shang等人［11］設(shè)計(jì)了既能反映網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)關(guān)系也能包含屬性相似性的TA-graph來(lái)檢測(cè)局部社區(qū).但高維的屬性信息使得這類(lèi)方法的存儲(chǔ)開(kāi)銷(xiāo)加劇.因此，有研究人員指出查詢(xún)節(jié)點(diǎn)所攜帶的核心屬性足以指導(dǎo)算法挖掘出融合用戶(hù)偏好的個(gè)性化局部社區(qū)［12］.在不影響精確性的前提下，可以使用核心屬性進(jìn)行個(gè)性化屬性社區(qū)搜索.如Huang等人［13］研究了滿(mǎn)足結(jié)構(gòu)內(nèi)聚性k-core和關(guān)鍵字內(nèi)聚性的屬性社區(qū).VAC（Vertex-centric Attributed Community）［14］旨在挖掘包含查詢(xún)節(jié)點(diǎn)且具有最大屬性得分的連通k-truss.Ye等人［15］通過(guò)引入統(tǒng)計(jì)學(xué)方法來(lái)搜索具有指定屬性的查詢(xún)節(jié)點(diǎn)所在社區(qū).同時(shí)，目標(biāo)社區(qū)發(fā)現(xiàn)方法也因其能捕獲個(gè)性化需求而被廣泛研究.如Perozzi等人［16］提出了面向用戶(hù)的屬性圖挖掘方法，利用焦點(diǎn)屬性以提取目標(biāo)社區(qū)與離群點(diǎn).TSCM（Target Subspace and Communities Mining）［17］通過(guò)屬性子空間來(lái)定位和挖掘目標(biāo)社區(qū).盡管以上方法緩解了存儲(chǔ)開(kāi)銷(xiāo)，但大多數(shù)方法均僅能定位查詢(xún)節(jié)點(diǎn)所在社區(qū)，未整合用戶(hù)偏好到社區(qū)搜索過(guò)程以挖掘融合用戶(hù)偏好的多社區(qū)且精準(zhǔn)定位與社區(qū)中成員緊密連接但屬性偏離其社區(qū)成員的節(jié)點(diǎn).此外，盡管部分方法考慮了整合用戶(hù)偏好到社區(qū)搜索過(guò)程中，但仍需用戶(hù)提供足夠多的查詢(xún)節(jié)點(diǎn)來(lái)幫助算法捕獲用戶(hù)偏好，具有靈活性不足且不切合實(shí)際的局限性.

針對(duì)以上問(wèn)題，提出了屬性網(wǎng)絡(luò)中結(jié)合用戶(hù)偏好的社區(qū)搜索和離群點(diǎn)檢測(cè)方法（Incorporating user Preference for Community Search and Outlier detection in attributed network，IPCSO）.具體地，通過(guò)編碼查詢(xún)節(jié)點(diǎn)鄰域網(wǎng)絡(luò)中節(jié)點(diǎn)屬性和結(jié)構(gòu)間關(guān)系來(lái)捕獲潛在社區(qū)成員.其次，定義平均劃分相似度來(lái)挖掘?qū)傩宰涌臻g，并將其作為用戶(hù)偏好來(lái)指導(dǎo)社區(qū)搜索過(guò)程.最后，將屬性子空間蘊(yùn)含的重要信息融入到網(wǎng)絡(luò)中，并采用結(jié)構(gòu)凝聚力約束k-core和屬性?xún)?nèi)聚性約束fractional-core來(lái)搜索網(wǎng)絡(luò)中的多社區(qū)并檢測(cè)離群點(diǎn).多種真實(shí)網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上的廣泛實(shí)驗(yàn)證明了本文方法的有效性和效率.

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

2.1 符號(hào)說(shuō)明與問(wèn)題定義

給定無(wú)向加權(quán)屬性圖G=（V，E，T，W），其中V=｛vi｝i=1，…，n表示圖中節(jié)點(diǎn)集且|V|=n；E?V×V表示邊集且|E|=m.屬性集為T(mén)=｛ti｝i=1，…，d，|T|=d.設(shè)節(jié)點(diǎn)屬性矩陣為F∈Rn×d，fTi表示節(jié)點(diǎn)vi的屬性向量.權(quán)重矩陣記為W∈Rn×n，其中wij=cos（fi，fj）表示邊（vi，vj）的權(quán)重.設(shè)用戶(hù)給定的查詢(xún)節(jié)點(diǎn)集為Q=｛qi｝i=1，…，s，Q?V.屬性約束fractional-core的閾值為w，結(jié)構(gòu)約束k-core的閾值為k.IPCSO的目標(biāo)是找到目標(biāo)社區(qū)集C=｛Ci｝i=1，…，l和離群點(diǎn)集O=｛Oi｝i=1，…，b，滿(mǎn)足：（1）社區(qū)內(nèi)緊密連接；（2）在屬性上與用戶(hù)偏好（屬性子空間）一致；（3）找到偏離屬性約束的社區(qū)內(nèi)成員（離群點(diǎn)）.具體地，本文方法的問(wèn)題定義如下：（1）輸入：屬性圖G=（V，E，T，W），用戶(hù)提供的查詢(xún)節(jié)點(diǎn)集合Q，屬性約束閾值w以及結(jié)構(gòu)約束閾值k.（2）輸出：融合用戶(hù)偏好的社區(qū)集C與離群點(diǎn)集O.

2.2 結(jié)合用戶(hù)偏好的社區(qū)搜索和離群點(diǎn)檢測(cè)基本框架

本文提出的方法框架如圖1所示：在給定屬性網(wǎng)絡(luò)G=（V，E，T，W），查詢(xún)節(jié)點(diǎn)集Q，結(jié)構(gòu)約束閾值k和屬性約束閾值w的情況下，采用編碼可以顯式建模鄰居之間的交互以突出局部結(jié)構(gòu)內(nèi)的公共屬性，有助于算法挖掘潛在社區(qū)成員.通過(guò)平均劃分相似度獲取每個(gè)屬性的重要性權(quán)重，以此表示用戶(hù)偏好.通過(guò)屬性子空間的指導(dǎo)對(duì)網(wǎng)絡(luò)重加權(quán)，并設(shè)定結(jié)構(gòu)約束及屬性約束檢測(cè)多社區(qū)以及社區(qū)中的離群點(diǎn).接下來(lái)將詳細(xì)介紹該算法.

圖1 結(jié)合用戶(hù)偏好的社區(qū)搜索和離群點(diǎn)檢測(cè)的基本框架

定義1（節(jié)點(diǎn)vi的鄰域網(wǎng)絡(luò)）給定節(jié)點(diǎn)vi，其鄰域網(wǎng)絡(luò)被定義為N（vi）=（VN（vi），EN（vi），TN（vi），WN（vi）），其中節(jié)點(diǎn)集為VN（vi）=｛vw|（vi，vw）∈E｝∪｛vi｝，EN（vi）=｛（vu，vw）|vu∈VN（vi）^vw∈VN（vi）^（vu，vw）∈E｝為 邊 集，TN（vi）表 示VN（vi）的 屬 性 集，TN（vi）?T.WN（vi）∈R|VN(νi)|×|VN(νi)|為EN（vi）的權(quán)重矩陣.

3 結(jié)合用戶(hù)偏好的社區(qū)搜索和離群點(diǎn)檢測(cè)

3.1 編碼節(jié)點(diǎn)屬性和結(jié)構(gòu)

較少的查詢(xún)節(jié)點(diǎn)（例如，一個(gè)查詢(xún)節(jié)點(diǎn)）包含的信息有限，無(wú)法準(zhǔn)確計(jì)算屬性子空間.此外，查詢(xún)節(jié)點(diǎn)間可能沒(méi)有相互作用關(guān)系，無(wú)法保證推斷出的子空間與內(nèi)聚連接相關(guān)聯(lián).針對(duì)此，受CDE模型［18］的啟發(fā)，設(shè)計(jì)了建模查詢(xún)節(jié)點(diǎn)與其鄰居間相互作用及屬性相關(guān)性的方法.該方法可有效地挖掘查詢(xún)節(jié)點(diǎn)所在社區(qū)的潛在成員，將較少的查詢(xún)節(jié)點(diǎn)擴(kuò)展為一組候選查詢(xún)節(jié)點(diǎn).具體地，編碼節(jié)點(diǎn)結(jié)構(gòu)和屬性信息以增強(qiáng)節(jié)點(diǎn)的表示能力，從而避免丟失與查詢(xún)節(jié)點(diǎn)相似的潛在社區(qū)成員信息.因此，盡管給定少量查詢(xún)節(jié)點(diǎn)，查詢(xún)節(jié)點(diǎn)的特征信息仍可保留用以查找與其相似的候選節(jié)點(diǎn).

接下來(lái)將詳細(xì)介紹該策略.首先，編碼節(jié)點(diǎn)結(jié)構(gòu)和屬性相似性mij的公式被定義為：

具體地，首先提取節(jié)點(diǎn)vi的鄰域網(wǎng)絡(luò).然后，利用式（1）對(duì)每個(gè)候選查詢(xún)節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的結(jié)構(gòu)和屬性關(guān)系進(jìn)行編碼.最后，將mij值最大的節(jié)點(diǎn)vj加入候選節(jié)點(diǎn)集中.上述過(guò)程持續(xù)進(jìn)行到候選節(jié)點(diǎn)的數(shù)量大于擴(kuò)展深度h為止.圖2顯示了編碼節(jié)點(diǎn)屬性和結(jié)構(gòu)的過(guò)程，其中邊的粗度表示端點(diǎn)節(jié)點(diǎn)的屬性相似度.設(shè)h=5，v2為用戶(hù)提供的查詢(xún)節(jié)點(diǎn)，首先初始化候選查詢(xún)節(jié)點(diǎn)集Q1=｛v2｝并提取v2的鄰域網(wǎng)絡(luò).其次，通過(guò)式（1）對(duì)查詢(xún)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)間的相似度進(jìn)行編碼，選擇具有最大m2j的節(jié)點(diǎn)vj添加到候選查詢(xún)節(jié)點(diǎn)集中，得Q1=｛v2，v3｝.重復(fù)上述步驟，分別提取v2和v3的鄰域網(wǎng)絡(luò)，計(jì)算v2與其鄰居vj∈VN（v2）間的相似強(qiáng)度m2j，v3與其鄰居va∈VN（v3）間的相似強(qiáng)度m3a，選擇節(jié)點(diǎn)v8加入到候選查詢(xún)節(jié)點(diǎn)集中.上述過(guò)程在候選查詢(xún)節(jié)點(diǎn)個(gè)數(shù)大于5時(shí)停止，最后得候選查詢(xún)節(jié)點(diǎn)集為Q1=｛v1，v2，v3，v4，v8｝.

圖2 編碼節(jié)點(diǎn)屬性和結(jié)構(gòu)策略的示例

3.2 基于平均劃分相似度挖掘?qū)傩宰涌臻g

本節(jié)設(shè)計(jì)了一種屬性子空間推斷方法，該方法適用于衡量真實(shí)社區(qū)中屬性的重要性.首先通過(guò)擴(kuò)展后的查詢(xún)節(jié)點(diǎn)集來(lái)提取用戶(hù)所關(guān)注的核心屬性，隨后根據(jù)核心屬性集挖掘用戶(hù)所聚焦的屬性子空間，以此來(lái)指導(dǎo)算法挖掘融合用戶(hù)偏好的社區(qū).特別地，基于距離屬性劃分方法［19，20］的潛在含義，同一社區(qū)中的屬性應(yīng)產(chǎn)生相似的劃分，存在一些由屬性定義的劃分與實(shí)際節(jié)點(diǎn)所屬社區(qū)一致.首先根據(jù)候選查詢(xún)節(jié)點(diǎn)集將其中節(jié)點(diǎn)所攜帶的屬性提取為核心屬性集Tcore，Tcore?T.對(duì)于?ti∈Tcore，由屬性ti劃分的節(jié)點(diǎn)集V表示為V/ti=｛Ci，Γi｝，Ci表示包含屬性ti的節(jié)點(diǎn)集，Γi表示不包含屬性ti的節(jié)點(diǎn)集，且Ci∪Γi=V.

定義2（劃分熵）給定屬性ti∈Tcore，設(shè)屬性ti的劃分為V/ti=｛Ci，Γi｝.P（Ci）表示包含屬性ti的節(jié)點(diǎn)集合的概率，則屬性ti的劃分熵E（ti）定義為：

定義3（劃分條件熵）給定核心屬性ti，tj∈Tcore，設(shè)屬性ti和tj的劃分分別為V/ti=｛Ci，Γi｝，V/tj=｛Cj，Γj｝.則核心屬性tj關(guān)于屬性ti的劃分條件熵CEti(tj)定義為：

定義4（劃分聯(lián)合熵）給定核心屬性ti，tj∈Tcore，核心屬性ti和tj的劃分聯(lián)合熵E（ti，tj）定義為：

定義5（屬性劃分距離）劃分V/ti和V/tj的屬性劃分距離d（V/ti，V/tj）為：

定義6（歸一化屬性劃分相似度）為了便于度量屬性劃分的相似性，對(duì)屬性劃分距離進(jìn)行歸一化并將其轉(zhuǎn)化為屬性劃分相似度：

值得注意的是，式（6）的分母不能為零，所以不會(huì)出現(xiàn)未定義的情況.此外，由于式（6）的分母總是大于分子，因此不會(huì)因?yàn)榉帜高^(guò)大而放小比值.

由上可知，平均劃分相似度可形式化為：

定義7（平均劃分相似度）給定屬性ti，tj∈Tcore，屬性ti的平均劃分相似度定義為：

APS衡量劃分相似度差異性，可表示選用某一屬性ti進(jìn)行劃分與其他屬性進(jìn)行劃分的相異程度.屬性ti的APS值越大，則表明選用屬性ti劃分所得的社區(qū)與其他屬性劃分所得社區(qū)的相似程度越高.用向量τ來(lái)表示屬性子空間，其元素值計(jì)算如下：

元素τi表示對(duì)應(yīng)屬性ti在屬性子空間中的重要性或與查詢(xún)節(jié)點(diǎn)的相關(guān)性，若屬性ti∈Tcore，則屬性子空間中元素設(shè)為APS（ti），否則，將其在屬性子空間下的重要性設(shè)為0.

3.3 編碼節(jié)點(diǎn)屬性和結(jié)構(gòu)

3.3.1 網(wǎng)絡(luò)重加權(quán)

屬性子空間可幫助用戶(hù)探索在核心屬性上內(nèi)聚的社區(qū)，通過(guò)重加權(quán)網(wǎng)絡(luò)將屬性子空間對(duì)屬性的關(guān)注程度融入到整個(gè)網(wǎng)絡(luò)中.首先定義在屬性子空間的指導(dǎo)下重加權(quán)后的權(quán)重矩陣Wτ，Wτ中元素表示節(jié)點(diǎn)vi和vj在屬性子空間下的相似度.具體計(jì)算公式如下：

3.3.2 社區(qū)搜索與離群點(diǎn)檢測(cè)

現(xiàn)有方法常使用k-core［21］，k-truss［22］和k-clique［23］等結(jié)構(gòu)約束來(lái)度量社區(qū)結(jié)構(gòu)的內(nèi)聚性.k-core考慮了圖中節(jié)點(diǎn)的結(jié)構(gòu)內(nèi)聚性，fractional-core［24］不僅考慮了圖中節(jié)點(diǎn)的度，而且也考慮節(jié)點(diǎn)間的連接強(qiáng)度.因此，選用前者來(lái)度量社區(qū)的結(jié)構(gòu)凝聚力，后者度量屬性子空間下端點(diǎn)節(jié)點(diǎn)屬性的凝聚性.具體定義如下：

定義8（k-core［21］）給定一個(gè)正整數(shù)k（k≥0），圖G的k-core表示為Hk，其是圖G的最大子圖，使得?ν∈Hk，degHk(ν)≥k，其中degHK(ν)=|VN(ν)-ν|.

值得注意的是Hk可能不是一個(gè)連通子圖，設(shè)k-core的連通分量為

定義9（fractional-core［24］）給定一個(gè)有理數(shù)w，fractional-core是圖G的最大子圖Hw，Hw中節(jié)點(diǎn)的度都不小于w，即?νi∈Hw，di≥w，其中

IPCSO方法旨在通過(guò)屬性子空間的指導(dǎo)搜索出滿(mǎn)足fractional-core和k-core約束的多社區(qū)，同時(shí)識(shí)別出社區(qū)中的離群點(diǎn)，且所挖掘到的社區(qū)都是最大的.也就是說(shuō)，不存在另一個(gè)滿(mǎn)足結(jié)構(gòu)和屬性?xún)?nèi)聚性約束的社區(qū)C?C'.具體地，首先提取滿(mǎn)足結(jié)構(gòu)約束k-core的所有密集連通子圖作為候選社區(qū).其次，在這些密集連通子圖上設(shè)置屬性約束以滿(mǎn)足屬性?xún)?nèi)聚性.最后，返回滿(mǎn)足結(jié)構(gòu)和屬性約束的社區(qū)，其中不滿(mǎn)足屬性約束的節(jié)點(diǎn)為離群點(diǎn).

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

本節(jié)將通過(guò)實(shí)驗(yàn)驗(yàn)證IPCSO方法的有效性和效率，旨在回答以下三個(gè)研究問(wèn)題.問(wèn)題1：參數(shù)的變化對(duì)于IPCSO方法影響如何？問(wèn)題2：IPCSO方法相比其他基準(zhǔn)方法的性能表現(xiàn)如何？以及問(wèn)題3：IPCSO方法在實(shí)際應(yīng)用中表現(xiàn)如何？

4.1 數(shù)據(jù)集描述

4.1.1 人工數(shù)據(jù)集

為研究IPCSO方法的性能，基于LFR［25］生成了節(jié)點(diǎn)數(shù)為n、屬性數(shù)為d的具有真實(shí)基準(zhǔn)的人工網(wǎng)絡(luò).其中人工網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度數(shù)由davg來(lái)控制，最大度通過(guò)dmax來(lái)設(shè)定.此外，μ控制社區(qū)內(nèi)邊數(shù)與社區(qū)間邊數(shù)的比值.社區(qū)的大小分別通過(guò)參數(shù)cmax和cmin來(lái)控制.給定社區(qū)中所需節(jié)點(diǎn)數(shù)，鄰接矩陣對(duì)角線(xiàn)上定義的塊以0.35的概率隨機(jī)為塊中的每個(gè)元素分配一條邊.對(duì)于非對(duì)角線(xiàn)上的塊，以0.01的概率隨機(jī)分配邊.更進(jìn)一步地，按照均值為［0，1］以及方差控制在0.001范圍內(nèi)的高斯分布來(lái)分配屬性值.較小的方差便于社區(qū)中的節(jié)點(diǎn)包含有核心屬性.其余屬性可從方差較大的正態(tài)分布中提取.離群點(diǎn)可從每個(gè)社區(qū)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)，將其屬性替換為與該社區(qū)屬性差異較大的屬性.經(jīng)過(guò)多次測(cè)試，人工網(wǎng)絡(luò)參數(shù)設(shè)置為：davg=20，dmax=80，cmin=2，cmax=80.具體設(shè)置如表1所示.

表1 人工數(shù)據(jù)集統(tǒng)計(jì)信息

4.1.2 真實(shí)數(shù)據(jù)集

選取了5個(gè)真實(shí)屬性網(wǎng)絡(luò).4Area是計(jì)算機(jī)科學(xué)領(lǐng)域的合著網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示作者，邊表示作者間的合著關(guān)系，屬性表征作者在數(shù)據(jù)庫(kù)、信息檢索和機(jī)器學(xué)習(xí)等方面發(fā)表的會(huì)議.YouTube是一個(gè)社交網(wǎng)絡(luò)的視頻分享網(wǎng)站，節(jié)點(diǎn)表示用戶(hù)，邊表示友誼關(guān)系，屬性描述用戶(hù)的身份信息.而Disney數(shù)據(jù)集是共同購(gòu)買(mǎi)網(wǎng)絡(luò)，其中節(jié)點(diǎn)為影片，邊表示共同購(gòu)買(mǎi)關(guān)系，每部電影有28個(gè)屬性.由聯(lián)邦能源管理委員會(huì)發(fā)布的Enron中，節(jié)點(diǎn)表示電子郵件地址，電子郵件之間的傳輸關(guān)系記為邊.節(jié)點(diǎn)上攜帶18個(gè)屬性，用于描述郵件的平均內(nèi)容長(zhǎng)度、平均收件人數(shù)量等信息.此外，IMDB（Internet Movie Date-Base）數(shù)據(jù)集中節(jié)點(diǎn)表示電影，邊表示電影中演員的共同參演關(guān)系.具體統(tǒng)計(jì)數(shù)據(jù)如表2所示.

表2 真實(shí)數(shù)據(jù)集統(tǒng)計(jì)信息

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

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

為評(píng)估IPCSO方法在屬性圖上的有效性，采用Precision和CAS（Community Attribute Similarity）［14］來(lái)度量社區(qū)的質(zhì)量.設(shè)算法搜索到的社區(qū)為C，基準(zhǔn)社區(qū)為C'，則Precision=|C'∩C|||C，其他評(píng)價(jià)指標(biāo)定義如下：

定義10（CAS）CAS度量社區(qū)C中的屬性凝聚力，形式上：

其中T（vi）為節(jié)點(diǎn)vi所攜帶的屬性集合.CAS值越高，屬性?xún)?nèi)聚性越強(qiáng).

4.2.2 對(duì)比方法

為度量IPCSO方法的性能，選取了以下三類(lèi)方法進(jìn)行對(duì)比.第一，比較本文方法與目標(biāo)社區(qū)發(fā)現(xiàn)方法的性能，選取了FocusCO（Focused Clustering and Outlier）和TSCM.FocusCO為經(jīng)典的目標(biāo)社區(qū)發(fā)現(xiàn)算法之一，TSCM與IPCSO均采用了擴(kuò)展查詢(xún)節(jié)點(diǎn)的策略來(lái)挖掘社區(qū).第二，為研究IPCSO與其他基于結(jié)構(gòu)度量的屬性社區(qū)搜索方法的性能，選擇了ACQ（Attributed Community Query）和VAC-Etruss（Vertex-centric Attributed Community-Etruss）.其中ACQ是具有奠基性的社區(qū)搜索方法之一，而VAC-Ecore（Vertex-centric Attributed Community-Ecore）是以節(jié)點(diǎn)為中心的屬性社區(qū)搜索方法的變體.第三，為了探索IPCSO方法挖掘融合用戶(hù)偏好社區(qū)的有效性，選取了LOCLU（LOcal CLustering Unimodality）方法.

4.3 參數(shù)分析（問(wèn)題1）

本節(jié)將從三方面研究不同參數(shù)設(shè)置對(duì)于IPCSO的影響.探索查詢(xún)節(jié)點(diǎn)個(gè)數(shù)對(duì)于IPCSO的性能影響.研究編碼查詢(xún)節(jié)點(diǎn)結(jié)構(gòu)和屬性策略中超參數(shù)a的選定以及擴(kuò)展深度h的選擇對(duì)于IPCSO的影響.觀(guān)察k和w的變化對(duì)于IPCSO性能的影響.

對(duì)于查詢(xún)節(jié)點(diǎn)個(gè)數(shù)s，從每個(gè)真實(shí)數(shù)據(jù)集中任意選取6個(gè)查詢(xún)節(jié)點(diǎn)，在s取值不同的情況下運(yùn)行方法50次并取其平均值返回結(jié)果.如圖3所示.不同數(shù)據(jù)集上查詢(xún)節(jié)點(diǎn)個(gè)數(shù)的變化對(duì)于本文方法的影響均較小.原因在于IPCSO方法使用較少的查詢(xún)節(jié)點(diǎn)就可以有效的編碼節(jié)點(diǎn)信息以找到潛在社區(qū)成員，有助于增強(qiáng)用戶(hù)偏好以達(dá)到較為精確地搜索結(jié)果.此外，由于所查找社區(qū)的屬性?xún)?nèi)聚性通過(guò)用戶(hù)指定的屬性約束來(lái)控制，故查詢(xún)節(jié)點(diǎn)個(gè)數(shù)的變化對(duì)于CAS的影響較小.

圖3 不同數(shù)據(jù)集上s取值對(duì)應(yīng)的Precision和CAS

圖4展示了編碼查詢(xún)節(jié)點(diǎn)結(jié)構(gòu)和屬性策略中的超參數(shù)a和擴(kuò)展深度h取值的影響.從圖4（a）和圖4（b）均可觀(guān)察到，a和h的增加首先會(huì)帶來(lái)較大的性能提升，但隨著其取值不斷增大會(huì)使得IPCSO的性能下降.a=2時(shí)所有數(shù)據(jù)集上的性能表現(xiàn)較好，當(dāng)a=6時(shí)部分?jǐn)?shù)據(jù)集上的性能下降.這說(shuō)明當(dāng)a設(shè)定為2時(shí)編碼節(jié)點(diǎn)屬性和結(jié)構(gòu)策略足以幫助IPCSO找到候選查詢(xún)節(jié)點(diǎn)集以提取用戶(hù)偏好.當(dāng)h=6時(shí)，較小的數(shù)據(jù)集上的性能達(dá)到了最優(yōu).在較大數(shù)據(jù)集中，h=8時(shí)性能表現(xiàn)最好，之后則出現(xiàn)了性能下降.究其原因在于擴(kuò)展過(guò)深會(huì)使得將不屬于查詢(xún)節(jié)點(diǎn)所在社區(qū)的節(jié)點(diǎn)納入.

圖4 不同數(shù)據(jù)集上a和h取值對(duì)應(yīng)的Precision

圖5給出了結(jié)構(gòu)約束閾值k和屬性約束閾值w分別從8以4的步長(zhǎng)變化到20，0.2以0.2的步長(zhǎng)變化到0.8的結(jié)果.圖5（a）中可觀(guān)察到，k值的增加會(huì)使得算法所找到社區(qū)的結(jié)構(gòu)凝聚性增強(qiáng)，其精度也會(huì)隨之增加.k的大小與返回社區(qū)的大小密切相關(guān).圖5（b）可觀(guān)察到隨著w的增加，算法的精度隨之降低，源于較小的屬性閾值將會(huì)使得所返回社區(qū)的屬性?xún)?nèi)聚性更強(qiáng)，精度更高.但如果將w設(shè)置過(guò)小，算法將會(huì)返回一個(gè)空社區(qū).本文設(shè)置k=8，w=0.7.

圖5 不同數(shù)據(jù)集上k和w取值對(duì)應(yīng)的Precision

4.4 性能比較（問(wèn)題2）

本節(jié)將評(píng)價(jià)IPCSO方法的有效性，觀(guān)察IPCSO方法與基準(zhǔn)方法的性能差異.

表3給出了在不同數(shù)據(jù)集上取4個(gè)查詢(xún)節(jié)點(diǎn)，運(yùn)行100次的平均結(jié)果.從實(shí)驗(yàn)結(jié)果可得，TSCM在所有數(shù)據(jù)集上的表現(xiàn)都優(yōu)于FocusCO.因?yàn)檩^少的查詢(xún)節(jié)點(diǎn)不足以精確地捕獲到用戶(hù)偏好，進(jìn)而使得算法不能準(zhǔn)確定位與查詢(xún)節(jié)點(diǎn)相似的社區(qū)成員.TSCM性能表現(xiàn)雖好，但不足以與IPCSO方法競(jìng)爭(zhēng)，這是由于IPCSO對(duì)社區(qū)內(nèi)聚性的要求更高.由于結(jié)構(gòu)內(nèi)聚性的要求，ACQ和VAC-Ecore在所有數(shù)據(jù)集上的表現(xiàn)均優(yōu)于目標(biāo)社區(qū)發(fā)現(xiàn)方法，且ACQ的CAS高于VAC-Ecore但卻低于IPCSO，原因在于A(yíng)CQ需要用戶(hù)將查詢(xún)節(jié)點(diǎn)所攜帶的屬性作為輸入并返回覆蓋該屬性的社區(qū)，而VAC-Ecore只需要找到屬性得分最小的查詢(xún)節(jié)點(diǎn)所在社區(qū).對(duì)于IPCSO，其返回的社區(qū)均在屬性子空間的指導(dǎo)下，社區(qū)內(nèi)節(jié)點(diǎn)與查詢(xún)節(jié)點(diǎn)具有較大的相似性.LOCLU可與IPCSO方法相媲美，其在所有數(shù)據(jù)集上的表現(xiàn)均優(yōu)于目標(biāo)社區(qū)發(fā)現(xiàn)方法和基于結(jié)構(gòu)度量的方法，但該方法容易將其他社區(qū)節(jié)點(diǎn)囊括在內(nèi).整體而言，IPCSO始終優(yōu)于所有方法.

表3 IPCSO與基線(xiàn)方法的整體性能比較

4.5 案例分析（問(wèn)題3）

本節(jié)將對(duì)比IPCSO和FocusCO在Disney上的運(yùn)行結(jié)果，深入挖掘?qū)嶒?yàn)現(xiàn)象的原因.圖6給出了Disney數(shù)據(jù)集上兩種方法的運(yùn)行結(jié)果：

圖6 IPCSO與FocusCO在Dinsey上的結(jié)果對(duì)比

以影片ID是52和24的節(jié)點(diǎn)為查詢(xún)節(jié)點(diǎn)，使用IPCSO與FocusCO方法分別搜索與ν52和ν24具有相似評(píng)分和價(jià)格的其他節(jié)點(diǎn).結(jié)果如圖6所示.其中紅色節(jié)點(diǎn)ν52和ν24表示用戶(hù)給定的查詢(xún)節(jié)點(diǎn)，綠色節(jié)點(diǎn)表示離群點(diǎn)，算法找到與查詢(xún)節(jié)點(diǎn)相似的節(jié)點(diǎn)用藍(lán)色標(biāo)識(shí).從圖中可觀(guān)察到，F(xiàn)ocusCO檢測(cè)到三個(gè)目標(biāo)社區(qū)，而IPCSO找到了四個(gè)社區(qū).IPCSO發(fā)現(xiàn)的每個(gè)社區(qū)都與用戶(hù)偏好密切相關(guān)，并且精準(zhǔn)的定位到了離群點(diǎn)，而FocusCO由于較少的查詢(xún)節(jié)點(diǎn)使得算法錯(cuò)誤的判別了離群點(diǎn).此外，F(xiàn)ocusCO發(fā)現(xiàn)的社區(qū)的內(nèi)部連接比IPCSO所發(fā)現(xiàn)的社區(qū)連接松散.這是因?yàn)檩^少的查詢(xún)節(jié)點(diǎn)對(duì)于FocusCO方法而言具有較大的局限性，而本文方法對(duì)于查詢(xún)節(jié)點(diǎn)的個(gè)數(shù)不敏感，可通過(guò)較少的查詢(xún)節(jié)點(diǎn)準(zhǔn)確的捕獲到用戶(hù)偏好，從而使得社區(qū)搜索結(jié)果更精確.

5 結(jié)論

在屬性網(wǎng)絡(luò)中結(jié)合用戶(hù)偏好的社區(qū)搜索和離群點(diǎn)檢測(cè)任務(wù)中，基于現(xiàn)有大多數(shù)方法僅利用拓?fù)浣Y(jié)構(gòu)信息且只定位查詢(xún)節(jié)點(diǎn)所在社區(qū)，未整合用戶(hù)偏好到社區(qū)搜索過(guò)程中的局限性，設(shè)計(jì)了面向?qū)傩跃W(wǎng)絡(luò)的融合用戶(hù)偏好的多社區(qū)和離群點(diǎn)檢測(cè)方法.具體地，通過(guò)編碼節(jié)點(diǎn)屬性和結(jié)構(gòu)得到候選查詢(xún)節(jié)點(diǎn)集，利用候選查詢(xún)節(jié)點(diǎn)集所攜帶的屬性為核心屬性設(shè)計(jì)了平均劃分相似度來(lái)挖掘符合用戶(hù)偏好的屬性子空間方法，并設(shè)置結(jié)構(gòu)和屬性約束以搜索內(nèi)聚社區(qū).真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上的實(shí)驗(yàn)證明了本文方法的有效性.