一種融合鄰邊屬性的個(gè)人社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

李有紅，王學(xué)軍，諶裕勇，趙躍龍，徐文賢，3

（1.廣東工業(yè)大學(xué)華立學(xué)院輿情大數(shù)據(jù)中心，廣州511325；2.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣州510006；3.華南師范大學(xué)圖書館，廣州510631）

0 概述

隨著信息技術(shù)的快速發(fā)展以及互聯(lián)網(wǎng)絡(luò)應(yīng)用的日益普及，社交網(wǎng)絡(luò)中的交互關(guān)系呈現(xiàn)出多樣化發(fā)展趨勢(shì)。社區(qū)是社交網(wǎng)絡(luò)中一種典型的隱形中觀結(jié)構(gòu)［1-3］，利用社區(qū)發(fā)現(xiàn)方法識(shí)別個(gè)人社交網(wǎng)絡(luò)［4-5］中的社區(qū)，可實(shí)現(xiàn)最大限度的資源共享、咨詢決策和信息服務(wù)等功能，利用社交數(shù)據(jù)構(gòu)建智能化的社交電商系統(tǒng)已成為當(dāng)今知識(shí)發(fā)現(xiàn)領(lǐng)域的研究熱點(diǎn)。在個(gè)人社交網(wǎng)絡(luò)中，邊是結(jié)構(gòu)的支撐，節(jié)點(diǎn)的屬性是網(wǎng)絡(luò)多樣性的重要延伸，因此邊和屬性的權(quán)重、時(shí)效、密集程度等多模特征演化都可能會(huì)導(dǎo)致社區(qū)結(jié)構(gòu)的重構(gòu)。在社交網(wǎng)絡(luò)中，兩條邊的公共鄰邊（與兩條邊各自節(jié)點(diǎn)相連的邊）越多，鄰邊和節(jié)點(diǎn)在同一社交圈的可能性越大。本文在融合鄰邊結(jié)構(gòu)及其節(jié)點(diǎn)屬性相似特性的基礎(chǔ)上，利用差分進(jìn)化的群體智能社會(huì)蜘蛛優(yōu)化（Social Spider Optimization，SSO）算法尋求最佳的個(gè)人社區(qū)結(jié)構(gòu)劃分，并提出融合鄰邊屬性的群智能個(gè)人社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法NLA/SCD。

1 相關(guān)工作

1.1 個(gè)人社交網(wǎng)絡(luò)特征分析

在個(gè)人社交網(wǎng)絡(luò)中，邊和屬性的權(quán)重、時(shí)效、密集程度等多模特征演化可能會(huì)導(dǎo)致社區(qū)結(jié)構(gòu)的重構(gòu)。如圖1所示，在現(xiàn)實(shí)世界中，一個(gè)以個(gè)人親屬關(guān)系、同學(xué)關(guān)系等組成的社交網(wǎng)絡(luò)圈隨著用戶個(gè)人的地理位置、興趣愛好、研究方向等內(nèi)在因素（節(jié)點(diǎn)屬性）的變化，網(wǎng)絡(luò)結(jié)構(gòu)也會(huì)發(fā)生變化。

圖1 帶有社區(qū)標(biāo)記的個(gè)人社交網(wǎng)絡(luò)Fig.1 Personal social network with community flags

在社交網(wǎng)絡(luò)結(jié)構(gòu)中，兩條邊的公共鄰邊越多，鄰邊和節(jié)點(diǎn)在同一社交圈的可能性就越大。如圖2所示，邊1 和邊9 存在鄰邊3 和鄰邊8，因此邊1 和邊9就可能屬于同一個(gè)社區(qū)。在微信社交圈中，如果用戶朋友的朋友之間相互認(rèn)識(shí)，那么兩個(gè)用戶各自的朋友在一個(gè)社交圈的概率就很大。邊1 的鄰邊有邊2、邊3、邊4、邊6、邊7 和邊8，其中邊5 和邊9 雖然不是邊1 的鄰邊也不相連，但是分別都與邊1 的兩個(gè)或以上鄰邊相連，因此可認(rèn)為邊5 和邊9 與邊1 的相似程度非常高，它們和各自的節(jié)點(diǎn)屬于同一社區(qū)。

