基于節點多關系的社團挖掘算法及其應用

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

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

0 引言

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

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

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

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

1 基本知識

度量多關系節點相似性的關鍵問題為刻畫節點多屬性關系量化模型。本文涉及的多關系節點網絡模型定義如下：

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

如圖1 所示的多關系節點網絡模型，記為user-app 網絡，刻畫了由7 個節點形成的多關系網絡，按照式（1）描述如下：

圖1 多關系節點網絡示例Fig.1 Example of multi-relational node network

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

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

3）節點多關系：根據R1關系形成的節點連邊分別記為e1、e2及e3；根據R2關系形成的節點連邊分別記為e6及e7；根據R3關系形成的節點連邊分別記為e4和e5。

由此，圖1 的多關系節點網絡模型記為：

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

1.1 鄰接矩陣

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

1.2 共同鄰居

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

1.3 LHN-I指標

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

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

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

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

圖2 網絡G0的拓撲結構Fig.2 Topology of network G0

1.4 路徑長度

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

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

1.5 GN算法

GN 社團劃分算法［8］是基于網絡全局信息的經典社團劃分算法之一，算法復雜度依賴于網絡中邊的數目。GN 算法主要通過割斷邊介數值較大的邊進行社團劃分，實現過程如下：

1）計算每一條邊的邊介數，其中邊介數為網絡中所有節點間最短路徑經過該邊的次數；

2）刪除邊介數最大的邊；

3）重復上述步驟，直到網絡中的任一頂點作為一個社區為止。

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

2 LSL-GN社團挖掘算法

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

2.1 算法描述

2.1.1 LHN-ISL指標

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

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

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

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

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

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

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

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

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

圖4 網絡G1劃分前后的拓撲結構Fig.4 Topology of network G1 before and after division

2.1.3 LSL-GN社團挖掘算法

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

2.2 算法評價指標

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

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

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

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

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

其中：N為網絡節點個數；CA表示真實社區個數，CB表示算法所得到的社區個數；Ni和Nj分別表示為真實社團劃分中節點個數和算法劃分后節點個數。

3 實驗與結果分析

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

Karate 網絡為美國空手道俱樂部的人物關系網絡，該網絡共有34 個節點和78 條邊，代表34 位成員間的交際關系。

Adjnoun 網絡是《大衛·科波菲爾》中常見形容詞和名詞的鄰接網絡，其中：110 個節點分別代表書中最常見的形容詞和名詞；425 條連邊代表書中出現在相鄰位置的單詞關系，具有較低的聚類系數。

Football 網絡存在115 個節點和616 條邊，其中節點表示球隊，邊表示球隊之間存在過比賽，原始數據中將115 支隊伍分為12 個聯盟。本文以Football 網絡為例，該網絡的真實結構如圖6 所示。

圖6 Football網絡結構Fig.6 Football network structure

表1 網絡基本信息Tab.1 Basic network information

利用LSL-GN 算法進行社團劃分：首先計算節點間相似度LHN-ISL 指標，其次通過調整LHN-ISL 指標的閾值獲取最優的社團劃分結果。當LHN-ISL 閾值取值為0.527 時，該連通網絡的社團劃分效果最好。最后利用GN 算法對其進行社團挖掘。如圖7 所示，Football 網絡利用LSL-GN 算法進行社團劃分，其結構較為明顯。

圖7 Football網絡劃分后的結構Fig.7 Football network structure after division

由圖8 可知，在Football 網絡中，當LSL-GN 算法將網絡劃分成10 個社團時，模塊度獲得最優值，為0.788 884，此時所劃分的Football 網絡社團結構最佳。

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

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

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

根據表2 的數據，有如下幾種情形：

1）基于模塊度的社團劃分效果。在同一個網絡中，GN算法、LSL-GN 算法和Louvain 算法表現出如下關系：QGN＜QLouvain＜QLSL-GN，顯然，LSL-GN 算法在低密度網絡上進行社團劃分時，其劃分的社團質量相對其他兩種算法更好，社團結構強度較大；同時，除了Football 網絡之外，低模塊度劃分出的社團個數相對較多。

2）基于NMI 的社團劃分相似性指標。在Karate 網絡和Football 網絡中，GN 算法、LSL-GN 算法和Louvain 算法表現出如下關系：NMIGN＜NMILouvain＜NMILSL-GN；在Adjnoun 網絡中，表現出如下關系：NMILouvain＜NMIGN＜NMILSL-GN。

3）基于ARI 的社團劃分相似性指標。在Karate 網絡和Football 網絡中，GN 算法、LSL-GN 算法和Louvain 算法表現出如下關系：ARIGN＜ARILouvain＜ARILSL-GN；在Adjnoun 網絡中，表現出如下關系：ARILouvain＜ARIGN＜ARILSL-GN。

情形2）和3）度量了真實社團結構與算法劃分社團之間的相似程度。

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

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

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

4 移動漫游網絡上的社團挖掘

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

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

如圖9 刻畫了一類移動漫游網絡模型，其中的節點具有多關系性，根據多關系節點網絡模型定義（1），該網絡模型存在如下關系：

圖9 移動漫游網絡模型示例Fig.9 Mobile roaming network model example

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

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

3）節點多關系：根據R1關系形成的用戶節點連邊，分別記為e1至e4；根據R2關系形成的應用節點連邊，分別記為e7和e8；根據R3關系形成的“用戶-應用”節點連邊，分別記為e5和e6。由此，構建具有多關系的移動漫游網絡模型。

4.1 數據預處理

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

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

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

表3 用戶信息Tab.3 User information

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

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

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

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

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

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

表4 通話等級設置Tab.4 Call level setting

4.2 網絡模型構建

構建一類基于“用戶-應用”移動漫游網絡模型，用戶類節點數為1 097，應用類節點數為37，兩類節點間通過不同的連邊關系R1、R2和R3進行連接。假設節點之間的連邊概率為p，生成最終的網絡模型G。構建過程如下：

1）用戶類節點以R1連邊關系構建。按照表4 通話等級，對1 097 個用戶進行連邊，具體如下：

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

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

2）應用類節點以R2連邊關系構建。按照應用平臺分類對37 個應用平臺進行連邊，具體如下：

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

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

3）用戶與應用類節點間以R3連邊關系構建。按照表3用戶信息對應用平臺按照出行類應用、通信類應用、視頻類應用進行分類，并將應用按照使用流量排序。為了構建移動漫游網絡模型中用戶與應用之間的連邊，設定連邊概率p5、p6、p7和p8，具體如下：

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

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

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

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

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

經過大量對比實驗，針對移動漫游網絡模型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。

最終生成的移動漫游網絡G包含了1 134 節點，10 899 條連邊。該網絡的密度為0.017，網絡的平均路徑長度為2.594，平均聚類系數為0.093，網絡拓撲結構如圖10 所示。

圖10 移動漫游網絡的拓撲結構Fig.10 Topology of mobile roaming network

4.3 基于LSL-GN算法的移動漫游網絡社團挖掘

基于節點多關系的LSL-GN 社團挖掘算法對移動漫游網絡進行社團挖掘。由于移動漫游網絡模型中節點社團個數未知，為了驗證LSL-GN 社團挖掘算法的合理性，本文采用了GN 算法與Louvain 算法對網絡模型進行社團挖掘，并在模塊度上進行對比。

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

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

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

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

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

5 結語

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

本文所采用的移動漫游網絡數據量相對較少，沒有充分考慮網絡規模較大的情況。面對海量數據時，社團挖掘技術可結合機器學習進一步分析社團結構，以提高大型數據集的社團挖掘質量，增強社團挖掘技術的普適性。