一種基于鏈路優化的社團挖掘算法及其應用

姚鑫宇 肖玉芝 趙洪凱

(青海師范大學計算機學院 青海 西寧 810016) (青海省藏文信息處理與機器翻譯重點實驗室 青海 西寧 810016) (藏文信息處理教育部重點實驗室 青海 西寧 810016)

0 引 言

復雜網絡社團挖掘對分析網絡拓撲結構起著至關重要的作用,其研究成果被應用到推薦系統和社會網絡分析等領域中[1]。Newman等[2]將社團定義為一組在網絡內部連接緊密而相互間連接稀疏的子圖。社團結構廣泛存在于現實世界中,例如通信網絡中的不同個體,因為朋友關系而形成團簇。社交網絡中基于個體興趣愛好,自發形成彼此間關聯緊密的不同社團。隨著5G的發展和移動設備的普及,運營商更加注重分析用戶的興趣偏好,從而為其制定個性化產品推薦,并且依靠用戶團體進行推廣。因此,在海量數據中運用社團挖掘技術快速劃分出不同興趣愛好社團顯得尤為重要。

經典社團挖掘算法有基于模塊度優化的G-N算法、Louvain算法和基于標簽傳播的LPA算法[3]。G-N算法是一種采用分裂思想的社團挖掘算法,算法中通過不斷計算邊介數并刪除介數值最高的連邊獲取社團劃分,但該算法時間復雜度較高,不適用于超大網絡規模[4]。Blondel等[5]提出Louvain算法,其計算速度較快,由于采用一種與G-N算法相反的自下而上的凝聚過程,不會對小規模的社團探測產生遺漏。基于標簽傳播的LPA算法最早由Raghavan等[6]中提出,該算法時間復雜度接近線性時間(O(m),其中m為邊數目),但算法運行過程中卻因為節點選擇隨機性導致結果不穩定。

鑒于上述經典社團挖掘算法的優缺點,有學者提出基于節點相似度的社團挖掘算法。化君[7]根據節點相似性提出了ADL-CN算法,該算法通過計算兩個節點之間的共鄰居數來決定增加或刪除兩個節點之間的連邊進而獲得社團結構。武龍舉[8]通過計算接近度中心性與Jaccard相似系數提出了一種距離中心性相似度指標,并通過使用K-means聚類算法實現網絡中社團的挖掘。節點相似度的計算方法有兩種:基于局部信息的節點相似度指標和基于全局信息的節點相似度指標。

隨著網絡規模增大,節點間多維性關系增加,在社團挖掘中很難獲取節點的全局拓撲信息。因此為了盡可能利用節點的拓撲信息,并準確劃分出其歸屬社團,本文提出一種基于鏈路優化的P-L(Priority-Louvain)算法,即選取基于局部信息相似度指標對網絡鏈路進行處理,預測網絡中未正確采集到的節點關系,刪除在收集信息過程中產生的錯誤關系,形成初始社團結構,并結合Louvain算法的多層次優化Modularity指標衡量社團挖掘結果質量。通過驗證,算法既能刻畫出社團的緊密程度,又能較大程度地保留節點歸屬,并且提升了Louvain算法的社團挖掘質量。

本文使用常用數據集與經典的社團挖掘算法Louvain、GN和LPA算法進行實驗對比。結果表明,P-L算法在社團挖掘質量上比其他算法均有一定的提升。作為算法的應用,本文構建并刻畫了一個兩層網絡模型,第一層為用戶層,第二層為用戶使用的App應用層,簡稱“用戶-App”網絡。利用P-L算法對網絡中所有用戶使用的視頻類App進行探測劃分,得出使用如愛奇藝等App的用戶群體,為通信行業的客戶細分提供決策。

1 預備知識

1.1 Salton指標

Salton指標[9]即余弦相似性,是一種用于描述兩個節點之間的相似度指標,Salton指標值越大,兩個節點之間的相似度越高。稀疏網絡中Salton指標也具有較好的計算效果。本文利用Salton指標衡量節點間的相似度,進而為鏈路優化過程提供依據。Salton指標計算式為:

(1)

