基于節(jié)點多關(guān)系的社團挖掘算法及其應(yīng)用

周 琳，肖玉芝*，劉 鵬，秦有鵬

（1.青海師范大學(xué) 計算機學(xué)院，西寧 810016；2.青海省藏文信息處理與機器翻譯重點實驗室（青海師范大學(xué)），西寧 810008；3.藏文信息處理教育部重點實驗室（青海師范大學(xué)），西寧 810008）

0 引言

5G 應(yīng)用技術(shù)進一步推動了多媒體深度融合發(fā)展。媒體、內(nèi)容與用戶之間的傳播形態(tài)格局與移動社交網(wǎng)絡(luò)形成新生態(tài)網(wǎng)絡(luò)，使交互對象之間呈現(xiàn)多關(guān)系性和群體性，如手機通信網(wǎng)絡(luò)中多用戶形成基于家庭關(guān)系的親情群體，同時形成基于某些產(chǎn)品的使用群體，體現(xiàn)出節(jié)點多關(guān)系及群體內(nèi)部緊密連接、群體之間稀疏連接的社團性質(zhì)［1］。因此，研究新生態(tài)網(wǎng)絡(luò)中社團群體結(jié)構(gòu)，有助于挖掘新生態(tài)網(wǎng)絡(luò)價值。社團的定義主要分為以下三種：1）從局部定義社團，即將一個全連通的子圖定義為社團；2）從網(wǎng)絡(luò)整體定義社團，即將隨機網(wǎng)絡(luò)作為比較對象，若某個網(wǎng)絡(luò)社團特征與這個隨機網(wǎng)絡(luò)存在顯著差異，則認為該網(wǎng)絡(luò)具有社團結(jié)構(gòu)；3）從節(jié)點的相似性來定義社團，即采用某種指標衡量節(jié)點的相似性，根據(jù)相似性劃分社團，認為社團內(nèi)部的節(jié)點都是相似性的。在新生態(tài)網(wǎng)絡(luò)中，由于節(jié)點間存在多種連接關(guān)系以及特性，呈現(xiàn)出多樣性和多關(guān)系性，利用節(jié)點相似性識別新生態(tài)網(wǎng)絡(luò)中的社團結(jié)構(gòu)具有可行性。如何度量多關(guān)系節(jié)點相似性，如何設(shè)計融合相似性指標的社團挖掘算法是新生態(tài)網(wǎng)絡(luò)社團劃分及其應(yīng)用的關(guān)鍵問題。

度量節(jié)點相似性的關(guān)鍵問題之一是考慮節(jié)點是帶有全局知識還是帶有局部知識。帶有全局知識的節(jié)點便于被外界使用但是維護成本高，比如計算手機通信網(wǎng)絡(luò)中的某兩個用戶節(jié)點的相似性，從全局角度總能找到這兩個節(jié)點，但是計算量較大；而帶有局部知識的節(jié)點不便于外界找到內(nèi)部元素，但維護成本低，比如同樣計算手機通信網(wǎng)絡(luò)中的某兩個用戶節(jié)點的相似性，每個用戶節(jié)點只關(guān)注和自己連接的前后節(jié)點信息。面向全局節(jié)點關(guān)系的社團挖掘算法有：譜分析方法［2-3］、圖劃分算法［4-5］、模塊度法［6-7］、GN（Girvan-Newman）算法［8］；面向局部節(jié)點關(guān)系的社團挖掘算法有：隨機游走算法［9-10］、局部擴展算法［11-12］和基于標簽傳播的算法［13］。這些經(jīng)典算法中，節(jié)點關(guān)系具有單一性，社團劃分出的屬性也較為單一，但是在新生態(tài)網(wǎng)絡(luò)中，節(jié)點具有多關(guān)系和多樣性，在社團劃分時，更傾向于節(jié)點隱藏信息的挖掘。

在確定了從全局角度或者從局部角度衡量節(jié)點屬性后，度量多關(guān)系節(jié)點相似性的關(guān)鍵問題轉(zhuǎn)化為刻畫節(jié)點多屬性關(guān)系量化模型。目前已有學(xué)者基于點、線、面的思路，分別以節(jié)點-節(jié)點、節(jié)點-鄰居，節(jié)點-鄰居-鄰居方法進行了社團挖掘算法的設(shè)計并在特定場景中進行應(yīng)用?；诠?jié)點自身屬性關(guān)系，Weiss 等［14］提出的一種基于屬性-關(guān)系相似度的聚類HyPursuit 社團挖掘算法考慮了節(jié)點的屬性-關(guān)系相似度，用于分析互聯(lián)網(wǎng)上的超文本文檔。基于節(jié)點自身屬性和鄰居屬性關(guān)系，黃新宇等［15］以節(jié)點度和鄰居節(jié)點的度為核心，刻畫了節(jié)點間相互作用影響力，提出了CDMN 社團挖掘算法?；诠?jié)點自身屬性、鄰居屬性關(guān)系以及鄰居與鄰居屬性關(guān)系，邱少明等［16］在考慮鄰居節(jié)點關(guān)系時，還考慮了鄰居節(jié)點之間聯(lián)系的緊密程度，根據(jù)節(jié)點聚集系數(shù)和節(jié)點共有引力作為節(jié)點的自身屬性和結(jié)構(gòu)屬性，提出了基于多屬性相似聚類的社團挖掘算法，實驗結(jié)果表明該算法能有效提高社團劃分的質(zhì)量。

