一種基于鏈路優(yōu)化的社團(tuán)挖掘算法及其應(yīng)用

姚鑫宇 肖玉芝 趙洪凱

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

0 引 言

復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘?qū)Ψ治鼍W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)起著至關(guān)重要的作用,其研究成果被應(yīng)用到推薦系統(tǒng)和社會(huì)網(wǎng)絡(luò)分析等領(lǐng)域中[1]。Newman等[2]將社團(tuán)定義為一組在網(wǎng)絡(luò)內(nèi)部連接緊密而相互間連接稀疏的子圖。社團(tuán)結(jié)構(gòu)廣泛存在于現(xiàn)實(shí)世界中,例如通信網(wǎng)絡(luò)中的不同個(gè)體,因?yàn)榕笥殃P(guān)系而形成團(tuán)簇。社交網(wǎng)絡(luò)中基于個(gè)體興趣愛好,自發(fā)形成彼此間關(guān)聯(lián)緊密的不同社團(tuán)。隨著5G的發(fā)展和移動(dòng)設(shè)備的普及,運(yùn)營(yíng)商更加注重分析用戶的興趣偏好,從而為其制定個(gè)性化產(chǎn)品推薦,并且依靠用戶團(tuán)體進(jìn)行推廣。因此,在海量數(shù)據(jù)中運(yùn)用社團(tuán)挖掘技術(shù)快速劃分出不同興趣愛好社團(tuán)顯得尤為重要。

經(jīng)典社團(tuán)挖掘算法有基于模塊度優(yōu)化的G-N算法、Louvain算法和基于標(biāo)簽傳播的LPA算法[3]。G-N算法是一種采用分裂思想的社團(tuán)挖掘算法,算法中通過(guò)不斷計(jì)算邊介數(shù)并刪除介數(shù)值最高的連邊獲取社團(tuán)劃分,但該算法時(shí)間復(fù)雜度較高,不適用于超大網(wǎng)絡(luò)規(guī)模[4]。Blondel等[5]提出Louvain算法,其計(jì)算速度較快,由于采用一種與G-N算法相反的自下而上的凝聚過(guò)程,不會(huì)對(duì)小規(guī)模的社團(tuán)探測(cè)產(chǎn)生遺漏。基于標(biāo)簽傳播的LPA算法最早由Raghavan等[6]中提出,該算法時(shí)間復(fù)雜度接近線性時(shí)間(O(m),其中m為邊數(shù)目),但算法運(yùn)行過(guò)程中卻因?yàn)楣?jié)點(diǎn)選擇隨機(jī)性導(dǎo)致結(jié)果不穩(wěn)定。

鑒于上述經(jīng)典社團(tuán)挖掘算法的優(yōu)缺點(diǎn),有學(xué)者提出基于節(jié)點(diǎn)相似度的社團(tuán)挖掘算法?；齕7]根據(jù)節(jié)點(diǎn)相似性提出了ADL-CN算法,該算法通過(guò)計(jì)算兩個(gè)節(jié)點(diǎn)之間的共鄰居數(shù)來(lái)決定增加或刪除兩個(gè)節(jié)點(diǎn)之間的連邊進(jìn)而獲得社團(tuán)結(jié)構(gòu)。武龍舉[8]通過(guò)計(jì)算接近度中心性與Jaccard相似系數(shù)提出了一種距離中心性相似度指標(biāo),并通過(guò)使用K-means聚類算法實(shí)現(xiàn)網(wǎng)絡(luò)中社團(tuán)的挖掘。節(jié)點(diǎn)相似度的計(jì)算方法有兩種:基于局部信息的節(jié)點(diǎn)相似度指標(biāo)和基于全局信息的節(jié)點(diǎn)相似度指標(biāo)。

