劉海姣 馬慧芳, 趙琪琪 李志欣

1(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 蘭州 730070)

2(廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室(廣西師范大學(xué)) 廣西桂林 541004)(haihai1202@foxmail.com)

現(xiàn)實(shí)世界中事物與事物之間是密切聯(lián)系的，普遍存在的聯(lián)系將大部分事物映射成一個個復(fù)雜系統(tǒng)，這些系統(tǒng)往往能表示為圖或網(wǎng)絡(luò)的形式.網(wǎng)絡(luò)中節(jié)點(diǎn)間除了存在連接關(guān)系外，節(jié)點(diǎn)往往可由描述其特征的屬性信息刻畫.面向?qū)傩跃W(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的深入研究有助于揭示相對獨(dú)立而又相互關(guān)聯(lián)的社區(qū)是如何形成錯綜復(fù)雜的網(wǎng)絡(luò)，幫助人們更好地理解網(wǎng)絡(luò)不同層次的結(jié)構(gòu)和功能特性.盡管面向?qū)傩跃W(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法已經(jīng)得到了廣泛的關(guān)注，但現(xiàn)有方法大多數(shù)未能定位基于用戶偏好的目標(biāo)社區(qū).目標(biāo)社區(qū)發(fā)現(xiàn)是半監(jiān)督局部聚類方法，其挖掘到的社區(qū)節(jié)點(diǎn)受用戶偏好控制.例如，化妝品銷售經(jīng)理可能更關(guān)注社交網(wǎng)絡(luò)中的某個社區(qū)，該社區(qū)中的成員具有一定年齡、性別以及收入水平等特點(diǎn)，并且社區(qū)外部影響力較高，經(jīng)理可以向社區(qū)中成員進(jìn)行產(chǎn)品推薦并期望通過口碑傳播的方式推廣其產(chǎn)品；科研人員則需要挖掘特定領(lǐng)域的研究人員所在的社區(qū)，該社區(qū)中的成員具有較高的學(xué)術(shù)影響力且成員研究興趣相似.因此，在屬性網(wǎng)絡(luò)中如何基于用戶給定的樣例信息挖掘與用戶興趣相關(guān)的內(nèi)部一致且與外部分離良好的高影響力目標(biāo)社區(qū)顯得尤為重要.少數(shù)研究人員通過對現(xiàn)有社區(qū)發(fā)現(xiàn)方法改進(jìn)，在一定程度上能夠提升目標(biāo)社區(qū)質(zhì)量，但是現(xiàn)有方法的局限性使得基于用戶興趣的目標(biāo)社區(qū)發(fā)現(xiàn)任務(wù)仍然面臨著嚴(yán)峻挑戰(zhàn)，如何同時利用節(jié)點(diǎn)間的連接關(guān)系和屬性信息挖掘外部影響力高的目標(biāo)社區(qū)仍是研究熱點(diǎn).

本文提出融合用戶興趣偏好與影響力的目標(biāo)社區(qū)發(fā)現(xiàn)方法(target community detection method with user interest preferences and influence, TCPI).首先，結(jié)合節(jié)點(diǎn)屬性信息，挖掘包含樣例節(jié)點(diǎn)的極大k-團(tuán)作為潛在目標(biāo)社區(qū)核心；其次，對于每個極大k-團(tuán)，設(shè)計(jì)熵加權(quán)屬性權(quán)重計(jì)算方法，計(jì)算得到潛在目標(biāo)社區(qū)屬性子空間權(quán)重；再次，利用屬性子空間權(quán)重，基于改進(jìn)的模塊度定義社區(qū)模型，挖掘高質(zhì)量潛在目標(biāo)社區(qū)；最后，結(jié)合社區(qū)質(zhì)量及外部影響分?jǐn)?shù)對所有潛在目標(biāo)社區(qū)降序排列，選取綜合質(zhì)量較高的社區(qū)為目標(biāo)社區(qū).此外，基于無監(jiān)督技術(shù)給出2重剪枝策略提升方法性能和效率.在人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果印證了本文所提方法的效率和有效性.

本文的主要貢獻(xiàn)有3方面:

1) 以包含用戶給定樣例節(jié)點(diǎn)的極大k-團(tuán)作為潛在目標(biāo)社區(qū)的核心，利用熵加權(quán)屬性子空間挖掘方法，充分利用用戶給定的先驗(yàn)信息，計(jì)算目標(biāo)社區(qū)核心節(jié)點(diǎn)彼此相似的屬性權(quán)重，從而精確采集用戶偏好信息.特別地，考慮到極大k-團(tuán)間的冗余特征，設(shè)計(jì)2重剪枝策略，減少運(yùn)行時間并增強(qiáng)方法效率.

2) 基于社區(qū)內(nèi)部連接緊密且外部分離性較好的性質(zhì)，定義高質(zhì)量的目標(biāo)社區(qū)模型，使得社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密，與此同時在對應(yīng)屬性子空間權(quán)重下內(nèi)部節(jié)點(diǎn)彼此相似且與外部節(jié)點(diǎn)不相似，因此提升方法的性能.

3) 除了準(zhǔn)確挖掘與用戶給定樣例節(jié)點(diǎn)相似的高質(zhì)量節(jié)點(diǎn)所構(gòu)成的社區(qū)外，社區(qū)向外部用戶傳播社區(qū)內(nèi)部信息的能力即社區(qū)的外部影響力也是非常重要的方面.本文創(chuàng)新性地融合用戶偏好和節(jié)點(diǎn)及社區(qū)的影響力挖掘目標(biāo)社區(qū)，增進(jìn)方法的應(yīng)用價值.

融合用戶興趣偏好與影響力的目標(biāo)社區(qū)發(fā)現(xiàn)方法框架圖如圖1所示：

Fig. 1 Research framework for target community detection method with user interest preferences and influence

1 相關(guān)工作

1.1 社區(qū)發(fā)現(xiàn)研究現(xiàn)狀