圖2 邊結(jié)構(gòu)相似示意圖Fig.2 Schematic diagram of edge structural similarity

1.2 基于結(jié)構(gòu)和屬性的社區(qū)發(fā)現(xiàn)

目前，關(guān)于個(gè)人社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究主要包括基于拓?fù)浣Y(jié)構(gòu)的劃分［2］和基于主題內(nèi)容的劃分［6］兩個(gè)方面。拓?fù)浣Y(jié)構(gòu)是網(wǎng)絡(luò)關(guān)系的支撐，用戶通過各種長(zhǎng)期的交互關(guān)系建立穩(wěn)定的社交圈。由于個(gè)人社交網(wǎng)絡(luò)社區(qū)具有高度的重疊特性，因此基于邊結(jié)構(gòu)的社區(qū)劃分方法成為近年來的研究熱點(diǎn)。文獻(xiàn)［7］根據(jù)用戶朋友關(guān)系，提出一種基于邊的個(gè)人社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型，并將其應(yīng)用于物聯(lián)網(wǎng)絡(luò)優(yōu)化中。文獻(xiàn)［4］根據(jù)用戶鄰近關(guān)系，采用k-近鄰方法劃分社交網(wǎng)絡(luò)，但該方法中k的取值是影響社區(qū)劃分結(jié)果的關(guān)鍵，k值越大噪聲越多，k值越小可供參考的鄰邊信息越少，社區(qū)劃分精度越低。文獻(xiàn)［5］指出若鄰節(jié)點(diǎn)重疊比例高，則節(jié)點(diǎn)相似度高，并設(shè)計(jì)基于鄰節(jié)點(diǎn)重疊比例的社區(qū)劃分方法。文獻(xiàn)［8］將節(jié)點(diǎn)輪廓和網(wǎng)絡(luò)結(jié)構(gòu)相結(jié)合，設(shè)計(jì)邊輪廓的增強(qiáng)鏈接聚類算法ELC 用于社交圈識(shí)別?；谥黝}內(nèi)容的方法主要是將用戶主題屬性與內(nèi)容關(guān)系強(qiáng)度相結(jié)合。文獻(xiàn)［9］基于微博中的個(gè)人局部屬性特征，設(shè)計(jì)模塊函數(shù)，利用貪婪算法優(yōu)化社團(tuán)劃分。文獻(xiàn)［10］基于社交網(wǎng)絡(luò)語義評(píng)分提出局部子網(wǎng)邊權(quán)重加權(quán)策略并構(gòu)建SNTOCD 算法，在挖掘興趣子群和語義主題方面取得了較好的效果，但該算法仍存在過早收斂的問題。文獻(xiàn)［6］將邊結(jié)構(gòu)和節(jié)點(diǎn)屬性相似相結(jié)合，提出一種擴(kuò)展屬性的個(gè)人社交網(wǎng)絡(luò)發(fā)現(xiàn)算法CESNA，在規(guī)模較大且存在噪聲的情況下，檢測(cè)準(zhǔn)確度和擴(kuò)展性均有所提升，但在個(gè)人社交網(wǎng)絡(luò)環(huán)境中仍存在適應(yīng)性較差的問題。

1.3 群智能蜘蛛算法

社會(huì)蜘蛛優(yōu)化算法［11］是一種優(yōu)化的群體智能進(jìn)化算法，將對(duì)象初始化為雌雄蜘蛛，模仿蜘蛛的社會(huì)行為。在社會(huì)蜘蛛優(yōu)化算法中，通過雌雄個(gè)體差分化的個(gè)體振動(dòng)協(xié)作學(xué)習(xí)、婚配（雜交）等行為進(jìn)行繁衍優(yōu)化，快速高效地探索空間解集（最優(yōu)目標(biāo)解集）。社會(huì)蜘蛛優(yōu)化算法可從局部和全局角度優(yōu)化尋優(yōu)過程，較好地保持種群多樣性，避免尋優(yōu)過程過早收斂［11-12］。

1.3.1 種群初始化

初始化相關(guān)參數(shù)為種群數(shù)目N、概率因子PE、雌雄蜘蛛數(shù)目Nf和Nm，計(jì)算公式如下：

其中：floor（）表示向下取整；rand 表示［0，1］中的隨機(jī)數(shù)，隨機(jī)產(chǎn)生雌雄種群的計(jì)算公式如下：