綜上所述，本文考慮借鑒已有的多關(guān)系節(jié)點社團挖掘算法思路，以手機通信用戶在多個社交平臺中的交互行為為研究對象，旨在挖掘出具有多個社交行為的用戶歸屬團體，重點刻畫了一種多關(guān)系節(jié)點相似性度量指標；同時基于全局節(jié)點關(guān)系的GN 算法提出了一種基于節(jié)點多關(guān)系的社團挖掘算法LSL-GN。該算法的基本思路為：提出節(jié)點多關(guān)系度量指標LHN-ISL，并用該指標刻畫密度較低的重構(gòu)網(wǎng)絡(luò)，再結(jié)合GN 算法在重構(gòu)網(wǎng)絡(luò)中進行社團劃分。為驗證LSL-GN 算法的有效性，使用開源數(shù)據(jù)集與GN 算法和Louvain 算法［17］在模塊度（Modularity，Q）［18］、標準化互信息（Normalized Mutual Information，NMI）［19］和調(diào)整蘭德指數(shù)（Adjusted Rand Index，ARI）［20］3 個評價準則上進行對比。算法在實際應(yīng)用時，充分考慮了節(jié)點的多種關(guān)系，如用戶節(jié)點的出行記錄、通話時長、應(yīng)用平臺的使用記錄等，按照不同概率定量刻畫出了基于“用戶-應(yīng)用”的移動漫游網(wǎng)絡(luò)模型。利用LSL-GN 算法，劃分出以攜程旅行、高德地圖、滴滴出行等為基礎(chǔ)應(yīng)用的社團群體。例如以攜程旅行為基礎(chǔ)應(yīng)用的社團1，該社團中的所有用戶還有對QQ、釘釘、Bilibili、快手等應(yīng)用的使用。根據(jù)實驗結(jié)果，運營商可制定具體的套餐業(yè)務(wù)，該業(yè)務(wù)包含日通話時長和流量包使用業(yè)務(wù)，針對社團1 中的用戶，流量包使用業(yè)務(wù)為攜程旅行、QQ、釘釘、Bilibili、快手等。

1 基本知識

度量多關(guān)系節(jié)點相似性的關(guān)鍵問題為刻畫節(jié)點多屬性關(guān)系量化模型。本文涉及的多關(guān)系節(jié)點網(wǎng)絡(luò)模型定義如下：

G=(V；E；A；R)（1）其中：G為網(wǎng)絡(luò)圖；V為節(jié)點集合V={v1，v2，…，vN}；E為節(jié)點連邊集 合E={e1，e2，…，em}；A為節(jié)點 類型集 合A={A1，A2，…，An}；R為節(jié)點連邊關(guān)系類型集合R={R1，R2，…，Rr}。

如圖1 所示的多關(guān)系節(jié)點網(wǎng)絡(luò)模型，記為user-app 網(wǎng)絡(luò)，刻畫了由7 個節(jié)點形成的多關(guān)系網(wǎng)絡(luò)，按照式（1）描述如下：

圖1 多關(guān)系節(jié)點網(wǎng)絡(luò)示例Fig.1 Example of multi-relational node network

1）兩類節(jié)點類型：節(jié)點v1～v4分別代表了4 個手機用戶，該節(jié)點類型記為A1；節(jié)點v5～v7分別代表3 個不同類型的移動社交app 軟件，該節(jié)點類型記為A2。

2）節(jié)點連邊關(guān)系：手機用戶節(jié)點之間按照通話等級進行連邊，該關(guān)系記為R1；移動社交app 軟件之間按照功能進行連邊，該關(guān)系記為R2；手機用戶節(jié)點與移動社交app 軟件之間按照用戶使用app 流量進行連邊，該關(guān)系記為R3。

3）節(jié)點多關(guān)系：根據(jù)R1關(guān)系形成的節(jié)點連邊分別記為e1、e2及e3；根據(jù)R2關(guān)系形成的節(jié)點連邊分別記為e6及e7；根據(jù)R3關(guān)系形成的節(jié)點連邊分別記為e4和e5。

由此，圖1 的多關(guān)系節(jié)點網(wǎng)絡(luò)模型記為：

網(wǎng)絡(luò)模型關(guān)系確定后，需要進行多關(guān)系節(jié)點的表示和計算，本文針對節(jié)點局部性和全局性，在節(jié)點共同鄰居的基礎(chǔ)上考慮了節(jié)點自身屬性、節(jié)點-鄰居屬性、節(jié)點-路徑屬性等，刻畫了基于路徑相似度的指標。接下來，依次介紹與之有關(guān)的基本概念。

1.1 鄰接矩陣

圖的鄰接矩陣可描述節(jié)點間的多關(guān)系特征［21］，其中無向圖的鄰接矩陣是對稱矩陣。設(shè)一個無向無權(quán)簡單圖G=(V，E)，V={V1，V2，…，VN}有N個節(jié)點，則圖G的鄰接矩陣A是一個N階方陣。鄰接矩陣A=（aij）N×N，aij為鄰接矩陣A中第i行第j列上的元素，aij定義為節(jié)點i和j之間相連的邊，即節(jié)點間存在連邊時值為1，反之值為0。具體定義如下：