社區(qū)發(fā)現(xiàn)已成為復(fù)雜網(wǎng)絡(luò)分析領(lǐng)域中非常重要的研究方向[1-2].現(xiàn)有的社區(qū)發(fā)現(xiàn)方法大致可以劃分為2類：面向整個復(fù)雜網(wǎng)絡(luò)分析的全局社區(qū)發(fā)現(xiàn)方法和針對特定目標(biāo)設(shè)計(jì)的局部社區(qū)發(fā)現(xiàn)方法.

1) 全局社區(qū)檢測.傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法多是基于全局信息，主要可以分為兩大類：一類是計(jì)算機(jī)科學(xué)中的圖分割方法，主要根據(jù)添加或者刪除邊的原理[3]；另一類是社會學(xué)中分級聚類方法，這是尋找網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的傳統(tǒng)方法，其原理是將具有相似性的一類節(jié)點(diǎn)歸為同一個社區(qū).除此之外，也有很多學(xué)者提出了與其他領(lǐng)域融合的方法:如基于信息論、基于模擬物理電路、基于信號傳播等特殊的方法.Rosvall等人[4]從信息論出發(fā)，對網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)進(jìn)行編碼，并對編碼進(jìn)行壓縮可得到社區(qū)劃分.馬慧芳等人[5]提出融合標(biāo)簽平均劃分距離和結(jié)構(gòu)關(guān)系的微博用戶可重疊社區(qū)發(fā)現(xiàn)方法.然而，隨著網(wǎng)絡(luò)規(guī)模不斷增大，要獲得網(wǎng)絡(luò)的全局信息是十分困難，同時獲取過程中計(jì)算量也十分巨大，因此傳統(tǒng)社區(qū)發(fā)現(xiàn)方法在大規(guī)模網(wǎng)絡(luò)環(huán)境下效率不高.

2) 局部社區(qū)檢測.現(xiàn)有大多數(shù)局部社區(qū)檢測方法往往以種子為初始社區(qū)，通過運(yùn)行質(zhì)量函數(shù)的貪婪優(yōu)化過程來擴(kuò)展社區(qū).因此，質(zhì)量函數(shù)和擴(kuò)展辦法決定了局部社區(qū)檢測方法的有效性.Rhouma等人[6]提出了基于凝聚聚類的重疊社區(qū)發(fā)現(xiàn)方法.該方法從節(jié)點(diǎn)開始聚類，通過重復(fù)擴(kuò)展節(jié)點(diǎn)的鄰居直到擴(kuò)展達(dá)到平衡狀態(tài)停止.Ding等人[7]設(shè)計(jì)了基于核檢測和社區(qū)擴(kuò)展的2階段局部社區(qū)檢測方法.核心檢測階段將種子替換為目標(biāo)社區(qū)的核心成員，而社區(qū)擴(kuò)展階段以檢測到的社區(qū)核心單元為初始社區(qū)，并根據(jù)節(jié)點(diǎn)關(guān)系強(qiáng)度對社區(qū)進(jìn)行擴(kuò)展.Zhang等人[8]提出了將網(wǎng)絡(luò)劃分為任意數(shù)量社區(qū)的譜方法，該方法利用從模塊度最大化到向量分區(qū)問題的映射，并結(jié)合向量分區(qū)對網(wǎng)絡(luò)進(jìn)行劃分.局部社區(qū)檢測一定程度上緩解了全局社區(qū)檢測所面臨的效率問題，但是難以針對特定應(yīng)用準(zhǔn)確定位基于用戶偏好的目標(biāo)社區(qū).

1.2 社區(qū)外部影響力量化方法

“口碑效應(yīng)”和“病毒式營銷”中的影響力模型研究是近年來網(wǎng)絡(luò)分析領(lǐng)域的研究熱點(diǎn)之一.因此，節(jié)點(diǎn)及社區(qū)影響力量化變得尤為重要.現(xiàn)有影響力計(jì)算方法主要分為2類：一類是針對單個節(jié)點(diǎn)的中心性度量；另一類是將社區(qū)作為整體量化其外部影響力.

1) 基于核心節(jié)點(diǎn)的外部影響力量化方法.節(jié)點(diǎn)中心性度量主要針對局部社區(qū)發(fā)現(xiàn)方法中核心節(jié)點(diǎn)的選擇所設(shè)計(jì).Zhang等人[9]針對大規(guī)模的社會網(wǎng)絡(luò)提出了基于節(jié)點(diǎn)重要性和標(biāo)簽影響的社區(qū)檢測標(biāo)簽傳播方法.Shi等人[10]認(rèn)為具有較大影響力的人總是扮演更重要的角色，更可能成為社區(qū)的核心，據(jù)此提出了基于影響力的方法來發(fā)現(xiàn)潛在的核心成員，從而揭示社區(qū)結(jié)構(gòu)特征.特別地，王星等人[11]針對復(fù)雜網(wǎng)絡(luò)中的社區(qū)檢測問題，提出了基于節(jié)點(diǎn)影響力的離散粒子群社區(qū)檢測方法，將社區(qū)中節(jié)點(diǎn)影響力與社區(qū)檢測相結(jié)合.從影響范圍、影響程度等角度來看，將眾多節(jié)點(diǎn)組成的社區(qū)作為一個整體，其影響力無疑將大大超過單個節(jié)點(diǎn)的影響力[12].

2) 基于社區(qū)整體的外部影響力.現(xiàn)有針對以社區(qū)為整體開展影響力分析的工作較少.代表性工作有：Liu等人[13]研究微博社區(qū)影響力的評價方法，提出了一個基于微博信息傳播機(jī)制的指標(biāo)體系，將定量指標(biāo)和定性指標(biāo)相結(jié)合，并利用主成分分析將這些指標(biāo)組合成若干綜合指標(biāo)，簡化了指標(biāo)體系；Zhang等人[14]提出了具有信息傳播視角的社區(qū)影響評價模型框架和一套相關(guān)的社區(qū)影響評價形式定義，涉及到用戶影響和社區(qū)影響；Yao等人[15]提出基于PageRank的可變影響社區(qū)檢測方法，可以調(diào)整特定節(jié)點(diǎn)所在的社區(qū)，增加其影響力.然而對于目標(biāo)社區(qū)發(fā)現(xiàn)任務(wù)，除了準(zhǔn)確挖掘高質(zhì)量的與用戶給定的樣例節(jié)點(diǎn)相似的節(jié)點(diǎn)構(gòu)成的社區(qū)外，社區(qū)向外部用戶傳播社區(qū)內(nèi)部信息的能力即社區(qū)的外部影響力也是一個非常重要的方面.

