李曉紅，王閃閃，周學(xué)銘，宿 云

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

0 概述

復(fù)雜網(wǎng)絡(luò)是指具有自組織、自相似、吸引子、小世界、無(wú)標(biāo)度特征中部分或全部性質(zhì)的網(wǎng)絡(luò)，如現(xiàn)實(shí)生活中的交通網(wǎng)、社交網(wǎng)、基因調(diào)控網(wǎng)等。社區(qū)是指具有相同或相似特性的節(jié)點(diǎn)構(gòu)成的集合，同一社區(qū)內(nèi)部節(jié)點(diǎn)之間鏈接的概率比不同社區(qū)間節(jié)點(diǎn)的鏈接概率高得多，這反映了復(fù)雜網(wǎng)絡(luò)中個(gè)體行為的局部特征及其相互之間的關(guān)聯(lián)關(guān)系。對(duì)于社區(qū)發(fā)現(xiàn)的研究有助于揭示網(wǎng)絡(luò)重要結(jié)構(gòu)和功能信息，在過(guò)去的幾十年中，研究人員設(shè)計(jì)了大量的社區(qū)發(fā)現(xiàn)算法，但隨著研究的深入發(fā)現(xiàn)社區(qū)結(jié)構(gòu)還表現(xiàn)出重疊特性，例如社交網(wǎng)絡(luò)中有一些節(jié)點(diǎn)同時(shí)歸屬于不同社區(qū)，且這種同時(shí)屬于多個(gè)社區(qū)的節(jié)點(diǎn)又是信息傳播和網(wǎng)絡(luò)演變中的關(guān)鍵節(jié)點(diǎn)。因此，區(qū)分穩(wěn)定的重疊社區(qū)并設(shè)計(jì)高效的發(fā)現(xiàn)算法是亟需解決的問(wèn)題，受到研究人員的廣泛關(guān)注。

目前，重疊社區(qū)發(fā)現(xiàn)算法主要包括基于派系過(guò)濾、基于局部擴(kuò)張及優(yōu)化、基于線圖或邊社區(qū)3 類。基于派系過(guò)濾的重疊社區(qū)發(fā)現(xiàn)算法［1-2］是一種基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法，從網(wǎng)絡(luò)特性出發(fā)，認(rèn)為社區(qū)由多個(gè)K 派系組成，每個(gè)派系都是一個(gè)全連通網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)可以劃分到不同的K派系中。EVANS［3］提出的Clique Graph 借鑒了派系過(guò)濾的思想，通過(guò)在網(wǎng)絡(luò)中建立派系圖來(lái)研究社區(qū)結(jié)構(gòu)。盧志剛等［4］提出一種基于貪婪派系擴(kuò)張（Greedy Factional Expansion，GFE）的重疊社區(qū)發(fā)現(xiàn)算法。該算法根據(jù)企業(yè)社會(huì)化網(wǎng)絡(luò)中極大派系間的鏈接強(qiáng)度將原始網(wǎng)絡(luò)圖轉(zhuǎn)換成最大派系圖，在最大化適應(yīng)度函數(shù)的條件下貪婪擴(kuò)張最大派系圖中的種子派系進(jìn)行社區(qū)發(fā)現(xiàn)。但是，基于派系過(guò)濾的重疊社區(qū)發(fā)現(xiàn)算法受限于網(wǎng)絡(luò)中缺失完全子圖，自由參數(shù)較多，不同參數(shù)設(shè)定對(duì)結(jié)果影響較大，并且經(jīng)常產(chǎn)生較大的時(shí)間復(fù)雜度。WEN 等［5］提出一種基于最大團(tuán)的多目標(biāo)進(jìn)化算法（MΟEA）檢測(cè)重疊社區(qū)。該算法用原始圖的一組最大團(tuán)作為節(jié)點(diǎn)定義，兩個(gè)最大團(tuán)可共享原始圖的相同節(jié)點(diǎn)。MΟEA 以類似于非重疊社區(qū)檢測(cè)的方式處理重疊社區(qū)檢測(cè)問(wèn)題。基于局部擴(kuò)張及優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法通常將種子節(jié)點(diǎn)作為初始社區(qū)，通過(guò)不斷優(yōu)化質(zhì)量函數(shù)擴(kuò)展社區(qū)，最終得出社區(qū)劃分結(jié)果［6-7］。代表算法為局部擴(kuò)展算法（Local Fitness Method，LFM）［8］，LFM 隨機(jī)選取一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展，通過(guò)迭代局部社區(qū)得到重疊社區(qū)。CHANG 等［9］提出一種新的重疊社區(qū)發(fā)現(xiàn)算法ENFI，該算法利用網(wǎng)絡(luò)的微觀特征，通過(guò)計(jì)算朋友親密度提取本地社區(qū)并形成網(wǎng)絡(luò)的重疊社區(qū)。WILDER 等［10］用隨機(jī)游走算法為每個(gè)節(jié)點(diǎn)找出一個(gè)子圖，同時(shí)計(jì)算出該節(jié)點(diǎn)的權(quán)重以及正比于權(quán)重的概率，并以此判定初始節(jié)點(diǎn)，該算法的時(shí)間復(fù)雜度較高。但是以上算法具有不確定性和向外擴(kuò)展性，形成的網(wǎng)絡(luò)模塊容易存在不穩(wěn)定性和漂移性。基于線圖或邊社區(qū)的重疊社區(qū)發(fā)現(xiàn)算法計(jì)算過(guò)程復(fù)雜，不適用于小規(guī)模邊社區(qū)。AHN 等［11］根據(jù)鏈接網(wǎng)絡(luò)非重疊與重疊的轉(zhuǎn)化思想，對(duì)網(wǎng)絡(luò)中的鏈接進(jìn)行層次聚類提出LINK 算法，該算法揭示了這種邊社區(qū)在真實(shí)網(wǎng)絡(luò)中的普遍存在性。除了以上3 類重疊社區(qū)發(fā)現(xiàn)算法之外，研究人員還提出了一些其他的改進(jìn)算法［12-14］，均取得了不錯(cuò)的效果。