1.2 共同鄰居

共同鄰居（Common Neighbors，CN）表示兩個節(jié)點之間相同的鄰居節(jié)點［22］。通過共同鄰居數(shù)衡量節(jié)點在同一社區(qū)的可能性。一般認為，共同鄰居數(shù)越大，兩個節(jié)點的相似度較高，它們在同一社團的可能性越大。定義如下：網(wǎng)絡(luò)中任意節(jié)點i、j的鄰居節(jié)點集合分別為Γ(i)、Γ(j)，則i、j的共同鄰居數(shù)如式（3）：

1.3 LHN-I指標

LHN-I 指標是一種描述局部節(jié)點間相似度的指標［23］，如式（4）所示：

其中：Ki、Kj分別表示節(jié)點i、j的度，即同時考慮了節(jié)點間的共同鄰居數(shù)量和節(jié)點度值。

通常節(jié)點間度的乘積不為空，而節(jié)點間共同鄰居的數(shù)量存在為空的情況，且節(jié)點間共同鄰居數(shù)量小于度的乘積，故LHN-I 指標取值一般在［0，1）。LHN-I 指標數(shù)值越大，節(jié)點間的交互信息量越大，則節(jié)點間越傾向于連接。

例如在圖2 的網(wǎng)絡(luò)G0中，假設(shè)網(wǎng)絡(luò)共有2 個社團，其中社團1 的節(jié)點集合為｛1，2，3，4，6｝，社團2 的節(jié)點集合為｛5，7，8｝。采用LHN-I 指標度量節(jié)點3 和節(jié)點5 相似度數(shù)值為0.083，LHN-I 指標取得數(shù)值小，說明節(jié)點3 和節(jié)點5 相似程度小，則被劃分在同一社團的可能性較小，符合圖G0中社團的分布情況。LHN-I 指標的數(shù)值可精確至小數(shù)點后兩位及以上，有利于社團結(jié)構(gòu)的探索。

圖2 網(wǎng)絡(luò)G0的拓撲結(jié)構(gòu)Fig.2 Topology of network G0

1.4 路徑長度

最短路徑長度（Length of Shortest path，LS）是指連接兩個節(jié)點間的最短路徑邊數(shù)。一般而言，路徑長度用來描述節(jié)點間的緊密程度。節(jié)點i和節(jié)點j的路徑長度［24］如式（5）所示，其中d（i，j）表示節(jié)點i和節(jié)點j之間的最短路徑所包含的邊數(shù)目。本文設(shè)定初始網(wǎng)絡(luò)為連通網(wǎng)絡(luò)，故不考慮節(jié)點i與節(jié)點j不連通情況。

在連通網(wǎng)絡(luò)中，任意節(jié)點間均存在路徑，則LS 指標不為空；網(wǎng)絡(luò)拓撲中節(jié)點間最短路徑所包含的邊數(shù)唯一，當節(jié)點間相隔較遠時，其最短路徑長度數(shù)值較大，使得LS 指標數(shù)值減??；當節(jié)點間距離較近時，LS 指標數(shù)值增大，其中相鄰節(jié)點間的最短路徑長度為1，即d(i，j)=1，此時LS 指標取值最大，數(shù)值為0.5；故LS 指標的取值范圍一般為（0，0.5］。LS（i，j）數(shù)值越大，則節(jié)點i和節(jié)點j之間相互認識的可能性越大，在社團劃分上，屬于一個社團的可能性便越大。

1.5 GN算法

GN 社團劃分算法［8］是基于網(wǎng)絡(luò)全局信息的經(jīng)典社團劃分算法之一，算法復(fù)雜度依賴于網(wǎng)絡(luò)中邊的數(shù)目。GN 算法主要通過割斷邊介數(shù)值較大的邊進行社團劃分，實現(xiàn)過程如下：

1）計算每一條邊的邊介數(shù)，其中邊介數(shù)為網(wǎng)絡(luò)中所有節(jié)點間最短路徑經(jīng)過該邊的次數(shù)；

2）刪除邊介數(shù)最大的邊；

3）重復(fù)上述步驟，直到網(wǎng)絡(luò)中的任一頂點作為一個社區(qū)為止。

本文基于節(jié)點多關(guān)系的全局和局部特性，分別考慮節(jié)點間鄰居數(shù)目以及節(jié)點間的路徑長度，即通過鄰居節(jié)點衡量節(jié)點局部關(guān)系，又通過路徑長度約束節(jié)點間存在的鏈路關(guān)系，進而利用邊介數(shù)概念，將GN 社團劃分算法應(yīng)用到其中。

2 LSL-GN社團挖掘算法

本文擬解決的關(guān)鍵問題是如何表征節(jié)點多關(guān)系以及如何計算具有多關(guān)系的節(jié)點相似度。為全面度量節(jié)點的多關(guān)系特征，在節(jié)點共同鄰居的基礎(chǔ)上考慮了兩端節(jié)點度的影響以及節(jié)點的所有路徑的影響，利用節(jié)點相似性及路徑長度，度量多關(guān)系節(jié)點間的相似性，定義了相似性度量指標LHNISL，并提出一種基于節(jié)點多關(guān)系的社團挖掘算法LSL-GN。