隨著網(wǎng)絡(luò)規(guī)模增大,節(jié)點(diǎn)間多維性關(guān)系增加,在社團(tuán)挖掘中很難獲取節(jié)點(diǎn)的全局拓?fù)湫畔?。因此為了盡可能利用節(jié)點(diǎn)的拓?fù)湫畔?并準(zhǔn)確劃分出其歸屬社團(tuán),本文提出一種基于鏈路優(yōu)化的P-L(Priority-Louvain)算法,即選取基于局部信息相似度指標(biāo)對(duì)網(wǎng)絡(luò)鏈路進(jìn)行處理,預(yù)測(cè)網(wǎng)絡(luò)中未正確采集到的節(jié)點(diǎn)關(guān)系,刪除在收集信息過(guò)程中產(chǎn)生的錯(cuò)誤關(guān)系,形成初始社團(tuán)結(jié)構(gòu),并結(jié)合Louvain算法的多層次優(yōu)化Modularity指標(biāo)衡量社團(tuán)挖掘結(jié)果質(zhì)量。通過(guò)驗(yàn)證,算法既能刻畫出社團(tuán)的緊密程度,又能較大程度地保留節(jié)點(diǎn)歸屬,并且提升了Louvain算法的社團(tuán)挖掘質(zhì)量。

本文使用常用數(shù)據(jù)集與經(jīng)典的社團(tuán)挖掘算法Louvain、GN和LPA算法進(jìn)行實(shí)驗(yàn)對(duì)比。結(jié)果表明,P-L算法在社團(tuán)挖掘質(zhì)量上比其他算法均有一定的提升。作為算法的應(yīng)用,本文構(gòu)建并刻畫了一個(gè)兩層網(wǎng)絡(luò)模型,第一層為用戶層,第二層為用戶使用的App應(yīng)用層,簡(jiǎn)稱“用戶-App”網(wǎng)絡(luò)。利用P-L算法對(duì)網(wǎng)絡(luò)中所有用戶使用的視頻類App進(jìn)行探測(cè)劃分,得出使用如愛奇藝等App的用戶群體,為通信行業(yè)的客戶細(xì)分提供決策。

1 預(yù)備知識(shí)

1.1 Salton指標(biāo)

Salton指標(biāo)[9]即余弦相似性,是一種用于描述兩個(gè)節(jié)點(diǎn)之間的相似度指標(biāo),Salton指標(biāo)值越大,兩個(gè)節(jié)點(diǎn)之間的相似度越高。稀疏網(wǎng)絡(luò)中Salton指標(biāo)也具有較好的計(jì)算效果。本文利用Salton指標(biāo)衡量節(jié)點(diǎn)間的相似度,進(jìn)而為鏈路優(yōu)化過(guò)程提供依據(jù)。Salton指標(biāo)計(jì)算式為:

(1)

式中:A和B為網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn),k(A)、k(B)分別為節(jié)點(diǎn)A和節(jié)點(diǎn)B的度。

1.2 社團(tuán)挖掘評(píng)價(jià)指標(biāo)

1.2.1模塊度Q函數(shù)

Newman和Girvan在研究社團(tuán)挖掘問題的同時(shí),提出了用模塊度Q函數(shù)衡量社團(tuán)挖掘的效果。

所謂模塊度,是指在網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部節(jié)點(diǎn)的邊所占比例與某一個(gè)隨機(jī)網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部節(jié)點(diǎn)的邊所占比例的期望值的差值[10]。其中,這個(gè)隨機(jī)網(wǎng)絡(luò)的構(gòu)造方法為:在保持各個(gè)節(jié)點(diǎn)的社團(tuán)屬性不變的同時(shí),按照節(jié)點(diǎn)的度來(lái)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行隨機(jī)連接。在具有較強(qiáng)社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)中則社團(tuán)內(nèi)部的連邊比例應(yīng)高于隨機(jī)網(wǎng)絡(luò)的期望值。模塊度計(jì)算式為:

(2)

式中:M為已發(fā)現(xiàn)的社團(tuán)個(gè)數(shù);L為網(wǎng)絡(luò)中的邊數(shù);ls為社團(tuán)s中邊的數(shù)目;ds為社團(tuán)s中包含邊的總數(shù)目。