其中：F和M分別表示雌性和雄性種群；S表示所有種群且S=F∪M；Fjmax和Fjmin分別表示第j維的上限和下限，i∈｛1，2，…，Nf｝，k∈｛1，2，…，Nm｝，j∈｛1，2，…，N｝。

1.3.2 蜘蛛個(gè)體振動(dòng)協(xié)作學(xué)習(xí)

雌性個(gè)體通過震動(dòng)進(jìn)行吸引或排斥其他個(gè)體，雌性蜘蛛分為兩類進(jìn)行個(gè)體更新，若小于等于概率因子PE則為吸引，反之為排斥。Fi個(gè)體的更新方式如下：

其中：Vibci、Vibbi表示個(gè)體i對(duì)個(gè)體c、b的震動(dòng)感知能力；rm為雌性個(gè)體的婚配半徑。

其中：Max 表示最大化問題的取值；Min 表示最小化問題的取值；t表示當(dāng)前迭代次數(shù)；rm、α、β、δ表示在［0，1］中的隨機(jī)數(shù)；l∈｛1，2，…，N｝；Sc表示距離Fi最近且優(yōu)于自身的個(gè)體；Sb表示雌性種群中的最優(yōu)個(gè)體；Vibvl表示個(gè)體l對(duì)個(gè)體v的振動(dòng)感知能力；J（Sl）表示個(gè)體Sl的目標(biāo)函數(shù)適應(yīng)度值；dvl表示個(gè)體v與個(gè)體l的歐氏距離。

雄性蜘蛛的個(gè)體更新按種群適應(yīng)度大小排序，可分為支配和非支配兩種情況，支配個(gè)體具有較強(qiáng)的吸引異性靠攏的能力，而非支配個(gè)體則有向雄性中間個(gè)體聚集的能力。Mi個(gè)體的更新方式如下：

1.3.3 婚配選擇

雌雄蜘蛛經(jīng)過逐代更新后，婚配產(chǎn)生新個(gè)體替換劣質(zhì)蜘蛛，直到滿足條件為止。對(duì)于處于支配的雄性，將按輪盤賭注方式選擇婚配半徑r內(nèi)的雌性組成新的個(gè)體Snew，即dik≤r，i∈Tg，k，k=（1，2，…，D），其中D為雄性支配個(gè)體的總數(shù)。若J（Snew）的適應(yīng)度值優(yōu)于種群中的最差個(gè)體，則用Snew替換它在雄性個(gè)體i婚配半徑內(nèi)的全部雌性個(gè)體并標(biāo)記為子種群Tg，i，在Tg，i內(nèi)雌性個(gè)體q被雄性個(gè)體i選擇婚配的概率為Pq，計(jì)算公式如下：

婚配半徑r的計(jì)算公式如下：

2 個(gè)人社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

2.1 基于群智能蜘蛛算法的社區(qū)發(fā)現(xiàn)

基于群體智能進(jìn)化算法的社區(qū)發(fā)現(xiàn)通常是將社區(qū)劃分質(zhì)量增量作為進(jìn)化篩選條件，以局部節(jié)點(diǎn)相似或聚集系數(shù)等值作為進(jìn)化算法種群的適應(yīng)度函數(shù)值［12-14］，若算法收斂則社區(qū)劃分結(jié)束。為提高社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的適應(yīng)度值，本文將網(wǎng)絡(luò)連接邊、鄰邊屬性相似和基于邊的模塊度增量分別作為蜘蛛種群、適應(yīng)度函數(shù)和進(jìn)化停止條件，設(shè)計(jì)NLA/SCD 算法，NLA/SCD 算法流程如圖3所示。

圖3 NLA/SCD 算法流程Fig.3 Procedure of NLA/SCD algorithm

2.2 鄰邊屬性相似

本文以個(gè)人社交網(wǎng)絡(luò)中連接邊為研究對(duì)象，將社區(qū)發(fā)現(xiàn)問題轉(zhuǎn)換為網(wǎng)絡(luò)邊及其屬性相似的聚類問題。