1.3 現(xiàn)有目標(biāo)社區(qū)發(fā)現(xiàn)方法

無論是基于全局的社區(qū)發(fā)現(xiàn)還是基于局部的社區(qū)發(fā)現(xiàn)方法均與基于用戶偏好的目標(biāo)社區(qū)發(fā)現(xiàn)方法具有緊密的聯(lián)系和嚴(yán)格的區(qū)別.與本研究相關(guān)的研究通常可分為社區(qū)搜索和目標(biāo)社區(qū)發(fā)現(xiàn).

1) 社區(qū)搜索.在圖中給定樣例節(jié)點(diǎn)，社區(qū)搜索旨在查找樣本節(jié)點(diǎn)周圍的子圖，這些子圖中的節(jié)點(diǎn)由與種子節(jié)點(diǎn)高度相關(guān)的節(jié)點(diǎn)組成.將輸入節(jié)點(diǎn)作為種子，并根據(jù)特定的目標(biāo)函數(shù)從種子中擴(kuò)張社區(qū)同樣可以獲得與查詢節(jié)點(diǎn)相關(guān)的社區(qū).

代表性的目標(biāo)函數(shù)有局部模塊度、偏向密度的查詢、個性化PageRank和鄰域擴(kuò)張.例如：Fang等人[16]研究有向圖上的社區(qū)搜索問題，在給定有向圖和查詢節(jié)點(diǎn)的情況下，基于節(jié)點(diǎn)的最小入出度，尋找一個包含查詢節(jié)點(diǎn)的稠密連通子圖；Liu等人[17]設(shè)計(jì)了2階段局部社區(qū)檢測方法，利用廣度優(yōu)先擴(kuò)展由種子替換和擴(kuò)展來定位局部社區(qū)；Kloumann等人[18]研究了使用個性化PageRank模型來識別一組種子節(jié)點(diǎn)所在社區(qū)，該研究依賴于種子選擇并假設(shè)有一些基準(zhǔn)社區(qū)，但無法高效地基于查詢請求在大型圖中搜索特定的目標(biāo)社區(qū)；Bian等人[19]提出了基于多查詢隨機(jī)游走社區(qū)檢測方法，該方法在訪問過程中考慮不同游走者之間的交互信息精準(zhǔn)捕獲社區(qū)；Yan等人[20]以種子節(jié)點(diǎn)的社區(qū)隸屬關(guān)系作為先驗(yàn)信息，通過顏色標(biāo)記不同種子節(jié)點(diǎn)，并引入基于染色的隨機(jī)游走機(jī)制將種子節(jié)點(diǎn)顏色傳播到圖中的其余節(jié)點(diǎn)，挖掘不同顏色種子所在社區(qū).然而以上方法均適用于簡單圖且僅僅考慮節(jié)點(diǎn)間直接交互信息，忽略了高階鄰居對節(jié)點(diǎn)重要性的影響，因此對于用戶興趣發(fā)現(xiàn)不夠有效.在這些方法中，局部社區(qū)結(jié)構(gòu)通常通過某些度量值(如局部模塊化、k-團(tuán)、k-truss和k-core)來捕獲[21-23].近年來出現(xiàn)了許多新穎的網(wǎng)絡(luò)模型，社區(qū)搜索方法面向這些類型多樣的網(wǎng)絡(luò)也開展了一些初步研究，包括異構(gòu)網(wǎng)絡(luò)[24]、public-private網(wǎng)絡(luò)[25]、地理社會網(wǎng)絡(luò)[26]和層次屬性圖[27]等.特別地，在搜索社區(qū)時，將屬性引入圖節(jié)點(diǎn)可以在一定程度上實(shí)現(xiàn)更大的個性化[28].例如基于關(guān)鍵字的社區(qū)搜索方法可以顯著提高檢索有效性.但是，基于屬性的社區(qū)搜索只關(guān)注簡單的屬性，現(xiàn)實(shí)世界中的圖具有3種類型的屬性，即數(shù)字屬性、二進(jìn)制屬性和分類屬性.

2) 目標(biāo)社區(qū)發(fā)現(xiàn).目標(biāo)社區(qū)發(fā)現(xiàn)方法以用戶給定樣例節(jié)點(diǎn)作為先驗(yàn)信息，發(fā)現(xiàn)與用戶偏好相關(guān)節(jié)點(diǎn)所構(gòu)成的高質(zhì)量且有一定的外部影響力的社區(qū).Perozzi等人[29]提出了面向用戶的屬性圖挖掘方法，該方法允許用戶通過提供一組樣本節(jié)點(diǎn)來引導(dǎo)社區(qū)，所提供的樣例節(jié)點(diǎn)被認(rèn)為是相似的，并且與用戶感興趣的社區(qū)節(jié)點(diǎn)相似.Perozzi等人提出的方法沒有說明需要多少樣例節(jié)點(diǎn)，但明確指出需要2個以上的樣例節(jié)點(diǎn).Wu等人[30]提出了在目標(biāo)子空間中挖掘目標(biāo)社區(qū)集合的方法，該方法根據(jù)用戶提供的2個樣本節(jié)點(diǎn)擴(kuò)展一組樣本節(jié)點(diǎn)，并從中推導(dǎo)出目標(biāo)屬性權(quán)重指導(dǎo)挖掘目標(biāo)社區(qū)的集合.然而，現(xiàn)有的半監(jiān)督目標(biāo)社區(qū)聚類技術(shù)雖然考慮了用戶偏好，但在聚類過程中僅考慮了節(jié)點(diǎn)屬性信息或只利用節(jié)點(diǎn)部分屬性.文獻(xiàn)[31]提出的目標(biāo)社區(qū)發(fā)現(xiàn)方法未能考慮社區(qū)外部影響，并且社區(qū)模型僅考慮社區(qū)內(nèi)部節(jié)點(diǎn)間的緊密程度，忽略了社區(qū)與其外部節(jié)點(diǎn)間的連接關(guān)系.此外，現(xiàn)有的目標(biāo)社區(qū)方法均忽略了社區(qū)對外部節(jié)點(diǎn)及社區(qū)的影響能力.