2.1 算法描述

2.1.1 LHN-ISL指標

為表征節(jié)點多屬性關(guān)系，利用節(jié)點間的共同鄰居及兩端節(jié)點度衡量多關(guān)系節(jié)點之間的相似程度，同時考慮路徑可達性，刻畫了節(jié)點間無共同鄰居時的相似性。

LHN-I 指標是描述局部節(jié)點間相似度的指標。利用LHN-I 指標計算圖3 中節(jié)點i和節(jié)點j的相似度，由于節(jié)點i的鄰居集合為｛u，w，p，j｝，節(jié)點j的鄰居集合為｛m，n，i｝。節(jié)點i和節(jié)點j之間不存在共同鄰居，因此根據(jù)式（4）可知，節(jié)點i和節(jié)點j的LHN-I 指標取值為0。

圖3 節(jié)點相似度示意圖Fig.3 Schematic diagram of node similarity

圖3 中，假設(shè)節(jié)點i和節(jié)點j代表用戶，節(jié)點u及m為相同類型的社交應(yīng)用平臺。當用戶i和用戶j對u、m兩個社交應(yīng)用平臺使用流量較大時，運營商在對用戶進行套餐推薦過程中，用戶i和j極有可能被劃分在相同套餐內(nèi)。但由于節(jié)點i和j無共同鄰居，節(jié)點間相似度為0，使LHN-I 相似度指標存在低估傾向，與實際情況不符，因此對LHN-I 相似度計算公式作出調(diào)整，節(jié)點鄰居集合包含節(jié)點本身，避免相似性系數(shù)為0 的情況，記為LHN-IS 相似度，如式（6）、（7）：

在較大的網(wǎng)絡(luò)拓撲中會出現(xiàn)大多數(shù)節(jié)點之間距離較遠且交集較少的情況，此時LHN-IS 指標無法較好地描述節(jié)點之間的相似程度。為全面度量網(wǎng)絡(luò)結(jié)構(gòu)，在節(jié)點共同鄰居及兩端節(jié)點度的基礎(chǔ)上，考慮了節(jié)點可達性，在LHN-IS 指標中融入路徑長度，基于節(jié)點相似性和節(jié)點可達性提出一種新的節(jié)點相似度指標LHN-IS Length，簡記為LHN-ISL，如式（8）：

根據(jù)LHN-ISL 指標定義，計算圖3 中節(jié)點i和節(jié)點j的LHN-ISL 相似度，其中節(jié)點i的鄰居集合為｛u，w，p，j，i｝，節(jié)點j的鄰居集合為｛m，n，i，j｝，它們的共同鄰居集合為｛i，j｝。節(jié)點間度乘積為12，LHN-IS 數(shù)值約為0.166 7（精確至小數(shù)點后四位），節(jié)點i和節(jié)點j的最短路徑為1，即LS 取值為0.5，最終節(jié)點i和節(jié)點j的LHN-ISL 指標數(shù)值約為0.666 7。

2.1.2 基于LHN-ISL指標的相似度矩陣

利用LHN-ISL 指標計算相似度矩陣，矩陣中的元素數(shù)值對應(yīng)網(wǎng)絡(luò)中節(jié)點間的相似程度。通過設(shè)定LHN-ISL 指標閾值，將矩陣中小于閾值的元素值設(shè)為0；反之，設(shè)為1。最終得到n×n的對稱相似度矩陣Ssim，n為節(jié)點數(shù)，如式（9）所示：

基于圖4（a）中網(wǎng)絡(luò)G1的拓撲結(jié)構(gòu)，計算該網(wǎng)絡(luò)的節(jié)點相似度LHN-ISL 指標，它的鄰接矩陣如式（10）所示；根據(jù)鄰接矩陣和LHN-ISL 相似度定義計算得到圖G1的節(jié)點相似度矩陣Ssim1，如式（11）所示；假設(shè)將Ssim1的相似度閾值設(shè)為0.67，則相似度矩陣中小于閾值的元素值設(shè)為0，大于閾值的元素值設(shè)為1，進而生成重構(gòu)網(wǎng)絡(luò)的鄰接矩陣A1＇，如式（12）所示；利用LHN-ISL 相似度指標調(diào)控網(wǎng)絡(luò)結(jié)構(gòu)，減少網(wǎng)絡(luò)冗余鏈路，刻畫出密度較低的重構(gòu)網(wǎng)絡(luò)，如圖4（b）所示。

圖4 網(wǎng)絡(luò)G1劃分前后的拓撲結(jié)構(gòu)Fig.4 Topology of network G1 before and after division

2.1.3 LSL-GN社團挖掘算法