定義1假設(shè)Gu=(Vu,Eu)是個(gè)人u所屬的社交網(wǎng)絡(luò)，其中和分別表示u所屬社交網(wǎng)絡(luò)的節(jié)點(diǎn)集合和邊集合，基于邊屬性相似的個(gè)人社交網(wǎng)絡(luò)社區(qū)劃分計(jì)算公式如下：

其中，Ce為社區(qū)劃分，θk是邊相似控制系數(shù)，eij和euv分別表示網(wǎng)絡(luò)中的兩條邊，Sim(eij,euv)∈[0,1]。兩條邊越相似在社區(qū)劃分時(shí)被分配到同一社區(qū)的概率越大，即同一社區(qū)內(nèi)部連接的邊密度相比社區(qū)間連接的邊密度更大［2］。

定義2通過邊相似控制系數(shù)對(duì)節(jié)點(diǎn)結(jié)構(gòu)和屬性進(jìn)行聚類來表示鄰邊屬性相似，計(jì)算公式如下：

其中：wt和wp分別表示網(wǎng)絡(luò)邊結(jié)構(gòu)相似和邊屬性相似的控制權(quán)值；Simt(eij,euv)和Simp(eij,euv)分別表示兩條邊eij、euv在網(wǎng)絡(luò)結(jié)構(gòu)和屬性上的相似度值。

定義3在JACCARD 邊結(jié)構(gòu)相似的基礎(chǔ)上，結(jié)合鄰節(jié)點(diǎn)關(guān)系和公共鄰邊來表示鄰邊結(jié)構(gòu)相似，計(jì)算公式如下：

其中：Ni表示連接節(jié)點(diǎn)i的邊集合；E(Ni∩Nu)表示節(jié)點(diǎn)i和v公共的鄰邊集合；ξ∈[0,1]表示邊結(jié)構(gòu)控制系數(shù)，當(dāng)ξ=1 時(shí)類似于文獻(xiàn)［8］，僅考慮邊的JACCARD相似，當(dāng)ξ≠1 時(shí)兼顧?quán)忂厡?duì)邊相似所起的作用。若各條邊兩端節(jié)點(diǎn)間公共的鄰邊越多，則表示邊結(jié)構(gòu)越相似。

在社交網(wǎng)絡(luò)中，除了用戶間的關(guān)注或被關(guān)注關(guān)系外，興趣屬性、意見屬性和所屬地域?qū)傩缘纫蛩囟紩?huì)與社區(qū)形成和演化有關(guān)，因此在社區(qū)劃分時(shí)需要對(duì)邊的屬性進(jìn)行擬合。

定義4節(jié)點(diǎn)屬性向量表示將相鄰多個(gè)節(jié)點(diǎn)的屬性相關(guān)聯(lián)，其中邊的屬性由連接邊節(jié)點(diǎn)的屬性共同決定，即由該邊兩端節(jié)點(diǎn)的所有屬性進(jìn)行and 運(yùn)算組合，計(jì)算公式如下：

定義5通過邊中屬性相同的個(gè)數(shù)與邊屬性總數(shù)比來表示邊屬性相似，計(jì)算公式如下：

其中：num1()表示屬性向量的值為1 的數(shù)量總和。

2.3 模塊度增量判定條件

基于SSO 算法的群體智能社區(qū)劃分的本質(zhì)是最大化模塊度問題。在SSO 算法的優(yōu)化過程中，以邊為個(gè)體的更新與婚配，保證了局部的社區(qū)優(yōu)化。種群的每一代婚配都能產(chǎn)生社區(qū)劃分模塊度增量，當(dāng)連續(xù)幾代邊合并為社區(qū)且模塊度增量不發(fā)生明顯變化時(shí)算法停止，因此引入基于邊的模塊度增量模型［15］，模塊度計(jì)算公式如下：

其中：Wij表示邊Eij的權(quán)值；dw(i)表示與節(jié)點(diǎn)i連接邊的權(quán)值和；表示網(wǎng)絡(luò)中所有連接邊的權(quán)值總和；ci、cj分別表示兩個(gè)社區(qū)內(nèi)部的所有節(jié)點(diǎn)。若節(jié)點(diǎn)i和j屬于同一個(gè)社區(qū)則δ(ci,cj)=1，否則δ(ci,cj)=0。若一條含節(jié)點(diǎn)i的邊從自身所屬社區(qū)Cx合并到另一個(gè)社區(qū)Cy，則社區(qū)的模塊度增量計(jì)算公式如下：