針對以上問題，本文提出的方法可以有效地挖掘與用戶偏好相關(guān)的高質(zhì)量且具有一定外部影響力的目標(biāo)社區(qū).首先，為了有效挖掘用戶偏好信息，基于用戶給定的樣例節(jié)點(diǎn)，挖掘包含樣例節(jié)點(diǎn)的極大k-團(tuán)作為社區(qū)核心，并設(shè)計(jì)熵加權(quán)屬性子空間計(jì)算辦法，自動捕獲用戶興趣；然后，基于社區(qū)內(nèi)部連接緊密及與外部節(jié)點(diǎn)分離較好的特性，定義高質(zhì)量的目標(biāo)社區(qū)模型，以極大k-團(tuán)為社區(qū)核心挖掘得到質(zhì)量較高的潛在目標(biāo)社區(qū)；最后，利用社區(qū)內(nèi)部節(jié)點(diǎn)與外部剩余節(jié)點(diǎn)的連接及屬性關(guān)系，定義社區(qū)外部影響力，并創(chuàng)新性地首次將社區(qū)內(nèi)部質(zhì)量與其外部影響力相結(jié)合，基于用戶偏好挖掘得到高質(zhì)量且具有一定影響力的目標(biāo)社區(qū).此外，該方法可以擴(kuò)展到網(wǎng)絡(luò)中多個社區(qū)發(fā)現(xiàn)任務(wù)中.在人工數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果印證了本文所提方法的有效性和效率以及應(yīng)用價值.

2 社區(qū)核心挖掘

2.1 問題定義

2.2 極大k-團(tuán)挖掘

極大k-團(tuán)模型具有4個可取的內(nèi)在屬性，即社團(tuán)、凝聚力、連通性和極大值.具體來說，一個極大k-團(tuán)是一個連通的誘導(dǎo)子圖，包含至少k個節(jié)點(diǎn)(社團(tuán))；k-團(tuán)中任意2個節(jié)點(diǎn)之間連接(連通性)，且屬性相似性較高(內(nèi)聚性)；對于任意k-團(tuán)都不是另一個k-團(tuán)的子圖(極大值).

基于節(jié)點(diǎn)間的屬性關(guān)系，改進(jìn)文獻(xiàn)[32]提出了非遞歸極大團(tuán)挖掘算法，即Kose算法，具體地，定義節(jié)點(diǎn)間屬性相似度如下：

定義1.節(jié)點(diǎn)屬性相似度.節(jié)點(diǎn)u和v的屬性相似度s(u,v)定義為

(1)

如果2個具有N個節(jié)點(diǎn)的團(tuán)有N-1個節(jié)點(diǎn)相同，剩余不相同的2個節(jié)點(diǎn)之間存在邊且節(jié)點(diǎn)間屬性相似度較大，即s(u,v)>α，α為節(jié)點(diǎn)間最低屬性相似度閾值，則2個N節(jié)點(diǎn)大小的團(tuán)可以形成一個N+1個節(jié)點(diǎn)團(tuán).改進(jìn)Kose算法從2個節(jié)點(diǎn)大小的極大團(tuán)生成所有3個節(jié)點(diǎn)大小的團(tuán)，再用3個節(jié)點(diǎn)大小的團(tuán)來生成所有4個節(jié)點(diǎn)大小的團(tuán)，迭代直到?jīng)]有新的更大的團(tuán)可以生成為止.

2.3 基于熵權(quán)約束的屬性子空間挖掘

以極大k-團(tuán)作為潛在目標(biāo)社區(qū)的核心，計(jì)算核心內(nèi)節(jié)點(diǎn)彼此相似的屬性權(quán)重，該屬性權(quán)重能夠使得社區(qū)中的內(nèi)部節(jié)點(diǎn)基于屬性彼此相似且與外部節(jié)點(diǎn)不相似[33].利用文獻(xiàn)[31]改進(jìn)的目標(biāo)社區(qū)屬性子空間權(quán)重目標(biāo)函數(shù)計(jì)算屬性子空間權(quán)重向量.社區(qū)Cx(x∈{1,2,…,d})屬性子空間權(quán)重目標(biāo)函數(shù)定義為

(2)

通過對F(lx)最小化，求得：

(3)

2.4 挖掘k-團(tuán)剪枝策略

考慮到以用戶所給定樣例節(jié)點(diǎn)作為先驗(yàn)信息，挖掘得到的包含已知節(jié)點(diǎn)的極大k-團(tuán)彼此之間存在相互重疊，因此基于無監(jiān)督技術(shù)設(shè)計(jì)2重剪枝策略，優(yōu)化極大k-團(tuán)集合，提高方法的效率.

策略1.無監(jiān)督剪枝策略.如果用戶未能給定任何有關(guān)屬性先驗(yàn)信息，則定義2重?zé)o監(jiān)督剪枝策略.首先，消除所有多余極大k-團(tuán).在當(dāng)前極大k-團(tuán)集合中，如果選中的極大k-團(tuán)不是冗余的，那么該極大k-團(tuán)將保留在集合中，否則刪除.其次，在去除冗余后的極大k-團(tuán)挖掘得到的目標(biāo)子空間集合中，依據(jù)不同節(jié)點(diǎn)間可能沒有連接關(guān)系但基于屬性可能相似的特性，基于改進(jìn)的k-medoid算法[24]中的初始點(diǎn)選取策略選擇差異最大的d個k-團(tuán)作為每個潛在目標(biāo)社區(qū)的核心.

(4)

3 社區(qū)發(fā)現(xiàn)及綜合排名

3.1 目標(biāo)社區(qū)模型構(gòu)建

