融合用戶興趣偏好與影響力的目標社區發現

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

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

2(廣西多源信息挖掘與安全重點實驗室(廣西師范大學) 廣西桂林 541004)(haihai1202@foxmail.com)

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

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

本文的主要貢獻有3方面:

1) 以包含用戶給定樣例節點的極大k-團作為潛在目標社區的核心，利用熵加權屬性子空間挖掘方法，充分利用用戶給定的先驗信息，計算目標社區核心節點彼此相似的屬性權重，從而精確采集用戶偏好信息.特別地，考慮到極大k-團間的冗余特征，設計2重剪枝策略，減少運行時間并增強方法效率.

2) 基于社區內部連接緊密且外部分離性較好的性質，定義高質量的目標社區模型，使得社區內部節點連接緊密，與此同時在對應屬性子空間權重下內部節點彼此相似且與外部節點不相似，因此提升方法的性能.

3) 除了準確挖掘與用戶給定樣例節點相似的高質量節點所構成的社區外，社區向外部用戶傳播社區內部信息的能力即社區的外部影響力也是非常重要的方面.本文創新性地融合用戶偏好和節點及社區的影響力挖掘目標社區，增進方法的應用價值.

融合用戶興趣偏好與影響力的目標社區發現方法框架圖如圖1所示：

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

1 相關工作

1.1 社區發現研究現狀

社區發現已成為復雜網絡分析領域中非常重要的研究方向[1-2].現有的社區發現方法大致可以劃分為2類：面向整個復雜網絡分析的全局社區發現方法和針對特定目標設計的局部社區發現方法.

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

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

1.2 社區外部影響力量化方法

“口碑效應”和“病毒式營銷”中的影響力模型研究是近年來網絡分析領域的研究熱點之一.因此，節點及社區影響力量化變得尤為重要.現有影響力計算方法主要分為2類：一類是針對單個節點的中心性度量；另一類是將社區作為整體量化其外部影響力.

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

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

1.3 現有目標社區發現方法

無論是基于全局的社區發現還是基于局部的社區發現方法均與基于用戶偏好的目標社區發現方法具有緊密的聯系和嚴格的區別.與本研究相關的研究通常可分為社區搜索和目標社區發現.

1) 社區搜索.在圖中給定樣例節點，社區搜索旨在查找樣本節點周圍的子圖，這些子圖中的節點由與種子節點高度相關的節點組成.將輸入節點作為種子，并根據特定的目標函數從種子中擴張社區同樣可以獲得與查詢節點相關的社區.

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

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

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

2 社區核心挖掘

2.1 問題定義

2.2 極大k-團挖掘

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

基于節點間的屬性關系，改進文獻[32]提出了非遞歸極大團挖掘算法，即Kose算法，具體地，定義節點間屬性相似度如下：

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

(1)

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

2.3 基于熵權約束的屬性子空間挖掘

以極大k-團作為潛在目標社區的核心，計算核心內節點彼此相似的屬性權重，該屬性權重能夠使得社區中的內部節點基于屬性彼此相似且與外部節點不相似[33].利用文獻[31]改進的目標社區屬性子空間權重目標函數計算屬性子空間權重向量.社區Cx(x∈{1,2,…,d})屬性子空間權重目標函數定義為

(2)

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

(3)

2.4 挖掘k-團剪枝策略

考慮到以用戶所給定樣例節點作為先驗信息，挖掘得到的包含已知節點的極大k-團彼此之間存在相互重疊，因此基于無監督技術設計2重剪枝策略，優化極大k-團集合，提高方法的效率.

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

(4)

3 社區發現及綜合排名

3.1 目標社區模型構建

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

定義2.節點加權屬性相似度.給定節點u和v在社區Cx的屬性子空間下的加權屬性相似度s(u,v|lx)定義為

(5)

其中，f(v)表示與節點v關聯的屬性向量,diag(lx)是用lx構建的一個對角矩陣.對于一個社區而言，每個屬性對社區均有貢獻，但貢獻不同.通過引入社區Cx的非負權向量lx來計算加權節點相似性.