LSL-GN 社團挖掘算法主要思想是：首先利用上文定義的LHN-ISL 指標獲取相似度矩陣，然后通過LHN-ISL 指標閾值刻畫低密度網(wǎng)絡(luò)，最后利用GN 算法對重構(gòu)網(wǎng)絡(luò)的社團進行劃分。該算法既保證了節(jié)點多關(guān)系性又提高了GN 算法的有效性，實現(xiàn)了GN 算法在連邊較多的密集網(wǎng)絡(luò)中的應(yīng)用。算法實現(xiàn)過程如下：設(shè)初始網(wǎng)絡(luò)中節(jié)點數(shù)為n，首先遍歷網(wǎng)絡(luò)圖G中的每一個節(jié)點v，計算網(wǎng)絡(luò)中每個節(jié)點間的LHNISL 指標，生成相似度矩陣；其次綜合網(wǎng)絡(luò)最終社團挖掘目標設(shè)定LHN-ISL 指標的閾值p，將相似度矩陣中小于閾值的元素Ssim(i，j)和Ssim(j，i)設(shè)為0，反之設(shè)為1，進而生成鄰接矩陣；然后將鄰接矩陣轉(zhuǎn)化為重構(gòu)網(wǎng)絡(luò)，采用經(jīng)典社團劃分GN算法對重構(gòu)網(wǎng)絡(luò)進行社團挖掘；最終輸出社團挖掘的結(jié)果。

2.2 算法評價指標

模塊度Q 是衡量社團劃分質(zhì)量時最廣泛使用的評價指標［18］，取值范圍為［0，1］，社團劃分的質(zhì)量越高，模塊度的值越大，社團內(nèi)的節(jié)點相似性越強，社團劃分效果越好。模塊度具體定義如式（13）所示：

其中：aij表示節(jié)點i和j之間的連接關(guān)系，如果節(jié)點間存在連接，則aij=1，否則為0；ki和kj分別表示節(jié)點i和節(jié)點j的度；ci與cj分別表示節(jié)點i和節(jié)點j在網(wǎng)絡(luò)中所屬社團，如果這兩個節(jié)點屬于同一個社團，δ取值為1，否則δ取值為0；M表示網(wǎng)絡(luò)中邊的數(shù)目。

NMI 可用于度量算法劃分社區(qū)和真實社區(qū)之間的相似程度［19］，取值范圍為［0，1］，值越大則算法所挖掘的社團結(jié)構(gòu)與真實社團結(jié)構(gòu)越貼合，具體定義如式（14）所示：

其中：矩陣中的行表示真實的社區(qū)，列表示算法得到的社區(qū)，矩陣中第i行的元素表示為Ni*，第j列的元素表示為N*j，Nij表示真實社區(qū)與算法所得到的社區(qū)相同的節(jié)點個數(shù)；N為節(jié)點個數(shù)，CA表示真實社區(qū)個數(shù)，CB表示算法所得到的社區(qū)個數(shù)。

ARI 可用于社團劃分結(jié)果的性能評估［20］，取值范圍為［-1，1］，值越大意味著算法劃分社團的結(jié)果與真實社團情況越吻合。具體定義如式（15）所示：

其中：N為網(wǎng)絡(luò)節(jié)點個數(shù)；CA表示真實社區(qū)個數(shù)，CB表示算法所得到的社區(qū)個數(shù)；Ni和Nj分別表示為真實社團劃分中節(jié)點個數(shù)和算法劃分后節(jié)點個數(shù)。

3 實驗與結(jié)果分析

為了驗證本文算法LSL-GN 的有效性，在Karate 網(wǎng)絡(luò)、Football 網(wǎng)絡(luò)、Adjnoun 網(wǎng)絡(luò)中利用LSL-GN 算法進行社團劃分。這3 個網(wǎng)絡(luò)數(shù)據(jù)集的基本信息如表1 所示。

Karate 網(wǎng)絡(luò)為美國空手道俱樂部的人物關(guān)系網(wǎng)絡(luò)，該網(wǎng)絡(luò)共有34 個節(jié)點和78 條邊，代表34 位成員間的交際關(guān)系。

Adjnoun 網(wǎng)絡(luò)是《大衛(wèi)·科波菲爾》中常見形容詞和名詞的鄰接網(wǎng)絡(luò)，其中：110 個節(jié)點分別代表書中最常見的形容詞和名詞；425 條連邊代表書中出現(xiàn)在相鄰位置的單詞關(guān)系，具有較低的聚類系數(shù)。

Football 網(wǎng)絡(luò)存在115 個節(jié)點和616 條邊，其中節(jié)點表示球隊，邊表示球隊之間存在過比賽，原始數(shù)據(jù)中將115 支隊伍分為12 個聯(lián)盟。本文以Football 網(wǎng)絡(luò)為例，該網(wǎng)絡(luò)的真實結(jié)構(gòu)如圖6 所示。

圖6 Football網(wǎng)絡(luò)結(jié)構(gòu)Fig.6 Football network structure

表1 網(wǎng)絡(luò)基本信息Tab.1 Basic network information

利用LSL-GN 算法進行社團劃分：首先計算節(jié)點間相似度LHN-ISL 指標，其次通過調(diào)整LHN-ISL 指標的閾值獲取最優(yōu)的社團劃分結(jié)果。當LHN-ISL 閾值取值為0.527 時，該連通網(wǎng)絡(luò)的社團劃分效果最好。最后利用GN 算法對其進行社團挖掘。如圖7 所示，F(xiàn)ootball 網(wǎng)絡(luò)利用LSL-GN 算法進行社團劃分，其結(jié)構(gòu)較為明顯。