高質(zhì)量的社區(qū)滿足2個特性[34]：1)內(nèi)部一致性；2)外部可分性.直觀地說，好的社區(qū)在其內(nèi)部節(jié)點(diǎn)之間有許多內(nèi)部邊，且彼此共享一組具有相似值的屬性.換句話說，其內(nèi)部節(jié)點(diǎn)只在對應(yīng)屬性子空間權(quán)重下彼此相似且與外部節(jié)點(diǎn)不相似.此外，好的社區(qū)在其邊界上要么只有較少邊，要么許多交叉邊可以被“免除”，也就是說，使社區(qū)內(nèi)部節(jié)點(diǎn)彼此相似的屬性子空間也會使其與邊界節(jié)點(diǎn)不相似或與其邊界節(jié)點(diǎn)分離.因此，本文基于高質(zhì)量社區(qū)的2個方面量化了社區(qū)質(zhì)量.

定義2.節(jié)點(diǎn)加權(quán)屬性相似度.給定節(jié)點(diǎn)u和v在社區(qū)Cx的屬性子空間下的加權(quán)屬性相似度s(u,v|lx)定義為

(5)

其中，f(v)表示與節(jié)點(diǎn)v關(guān)聯(lián)的屬性向量,diag(lx)是用lx構(gòu)建的一個對角矩陣.對于一個社區(qū)而言，每個屬性對社區(qū)均有貢獻(xiàn)，但貢獻(xiàn)不同.通過引入社區(qū)Cx的非負(fù)權(quán)向量lx來計(jì)算加權(quán)節(jié)點(diǎn)相似性.

定義3.社區(qū)質(zhì)量函數(shù).給定社區(qū)Cx及其屬性子空間lx，則社區(qū)Cx質(zhì)量函數(shù)的定義為：

s(vi,vj|lx)=Ix+Ex，

(6)

對于具有較高質(zhì)量分?jǐn)?shù)的目標(biāo)社區(qū)而言，存在較多“期望”低的內(nèi)部邊，與此同時成對節(jié)點(diǎn)的相似性很高.這確保了式(6)中第1項(xiàng)的最大化.此外，社區(qū)要么沒有交叉邊，要么現(xiàn)有交叉邊“期望”高，或者內(nèi)部節(jié)點(diǎn)基于屬性子空間與邊界節(jié)點(diǎn)的相似性接近于0，因此第2項(xiàng)消失.

3.2 候選目標(biāo)社區(qū)發(fā)現(xiàn)

確定了候選目標(biāo)社區(qū)中心點(diǎn)集及對應(yīng)屬性子空間權(quán)重后，挖掘每個候選中心點(diǎn)集及屬性子空間權(quán)重所在的潛在目標(biāo)社區(qū).首先以中心點(diǎn)集作為目標(biāo)社區(qū)的種子，然后擴(kuò)展種子以找到目標(biāo)社區(qū).算法1中描述了第x個初始潛在目標(biāo)社區(qū)Cx的挖掘過程.

算法1.潛在初始目標(biāo)社區(qū)挖掘.

系統(tǒng)建設(shè)的核心是：客運(yùn)組織、旅客服務(wù)，根據(jù)業(yè)務(wù)需求，建立以下12個子系統(tǒng)，分別是：信息采集管理子系統(tǒng)、廣播語音控制子系統(tǒng)、監(jiān)控子系統(tǒng)、客運(yùn)技術(shù)作業(yè)子系統(tǒng)、智能統(tǒng)計(jì)分析子系統(tǒng)、信息發(fā)布管理子系統(tǒng)、旅客輔助服務(wù)子系統(tǒng)、預(yù)警及處理子系統(tǒng)、應(yīng)急管理子系統(tǒng)、消防照明管理子系統(tǒng)、設(shè)備管理子系統(tǒng)、系統(tǒng)管理子系統(tǒng)。各子系統(tǒng)的主要功能見下表所示。

輸出:初始潛在目標(biāo)社區(qū)Cx.

①Ncn=?；*存儲候選節(jié)點(diǎn)*

③Ncn={vj|vi和vj之間有邊,vi∈Cx,vj?Cx∧vj∈V};*將集合中現(xiàn)有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)作為候選節(jié)點(diǎn)*

④ ΔQ(Cx,lx)=0,ΔQ(Cx,lx)best=0；

⑤ Repeat

⑥vbest=null；*最佳候選節(jié)點(diǎn)*

⑦ for eachv∈Ncndo

Q(Cx,lx)；*節(jié)點(diǎn)v加入社區(qū)時質(zhì)量值的變化*

⑨ if ΔQ(Cx,lx)>ΔQ(Cx,lx)best≥0

⑩ ΔQ(Cx,lx)best=ΔQ(Cx,lx)；

{vbest}；*更新候選節(jié)點(diǎn)*

采用貪婪算法對目標(biāo)社區(qū)進(jìn)行局部調(diào)整，在每次迭代中，計(jì)算所有可能調(diào)整質(zhì)量變化的操作，選擇社區(qū)質(zhì)量正變化最大的節(jié)點(diǎn)加入目標(biāo)社區(qū).迭代繼續(xù)，直到?jīng)]有節(jié)點(diǎn)的加入導(dǎo)致質(zhì)量發(fā)生正的改變，社區(qū)的質(zhì)量值不再增加.

節(jié)點(diǎn)的添加基于改進(jìn)的最優(yōu)搜索策略，即每次添加的節(jié)點(diǎn)都是當(dāng)前最優(yōu)的選擇.類似地，采用了追溯策略檢查是否有節(jié)點(diǎn)的移除使得社區(qū)的質(zhì)量正向增加.社區(qū)的質(zhì)量函數(shù)值小于等于1，每次選擇節(jié)點(diǎn)加入社區(qū)或者刪除社區(qū)中的節(jié)點(diǎn)都能使得目標(biāo)社區(qū)的質(zhì)量值正向增加，因此算法的收斂性得到保證.

3.3 社區(qū)綜合質(zhì)量評估

本節(jié)首先定義社區(qū)外部質(zhì)量分?jǐn)?shù)來衡量社區(qū)外部影響能力，然后結(jié)合社區(qū)的質(zhì)量分?jǐn)?shù)和外部影響能力綜合評估社區(qū)綜合質(zhì)量.