定義3.社區質量函數.給定社區Cx及其屬性子空間lx，則社區Cx質量函數的定義為：

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

(6)

對于具有較高質量分數的目標社區而言，存在較多“期望”低的內部邊，與此同時成對節點的相似性很高.這確保了式(6)中第1項的最大化.此外，社區要么沒有交叉邊，要么現有交叉邊“期望”高，或者內部節點基于屬性子空間與邊界節點的相似性接近于0，因此第2項消失.

3.2 候選目標社區發現

確定了候選目標社區中心點集及對應屬性子空間權重后，挖掘每個候選中心點集及屬性子空間權重所在的潛在目標社區.首先以中心點集作為目標社區的種子，然后擴展種子以找到目標社區.算法1中描述了第x個初始潛在目標社區Cx的挖掘過程.

算法1.潛在初始目標社區挖掘.

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

輸出:初始潛在目標社區Cx.

①Ncn=?；*存儲候選節點*

③Ncn={vj|vi和vj之間有邊,vi∈Cx,vj?Cx∧vj∈V};*將集合中現有節點的鄰居節點作為候選節點*

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

⑤ Repeat

⑥vbest=null；*最佳候選節點*

⑦ for eachv∈Ncndo

Q(Cx,lx)；*節點v加入社區時質量值的變化*

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

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

{vbest}；*更新候選節點*

采用貪婪算法對目標社區進行局部調整，在每次迭代中，計算所有可能調整質量變化的操作，選擇社區質量正變化最大的節點加入目標社區.迭代繼續，直到沒有節點的加入導致質量發生正的改變，社區的質量值不再增加.

節點的添加基于改進的最優搜索策略，即每次添加的節點都是當前最優的選擇.類似地，采用了追溯策略檢查是否有節點的移除使得社區的質量正向增加.社區的質量函數值小于等于1，每次選擇節點加入社區或者刪除社區中的節點都能使得目標社區的質量值正向增加，因此算法的收斂性得到保證.

3.3 社區綜合質量評估

本節首先定義社區外部質量分數來衡量社區外部影響能力，然后結合社區的質量分數和外部影響能力綜合評估社區綜合質量.

(7)

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

定義4.社區對節點影響分數.一個社區Cx對其鄰居節點bj的影響分數定義為

(8)

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

(9)

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

為了精確挖掘與用戶給定的先驗信息相關的目標社區，結合社區質量及社區與內部節點對外影響分數定義社區綜合質量分數，并降序排列所有候選目標社區.

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

(10)

因此，可以挖掘質量較高且外部影響力較大的目標社區.

3.4 方法推廣

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

4 實 驗

為驗證本文所提出方法的有效性及其效率，本節分別在人工數據集和真實數據集上設計了2組不同的實驗.首先，對實驗所用到的人工數據集和真實數據集分別進行了描述；其次，觀察不同參數值的設置對實驗結果的影響，選擇適宜的參數值；最后，選取3個目標社區發現方法與本文所提出方法進行分析比較.

4.1 實驗設置

4.1.1 人工數據集

對于社區檢測結果的評估最直接的方法就是將檢測結果和現實網絡中真實社區相比較.考慮到現實世界中針對目標社區發現的可用網絡較少且質量參差不齊，利用人工生成網絡對本文所提方法的有效性進行測評成為評價社區檢測方法優劣的高效可行的方法.本節利用LFR Benchmark算法生成人工圖，具體參數設置參照文獻[31].

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

實驗利用給定的來自社區1的樣例節點挖掘社區1，詳情如表1所示：

Table 1 Synthetic Network

4.1.2 真實數據集

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

Table 2 The Real-World Network Datasets

4.2 實驗結果

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

4.2.1 參數分析

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

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

Fig. 2 Parameter α analysis