2.4 算法步驟

NLA/SCD 算法的具體步驟如下：

步驟1種群初始化。將社交網(wǎng)絡(luò)用戶連接邊初始化為蜘蛛種群，種群規(guī)模N，概率因子PE，最大迭代次數(shù)max（t），按式（1）初始化Nf和Nm；按式（2）初始化蜘蛛雌雄種群S、F和M。

步驟2按式（10）計(jì)算個(gè)體的相似權(quán)值并排序。

步驟3按式（3）和式（6）更新雌雄蜘蛛種群。

步驟4按式（8）計(jì)算婚配半徑。

步驟5先對(duì)支配雄性個(gè)體婚配并對(duì)其婚配半徑內(nèi)的雌性按式（7）的選擇概率以輪盤賭注方式進(jìn)行婚配，再替換最差個(gè)體。

步驟6若模塊度增量連續(xù)幾代都不增加，則退出進(jìn)化，否則轉(zhuǎn)到步驟2。

步驟7將收斂后的種群標(biāo)簽映射為社區(qū)。

2.5 算法復(fù)雜度分析

NLA/SCD 算法耗時(shí)主要集中于個(gè)體的權(quán)值計(jì)算部分。假設(shè)np為用戶屬性數(shù)量，n為節(jié)點(diǎn)數(shù)，m為種群數(shù)，dmax為最大迭代次數(shù)，最多共享邊為ndmax(dmax-1)/2，連邊屬性計(jì)算的時(shí)間復(fù)雜度為。由于SSO 算法為分散尋優(yōu)，種群迭代的時(shí)間復(fù)雜度約為O(ndmax)，因此NLA/SCD算法理想狀態(tài)的時(shí)間復(fù)雜度約為。

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

為驗(yàn)證NLA/SCD 算法的有效性，本文主要進(jìn)行3 組實(shí)驗(yàn)：1）獲取邊結(jié)構(gòu)相似中控制系數(shù)的最佳值；2）驗(yàn)證SSO 算法的連邊屬性社區(qū)發(fā)現(xiàn)的改進(jìn)效果；3）比較NLA/SCD 算法與傳統(tǒng)智能進(jìn)化社區(qū)發(fā)現(xiàn)算法的劃分精度。在Karate［16］、Dolphins［16］、ego-Facebook［17］和ego-Twitter［17］這4 個(gè)不同規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，如表1所示。實(shí)驗(yàn)運(yùn)行平臺(tái)為Windows 7 企業(yè)版64 bit 操作系統(tǒng)、CPU Intel?CoreTM2 Q9550 ＠ 2.83 GHz、8 GB 內(nèi)存。社區(qū)劃分的評(píng)價(jià)指標(biāo)為模塊度和標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）［16］。NLA/SCD 算法最佳參數(shù)設(shè)置如表2所示。

表1 網(wǎng)絡(luò)數(shù)據(jù)集Table 1 Network datasets

表2 NLA/SCD 算法最佳參數(shù)設(shè)置Table 2 Optimal parameters setting of NLA/SCD algorithm

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

實(shí)驗(yàn)采用斯坦福大學(xué)個(gè)人社交網(wǎng)絡(luò)數(shù)據(jù)集ego-Facebook，以個(gè)人社交圈網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為變量進(jìn)行檢測(cè)，3 組不同規(guī)模的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)分別為59、227 和792，所有參數(shù)值取10 次實(shí)驗(yàn)的平均值，驗(yàn)證邊結(jié)構(gòu)控制系數(shù)ξ對(duì)劃分精度的影響。如圖4所示，當(dāng)邊結(jié)構(gòu)控制系數(shù)ξ取0.5～0.7 時(shí)，本文算法在3 個(gè)網(wǎng)絡(luò)數(shù)據(jù)集中均具有較好的表現(xiàn)，因此在下文實(shí)驗(yàn)中設(shè)置ξ=0.7。

圖4 邊結(jié)構(gòu)相似控制系數(shù)與NMI 的關(guān)系Fig.4 The relationship between edge structure similarity control coefficient and NMI