(7)

其中，r(vi,bj)表示節(jié)點(diǎn)vi和bj之間的最短路徑長度.

定義4.社區(qū)對節(jié)點(diǎn)影響分?jǐn)?shù).一個社區(qū)Cx對其鄰居節(jié)點(diǎn)bj的影響分?jǐn)?shù)定義為

(8)

定義5.社區(qū)外部影響率.給定社區(qū)Cx，其社區(qū)外部影響率定義為

(9)

其中，max(S)和avg(S)分別表示向量S中的最大值和平均值.鄰居節(jié)點(diǎn)bj基于2個原則可以被社區(qū)Cx影響：1)如果社區(qū)Cx內(nèi)大多數(shù)節(jié)點(diǎn)與bj基于屬性子空間lx較為相似且最短路徑長度較短，則bj受社區(qū)Cx的影響較大；2)與bj連接最短路徑長度較短的社區(qū)內(nèi)部節(jié)點(diǎn)與中心節(jié)點(diǎn)相似度較高.

為了精確挖掘與用戶給定的先驗(yàn)信息相關(guān)的目標(biāo)社區(qū)，結(jié)合社區(qū)質(zhì)量及社區(qū)與內(nèi)部節(jié)點(diǎn)對外影響分?jǐn)?shù)定義社區(qū)綜合質(zhì)量分?jǐn)?shù)，并降序排列所有候選目標(biāo)社區(qū).

定義6.社區(qū)綜合質(zhì)量.給定社區(qū)Cx其綜合質(zhì)量Qinf(Cx)定義為

(10)

因此，可以挖掘質(zhì)量較高且外部影響力較大的目標(biāo)社區(qū).

3.4 方法推廣

大多數(shù)屬性網(wǎng)絡(luò)中的節(jié)點(diǎn)具有較高的屬性維度，考慮到用戶更期望關(guān)注少數(shù)屬性，因此用戶可以選擇給定最關(guān)注的屬性fi∈F，i∈{1,2,…,r}作為先驗(yàn)信息.基于用戶給定的屬性信息，根據(jù)本文所提出的方法得到去除冗余后的極大k-團(tuán)所對應(yīng)的屬性子空間，修剪去除部分在用戶給定的屬性上權(quán)重較低的極大k-團(tuán)，得到新的極大k-團(tuán)集合，其中集合中每個元素均作為一個潛在目標(biāo)社區(qū)的核心.

4 實(shí) 驗(yàn)

為驗(yàn)證本文所提出方法的有效性及其效率，本節(jié)分別在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上設(shè)計(jì)了2組不同的實(shí)驗(yàn).首先，對實(shí)驗(yàn)所用到的人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集分別進(jìn)行了描述；其次，觀察不同參數(shù)值的設(shè)置對實(shí)驗(yàn)結(jié)果的影響，選擇適宜的參數(shù)值；最后，選取3個目標(biāo)社區(qū)發(fā)現(xiàn)方法與本文所提出方法進(jìn)行分析比較.

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

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

對于社區(qū)檢測結(jié)果的評估最直接的方法就是將檢測結(jié)果和現(xiàn)實(shí)網(wǎng)絡(luò)中真實(shí)社區(qū)相比較.考慮到現(xiàn)實(shí)世界中針對目標(biāo)社區(qū)發(fā)現(xiàn)的可用網(wǎng)絡(luò)較少且質(zhì)量參差不齊，利用人工生成網(wǎng)絡(luò)對本文所提方法的有效性進(jìn)行測評成為評價社區(qū)檢測方法優(yōu)劣的高效可行的方法.本節(jié)利用LFR Benchmark算法生成人工圖，具體參數(shù)設(shè)置參照文獻(xiàn)[31].

值得注意的是，在現(xiàn)實(shí)世界的圖中，每個社區(qū)中的成員基于多個屬性彼此相似.對于每個帶有屬性的子空間社區(qū)，對于所分配的屬性子集中的每個屬性fi，其節(jié)點(diǎn)屬性值從均值μi∈[0,1]和方差σ=0.001的正態(tài)分布N(μi,σ)中提取，使得社區(qū)節(jié)點(diǎn)在對應(yīng)屬性子空間上“一致”，其余屬性取值從方差較大的正態(tài)分布N(0,1)中提取.共生成了6個內(nèi)部節(jié)點(diǎn)基于屬性子空間彼此相似且連接緊密的社區(qū)(社區(qū)1～6)和1個不分配任何屬性子空間的社區(qū)(社區(qū)7)，總共有7個不同的社區(qū).

實(shí)驗(yàn)利用給定的來自社區(qū)1的樣例節(jié)點(diǎn)挖掘社區(qū)1，詳情如表1所示：

Table 1 Synthetic Network

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

為了驗(yàn)證本文所提出方法在真實(shí)網(wǎng)絡(luò)上的效果，本節(jié)選取4個真實(shí)世界中的屬性網(wǎng)絡(luò)進(jìn)行驗(yàn)證.Orkut是一個免費(fèi)的在線社交網(wǎng)絡(luò)，用戶之間形成友誼.Orkut還允許用戶組成一個組即真實(shí)社區(qū)，然后其他成員可以加入該組.Amazon網(wǎng)絡(luò)是基于消費(fèi)者購買某一項(xiàng)目收集的，如果產(chǎn)品1經(jīng)常與產(chǎn)品2被共同購買，則該圖包含從節(jié)點(diǎn)1到節(jié)點(diǎn)2的無向邊.Amazon數(shù)據(jù)集中為每個類別的產(chǎn)品都定義了真實(shí)的社區(qū).DBLP是計(jì)算機(jī)領(lǐng)域作者的合著網(wǎng)絡(luò)，以作者與作者合著的國際期刊和會議等公開發(fā)表的論文為邊構(gòu)建關(guān)系網(wǎng)絡(luò)，DBLP集成元素不多，只有最基本的論文題目、時間、作者、發(fā)表類型及期刊或會議名稱等.以DBLP中作者的主要研究方向所在的6個研究領(lǐng)域，即人工智能(artificial inte-lligence, AI)、計(jì)算機(jī)視覺(computer vision, CV)、數(shù)據(jù)庫(database, DB)、數(shù)據(jù)挖掘(data mining, DM)、信息檢索(information retrieval, IR)和機(jī)器學(xué)習(xí)(machine learning, ML)為社區(qū)劃分基準(zhǔn).LastFM是用戶收聽音樂的信息，具體包括雙向朋友關(guān)系、用戶所收聽藝術(shù)家信息、用戶對藝術(shù)家標(biāo)簽信息、藝術(shù)家標(biāo)簽信息.LastFM中的成員被劃分到該成員收聽最多的音樂風(fēng)格，如House，Britpop，Trip-Hop，Gangsta Rap等.預(yù)處理后的真實(shí)數(shù)據(jù)信息情況詳見表2:

