一種融合鄰邊屬性的個人社交網絡社區發現算法

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

（1.廣東工業大學華立學院輿情大數據中心，廣州511325；2.華南理工大學計算機科學與工程學院，廣州510006；3.華南師范大學圖書館，廣州510631）

0 概述

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

1 相關工作

1.1 個人社交網絡特征分析

在個人社交網絡中，邊和屬性的權重、時效、密集程度等多模特征演化可能會導致社區結構的重構。如圖1所示，在現實世界中，一個以個人親屬關系、同學關系等組成的社交網絡圈隨著用戶個人的地理位置、興趣愛好、研究方向等內在因素（節點屬性）的變化，網絡結構也會發生變化。

圖1 帶有社區標記的個人社交網絡Fig.1 Personal social network with community flags

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

圖2 邊結構相似示意圖Fig.2 Schematic diagram of edge structural similarity

1.2 基于結構和屬性的社區發現

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

1.3 群智能蜘蛛算法

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

1.3.1 種群初始化

初始化相關參數為種群數目N、概率因子PE、雌雄蜘蛛數目Nf和Nm，計算公式如下：

其中：floor（）表示向下取整；rand 表示［0，1］中的隨機數，隨機產生雌雄種群的計算公式如下：

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

1.3.2 蜘蛛個體振動協作學習

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

其中：Vibci、Vibbi表示個體i對個體c、b的震動感知能力；rm為雌性個體的婚配半徑。

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

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

1.3.3 婚配選擇

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

婚配半徑r的計算公式如下：

2 個人社交網絡社區發現算法

2.1 基于群智能蜘蛛算法的社區發現

基于群體智能進化算法的社區發現通常是將社區劃分質量增量作為進化篩選條件，以局部節點相似或聚集系數等值作為進化算法種群的適應度函數值［12-14］，若算法收斂則社區劃分結束。為提高社交網絡社區發現的適應度值，本文將網絡連接邊、鄰邊屬性相似和基于邊的模塊度增量分別作為蜘蛛種群、適應度函數和進化停止條件，設計NLA/SCD 算法，NLA/SCD 算法流程如圖3所示。

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

2.2 鄰邊屬性相似

本文以個人社交網絡中連接邊為研究對象，將社區發現問題轉換為網絡邊及其屬性相似的聚類問題。

定義1假設Gu=(Vu,Eu)是個人u所屬的社交網絡，其中和分別表示u所屬社交網絡的節點集合和邊集合，基于邊屬性相似的個人社交網絡社區劃分計算公式如下：

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

定義2通過邊相似控制系數對節點結構和屬性進行聚類來表示鄰邊屬性相似，計算公式如下：

其中：wt和wp分別表示網絡邊結構相似和邊屬性相似的控制權值；Simt(eij,euv)和Simp(eij,euv)分別表示兩條邊eij、euv在網絡結構和屬性上的相似度值。

定義3在JACCARD 邊結構相似的基礎上，結合鄰節點關系和公共鄰邊來表示鄰邊結構相似，計算公式如下：

其中：Ni表示連接節點i的邊集合；E(Ni∩Nu)表示節點i和v公共的鄰邊集合；ξ∈[0,1]表示邊結構控制系數，當ξ=1 時類似于文獻［8］，僅考慮邊的JACCARD相似，當ξ≠1 時兼顧鄰邊對邊相似所起的作用。若各條邊兩端節點間公共的鄰邊越多，則表示邊結構越相似。

在社交網絡中，除了用戶間的關注或被關注關系外，興趣屬性、意見屬性和所屬地域屬性等因素都會與社區形成和演化有關，因此在社區劃分時需要對邊的屬性進行擬合。

定義4節點屬性向量表示將相鄰多個節點的屬性相關聯，其中邊的屬性由連接邊節點的屬性共同決定，即由該邊兩端節點的所有屬性進行and 運算組合，計算公式如下：

定義5通過邊中屬性相同的個數與邊屬性總數比來表示邊屬性相似，計算公式如下：

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

2.3 模塊度增量判定條件

基于SSO 算法的群體智能社區劃分的本質是最大化模塊度問題。在SSO 算法的優化過程中，以邊為個體的更新與婚配，保證了局部的社區優化。種群的每一代婚配都能產生社區劃分模塊度增量，當連續幾代邊合并為社區且模塊度增量不發生明顯變化時算法停止，因此引入基于邊的模塊度增量模型［15］，模塊度計算公式如下：

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

2.4 算法步驟

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

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

步驟2按式（10）計算個體的相似權值并排序。

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

步驟4按式（8）計算婚配半徑。

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

步驟6若模塊度增量連續幾代都不增加，則退出進化，否則轉到步驟2。

步驟7將收斂后的種群標簽映射為社區。

2.5 算法復雜度分析

NLA/SCD 算法耗時主要集中于個體的權值計算部分。假設np為用戶屬性數量，n為節點數，m為種群數，dmax為最大迭代次數，最多共享邊為ndmax(dmax-1)/2，連邊屬性計算的時間復雜度為。由于SSO 算法為分散尋優，種群迭代的時間復雜度約為O(ndmax)，因此NLA/SCD算法理想狀態的時間復雜度約為。