1.2.2NMI指標(biāo)

NMI(Normalized Mutual information)指標(biāo)即標(biāo)準(zhǔn)化互信息,用來(lái)衡量算法劃分出的社團(tuán)和真實(shí)社團(tuán)之間的相似程度[11]。設(shè)X、Y分別表示網(wǎng)絡(luò)兩個(gè)特定的社團(tuán)劃分結(jié)果,X、Y中的第i位表示第i個(gè)節(jié)點(diǎn)所歸屬的社團(tuán),互信息越大,X、Y越相近?；バ畔⒂?jì)算式為:

(3)

式中:p(x,y)表示X、Y的聯(lián)合分布概率,將互信息調(diào)整到0～1之間即為標(biāo)準(zhǔn)互信息。標(biāo)準(zhǔn)互信息計(jì)算式為:

(4)

式中:H(X)和H(Y)為熵。

1.2.3ARI指標(biāo)

ARI指標(biāo)(Adjusted Rand Index)是應(yīng)用于評(píng)估聚類效果的指標(biāo)[12],社團(tuán)挖掘本質(zhì)上也是一種聚類問題,因此采用ARI指標(biāo)對(duì)社團(tuán)挖掘效果進(jìn)行評(píng)估,計(jì)算式為:

(5)

式中:C為給出的真實(shí)網(wǎng)絡(luò)社團(tuán)劃分。設(shè)K表示社團(tuán)劃分的結(jié)果,a表示C與K中屬于同一社團(tuán)元素的對(duì)數(shù),b表示C與K中不屬于同一社團(tuán)元素的對(duì)數(shù)。

1.3 Louvain算法

Louvain算法[5]是一種基于模塊度優(yōu)化的社團(tuán)挖掘算法,該算法具有良好的時(shí)間復(fù)雜度和社團(tuán)劃分效果。Louvain算法流程如下:

1) 初始,將網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)視作一個(gè)單獨(dú)的社團(tuán)。

2) 從網(wǎng)絡(luò)中隨機(jī)選取一個(gè)節(jié)點(diǎn)執(zhí)行步驟3)和步驟4)。

3) 對(duì)于選定的節(jié)點(diǎn)i,找到其全部的鄰居節(jié)點(diǎn),同時(shí)計(jì)算將節(jié)點(diǎn)i與其各個(gè)鄰居節(jié)點(diǎn)合并后產(chǎn)生的模塊度增益。

4) 找到產(chǎn)生模塊度最大增益的鄰居節(jié)點(diǎn),若模塊度增益值大于0,則將i移動(dòng)至此節(jié)點(diǎn)所在的社團(tuán):

當(dāng)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都無(wú)法再被移動(dòng)時(shí),將同一社團(tuán)中的所有節(jié)點(diǎn)合并為網(wǎng)絡(luò)中的一個(gè)新節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)繼承該社團(tuán)與其他社團(tuán)之間的連邊。

5) 對(duì)經(jīng)過(guò)重新構(gòu)建的網(wǎng)絡(luò)進(jìn)行迭代,直至網(wǎng)絡(luò)中所有節(jié)點(diǎn)均無(wú)法移動(dòng),則輸出結(jié)果,算法結(jié)束。

2 P-L算法

2.1 算法描述

為了將Louvain算法推廣到連邊缺失或噪聲網(wǎng)絡(luò)中,結(jié)合Salton指標(biāo),提出了一種基于鏈路優(yōu)化的社團(tuán)挖掘算法,記為Priority-Louvain算法,簡(jiǎn)稱P-L。首先使用Salton指標(biāo)獲取整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)相似度矩陣,接著根據(jù)設(shè)定的相似度閾值重新構(gòu)建網(wǎng)絡(luò),最后使用Louvain算法劃分社團(tuán)。社團(tuán)劃分過(guò)程中既充分利用了節(jié)點(diǎn)的拓?fù)湫畔⒂痔嵘薒ouvain算法劃分質(zhì)量。

算法實(shí)現(xiàn)如下:

第一步:根據(jù)網(wǎng)絡(luò)關(guān)系生成網(wǎng)絡(luò)節(jié)點(diǎn)相似度矩陣Similarity(v,w),其中v和w為網(wǎng)絡(luò)中的兩個(gè)任意節(jié)點(diǎn)。流程如下:

輸入:網(wǎng)絡(luò)圖G。

輸出:網(wǎng)絡(luò)節(jié)點(diǎn)相似度矩陣Similarity(v,w)。

1) 遍歷網(wǎng)絡(luò)圖G中的每個(gè)節(jié)點(diǎn)v。

2) 遍歷網(wǎng)絡(luò)中除v以外的所有節(jié)點(diǎn)w。

3) 計(jì)算v和w的Salton指標(biāo),并填入相應(yīng)位置。

4) 返回Similarity(v,w)。

第二步:使用Louvain算法對(duì)生成的網(wǎng)絡(luò)節(jié)點(diǎn)相似度矩陣Similarity(v,w)進(jìn)行社團(tuán)挖掘。流程如下:

輸入:Similarity(v,w)。

輸出:網(wǎng)絡(luò)社團(tuán)劃分。

1) 計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)平均度,根據(jù)該值設(shè)定相似度閾值。

2) 將網(wǎng)絡(luò)節(jié)點(diǎn)相似度矩陣Similarity(v,w)中大于該閾值的元素值置為1;小于該閾值的元素置為0;主對(duì)角線元素置為0,從而生成優(yōu)化后的網(wǎng)絡(luò)鄰接矩陣A(i,j),其中i、j為網(wǎng)絡(luò)中的節(jié)點(diǎn)。

3) 將優(yōu)化后的網(wǎng)絡(luò)鄰接矩陣A(i,j)轉(zhuǎn)化為網(wǎng)絡(luò)。

4) 采用Louvain算法進(jìn)行社團(tuán)挖掘。

5) 輸出最終的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。

2.2 兩個(gè)經(jīng)典網(wǎng)絡(luò)實(shí)例

2.2.1Zacharykarateclub網(wǎng)絡(luò)

Zachary karate club網(wǎng)絡(luò)[13]是由34個(gè)成員組成的網(wǎng)絡(luò),網(wǎng)絡(luò)中的節(jié)點(diǎn)由每位成員抽象而來(lái),成員與成員間的聯(lián)系抽象為網(wǎng)絡(luò)中的連邊,網(wǎng)絡(luò)中共包含34個(gè)節(jié)點(diǎn)和75條連邊。因俱樂部?jī)?nèi)部對(duì)增加會(huì)費(fèi)問題產(chǎn)生分歧,最終社團(tuán)分裂為以俱樂部主管(0號(hào)節(jié)點(diǎn))和校長(zhǎng)(32號(hào)節(jié)點(diǎn))為中心的兩個(gè)團(tuán)體,該網(wǎng)絡(luò)是用于研究社團(tuán)的經(jīng)典網(wǎng)絡(luò),常被用于評(píng)估社團(tuán)挖掘算法的效果。為了驗(yàn)證本文算法的正確性與優(yōu)越性,使用Zachary karate club網(wǎng)絡(luò)對(duì)社團(tuán)挖掘算法進(jìn)行比較,并使用Gephi工具進(jìn)行可視化。

首先通過(guò)使用鏈路優(yōu)化對(duì)Zachary karate club網(wǎng)絡(luò)進(jìn)行重構(gòu)。實(shí)驗(yàn)中設(shè)定節(jié)點(diǎn)間相似度閾值為0.35,即節(jié)點(diǎn)與節(jié)點(diǎn)間相似度高于0.35則存在連邊,若節(jié)點(diǎn)與節(jié)點(diǎn)間相似度低于0.35則不存在連邊,空手道俱樂部生成為一個(gè)34×34的相似度矩陣。

對(duì)網(wǎng)絡(luò)進(jìn)行重構(gòu),生成了包含34個(gè)節(jié)點(diǎn)以及184條連邊的新網(wǎng)絡(luò),如圖1所示。