本文借鑒物理學(xué)勢(shì)能中的拓?fù)鋭?shì)思想，提出一種基于拓?fù)鋭?shì)與信任度調(diào)整的重疊社區(qū)發(fā)現(xiàn)算法。由于網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)周圍存在一個(gè)作用場(chǎng)，場(chǎng)中的任何節(jié)點(diǎn)都將受到其他節(jié)點(diǎn)的聯(lián)合作用，因此利用拓?fù)鋭?shì)選取核心節(jié)點(diǎn)，然后從核心節(jié)點(diǎn)出發(fā)構(gòu)建初始社區(qū)群，并且充分利用社區(qū)間的共享邊越多社區(qū)越相容、節(jié)點(diǎn)間頻繁的交互和聯(lián)系促使社區(qū)發(fā)生融合這兩個(gè)特性，通過(guò)調(diào)整信任度進(jìn)行社區(qū)合并與調(diào)整。

1 相關(guān)工作

假設(shè)復(fù)雜網(wǎng)絡(luò)表示為有向圖G=（V，Ε，A），其中：頂點(diǎn)集合V=｛ν1，ν2，…，νi，…，νn｝，n表示節(jié)點(diǎn)數(shù)；Ai=｛ai1，ai2，…，aim｝表示節(jié)點(diǎn)νi的屬性集合，m=|A|表示網(wǎng)絡(luò)屬性數(shù)。

1.1 改進(jìn)的節(jié)點(diǎn)拓?fù)鋭?shì)

在物理學(xué)中，場(chǎng)表示物體間的相互作用，這種相互作用并不是接觸才有的，勢(shì)表示特定場(chǎng)中的質(zhì)點(diǎn)從一點(diǎn)移動(dòng)到另一點(diǎn)時(shí)產(chǎn)生的功。勢(shì)和場(chǎng)的分布對(duì)應(yīng)物質(zhì)粒子之間由位置確定的勢(shì)能分布［15-16］，并且這種勢(shì)能分布與粒子之間的距離成遞減關(guān)系，隨著距離的增長(zhǎng)勢(shì)能下降，直至衰減為0。類比于勢(shì)場(chǎng)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)周圍存在著一個(gè)作用場(chǎng)，位于場(chǎng)中的任何節(jié)點(diǎn)都將受到其他節(jié)點(diǎn)的聯(lián)合作用。通過(guò)路徑描述節(jié)點(diǎn)之間的聯(lián)系，利用路徑長(zhǎng)度描述節(jié)點(diǎn)間相互作用力的強(qiáng)弱。因此，節(jié)點(diǎn)間的相互作用與節(jié)點(diǎn)屬性及節(jié)點(diǎn)間的距離密切相關(guān)，并且每個(gè)節(jié)點(diǎn)的影響力會(huì)隨著節(jié)點(diǎn)間路徑長(zhǎng)度的增長(zhǎng)而衰減。采用高斯勢(shì)函數(shù)描述這種相互作用，將復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)νi的拓?fù)鋭?shì)定義為某個(gè)范圍內(nèi)其他節(jié)點(diǎn)在該節(jié)點(diǎn)處產(chǎn)生能量的累加和，如式（1）所示：