式中:A和B為網絡中的任意兩個節點,k(A)、k(B)分別為節點A和節點B的度。

1.2 社團挖掘評價指標

1.2.1模塊度Q函數

Newman和Girvan在研究社團挖掘問題的同時,提出了用模塊度Q函數衡量社團挖掘的效果。

所謂模塊度,是指在網絡中連接社團內部節點的邊所占比例與某一個隨機網絡中連接社團內部節點的邊所占比例的期望值的差值[10]。其中,這個隨機網絡的構造方法為:在保持各個節點的社團屬性不變的同時,按照節點的度來對網絡中的節點進行隨機連接。在具有較強社團結構的網絡中則社團內部的連邊比例應高于隨機網絡的期望值。模塊度計算式為:

(2)

式中:M為已發現的社團個數;L為網絡中的邊數;ls為社團s中邊的數目;ds為社團s中包含邊的總數目。

1.2.2NMI指標

NMI(Normalized Mutual information)指標即標準化互信息,用來衡量算法劃分出的社團和真實社團之間的相似程度[11]。設X、Y分別表示網絡兩個特定的社團劃分結果,X、Y中的第i位表示第i個節點所歸屬的社團,互信息越大,X、Y越相近。互信息計算式為:

(3)

式中:p(x,y)表示X、Y的聯合分布概率,將互信息調整到0～1之間即為標準互信息。標準互信息計算式為:

(4)

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

1.2.3ARI指標

ARI指標(Adjusted Rand Index)是應用于評估聚類效果的指標[12],社團挖掘本質上也是一種聚類問題,因此采用ARI指標對社團挖掘效果進行評估,計算式為:

(5)

式中:C為給出的真實網絡社團劃分。設K表示社團劃分的結果,a表示C與K中屬于同一社團元素的對數,b表示C與K中不屬于同一社團元素的對數。

1.3 Louvain算法

Louvain算法[5]是一種基于模塊度優化的社團挖掘算法,該算法具有良好的時間復雜度和社團劃分效果。Louvain算法流程如下:

1) 初始,將網絡中每一個節點視作一個單獨的社團。

2) 從網絡中隨機選取一個節點執行步驟3)和步驟4)。

3) 對于選定的節點i,找到其全部的鄰居節點,同時計算將節點i與其各個鄰居節點合并后產生的模塊度增益。

4) 找到產生模塊度最大增益的鄰居節點,若模塊度增益值大于0,則將i移動至此節點所在的社團:

當網絡中所有的節點都無法再被移動時,將同一社團中的所有節點合并為網絡中的一個新節點,這個節點繼承該社團與其他社團之間的連邊。

5) 對經過重新構建的網絡進行迭代,直至網絡中所有節點均無法移動,則輸出結果,算法結束。

2 P-L算法

2.1 算法描述

為了將Louvain算法推廣到連邊缺失或噪聲網絡中,結合Salton指標,提出了一種基于鏈路優化的社團挖掘算法,記為Priority-Louvain算法,簡稱P-L。首先使用Salton指標獲取整個網絡節點相似度矩陣,接著根據設定的相似度閾值重新構建網絡,最后使用Louvain算法劃分社團。社團劃分過程中既充分利用了節點的拓撲信息又提升了Louvain算法劃分質量。

算法實現如下:

第一步:根據網絡關系生成網絡節點相似度矩陣Similarity(v,w),其中v和w為網絡中的兩個任意節點。流程如下:

輸入:網絡圖G。

輸出:網絡節點相似度矩陣Similarity(v,w)。

1) 遍歷網絡圖G中的每個節點v。

2) 遍歷網絡中除v以外的所有節點w。

3) 計算v和w的Salton指標,并填入相應位置。

4) 返回Similarity(v,w)。

第二步:使用Louvain算法對生成的網絡節點相似度矩陣Similarity(v,w)進行社團挖掘。流程如下:

輸入:Similarity(v,w)。

輸出:網絡社團劃分。

1) 計算網絡節點平均度,根據該值設定相似度閾值。