Table 2 The Real-World Network Datasets

4.2 實(shí)驗(yàn)結(jié)果

為了評估所提出方法的性能，本節(jié)中采用標(biāo)準(zhǔn)化互信息(normalized mutual information,NMI)均值和F1評分均值[29]，即在同一數(shù)據(jù)集中運(yùn)行100次的NMIF1的平均值來度量檢測結(jié)果與標(biāo)準(zhǔn)結(jié)果之間的相似性.該相似性越高，NMI值越接近1；反之則NMI值接近0.F1評分是社區(qū)檢測方法常用的標(biāo)準(zhǔn)，是查全率和召回率的調(diào)和值.NMI和F1評分均值作為后續(xù)評價指標(biāo)并用于實(shí)驗(yàn)效果的綜合評價.

4.2.1 參數(shù)分析

本文所提出方法總共涉及4個參數(shù)，其中α為生成包含用戶提供節(jié)點(diǎn)樣例節(jié)點(diǎn)間的極大團(tuán)時所要求的最低屬性相似度閾值.β是決定屬性子空間個數(shù)的閾值，β越大則得到屬性子空間個數(shù)越多得到的社區(qū)越多，β的大小決定了過濾的子空間的數(shù)量，直接影響著方法效率.γ是控制多維度權(quán)重激勵強(qiáng)度的一個正參數(shù)，實(shí)驗(yàn)結(jié)果對γ取值的變化不敏感，與文獻(xiàn)[31]相同γ=0.5.μ∈[0,1]是控制極大團(tuán)冗余度的參數(shù)，選取不同的μ值對方法有效性影響較低.沒有特殊要求情形下，μ=0.5是可以被允許的重疊[29].給定參數(shù)γ和μ的情況下，α和β取不同值時，運(yùn)行結(jié)果不相同.為了尋找最優(yōu)參數(shù)取值，設(shè)置實(shí)驗(yàn)對比參數(shù)α和β取值不同時的運(yùn)行結(jié)果.

為了選取合適的參數(shù)，在人工數(shù)據(jù)集和4個真實(shí)數(shù)據(jù)集上運(yùn)行本文所提出的TCPI方法.本節(jié)將通過實(shí)驗(yàn)對參數(shù)進(jìn)行調(diào)節(jié)，以確定最優(yōu)的實(shí)驗(yàn)參數(shù).由于β的不同取值對參數(shù)α沒有影響，因此固定β=0.5后，將參數(shù)α作為自變量，給定不同參數(shù)值觀察NMI和F1評分均值的變化.最后通過比對不同參數(shù)下的NMI和F1評分均值，取使目標(biāo)社區(qū)的NMI和F1評分均值最大的參數(shù)值作為參數(shù)，該實(shí)驗(yàn)分別在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行.如圖2所示，x軸為參數(shù)α在0～1之間的不同取值，y軸為NMI或F1評分均值的變化情況.

Fig. 2 Parameter α analysis

當(dāng)α≥0.7時，5個數(shù)據(jù)集上的NMI和F1評分均值變化較小，基本趨于穩(wěn)定，因此設(shè)定α=0.7，該數(shù)值也將用作后續(xù)實(shí)驗(yàn)中參數(shù)α取值.

相似度閾值β作為選取中心點(diǎn)集時鄰居節(jié)點(diǎn)與樣例節(jié)點(diǎn)間相似度的最低標(biāo)準(zhǔn)，在目標(biāo)社區(qū)發(fā)現(xiàn)中有著極高的重要性.為選擇合適的閾值，設(shè)置α=0.7，將β作為自變量，給定不同的β觀察標(biāo)準(zhǔn)化互信息NMI和F1評分均值的變化.該實(shí)驗(yàn)在5種數(shù)據(jù)集上進(jìn)行.如圖3所示，x軸為β在0～1之間的不同取值，y軸為NMI均值或F1均值的變化情況.

Fig. 3 Parameter β analysis

從圖3可以看到，β=0.65左右時，5個數(shù)據(jù)集上的NMI和F1均值較高，即設(shè)定參數(shù)β=0.65可使得檢測結(jié)果與標(biāo)準(zhǔn)結(jié)果之間相似度趨于最大化，該數(shù)值也將用作后續(xù)實(shí)驗(yàn)中參數(shù)的取值.

4.2.2 與其他方法的對比

選取2個目標(biāo)社區(qū)劃分方法FocusCO(focused clustering and outlier detection in large attributed graphs)[29]，TSCM(mining target attribute subspace and set of target communities in large attributed networks)[30]和一個未考慮社區(qū)外部影響力的目標(biāo)社區(qū)發(fā)現(xiàn)方法TC-AE(target community discovery based on attribute subspace with entropy weighting)[31]與本文方法分別從發(fā)現(xiàn)的目標(biāo)社區(qū)質(zhì)量和運(yùn)行時間2方面進(jìn)行比較.其中FocusCO創(chuàng)新性地提出了以用戶為中心的屬性圖目標(biāo)社區(qū)發(fā)現(xiàn)方法；TSCM基于目標(biāo)子空間挖掘目標(biāo)社區(qū)集合；TC-AE在不考慮社區(qū)的外部影響力及邊“期望”的情況下劃分目標(biāo)社區(qū).因此本文選取上述3種方法作為對比方法，對比結(jié)果如表3所示.