3 實驗與結果分析

為驗證NLA/SCD 算法的有效性，本文主要進行3 組實驗：1）獲取邊結構相似中控制系數的最佳值；2）驗證SSO 算法的連邊屬性社區發現的改進效果；3）比較NLA/SCD 算法與傳統智能進化社區發現算法的劃分精度。在Karate［16］、Dolphins［16］、ego-Facebook［17］和ego-Twitter［17］這4 個不同規模的網絡數據集上進行實驗，如表1所示。實驗運行平臺為Windows 7 企業版64 bit 操作系統、CPU Intel?CoreTM2 Q9550 ＠ 2.83 GHz、8 GB 內存。社區劃分的評價指標為模塊度和標準化互信息（Normalized Mutual Information，NMI）［16］。NLA/SCD 算法最佳參數設置如表2所示。

表1 網絡數據集Table 1 Network datasets

表2 NLA/SCD 算法最佳參數設置Table 2 Optimal parameters setting of NLA/SCD algorithm

3.1 參數設置實驗

實驗采用斯坦福大學個人社交網絡數據集ego-Facebook，以個人社交圈網絡節點數為變量進行檢測，3 組不同規模的網絡節點數分別為59、227 和792，所有參數值取10 次實驗的平均值，驗證邊結構控制系數ξ對劃分精度的影響。如圖4所示，當邊結構控制系數ξ取0.5～0.7 時，本文算法在3 個網絡數據集中均具有較好的表現，因此在下文實驗中設置ξ=0.7。

圖4 邊結構相似控制系數與NMI 的關系Fig.4 The relationship between edge structure similarity control coefficient and NMI

在ego-Facebook 數據集上的網絡節點數為59、種群規模為500，wt+wp=1，Wt初始閾值設置參考文獻［14］，在NLA/SCD 算法中，將各項參數閾值從0 到1 進行調整測試來分析NMI 的變化情況。如圖5所示，在ego-Facebook 數據集中個人社交網絡邊結構相似權值wt對網絡劃分精度具有較大影響，且邊屬性相似權值wp也會影響社區劃分結果，而概率因子PE設置與SSO算法［11］接近時效果最佳，通過參數設置實驗驗證了表2 理論最佳參數設置的正確性與有效性。

圖5 NLA/SCD 參數設置對NMI 的影響Fig.5 The influence of parameters setting on NMI in NLA/SCD

3.2 邊和屬性社區發現實驗

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

圖6 3 種個人社交網絡發現算法的性能比較Fig.6 Performance comparison of three personal social network discovery algorithms

3.3 社區發現算法性能比較實驗

實驗網絡數據集為Karate 和Dolphins 社會網絡數據集以及ego-Facebook 和ego-Twitter 個人社交網絡數據集。對比算法為經典社區發現算法GA-Net［19］、隔代遺傳算法GGA+［13］、啟發式差分搜索算法HDSA［20］（這3 種算法是近幾年提出的社區劃分精度較高的群智能社區發現算法）、增強鏈聚類算法ELC［8］、擴展屬性的個人社交網絡發現算法CESNA［6］以及基于局部節點相似的群集蜘蛛差分進化社區發現算法DESSO/DC［14］。各算法參數值均采用最佳值，在同等規模數據集上進行實驗，模塊度比較如表3所示。

表3 7 種社區發現算法的模塊度比較Table 3 Modularity comparison of seven community discovery algorithms

可以看出，群智能社區發現算法在個人社交網絡劃分方面仍存在一定的適應性問題，導致劃分精度不高，而邊和屬性相結合的社區發現算法在尋優精度方面更具優勢。NLA/SCD 算法通過差分進化方式，采用局部和全局兼顧的混合學習設計，并利用婚配擇優的算子策略保證種群的多樣性，相比GA-Net、GGA+算法的進化算子更多樣，相比HDSA算法的算子排序可隨雌雄種群進一步差別化，適應性更強。另外，NLA/SCD 算法采用加權的模塊度增量算子擇優準則，可更有效地判斷社區劃分效果?？梢?，與現有群智能社區發現算法相比，NLA/SCD算法社區劃分精度更高，而且本文的適應度函數和算子擇優準則均是針對個人社交圈進行設計，因此在檢驗個人社交網絡社區劃分時效果更佳。

4 結束語

本文以個人社交網絡作為研究對象，在結合網絡邊拓撲結構和節點屬性的基礎上，利用社會蜘蛛優化算法尋求最佳的個人社區結構劃分，提出一種基于鄰邊屬性群智能聚類的個人社交網絡社區發現算法NLA/SCD。該算法以個人社交網絡的邊作為SSO 算法的種群，以個體為中心逐步對邊進行聚類，并且利用適應度函數和算子擇優準則反映個人社交網絡的真實社區劃分情況。實驗結果表明，該算法能保持網絡社區的多樣性，在參數依賴性、劃分精度、運行時間和適應性等方面都有較好的性能提升。后續將針對電商消費數據，利用NLA/SCD 算法挖掘并劃分其潛在的交易關系、興趣關系和客戶關系等社交關系社區，為用戶提供更精準的決策信息。