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

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

0 引言

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

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

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

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

1 基本知識

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

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

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

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

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

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

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

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

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

1.1 鄰接矩陣

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

1.2 共同鄰居

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

1.3 LHN-I指標(biāo)

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

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

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

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

圖2 網(wǎng)絡(luò)G0的拓?fù)浣Y(jié)構(gòu)Fig.2 Topology of network G0

1.4 路徑長度

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

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

1.5 GN算法

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

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

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

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

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

2 LSL-GN社團(tuán)挖掘算法

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

2.1 算法描述

2.1.1 LHN-ISL指標(biāo)

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

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

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

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

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

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

2.1.2 基于LHN-ISL指標(biāo)的相似度矩陣

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

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

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

2.1.3 LSL-GN社團(tuán)挖掘算法

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

2.2 算法評價指標(biāo)

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

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

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

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

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

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

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

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

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

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

Football 網(wǎng)絡(luò)存在115 個節(jié)點(diǎn)和616 條邊，其中節(jié)點(diǎn)表示球隊，邊表示球隊之間存在過比賽，原始數(shù)據(jù)中將115 支隊伍分為12 個聯(lián)盟。本文以Football 網(wǎng)絡(luò)為例，該網(wǎng)絡(luò)的真實(shí)結(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 算法進(jìn)行社團(tuán)劃分：首先計算節(jié)點(diǎn)間相似度LHN-ISL 指標(biāo)，其次通過調(diào)整LHN-ISL 指標(biāo)的閾值獲取最優(yōu)的社團(tuán)劃分結(jié)果。當(dāng)LHN-ISL 閾值取值為0.527 時，該連通網(wǎng)絡(luò)的社團(tuán)劃分效果最好。最后利用GN 算法對其進(jìn)行社團(tuán)挖掘。如圖7 所示，F(xiàn)ootball 網(wǎng)絡(luò)利用LSL-GN 算法進(jìn)行社團(tuán)劃分，其結(jié)構(gòu)較為明顯。

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

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

圖8 不同劃分?jǐn)?shù)下的模塊度Fig.8 Modularity under different division number

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

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

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

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

2）基于NMI 的社團(tuán)劃分相似性指標(biāo)。在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 的社團(tuán)劃分相似性指標(biāo)。在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）度量了真實(shí)社團(tuán)結(jié)構(gòu)與算法劃分社團(tuán)之間的相似程度。

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)某運(yùn)營商提供的用戶及其應(yīng)用平臺信息搭建了移動漫游網(wǎng)絡(luò)模型。網(wǎng)絡(luò)中：用戶類節(jié)點(diǎn)A1是指手機(jī)通信用戶，共計1 097 位用戶，其中包含886 位漫游用戶；應(yīng)用類節(jié)點(diǎn)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 個指標(biāo)，如表3 所示。

表3 用戶信息Tab.3 User information

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

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

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

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

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

計算得出通話總時長平均值a約為50 min。為方便后期比較，本文對用戶通話時長進(jìn)行了編號，并根據(jù)標(biāo)準(zhǔn)化結(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é)點(diǎn)數(shù)為1 097，應(yīng)用類節(jié)點(diǎn)數(shù)為37，兩類節(jié)點(diǎn)間通過不同的連邊關(guān)系R1、R2和R3進(jìn)行連接。假設(shè)節(jié)點(diǎn)之間的連邊概率為p，生成最終的網(wǎng)絡(luò)模型G。構(gòu)建過程如下：

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

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

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

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

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

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

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

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

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

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

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

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

經(jīng)過大量對比實(shí)驗(yàn)，針對移動漫游網(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é)點(diǎn)，10 899 條連邊。該網(wǎng)絡(luò)的密度為0.017，網(wǎng)絡(luò)的平均路徑長度為2.594，平均聚類系數(shù)為0.093，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖10 所示。

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

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

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

不同社團(tuán)挖掘算法在移動漫游網(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í)驗(yàn)數(shù)據(jù)集的模塊度值最高，其社團(tuán)內(nèi)部節(jié)點(diǎn)具有高的相似度，對社團(tuán)內(nèi)部節(jié)點(diǎn)進(jìn)行推送業(yè)務(wù)時，因他們相似的興趣愛好而精準(zhǔn)推薦。

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

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

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

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

5 結(jié)語

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

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