圖7 Football網(wǎng)絡(luò)劃分后的結(jié)構(gòu)Fig.7 Football network structure after division

由圖8 可知，在Football 網(wǎng)絡(luò)中，當LSL-GN 算法將網(wǎng)絡(luò)劃分成10 個社團時，模塊度獲得最優(yōu)值，為0.788 884，此時所劃分的Football 網(wǎng)絡(luò)社團結(jié)構(gòu)最佳。

圖8 不同劃分數(shù)下的模塊度Fig.8 Modularity under different division number

接下來，基于模塊度Q、NMI、ARI 等3 個社團度量指標分別在3 個網(wǎng)絡(luò)上利用不同的社團劃分算法進行對比驗證，社團劃分個數(shù)K由最優(yōu)模塊度確定，結(jié)果如表2 所示。

表2 模塊度Q、NMI和ARI的對比Tab.2 Comparison of Q，NMI and ARI

根據(jù)表2 的數(shù)據(jù)，有如下幾種情形：

1）基于模塊度的社團劃分效果。在同一個網(wǎng)絡(luò)中，GN算法、LSL-GN 算法和Louvain 算法表現(xiàn)出如下關(guān)系：QGN＜QLouvain＜QLSL-GN，顯然，LSL-GN 算法在低密度網(wǎng)絡(luò)上進行社團劃分時，其劃分的社團質(zhì)量相對其他兩種算法更好，社團結(jié)構(gòu)強度較大；同時，除了Football 網(wǎng)絡(luò)之外，低模塊度劃分出的社團個數(shù)相對較多。

2）基于NMI 的社團劃分相似性指標。在Karate 網(wǎng)絡(luò)和Football 網(wǎng)絡(luò)中，GN 算法、LSL-GN 算法和Louvain 算法表現(xiàn)出如下關(guān)系：NMIGN＜NMILouvain＜NMILSL-GN；在Adjnoun 網(wǎng)絡(luò)中，表現(xiàn)出如下關(guān)系：NMILouvain＜NMIGN＜NMILSL-GN。

3）基于ARI 的社團劃分相似性指標。在Karate 網(wǎng)絡(luò)和Football 網(wǎng)絡(luò)中，GN 算法、LSL-GN 算法和Louvain 算法表現(xiàn)出如下關(guān)系：ARIGN＜ARILouvain＜ARILSL-GN；在Adjnoun 網(wǎng)絡(luò)中，表現(xiàn)出如下關(guān)系：ARILouvain＜ARIGN＜ARILSL-GN。

情形2）和3）度量了真實社團結(jié)構(gòu)與算法劃分社團之間的相似程度。

在Karate 網(wǎng)絡(luò)和Football 網(wǎng)絡(luò)中，算法劃分具有相同的效果，即LSL-GN 算法與GN 算法和Louvain 算法相比，LSLGN 算法與真實網(wǎng)絡(luò)匹配度高，其次是Louvain 算法，而GN 算法劃分效果較差。

在Adjnoun 網(wǎng)絡(luò)中，由于該網(wǎng)絡(luò)具有較低的平均聚類系數(shù)，其中任意節(jié)點成團的可能性低，因此在社團劃分時Louvain 算法的效果比GN 算法差，LSL-GN 算法劃分效果最好。

綜上實驗結(jié)果表明，本文LSL-GN 算法在Karate 網(wǎng)絡(luò)、Football 網(wǎng)絡(luò)以及Adjnoun 網(wǎng)絡(luò)中具有相對較好的社團劃分效果。

4 移動漫游網(wǎng)絡(luò)上的社團挖掘

隨著移動互聯(lián)技術(shù)的發(fā)展，移動終端及應(yīng)用平臺被用戶廣泛使用。作為提供該產(chǎn)品和服務(wù)的運營商，重點在于解決如何快速定位相應(yīng)的需求用戶，如何提供個性化的套餐服務(wù)等問題。因此，本文基于真實數(shù)據(jù)，利用社團劃分算法獲取了移動漫游用戶社團結(jié)構(gòu)，并且對其進行個性化服務(wù)的訂制。

本文將手機通信用戶簡稱為用戶，其中包含的出差用戶群體定義為漫游用戶，用戶在移動終端使用的應(yīng)用軟件定義為應(yīng)用平臺。通過用戶使用諸如“去哪兒”“途牛旅游”“高德地圖”等應(yīng)用平臺獲取用戶的差旅信息，同時，此類用戶傾向于使用QQ、微信、抖音等視頻類應(yīng)用平臺。

如圖9 刻畫了一類移動漫游網(wǎng)絡(luò)模型，其中的節(jié)點具有多關(guān)系性，根據(jù)多關(guān)系節(jié)點網(wǎng)絡(luò)模型定義（1），該網(wǎng)絡(luò)模型存在如下關(guān)系：

圖9 移動漫游網(wǎng)絡(luò)模型示例Fig.9 Mobile roaming network model example

1）兩類節(jié)點類型：用戶1～4 分別代表不同的用戶類節(jié)點，該節(jié)點類型記為A1；應(yīng)用1～4 代表不同的應(yīng)用類節(jié)點，該節(jié)點類型記為A2。

