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

（1.西北師范大學計算機科學與工程學院,甘肅蘭州 730070；2.桂林電子科技大學廣西可信軟件重點實驗室,廣西桂林 541004；3.廣西師范大學廣西多源信息挖掘與安全重點實驗室,廣西桂林 541004）

1 引言

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

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

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

2 準備知識

2.1 符號說明與問題定義

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

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

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

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

定義1（節(jié)點vi的鄰域網(wǎng)絡）給定節(jié)點vi，其鄰域網(wǎng)絡被定義為N（vi）=（VN（vi），EN（vi），TN（vi），WN（vi）），其中節(jié)點集為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é)合用戶偏好的社區(qū)搜索和離群點檢測

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

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

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

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

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

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

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

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

定義3（劃分條件熵）給定核心屬性ti，tj∈Tcore，設屬性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（歸一化屬性劃分相似度）為了便于度量屬性劃分的相似性，對屬性劃分距離進行歸一化并將其轉(zhuǎn)化為屬性劃分相似度：

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

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

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

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

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

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

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

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

3.3.2 社區(qū)搜索與離群點檢測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 實驗設置

4.2.1 評價指標

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

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

其中T（vi）為節(jié)點vi所攜帶的屬性集合.CAS值越高，屬性內(nèi)聚性越強.

4.2.2 對比方法

為度量IPCSO方法的性能，選取了以下三類方法進行對比.第一，比較本文方法與目標社區(qū)發(fā)現(xiàn)方法的性能，選取了FocusCO（Focused Clustering and Outlier）和TSCM.FocusCO為經(jīng)典的目標社區(qū)發(fā)現(xiàn)算法之一，TSCM與IPCSO均采用了擴展查詢節(jié)點的策略來挖掘社區(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é)點為中心的屬性社區(qū)搜索方法的變體.第三，為了探索IPCSO方法挖掘融合用戶偏好社區(qū)的有效性，選取了LOCLU（LOcal CLustering Unimodality）方法.

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

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

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

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

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

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

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

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

4.4 性能比較（問題2）

本節(jié)將評價IPCSO方法的有效性，觀察IPCSO方法與基準方法的性能差異.

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

表3 IPCSO與基線方法的整體性能比較

4.5 案例分析（問題3）

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

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

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

5 結(jié)論

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