2) 將網絡節點相似度矩陣Similarity(v,w)中大于該閾值的元素值置為1;小于該閾值的元素置為0;主對角線元素置為0,從而生成優化后的網絡鄰接矩陣A(i,j),其中i、j為網絡中的節點。

3) 將優化后的網絡鄰接矩陣A(i,j)轉化為網絡。

4) 采用Louvain算法進行社團挖掘。

5) 輸出最終的網絡社團結構。

2.2 兩個經典網絡實例

2.2.1Zacharykarateclub網絡

Zachary karate club網絡[13]是由34個成員組成的網絡,網絡中的節點由每位成員抽象而來,成員與成員間的聯系抽象為網絡中的連邊,網絡中共包含34個節點和75條連邊。因俱樂部內部對增加會費問題產生分歧,最終社團分裂為以俱樂部主管(0號節點)和校長(32號節點)為中心的兩個團體,該網絡是用于研究社團的經典網絡,常被用于評估社團挖掘算法的效果。為了驗證本文算法的正確性與優越性,使用Zachary karate club網絡對社團挖掘算法進行比較,并使用Gephi工具進行可視化。

首先通過使用鏈路優化對Zachary karate club網絡進行重構。實驗中設定節點間相似度閾值為0.35,即節點與節點間相似度高于0.35則存在連邊,若節點與節點間相似度低于0.35則不存在連邊,空手道俱樂部生成為一個34×34的相似度矩陣。

對網絡進行重構,生成了包含34個節點以及184條連邊的新網絡,如圖1所示。

圖1 Zachary karate club網絡重構圖

使用Louvain算法對新網絡進行社團挖掘,結果顯示僅8號節點的社團劃分錯誤,如圖2所示。

圖2 P-L算法在Zachary karate club網絡運行結果

為了進一步驗證算法的可靠性,利用P-L算法與Louvain算法、LPA標簽傳播算法和G-N算法在Zachary karate club網絡針對模塊度Q函數值、NMI指標、ARI指標和社團劃分數量上進行比較,最終結果如表1所示。

表1 各社團挖掘算法在Zachary karate club網絡上結果比較

經過實驗比較發現,相比于其他三種經典算法,P-L算法對社團挖掘質量有顯著提升。從表1中看到,P-L算法中的Q函數值小于G-N算法和Louvain算法中的Q函數值,通過查閱資料,得知Zachary karate club網絡是由一個完整的社團分裂而來,所以分裂后的兩個社團成員間仍然存在著較多的聯系,造成P-L算法在進行鏈路優化增加社團內部連邊的同時也增加了較多的社團間連邊,導致Q函數值略低,但是整體社團劃分質量較好。

2.2.2Football網絡

Girvan等[14]通過對美國115所大學球隊間的613場橄欖球比賽進行統計,建立了Football網絡模型。將這115支隊伍抽象為網絡中的節點。613場比賽抽象為網絡中的連邊,便構成了Football網絡。對Football網絡進行社團挖掘后的結果一般為8～12個社團。運用P-L算法,該網絡最終劃分為12個社團。算法運行過程與Zachary karate club網絡相同。社團挖掘結果如圖3所示。

圖3 P-L算法在Football網絡上運行結果

通過計算得出,網絡模塊度為0.866 882,社團劃分數量為12個,P-L算法與其他社團挖掘算法對比見表2,在Football網絡上,無論是劃分數量還是劃分質量均比較優越。

表2 各社團挖掘算法在Football網絡上結果比較

3 實證社交網絡社區劃分

3.1 數據預處理

隨著互聯網的快速發展,人們更傾向于借助手機來獲取各種社交應用并進行交流。對于通信行業運營商而言,分析客戶使用產品的行為,制定個性化產品推薦變得非常重要。

本文使用某運營商提供的實驗訓練數據構建了網絡模型,并利用P-L算法進行社團檢測。實驗數據包含1 174位用戶和用戶使用的6款視頻類App見表3所示。

表3 用戶App使用情況