為了進(jìn)一步驗(yàn)證該方法的有效性，在上述參數(shù)設(shè)置下，本文基于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集對TCPI，F(xiàn)ocusCO，TSCM，TC-AE方法進(jìn)行了評價.所有比較方法的平均運(yùn)行次數(shù)超過10次，每次運(yùn)行都隨機(jī)提供樣本中描述的默認(rèn)參數(shù).圖4顯示了不同數(shù)據(jù)集上不同指標(biāo)的總體性能.

Table 3 Comparison of Different Target Community Detection Methods

Fig. 4 NMI/F1 scores on different datasets

由圖4可知，在4種數(shù)據(jù)集上，本文所提出的TCPI方法挖掘的目標(biāo)社區(qū)NMI均值和F1均值在所有真實(shí)數(shù)據(jù)集較為穩(wěn)定且最高，TC-AE與TSCM方法挖掘的目標(biāo)社區(qū)NMI均值和F1均值較為接近且均低于本文所提出方法；FocusCO方法效率最低.特別地，在Amazon數(shù)據(jù)集中，本文所提出目標(biāo)社區(qū)發(fā)現(xiàn)方法TCPI的NMI均值和F1均值最高，因此，TCPI方法適用于高維且具有多種屬性類型的數(shù)據(jù).

4.2.3 擴(kuò)展性驗(yàn)證

為了進(jìn)一步驗(yàn)證本文所提出方法的可擴(kuò)展性，基于LFR Benchmark生成具有不同節(jié)點(diǎn)個數(shù)、不同邊數(shù)或不同屬性個數(shù)社區(qū)的圖，并運(yùn)行基于2重剪枝策略的融合用戶興趣與影響力的目標(biāo)社區(qū)發(fā)現(xiàn)方法.圖5顯示了在人工網(wǎng)絡(luò)上隨著節(jié)點(diǎn)或?qū)傩詳?shù)量的增加子空間挖掘運(yùn)行的平均時間變化情況.

Fig. 6 Experimental results on Amazon data

Fig. 5 Running time analysis of mining target subspace

從圖5(a)可以看出，隨著節(jié)點(diǎn)個數(shù)的增長，F(xiàn)ocusCO，TSCM，TC-AE，TCPI的時間成本都略有增加.此外，這些方法的時間成本相對比較穩(wěn)定，并且維持在一個較低的水平.在圖5(b)中，隨著屬性個數(shù)變大時，所有方法花費(fèi)的時間均有所增加，而屬性個數(shù)對TSCM的運(yùn)行時間影響最小，TCPI略遜于TSCM，但是與基于距離度量優(yōu)化的FocusCO相比，可與TC-AE方法相媲美.盡管與TCPI相比，TSCM需要的時間更少，但本文所提出的方法能夠識別出更好的真實(shí)社區(qū).

4.2.4 案例分析

由于真實(shí)網(wǎng)絡(luò)對于融合影響力的目標(biāo)社區(qū)的集合沒有給定的基準(zhǔn)，而且大多數(shù)社區(qū)發(fā)現(xiàn)方法都未能考慮節(jié)點(diǎn)及社區(qū)影響力問題，因此在真實(shí)的網(wǎng)絡(luò)中對本文所提出的方法很難進(jìn)行定量分析.以下在真實(shí)網(wǎng)絡(luò)的案例研究主要說明本文所提出方法的應(yīng)用價值.針對本文所提出的方法在Amazon數(shù)據(jù)集上的運(yùn)行結(jié)果設(shè)計(jì)了目標(biāo)社區(qū)的案例研究.如圖6所示，同一種形狀的節(jié)點(diǎn)隸屬于同一個社區(qū)，特別地標(biāo)示出用戶給出的樣例節(jié)點(diǎn).

圖6中，左邊為原始網(wǎng)絡(luò)，右邊為檢測結(jié)果，其中每個圓圈中同一形狀節(jié)點(diǎn)構(gòu)成的子圖為一個真實(shí)社區(qū)，六邊形節(jié)點(diǎn)表示用戶給定的樣例節(jié)點(diǎn)，七角星節(jié)點(diǎn)表示部分社區(qū)的鄰居節(jié)點(diǎn).同樣地，對于某個產(chǎn)品的推銷人員而言，除了挖掘經(jīng)常購買該產(chǎn)品的客戶所構(gòu)成的社區(qū)方便進(jìn)行客戶維護(hù)外，還需要關(guān)注該社區(qū)內(nèi)人員能否吸引更多的潛在客戶進(jìn)行購買，以便擴(kuò)大產(chǎn)品銷售市場，增加市場占有率.因此，本文提出的方法在現(xiàn)實(shí)生活中有較高的應(yīng)用價值.

5 總 結(jié)

本文提出面向?qū)傩跃W(wǎng)絡(luò)的融合用戶興趣偏好與影響力的目標(biāo)社區(qū)發(fā)現(xiàn)方法TCPI，挖掘用戶偏好信息，挖掘包含樣例節(jié)點(diǎn)極大k-團(tuán)作為潛在目標(biāo)社區(qū)核心，并設(shè)計(jì)熵加權(quán)屬性權(quán)重計(jì)算方法來提取潛在目標(biāo)社區(qū)屬性子空間權(quán)重，捕獲用戶偏好；其次，綜合社區(qū)內(nèi)部緊密性和外部可分離性定義社區(qū)質(zhì)量函數(shù)，以極大k-團(tuán)為核心擴(kuò)展得到高質(zhì)量潛在目標(biāo)社區(qū)；最后，定義社區(qū)外部影響分?jǐn)?shù)，并結(jié)合社區(qū)質(zhì)量函數(shù)值及外部影響分?jǐn)?shù)對所有潛在目標(biāo)社區(qū)排序，輸出綜合質(zhì)量較高的社區(qū)為目標(biāo)社區(qū).并且，計(jì)算得到所有極大k-團(tuán)的屬性子空間權(quán)重后，設(shè)計(jì)了2重剪枝策略提升方法的性能和效率.此外，在用戶提供額外屬性信息的情況下，該方法可進(jìn)一步推廣.在人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果印證了本文所提方法的效率和有效性.