2）節(jié)點連邊關(guān)系：多關(guān)系節(jié)點連邊關(guān)系類型共有3 種，其中用戶節(jié)點之間按照通話等級進行連邊，該關(guān)系記為R1；應(yīng)用節(jié)點之間按照功能進行連邊，該關(guān)系記為R2；用戶節(jié)點與應(yīng)用節(jié)點間按照用戶使用的應(yīng)用平臺流量排名進行等級連邊，該關(guān)系記為R3。

3）節(jié)點多關(guān)系：根據(jù)R1關(guān)系形成的用戶節(jié)點連邊，分別記為e1至e4；根據(jù)R2關(guān)系形成的應(yīng)用節(jié)點連邊，分別記為e7和e8；根據(jù)R3關(guān)系形成的“用戶-應(yīng)用”節(jié)點連邊，分別記為e5和e6。由此，構(gòu)建具有多關(guān)系的移動漫游網(wǎng)絡(luò)模型。

4.1 數(shù)據(jù)預(yù)處理

根據(jù)某運營商提供的用戶及其應(yīng)用平臺信息搭建了移動漫游網(wǎng)絡(luò)模型。網(wǎng)絡(luò)中：用戶類節(jié)點A1是指手機通信用戶，共計1 097 位用戶，其中包含886 位漫游用戶；應(yīng)用類節(jié)點A2是指1 097 位用戶所使用的應(yīng)用平臺，共計37 個。

根據(jù)應(yīng)用平臺的功能可分為四類：通信類、出行類、短視頻類和影視類。應(yīng)用平臺所屬的功能類別不唯一，因此應(yīng)用平臺分類總計數(shù)量超過了37 個，其中通信類17 個，出行類8個，短視頻類6 個，影視類19 個。

用戶信息包含用戶ID 號、用戶是否出差、用戶出行時長、通話時長、出行類應(yīng)用平臺、社交類應(yīng)用平臺、視頻類應(yīng)用平臺及其使用流量等6 個指標，如表3 所示。

表3 用戶信息Tab.3 User information

在構(gòu)建網(wǎng)絡(luò)模型中R1連邊關(guān)系時，需對用戶通話時長進行數(shù)據(jù)預(yù)處理，包括：通過用戶i的通話時長、出行時長以及總用戶數(shù)n，計算該用戶的通話時長標準化結(jié)果，其中通話時長（callDuration）記為ci，出行時長（travelTime）記為t，通話時長平均值（averageCallDuration）記為a。首先對用戶通話時長進行標準化處理，過程如下：

1）計算所有用戶的通話總時長：C=

2）計算用戶i通話時長平均值：ai=，i∈[1，n]；

3）計算所有用戶通話總時長平均值：a=C/n；

4）輸出每位用戶通話時長平均值ai及所有用戶的話總時長平均值a。

計算得出通話總時長平均值a約為50 min。為方便后期比較，本文對用戶通話時長進行了編號，并根據(jù)標準化結(jié)果將每位用戶的通話時長平均值分為4 個等級，分別是低于平均通話時長、低于但接近平均時長、高于但接近平均時長和高于平均時長，如表4 所示。

表4 通話等級設(shè)置Tab.4 Call level setting

4.2 網(wǎng)絡(luò)模型構(gòu)建

構(gòu)建一類基于“用戶-應(yīng)用”移動漫游網(wǎng)絡(luò)模型，用戶類節(jié)點數(shù)為1 097，應(yīng)用類節(jié)點數(shù)為37，兩類節(jié)點間通過不同的連邊關(guān)系R1、R2和R3進行連接。假設(shè)節(jié)點之間的連邊概率為p，生成最終的網(wǎng)絡(luò)模型G。構(gòu)建過程如下：

1）用戶類節(jié)點以R1連邊關(guān)系構(gòu)建。按照表4 通話等級，對1 097 個用戶進行連邊，具體如下：

①若用戶通話等級相同，則用戶之間以概率p1連邊；

②若用戶通話等級不同，則用戶之間以概率p2連邊。

2）應(yīng)用類節(jié)點以R2連邊關(guān)系構(gòu)建。按照應(yīng)用平臺分類對37 個應(yīng)用平臺進行連邊，具體如下：

①若應(yīng)用類別相同，則該以概率p3與相同類別的應(yīng)用平臺進行連邊；

②若應(yīng)用類別不同，則該以概率p4與不同類別的應(yīng)用平臺進行連邊。

3）用戶與應(yīng)用類節(jié)點間以R3連邊關(guān)系構(gòu)建。按照表3用戶信息對應(yīng)用平臺按照出行類應(yīng)用、通信類應(yīng)用、視頻類應(yīng)用進行分類，并將應(yīng)用按照使用流量排序。為了構(gòu)建移動漫游網(wǎng)絡(luò)模型中用戶與應(yīng)用之間的連邊，設(shè)定連邊概率p5、p6、p7和p8，具體如下：

①以概率p5對不同類別中流量使用排名第一的應(yīng)用平臺進行層間連邊；

②以概率p6對不同類別中流量使用排名第二的應(yīng)用平臺進行層間連邊；

③以概率p7對不同類別中流量使用排名第三的應(yīng)用平臺進行層間連邊。