圖1 Zachary karate club網(wǎng)絡(luò)重構(gòu)圖

使用Louvain算法對(duì)新網(wǎng)絡(luò)進(jìn)行社團(tuán)挖掘,結(jié)果顯示僅8號(hào)節(jié)點(diǎn)的社團(tuán)劃分錯(cuò)誤,如圖2所示。

圖2 P-L算法在Zachary karate club網(wǎng)絡(luò)運(yùn)行結(jié)果

為了進(jìn)一步驗(yàn)證算法的可靠性,利用P-L算法與Louvain算法、LPA標(biāo)簽傳播算法和G-N算法在Zachary karate club網(wǎng)絡(luò)針對(duì)模塊度Q函數(shù)值、NMI指標(biāo)、ARI指標(biāo)和社團(tuán)劃分?jǐn)?shù)量上進(jìn)行比較,最終結(jié)果如表1所示。

表1 各社團(tuán)挖掘算法在Zachary karate club網(wǎng)絡(luò)上結(jié)果比較

經(jīng)過(guò)實(shí)驗(yàn)比較發(fā)現(xiàn),相比于其他三種經(jīng)典算法,P-L算法對(duì)社團(tuán)挖掘質(zhì)量有顯著提升。從表1中看到,P-L算法中的Q函數(shù)值小于G-N算法和Louvain算法中的Q函數(shù)值,通過(guò)查閱資料,得知Zachary karate club網(wǎng)絡(luò)是由一個(gè)完整的社團(tuán)分裂而來(lái),所以分裂后的兩個(gè)社團(tuán)成員間仍然存在著較多的聯(lián)系,造成P-L算法在進(jìn)行鏈路優(yōu)化增加社團(tuán)內(nèi)部連邊的同時(shí)也增加了較多的社團(tuán)間連邊,導(dǎo)致Q函數(shù)值略低,但是整體社團(tuán)劃分質(zhì)量較好。

2.2.2Football網(wǎng)絡(luò)

Girvan等[14]通過(guò)對(duì)美國(guó)115所大學(xué)球隊(duì)間的613場(chǎng)橄欖球比賽進(jìn)行統(tǒng)計(jì),建立了Football網(wǎng)絡(luò)模型。將這115支隊(duì)伍抽象為網(wǎng)絡(luò)中的節(jié)點(diǎn)。613場(chǎng)比賽抽象為網(wǎng)絡(luò)中的連邊,便構(gòu)成了Football網(wǎng)絡(luò)。對(duì)Football網(wǎng)絡(luò)進(jìn)行社團(tuán)挖掘后的結(jié)果一般為8～12個(gè)社團(tuán)。運(yùn)用P-L算法,該網(wǎng)絡(luò)最終劃分為12個(gè)社團(tuán)。算法運(yùn)行過(guò)程與Zachary karate club網(wǎng)絡(luò)相同。社團(tuán)挖掘結(jié)果如圖3所示。

圖3 P-L算法在Football網(wǎng)絡(luò)上運(yùn)行結(jié)果

通過(guò)計(jì)算得出,網(wǎng)絡(luò)模塊度為0.866 882,社團(tuán)劃分?jǐn)?shù)量為12個(gè),P-L算法與其他社團(tuán)挖掘算法對(duì)比見表2,在Football網(wǎng)絡(luò)上,無(wú)論是劃分?jǐn)?shù)量還是劃分質(zhì)量均比較優(yōu)越。

表2 各社團(tuán)挖掘算法在Football網(wǎng)絡(luò)上結(jié)果比較

3 實(shí)證社交網(wǎng)絡(luò)社區(qū)劃分

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

隨著互聯(lián)網(wǎng)的快速發(fā)展,人們更傾向于借助手機(jī)來(lái)獲取各種社交應(yīng)用并進(jìn)行交流。對(duì)于通信行業(yè)運(yùn)營(yíng)商而言,分析客戶使用產(chǎn)品的行為,制定個(gè)性化產(chǎn)品推薦變得非常重要。