其中：Γ（νi）表示節(jié)點(diǎn)νi影響某個(gè)范圍內(nèi)的節(jié)點(diǎn)集合；常數(shù)σ∈（0，+∞）用來(lái)控制節(jié)點(diǎn)的作用范圍；d（νi，νj）表示節(jié)點(diǎn)νj到節(jié)點(diǎn)νi的最短路徑長(zhǎng)度（i≠j）。

首先，為了突出各個(gè)節(jié)點(diǎn)固有屬性的差異，m（νj）的值由節(jié)點(diǎn)屬性值決定［17］。假定節(jié)點(diǎn)νi的屬性值為｛wi1，wi2，…，wij，…，wim｝，則節(jié)點(diǎn)νi的屬性重要性表示為其次，由于節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置及其鏈接關(guān)系存在差異，使得各個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中具有不同的重要性。為了突出這種差異，引入位置權(quán)重wweight(νj)，表示距離核心節(jié)點(diǎn)越遠(yuǎn)，位置權(quán)重越小。wweight(νj)計(jì)算公式如下：

同時(shí)，假設(shè)式（1）的拓?fù)鋭?shì)滿足規(guī)范化條件，則?νi∈V的拓?fù)鋭?shì)可重寫為：

1.2 信任值調(diào)整

從網(wǎng)絡(luò)結(jié)構(gòu)的角度來(lái)看，兩個(gè)節(jié)點(diǎn)νi與νj之間擁有的公共鄰居越多，它們?cè)较嗨?。擴(kuò)展至社區(qū)，同樣地，如果兩個(gè)社區(qū)共享邊較多，就意味著社區(qū)間重疊的部分越多，社區(qū)就越相容。用于比較有限集合之間的相似性與差異性的Jaccard 系數(shù)［18］可描述這種結(jié)構(gòu)上的重疊程度。除此之外，網(wǎng)絡(luò)中的節(jié)點(diǎn)不是獨(dú)立存在的，它們之間具有不同親疏的交互和聯(lián)系。社區(qū)間的信任解析為彼此所含節(jié)點(diǎn)之間的認(rèn)同，而這種認(rèn)同實(shí)質(zhì)上是一個(gè)互動(dòng)問(wèn)題，互動(dòng)會(huì)改變它們之間的關(guān)系，使它們發(fā)生交叉甚至融合，因此，采用節(jié)點(diǎn)間相似度來(lái)體現(xiàn)這種互動(dòng)。綜上，本文基于社區(qū)間的共享邊越多社區(qū)越相容及節(jié)點(diǎn)間頻繁的交互和聯(lián)系會(huì)促使社區(qū)發(fā)生融合這兩個(gè)特性判斷兩個(gè)社區(qū)能否合并，稱此過(guò)程為調(diào)整信任度。調(diào)整信任度的計(jì)算公式如下：

其中：λ為調(diào)節(jié)參數(shù)（0＜λ＜1），用于控制分析社區(qū)間共享邊數(shù)和社區(qū)間信任度的占比；NNE(Ci,Cj)表示兩社區(qū)共享的邊數(shù)；T(Ci,Cj)表示社區(qū)Ci與Cj的信任度［19］，為兩社區(qū)內(nèi)所有節(jié)點(diǎn)間信任度的和。NNE(Ci,Cj)和T(Ci,Cj)的計(jì)算公式如下：

其中：N（νi）為節(jié)點(diǎn)νi依附的邊構(gòu)成的集合；N（Ci，Cj）表示社區(qū)Ci與Cj合并后所包含的邊。

節(jié)點(diǎn)間的信任度采用基于節(jié)點(diǎn)屬性的相似度來(lái)度量，計(jì)算公式如下：

其中：ai、aj分別為節(jié)點(diǎn)νi、νj的屬性向量。

2 重疊社區(qū)發(fā)現(xiàn)算法