在ego-Facebook 數(shù)據(jù)集上的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為59、種群規(guī)模為500，wt+wp=1，Wt初始閾值設(shè)置參考文獻(xiàn)［14］，在NLA/SCD 算法中，將各項(xiàng)參數(shù)閾值從0 到1 進(jìn)行調(diào)整測(cè)試來分析NMI 的變化情況。如圖5所示，在ego-Facebook 數(shù)據(jù)集中個(gè)人社交網(wǎng)絡(luò)邊結(jié)構(gòu)相似權(quán)值wt對(duì)網(wǎng)絡(luò)劃分精度具有較大影響，且邊屬性相似權(quán)值wp也會(huì)影響社區(qū)劃分結(jié)果，而概率因子PE設(shè)置與SSO算法［11］接近時(shí)效果最佳，通過參數(shù)設(shè)置實(shí)驗(yàn)驗(yàn)證了表2 理論最佳參數(shù)設(shè)置的正確性與有效性。

圖5 NLA/SCD 參數(shù)設(shè)置對(duì)NMI 的影響Fig.5 The influence of parameters setting on NMI in NLA/SCD

3.2 邊和屬性社區(qū)發(fā)現(xiàn)實(shí)驗(yàn)

實(shí)驗(yàn)采用斯坦福大學(xué)個(gè)人社交網(wǎng)絡(luò)數(shù)據(jù)集ego-Facebook，對(duì)比算法為通過節(jié)點(diǎn)間連接和節(jié)點(diǎn)屬性相似的社交網(wǎng)絡(luò)發(fā)現(xiàn)算法M-L［18］和增強(qiáng)鏈聚類算法ELC［8］。以個(gè)人社交圈節(jié)點(diǎn)數(shù)為變量進(jìn)行實(shí)驗(yàn)，所有參數(shù)值取10 次實(shí)驗(yàn)的平均值。M-L、ELC 和NLA/SCD 算法均為基于網(wǎng)絡(luò)邊和屬性的社區(qū)發(fā)現(xiàn)算法。M-L 算法采用節(jié)點(diǎn)屬性相似計(jì)算方法，EML 與NLA/SCD 算法采用相似的屬性策略，不同的是NLA/SCD算法運(yùn)行在SSO 算法框架上。由于本文將連邊屬性作為SSO 算法的適應(yīng)度函數(shù)，因此在每一代結(jié)束后將社區(qū)模塊度增量作為判斷準(zhǔn)則，此類多層次和多粒度的設(shè)計(jì)可有效避免模塊度優(yōu)化而分辨率限制［6］問題，對(duì)算法精度的提升起到關(guān)鍵作用，如圖6（a）所示。3 種算法隨著節(jié)點(diǎn)數(shù)的增加，模塊度和NMI 值均有所下降，但NLA/SCD 算法由于結(jié)合了邊的屬性特征，采用SSO 差分尋優(yōu)策略使得算法劃分精度相對(duì)穩(wěn)定。如圖6（b）所示，由于SSO 算法在進(jìn)化第2 代時(shí)存在振蕩期，因此當(dāng)節(jié)點(diǎn)數(shù)在547 時(shí)會(huì)稍有影響，但SSO 算法經(jīng)過3 代或4 代進(jìn)化后能夠快速根據(jù)差分學(xué)習(xí)策略進(jìn)行自適應(yīng)調(diào)整，達(dá)到較高的劃分精度。其主要原因?yàn)樵贜MI 測(cè)試時(shí)因?yàn)樗惴ńK止判定與NMI 值不直接相關(guān)，所以節(jié)點(diǎn)數(shù)增加對(duì)NLA/SCD算法影響較小?；赟SO 的蜘蛛種群按雌雄差分進(jìn)化，從多路尋找最優(yōu)解，構(gòu)建與適應(yīng)度函數(shù)有關(guān)的半徑婚配算子，并逐代吞并劣質(zhì)個(gè)體，從而加快算法收斂。如圖6（c）所示，在ego-Facebook 中通過不斷增加節(jié)點(diǎn)數(shù)測(cè)試算法達(dá)到最佳劃分精度的收斂時(shí)間，可以看出NLA/SCD 算法相比另外兩種算法更穩(wěn)定且耗時(shí)更少。

圖6 3 種個(gè)人社交網(wǎng)絡(luò)發(fā)現(xiàn)算法的性能比較Fig.6 Performance comparison of three personal social network discovery algorithms