本文使用某運(yùn)營(yíng)商提供的實(shí)驗(yàn)訓(xùn)練數(shù)據(jù)構(gòu)建了網(wǎng)絡(luò)模型,并利用P-L算法進(jìn)行社團(tuán)檢測(cè)。實(shí)驗(yàn)數(shù)據(jù)包含1 174位用戶和用戶使用的6款視頻類App見表3所示。

表3 用戶App使用情況

其中愛奇藝、騰訊和優(yōu)酷三家視頻平臺(tái)分屬于百度系、騰訊系和阿里系應(yīng)用,代表了傳統(tǒng)視頻平臺(tái),快手、抖音和西瓜視頻代表了新興短視頻平臺(tái)。本文通過(guò)對(duì)用戶數(shù)據(jù)進(jìn)行采集、分析、處理以及模型構(gòu)建等過(guò)程后,利用社團(tuán)挖掘技術(shù),將用戶根據(jù)其使用的視頻平臺(tái)準(zhǔn)確聚類。為運(yùn)營(yíng)商根據(jù)社團(tuán)規(guī)模和社團(tuán)劃分推出流量套餐業(yè)務(wù)提供了決策參考。

通過(guò)用戶使用特定App流量大小衡量用戶對(duì)其愛好程度。同時(shí)由于傳統(tǒng)視頻類App和短視頻類App應(yīng)用場(chǎng)景不同,其所產(chǎn)生的流量信息并不能直接使用,因此首先對(duì)用戶流量數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理[15-16]。數(shù)據(jù)標(biāo)準(zhǔn)化過(guò)程如下:

輸入:某款A(yù)pp的用戶流量信息xi、使用人數(shù)n。

輸出:流量信息標(biāo)準(zhǔn)化結(jié)果a。

具體步驟如下:

4) 輸出用戶流量標(biāo)準(zhǔn)化信息a。

為方便后期比較,本文對(duì)App進(jìn)行了編號(hào)(詳見表4),并根據(jù)標(biāo)準(zhǔn)化結(jié)果a將每款A(yù)pp的用戶分為低于平均流量、低于但接近平均流量、高于但接近平均流量和高于平均流量四個(gè)等級(jí)(詳見表5)。

表4 App編號(hào)表

表5 流量等級(jí)表

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

根據(jù)數(shù)據(jù)預(yù)處理的結(jié)果,將數(shù)據(jù)分為用戶層和App層,用戶層包含1 147個(gè)用戶,App層包含6款A(yù)pp,如圖4所示,“用戶-App”兩層網(wǎng)絡(luò)的初始模型。

圖4 “用戶-App”網(wǎng)絡(luò)示意圖

可以看出,兩個(gè)獨(dú)立網(wǎng)絡(luò)層內(nèi)沒有連邊,層間依據(jù)用戶使用App行為進(jìn)行連邊。為了構(gòu)造用戶與用戶間的關(guān)聯(lián),結(jié)合App流量等級(jí)差異值,利用隨機(jī)概率p刻畫用戶層內(nèi)節(jié)點(diǎn)連邊關(guān)系。即將“用戶-App”層間關(guān)系映射成用戶層內(nèi)關(guān)系,并生成最終的網(wǎng)絡(luò)模型G。構(gòu)建規(guī)則如下:

1) 針對(duì)使用一款A(yù)pp的用戶。若用戶間使用同款A(yù)pp且流量等級(jí)相同,則用戶間以概率p1連邊。若用戶間使用同款A(yù)pp但流量等級(jí)不同,則用戶間以概率p2連邊。

2) 針對(duì)使用多款A(yù)pp的用戶。

(1) 若用戶使用的App和流量等級(jí)均與使用單款A(yù)pp的用戶群體相同,則該用戶以概率p3與僅使用單款A(yù)pp的用戶群體進(jìn)行連邊。