本文提出的基于節(jié)點(diǎn)拓?fù)鋭?shì)和信任值調(diào)整的重疊社區(qū)發(fā)現(xiàn)算法本質(zhì)上是發(fā)現(xiàn)核心節(jié)點(diǎn)并以該核心節(jié)點(diǎn)為中心進(jìn)行擴(kuò)展形成社區(qū)的過(guò)程。為方便描述，將本文算法簡(jiǎn)稱為CTPT 算法。CTPT 算法流程如圖1 所示，其中q表示最終合并社區(qū)的個(gè)數(shù)。

圖1 CTPT 算法流程Fig.1 Procedure of CTPT algorithm

2.1 核心節(jié)點(diǎn)選取

首先，計(jì)算網(wǎng)絡(luò)G中任意一對(duì)節(jié)點(diǎn)νi和νj的最短路徑長(zhǎng)度d（νi，νj），構(gòu)建最短路徑矩陣MMinDist。然后，利用MMinDist提供的路徑信息，生成每個(gè)節(jié)點(diǎn)νi的作用節(jié)點(diǎn)集合Γ（νi）。接下來(lái)，按照式（3）迭代地計(jì)算每個(gè)節(jié)點(diǎn)的拓?fù)鋭?shì)φ（νi），并以此為判斷依據(jù)選取K個(gè)φ（νi）最大的節(jié)點(diǎn)作為核心節(jié)點(diǎn)，保存在Top 數(shù)組中。核心節(jié)點(diǎn)選取流程如圖2 所示。

圖2 核心節(jié)點(diǎn)選取流程Fig.2 Procedure of core node selection

2.2 社區(qū)形成與再調(diào)整

在初始化時(shí)，將Top［K］中的每一個(gè)核心節(jié)點(diǎn)視為一個(gè)社區(qū)。首先，從單節(jié)點(diǎn)社區(qū)出發(fā)，依次取出V中的節(jié)點(diǎn)νi并嘗試加入社區(qū)IICk，計(jì)算模塊度函數(shù)Q［20］。如果Q增大，則將該節(jié)點(diǎn)加入社區(qū)，否則嘗試將節(jié)點(diǎn)νi加入下一個(gè)社區(qū)IICk+1，其中emm表示社區(qū)m內(nèi)部所有節(jié)點(diǎn)之間的邊的集合，am表示所有連接到社區(qū)m的邊數(shù)，emn表示社區(qū)m和社區(qū)n之間的邊數(shù)。然后，通過(guò)調(diào)整信任度對(duì)已形成的初始社區(qū)群落進(jìn)行合并與再調(diào)整，上述步驟完成后形成最終社區(qū)。未加入任何社區(qū)的節(jié)點(diǎn)被視為離群點(diǎn)，并將其剔除。社區(qū)形成與合并流程如圖3 所示。

圖3 社區(qū)發(fā)現(xiàn)與合并流程Fig.3 Procedure of community discovery and merging

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

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

3.1.1 數(shù)據(jù)集

為評(píng)價(jià)CTPT 算法性能，實(shí)驗(yàn)采用兩類數(shù)據(jù)集：1）LFR 人工網(wǎng)絡(luò)數(shù)據(jù)集，由經(jīng)典的LFR 基準(zhǔn)程序生成，可以模擬具有重疊社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)集，主要用于測(cè)試社區(qū)檢測(cè)算法的優(yōu)劣；2）真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，來(lái)源于斯坦福大學(xué)的大型網(wǎng)絡(luò)數(shù)據(jù)集網(wǎng)站（http：//memetracker.org/data/index.html）。表1 給出了人工網(wǎng)絡(luò)數(shù)據(jù)集Net1、Net2 和Net3 的參數(shù)信息，其中，Οn表示重疊節(jié)點(diǎn)數(shù)，μ表示LFR 網(wǎng)絡(luò)中的混合系數(shù)，其值越大表明所生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)越復(fù)雜。表2 給出了真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集ego-Facebook、Musae-twitch 和Web-flickr 的參數(shù)信息。ego-Facebook 數(shù)據(jù)集由facebook 的朋友列表組成，是facebook 上用戶間的社交網(wǎng)絡(luò)。Musae-twitch 數(shù)據(jù)集是使用某種語(yǔ)言進(jìn)行流式傳輸?shù)挠螒蛲婕业腡witch 用戶-用戶網(wǎng)絡(luò)，該網(wǎng)絡(luò)中的節(jié)點(diǎn)是用戶本身，鏈接是他們之間的好友關(guān)系。Web-flickr 是用戶分享圖片和視頻的社交網(wǎng)絡(luò)，該網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)都是flickr 中的用戶，每一條邊都是用戶之間的好友關(guān)系。另外，每一個(gè)節(jié)點(diǎn)都有標(biāo)簽，用于標(biāo)識(shí)用戶的興趣小組。