其中愛奇藝、騰訊和優酷三家視頻平臺分屬于百度系、騰訊系和阿里系應用,代表了傳統視頻平臺,快手、抖音和西瓜視頻代表了新興短視頻平臺。本文通過對用戶數據進行采集、分析、處理以及模型構建等過程后,利用社團挖掘技術,將用戶根據其使用的視頻平臺準確聚類。為運營商根據社團規模和社團劃分推出流量套餐業務提供了決策參考。

通過用戶使用特定App流量大小衡量用戶對其愛好程度。同時由于傳統視頻類App和短視頻類App應用場景不同,其所產生的流量信息并不能直接使用,因此首先對用戶流量數據進行標準化處理[15-16]。數據標準化過程如下:

輸入:某款App的用戶流量信息xi、使用人數n。

輸出:流量信息標準化結果a。

具體步驟如下:

4) 輸出用戶流量標準化信息a。

為方便后期比較,本文對App進行了編號(詳見表4),并根據標準化結果a將每款App的用戶分為低于平均流量、低于但接近平均流量、高于但接近平均流量和高于平均流量四個等級(詳見表5)。

表4 App編號表

表5 流量等級表

3.2 網絡模型構建

根據數據預處理的結果,將數據分為用戶層和App層,用戶層包含1 147個用戶,App層包含6款App,如圖4所示,“用戶-App”兩層網絡的初始模型。

圖4 “用戶-App”網絡示意圖

可以看出,兩個獨立網絡層內沒有連邊,層間依據用戶使用App行為進行連邊。為了構造用戶與用戶間的關聯,結合App流量等級差異值,利用隨機概率p刻畫用戶層內節點連邊關系。即將“用戶-App”層間關系映射成用戶層內關系,并生成最終的網絡模型G。構建規則如下:

1) 針對使用一款App的用戶。若用戶間使用同款App且流量等級相同,則用戶間以概率p1連邊。若用戶間使用同款App但流量等級不同,則用戶間以概率p2連邊。

2) 針對使用多款App的用戶。

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

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

經過大量對比實驗,針對網絡模型G,確定了4種連邊概率取值,分別為p1=0.020、p2=0.016、p3=0.160、p4=0.100。

網絡模型G包含了1 174個節點,8 331條連邊。網絡直徑為7,平均聚類系數為0.061,平均路徑長度為3.415,其拓撲結構如圖5所示。

圖5 網絡模型G可視化圖

3.3 基于P-L算法的社團劃分

為驗證選取Salton指標的合理性。本文設計了一組對比實驗,分別使用Salton指標和Jacaard相似系數來進行鏈路優化,在同一相似度閾值且劃分結果相近的前提下基于Salton指標優化后的網絡,其模塊度函數值為0.748 301,基于Jaccard相似系數優化后的網絡模塊度函數值為0.499 243。結果表明采用Salton指標的P-L算法可以正確地對網絡進行社團劃分。相對于Salton指標,Jaccard相似系數值偏低且鏈路優化后的網絡模塊度函數值小于Salton指標。因此,采用Salton指標預測的社團內部鏈接與外部鏈接的比值要更大。

不同社團挖掘算法在實證網絡上的運行結果如表6所示。顯然,P-L算法在社團劃分精度和模塊度值上均表現出較優性。該算法成功識別了6款App社團(如圖6)。不難看出,抖音用戶更傾向于使用愛奇藝,快手用戶更傾向于優酷視頻。根據劃分結果,制定短視頻類與傳統視頻類相結合的流量包,在增加用戶體驗的同時進行用戶團體推廣。

表6 各社團挖掘算法在實證網絡上結果比較

圖6 P-L算法在實證網絡上運行結果

4 結 語

本文利用節點相似度設計了基于鏈路優化的Louvain社團挖掘算法,并通過實驗證明了該算法的可行性及準確性。通過建立“用戶-App”模型來將算法進行推廣和應用。該算法無須預先設定社團劃分數目,只需要調整相似度閾值可提高劃分精度,并且算法在連邊稀疏或密集的網絡中均具有良好的適應性。在實驗過程中,算法在做劃分時會出現一些孤立節點或錯誤劃分的情況,因此下一步將對算法存在的缺陷進行改進并將算法推廣到復雜多層網絡模型中,針對層間關聯的差異性進行社團挖掘。