(2) 若用戶使用的App和僅使用單款A(yù)pp的用戶群體相同但流量等級(jí)不同,則該用戶以概率p4與僅使用單款A(yù)pp的用戶群體進(jìn)行連邊。

經(jīng)過(guò)大量對(duì)比實(shí)驗(yàn),針對(duì)網(wǎng)絡(luò)模型G,確定了4種連邊概率取值,分別為p1=0.020、p2=0.016、p3=0.160、p4=0.100。

網(wǎng)絡(luò)模型G包含了1 174個(gè)節(jié)點(diǎn),8 331條連邊。網(wǎng)絡(luò)直徑為7,平均聚類系數(shù)為0.061,平均路徑長(zhǎng)度為3.415,其拓?fù)浣Y(jié)構(gòu)如圖5所示。

圖5 網(wǎng)絡(luò)模型G可視化圖

3.3 基于P-L算法的社團(tuán)劃分

為驗(yàn)證選取Salton指標(biāo)的合理性。本文設(shè)計(jì)了一組對(duì)比實(shí)驗(yàn),分別使用Salton指標(biāo)和Jacaard相似系數(shù)來(lái)進(jìn)行鏈路優(yōu)化,在同一相似度閾值且劃分結(jié)果相近的前提下基于Salton指標(biāo)優(yōu)化后的網(wǎng)絡(luò),其模塊度函數(shù)值為0.748 301,基于Jaccard相似系數(shù)優(yōu)化后的網(wǎng)絡(luò)模塊度函數(shù)值為0.499 243。結(jié)果表明采用Salton指標(biāo)的P-L算法可以正確地對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分。相對(duì)于Salton指標(biāo),Jaccard相似系數(shù)值偏低且鏈路優(yōu)化后的網(wǎng)絡(luò)模塊度函數(shù)值小于Salton指標(biāo)。因此,采用Salton指標(biāo)預(yù)測(cè)的社團(tuán)內(nèi)部鏈接與外部鏈接的比值要更大。

不同社團(tuán)挖掘算法在實(shí)證網(wǎng)絡(luò)上的運(yùn)行結(jié)果如表6所示。顯然,P-L算法在社團(tuán)劃分精度和模塊度值上均表現(xiàn)出較優(yōu)性。該算法成功識(shí)別了6款A(yù)pp社團(tuán)(如圖6)。不難看出,抖音用戶更傾向于使用愛奇藝,快手用戶更傾向于優(yōu)酷視頻。根據(jù)劃分結(jié)果,制定短視頻類與傳統(tǒng)視頻類相結(jié)合的流量包,在增加用戶體驗(yàn)的同時(shí)進(jìn)行用戶團(tuán)體推廣。

表6 各社團(tuán)挖掘算法在實(shí)證網(wǎng)絡(luò)上結(jié)果比較

圖6 P-L算法在實(shí)證網(wǎng)絡(luò)上運(yùn)行結(jié)果

4 結(jié) 語(yǔ)

本文利用節(jié)點(diǎn)相似度設(shè)計(jì)了基于鏈路優(yōu)化的Louvain社團(tuán)挖掘算法,并通過(guò)實(shí)驗(yàn)證明了該算法的可行性及準(zhǔn)確性。通過(guò)建立“用戶-App”模型來(lái)將算法進(jìn)行推廣和應(yīng)用。該算法無(wú)須預(yù)先設(shè)定社團(tuán)劃分?jǐn)?shù)目,只需要調(diào)整相似度閾值可提高劃分精度,并且算法在連邊稀疏或密集的網(wǎng)絡(luò)中均具有良好的適應(yīng)性。在實(shí)驗(yàn)過(guò)程中,算法在做劃分時(shí)會(huì)出現(xiàn)一些孤立節(jié)點(diǎn)或錯(cuò)誤劃分的情況,因此下一步將對(duì)算法存在的缺陷進(jìn)行改進(jìn)并將算法推廣到復(fù)雜多層網(wǎng)絡(luò)模型中,針對(duì)層間關(guān)聯(lián)的差異性進(jìn)行社團(tuán)挖掘。