表1 LFR 人工網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)設(shè)置Table 1 Parameter setting of LFR artificial network dataset

表2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)設(shè)置Table 2 Parameter setting of real network dataset

為評(píng)價(jià)算法性能，通常需要選取度量社區(qū)劃分好壞的性能指標(biāo)。擴(kuò)展模塊度是最常用的指標(biāo)之一，計(jì)算公式如下：

指標(biāo)歸一化互信息（Normalized Mutual Information，NMI）［21］用于度量檢測(cè)到的社區(qū)與真值之間的距離，計(jì)算公式如下：

其中：H（X|Y）表示X對(duì)Y的規(guī)范條件熵；H（Y|X）表示Y對(duì)X的規(guī)范條件熵，該值越大，意味著算法所發(fā)現(xiàn)社區(qū)與網(wǎng)絡(luò)真實(shí)社區(qū)相吻合的程度越高。

3.1.2 對(duì)比算法

將本文提出的CTPT算法與以下4種算法進(jìn)行對(duì)比：

1）基于隸屬度傳播（Membership-Degree Propagation，MDP）的重疊社區(qū)劃分算法［22］：以種子節(jié)點(diǎn)的基本特征為依據(jù)構(gòu)建網(wǎng)絡(luò)節(jié)點(diǎn)之間的隸屬度傳播模型，將種子節(jié)點(diǎn)的社團(tuán)隸屬度傳播至非種子節(jié)點(diǎn)進(jìn)行社區(qū)發(fā)現(xiàn)。

2）面向?qū)傩跃W(wǎng)絡(luò)的重疊社區(qū)劃分算法（overlapping community discovery Algorithm for Attributed Networks，ANA）［23］：利用節(jié)點(diǎn)的密集度和間隔度搜索局部密度中心，并將其作為社區(qū)中心，通過(guò)計(jì)算非中心節(jié)點(diǎn)的社區(qū)隸屬度實(shí)現(xiàn)重疊社區(qū)的劃分。

3）基于GFE 的重疊社區(qū)劃分算法［4］：根據(jù)網(wǎng)絡(luò)中極大派系間的鏈接強(qiáng)度將原始網(wǎng)絡(luò)圖轉(zhuǎn)換成最大派系圖，在最大化適應(yīng)度函數(shù)的條件下，貪婪擴(kuò)張最大派系圖中的種子派系進(jìn)行社區(qū)發(fā)現(xiàn)。

4）基于種子擴(kuò)張（Two Expansions of Seeds，TES）的重疊社區(qū)劃分算法［24］：首先根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)涮卣餍纬沙跏忌鐓^(qū)，然后采用重力度再次進(jìn)行社區(qū)的合并和擴(kuò)展。

3.2 結(jié)果分析

3.2.1 LFR 人工生成網(wǎng)絡(luò)數(shù)據(jù)集上的結(jié)果分析

圖4 給出了在不同規(guī)模的LFR 人工生成網(wǎng)絡(luò)數(shù)據(jù)集上5 種重疊社區(qū)發(fā)現(xiàn)算法隨重疊社區(qū)數(shù)量變化對(duì)應(yīng)NMI 的變化規(guī)律。CTPT 算法考慮不同結(jié)構(gòu)和屬性的影響，分別設(shè)置調(diào)整信任度的調(diào)節(jié)參數(shù)λ為0.4、0.5、0.6，實(shí)驗(yàn)結(jié)果顯示λ=0.5 時(shí)效果最好。

圖4 不同重疊社區(qū)數(shù)量對(duì)算法NMI 值的影響Fig.4 Influence of the number of different overlapping communities on the NMI value of the algorithm