3.3 社區(qū)發(fā)現(xiàn)算法性能比較實(shí)驗(yàn)

實(shí)驗(yàn)網(wǎng)絡(luò)數(shù)據(jù)集為Karate 和Dolphins 社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集以及ego-Facebook 和ego-Twitter 個(gè)人社交網(wǎng)絡(luò)數(shù)據(jù)集。對(duì)比算法為經(jīng)典社區(qū)發(fā)現(xiàn)算法GA-Net［19］、隔代遺傳算法GGA+［13］、啟發(fā)式差分搜索算法HDSA［20］（這3 種算法是近幾年提出的社區(qū)劃分精度較高的群智能社區(qū)發(fā)現(xiàn)算法）、增強(qiáng)鏈聚類算法ELC［8］、擴(kuò)展屬性的個(gè)人社交網(wǎng)絡(luò)發(fā)現(xiàn)算法CESNA［6］以及基于局部節(jié)點(diǎn)相似的群集蜘蛛差分進(jìn)化社區(qū)發(fā)現(xiàn)算法DESSO/DC［14］。各算法參數(shù)值均采用最佳值，在同等規(guī)模數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，模塊度比較如表3所示。

表3 7 種社區(qū)發(fā)現(xiàn)算法的模塊度比較Table 3 Modularity comparison of seven community discovery algorithms

可以看出，群智能社區(qū)發(fā)現(xiàn)算法在個(gè)人社交網(wǎng)絡(luò)劃分方面仍存在一定的適應(yīng)性問題，導(dǎo)致劃分精度不高，而邊和屬性相結(jié)合的社區(qū)發(fā)現(xiàn)算法在尋優(yōu)精度方面更具優(yōu)勢(shì)。NLA/SCD 算法通過差分進(jìn)化方式，采用局部和全局兼顧的混合學(xué)習(xí)設(shè)計(jì)，并利用婚配擇優(yōu)的算子策略保證種群的多樣性，相比GA-Net、GGA+算法的進(jìn)化算子更多樣，相比HDSA算法的算子排序可隨雌雄種群進(jìn)一步差別化，適應(yīng)性更強(qiáng)。另外，NLA/SCD 算法采用加權(quán)的模塊度增量算子擇優(yōu)準(zhǔn)則，可更有效地判斷社區(qū)劃分效果?？梢姡c現(xiàn)有群智能社區(qū)發(fā)現(xiàn)算法相比，NLA/SCD算法社區(qū)劃分精度更高，而且本文的適應(yīng)度函數(shù)和算子擇優(yōu)準(zhǔn)則均是針對(duì)個(gè)人社交圈進(jìn)行設(shè)計(jì)，因此在檢驗(yàn)個(gè)人社交網(wǎng)絡(luò)社區(qū)劃分時(shí)效果更佳。

4 結(jié)束語

本文以個(gè)人社交網(wǎng)絡(luò)作為研究對(duì)象，在結(jié)合網(wǎng)絡(luò)邊拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性的基礎(chǔ)上，利用社會(huì)蜘蛛優(yōu)化算法尋求最佳的個(gè)人社區(qū)結(jié)構(gòu)劃分，提出一種基于鄰邊屬性群智能聚類的個(gè)人社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法NLA/SCD。該算法以個(gè)人社交網(wǎng)絡(luò)的邊作為SSO 算法的種群，以個(gè)體為中心逐步對(duì)邊進(jìn)行聚類，并且利用適應(yīng)度函數(shù)和算子擇優(yōu)準(zhǔn)則反映個(gè)人社交網(wǎng)絡(luò)的真實(shí)社區(qū)劃分情況。實(shí)驗(yàn)結(jié)果表明，該算法能保持網(wǎng)絡(luò)社區(qū)的多樣性，在參數(shù)依賴性、劃分精度、運(yùn)行時(shí)間和適應(yīng)性等方面都有較好的性能提升。后續(xù)將針對(duì)電商消費(fèi)數(shù)據(jù)，利用NLA/SCD 算法挖掘并劃分其潛在的交易關(guān)系、興趣關(guān)系和客戶關(guān)系等社交關(guān)系社區(qū)，為用戶提供更精準(zhǔn)的決策信息。