當α≥0.7時，5個數據集上的NMI和F1評分均值變化較小，基本趨于穩定，因此設定α=0.7，該數值也將用作后續實驗中參數α取值.

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

Fig. 3 Parameter β analysis

從圖3可以看到，β=0.65左右時，5個數據集上的NMI和F1均值較高，即設定參數β=0.65可使得檢測結果與標準結果之間相似度趨于最大化，該數值也將用作后續實驗中參數的取值.

4.2.2 與其他方法的對比

選取2個目標社區劃分方法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]和一個未考慮社區外部影響力的目標社區發現方法TC-AE(target community discovery based on attribute subspace with entropy weighting)[31]與本文方法分別從發現的目標社區質量和運行時間2方面進行比較.其中FocusCO創新性地提出了以用戶為中心的屬性圖目標社區發現方法；TSCM基于目標子空間挖掘目標社區集合；TC-AE在不考慮社區的外部影響力及邊“期望”的情況下劃分目標社區.因此本文選取上述3種方法作為對比方法，對比結果如表3所示.

為了進一步驗證該方法的有效性，在上述參數設置下，本文基于真實網絡數據集對TCPI，FocusCO，TSCM，TC-AE方法進行了評價.所有比較方法的平均運行次數超過10次，每次運行都隨機提供樣本中描述的默認參數.圖4顯示了不同數據集上不同指標的總體性能.

Table 3 Comparison of Different Target Community Detection Methods

Fig. 4 NMI/F1 scores on different datasets

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

4.2.3 擴展性驗證

為了進一步驗證本文所提出方法的可擴展性，基于LFR Benchmark生成具有不同節點個數、不同邊數或不同屬性個數社區的圖，并運行基于2重剪枝策略的融合用戶興趣與影響力的目標社區發現方法.圖5顯示了在人工網絡上隨著節點或屬性數量的增加子空間挖掘運行的平均時間變化情況.

Fig. 6 Experimental results on Amazon data

Fig. 5 Running time analysis of mining target subspace

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

4.2.4 案例分析

由于真實網絡對于融合影響力的目標社區的集合沒有給定的基準，而且大多數社區發現方法都未能考慮節點及社區影響力問題，因此在真實的網絡中對本文所提出的方法很難進行定量分析.以下在真實網絡的案例研究主要說明本文所提出方法的應用價值.針對本文所提出的方法在Amazon數據集上的運行結果設計了目標社區的案例研究.如圖6所示，同一種形狀的節點隸屬于同一個社區，特別地標示出用戶給出的樣例節點.

圖6中，左邊為原始網絡，右邊為檢測結果，其中每個圓圈中同一形狀節點構成的子圖為一個真實社區，六邊形節點表示用戶給定的樣例節點，七角星節點表示部分社區的鄰居節點.同樣地，對于某個產品的推銷人員而言，除了挖掘經常購買該產品的客戶所構成的社區方便進行客戶維護外，還需要關注該社區內人員能否吸引更多的潛在客戶進行購買，以便擴大產品銷售市場，增加市場占有率.因此，本文提出的方法在現實生活中有較高的應用價值.

5 總 結

本文提出面向屬性網絡的融合用戶興趣偏好與影響力的目標社區發現方法TCPI，挖掘用戶偏好信息，挖掘包含樣例節點極大k-團作為潛在目標社區核心，并設計熵加權屬性權重計算方法來提取潛在目標社區屬性子空間權重，捕獲用戶偏好；其次，綜合社區內部緊密性和外部可分離性定義社區質量函數，以極大k-團為核心擴展得到高質量潛在目標社區；最后，定義社區外部影響分數，并結合社區質量函數值及外部影響分數對所有潛在目標社區排序，輸出綜合質量較高的社區為目標社區.并且，計算得到所有極大k-團的屬性子空間權重后，設計了2重剪枝策略提升方法的性能和效率.此外，在用戶提供額外屬性信息的情況下，該方法可進一步推廣.在人工網絡和真實網絡數據集上的實驗結果印證了本文所提方法的效率和有效性.