通過(guò)觀察圖4 中NMI 變化曲線可以發(fā)現(xiàn)：隨著重疊社區(qū)數(shù)量的增加，5 種算法在3 組數(shù)據(jù)集上的NMI 值不斷減??；隨著網(wǎng)絡(luò)規(guī)模的增大，5 種算法的效率均有所下降，但CTPT 算法的社區(qū)劃分效果相對(duì)較好，并且具有較好的穩(wěn)定性。其中，ANA 算法在Net3 網(wǎng)絡(luò)數(shù)據(jù)集上表現(xiàn)較差，NMI 值下降較快，比其他算法效率差。同時(shí)，對(duì)比CTPT 算法在3 個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上的效果后發(fā)現(xiàn)，CTPT 算法在Net3 網(wǎng)絡(luò)數(shù)據(jù)集上得到的NMI 值低于Net1 和Net2 網(wǎng)絡(luò)數(shù)據(jù)集，意味著網(wǎng)絡(luò)越復(fù)雜，CTPT 算法的執(zhí)行效果越差，這是下一步需要改進(jìn)之處。由此可見(jiàn)，在大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集的重疊社區(qū)檢測(cè)方面，CTPT 算法具有較好的檢測(cè)效果和穩(wěn)定性。

3.2.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的結(jié)果分析

在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上采用擴(kuò)展模塊度進(jìn)行重疊社區(qū)發(fā)現(xiàn)算法的性能評(píng)估。表3、表4 給出了CTPT算法在3 個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果，分別選取社區(qū)數(shù)量|C|在不同值的情況下，運(yùn)行15 次CTPT 算法所得的EQ 均值作為最終結(jié)果。

表3 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上社區(qū)發(fā)現(xiàn)的EQ 值（|C|=20）Table 3 EQ value of community discovery on real network dataset（|C|=20）

表4 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上社區(qū)發(fā)現(xiàn)的EQ 值（|C|=30）Table 4 EQ value of community discovery on real network dataset（|C|=30）

由于CTPT 算法充分考慮了社區(qū)形成過(guò)程中各種因素的共同作用，一方面引入拓?fù)鋭?shì)，考慮了網(wǎng)絡(luò)結(jié)構(gòu)（最短路徑長(zhǎng)度）不同導(dǎo)致的節(jié)點(diǎn)重要性不同，另一方面多次融合節(jié)點(diǎn)屬性，兼顧了節(jié)點(diǎn)交互對(duì)社區(qū)的影響，因此在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上性能表現(xiàn)良好，實(shí)驗(yàn)結(jié)果整體優(yōu)于對(duì)比算法。TES 算法與CTPT 算法的第一階段均為使用網(wǎng)絡(luò)的節(jié)點(diǎn)拓?fù)涮卣鞯玫匠跏忌鐓^(qū)，在3 個(gè)網(wǎng)絡(luò)上的EQ 值僅次于CTPT 算法，表現(xiàn)較好，尤其是在Musae-twitch 網(wǎng)絡(luò)數(shù)據(jù)集上，在最好情況下EQ 值僅相差0.025。ANA 算法實(shí)現(xiàn)時(shí)會(huì)產(chǎn)生較小的鏈接社區(qū)，阻礙了社區(qū)的形成，導(dǎo)致難以獲得較好的性能，因此在3 個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均是最差的。

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

本文充分考慮社區(qū)形成過(guò)程中各種因素的共同作用，提出基于網(wǎng)絡(luò)拓?fù)鋭?shì)與信任度調(diào)整的重疊社區(qū)發(fā)現(xiàn)算法。由于節(jié)點(diǎn)在網(wǎng)絡(luò)中所處位置及其鏈接關(guān)系存在差異，使得節(jié)點(diǎn)重要性不同，通過(guò)網(wǎng)絡(luò)拓?fù)鋭?shì)來(lái)體現(xiàn)這一特征，并且每個(gè)節(jié)點(diǎn)又具有獨(dú)立的固有屬性，因此將屬性的影響力疊加在拓?fù)鋭?shì)的計(jì)算過(guò)程中。在社區(qū)合并階段，將節(jié)點(diǎn)間的信任度作為初始社區(qū)能否合并的依據(jù)，形成最終的社區(qū)劃分。在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法相對(duì)于同類算法的優(yōu)越性。在下一階段的研究中將嘗試在核心節(jié)點(diǎn)的選取中加入注意力機(jī)制來(lái)體現(xiàn)節(jié)點(diǎn)重要性，利用圖嵌入技術(shù)優(yōu)化生成的屬性向量，提升重疊社區(qū)發(fā)現(xiàn)算法的實(shí)現(xiàn)效率，并最終將其應(yīng)用于實(shí)際網(wǎng)絡(luò)分析及網(wǎng)絡(luò)推薦系統(tǒng)。