④以概率p8對不同類別中流量使用排名第四的應(yīng)用平臺進行層間連邊。

表3 中，如用戶1 根據(jù)流量排名，以概率p5將用戶1 與滴滴出行、微信和抖音進行連邊。

經(jīng)過大量對比實驗，針對移動漫游網(wǎng)絡(luò)模型G，確定了連邊概率取值，分別為p1=0.022，p2=0.000 31，p3=0.46，p4=0.15，p5=0.78，p6=0.35，p7=0.28，p8=0.22。

最終生成的移動漫游網(wǎng)絡(luò)G包含了1 134 節(jié)點，10 899 條連邊。該網(wǎng)絡(luò)的密度為0.017，網(wǎng)絡(luò)的平均路徑長度為2.594，平均聚類系數(shù)為0.093，網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖10 所示。

圖10 移動漫游網(wǎng)絡(luò)的拓撲結(jié)構(gòu)Fig.10 Topology of mobile roaming network

4.3 基于LSL-GN算法的移動漫游網(wǎng)絡(luò)社團挖掘

基于節(jié)點多關(guān)系的LSL-GN 社團挖掘算法對移動漫游網(wǎng)絡(luò)進行社團挖掘。由于移動漫游網(wǎng)絡(luò)模型中節(jié)點社團個數(shù)未知，為了驗證LSL-GN 社團挖掘算法的合理性，本文采用了GN 算法與Louvain 算法對網(wǎng)絡(luò)模型進行社團挖掘，并在模塊度上進行對比。

不同社團挖掘算法在移動漫游網(wǎng)絡(luò)上的劃分結(jié)果如表5 所示。由表5 可知，在GN 算法、LSL-GN 算法和Louvain 算法下表現(xiàn)出如下關(guān)系：QGN＜QLouvain＜QLSL-GN，KLouvain＜KLSL-GN＜KGN。顯然，LSL-GN 算法下實驗數(shù)據(jù)集的模塊度值最高，其社團內(nèi)部節(jié)點具有高的相似度，對社團內(nèi)部節(jié)點進行推送業(yè)務(wù)時，因他們相似的興趣愛好而精準推薦。

表5 不同社團挖掘算法在移動漫游網(wǎng)絡(luò)上的劃分結(jié)果對比Tab.5 Division results comparison of different community mining algorithms on mobile roaming network

LSL-GN 算法的社團劃分結(jié)果如表6 和圖11 所示。該算法將1 097 個手機用戶及37 個應(yīng)用平臺劃分為4 個社團，運營商可根據(jù)劃分結(jié)果進行套餐業(yè)務(wù)的設(shè)計及推送。LSL-GN算法劃分的社團內(nèi)部節(jié)點聚集性較強，同一社團內(nèi)用戶的相似性較高，不同社團所包含的用戶通話時長范圍及興趣不同。根據(jù)劃分結(jié)果可為社團1 中的用戶制定移動日套餐，該套餐應(yīng)包含85 min 以上的日通話時長，以及不限流量的四種類型的應(yīng)用平臺，包含攜程旅行、QQ、釘釘、Bilibili 和快手等。故運營商可根據(jù)移動漫游網(wǎng)絡(luò)的劃分結(jié)果，將通話時長與不同類型的應(yīng)用平臺相結(jié)合，并制定個性化流量包套餐。為用戶團體提供個性化服務(wù)并為運營商提供策略參考信息，在滿足用戶豐富多彩的需求的同時，提升業(yè)務(wù)質(zhì)量。

圖11 LSL-GN算法的社團劃分結(jié)果Fig.11 Community division result of LSL-GN algorithm

表6 LSL-GN算法的社團劃分結(jié)果Tab.6 Community division results of LSL-GN algorithm

5 結(jié)語

本文提出了一種基于節(jié)點多關(guān)系的LSL-GN 算法。為衡量節(jié)點間的多關(guān)系性和群體性，該算法通過節(jié)點局部相似性指標和全局路徑長度刻畫節(jié)點多關(guān)系特征，定義了一種多關(guān)系節(jié)點相似性度量指標LHN-ISL，基于GN 算法提出了LSLGN 算法。實驗過程采用Karate、Football、Adjnoun 網(wǎng)絡(luò)數(shù)據(jù)集，通過Q、NMI、ARI 等3 個評價指標，與GN 算法及Louvain算法進行比較實驗，驗證了該算法的有效性，證明LSL-GN 算法具有良好的社團結(jié)構(gòu)挖掘效果。作為算法的應(yīng)用，在移動漫游網(wǎng)絡(luò)中能有效地將相似的用戶劃分至同一團簇，為手機通信用戶及運營商提供個性化套餐業(yè)務(wù)的參考策略。

本文所采用的移動漫游網(wǎng)絡(luò)數(shù)據(jù)量相對較少，沒有充分考慮網(wǎng)絡(luò)規(guī)模較大的情況。面對海量數(shù)據(jù)時，社團挖掘技術(shù)可結(jié)合機器學(xué)習(xí)進一步分析社團結(jié)構(gòu)，以提高大型數(shù)據(jù)集的社團挖掘質(zhì)量，增強社團挖掘技術(shù)的普適性。