微博社交網絡中用戶群體關系挖掘與群體行為分析

黃涵霞+胡燕萍+孫知信

Community Relationship Mining and Behavior Analysis for a Microblog

中圖分類號：TP391 文獻標志碼：A 文章編號：1009-6868 （2014） 01-0011-003

摘要：提出了一種基于權重屬性的圖聚類方式。該圖聚類方式在圖聚類的基礎上，考慮了每個節點的不同屬性，并根據影響度給屬性分配權重，從而在依據親密度構建的網絡拓撲圖上進行圖聚類的修正。實驗證明，該方法更符合實際的群體聚合方式。

關鍵詞： 社群挖掘；圖聚類；相似度計算

Abstract： This paper proposes a graph-clustering algorithm based on attribute information. The attributes （and their weights） of each node are considered in this model when modifying the network topology based on intimacy. Experiments show that the modified algorithm is closer to the actual group polymerization.

Key words： community detection； graph clustering； similarity calculation

社交網絡發展勢頭強勁，微博更是一個強大的社交平臺。名人們紛紛開啟了認證微博，相互關注頓時拉近了陌生人在網絡空間中的距離。隨著智能終端性能的突破性革新，社交平臺向著移動互聯網絡進軍。中國互聯網絡信息中心（CNNIC）發布的第32次《中國互聯網絡發展狀況統計報告》中顯示2013年具有微博的網民數已達33 077萬人，社交網站的網民數已達28 880萬人。對比使用率與增長率，微博的發展勢頭超過了傳統的社交網站。與往年數據對比發現，傳統社交網站的用戶大批量轉戰到微博，這主要是因為微博用戶只需要即時即地的輸入簡短的文字信息或者上傳圖片就可以公開發布狀態，支持原創，更快速更便捷地反映微博用戶的情感等各方面資訊，關注、@等功能增強了微博用戶之間的互動。

從網絡營銷角度看，微博不僅成為用戶社交生活的網絡工具，也成為傳統網絡與移動互聯網的營銷基地，在普通微博用戶的博文被感知程度低的情況下，以營銷為目的的博文卻在潛移默化地培養著客戶群，然而這樣的客戶群是可以依靠群體挖掘技術實現的。因此，需要自適應隱式或顯示的在海量微博用戶中組件群組。基于微博的信息挖掘是實現微博資源多重利用的技術手段，本文主要依據六度空間理論，研究傳統社交網絡中群組機制在微博社交網絡中的移植性，研究群體關系的挖掘方案與行為，在依靠用戶興趣模聚類獲取到的網絡拓撲結構后依靠節點的屬性矩陣進行初始拓撲結構的重分割。

1 微博社交網絡相關工作

社交網絡不同于普通的靜態網絡，社交網絡中的網絡結構隨著時間變化而不斷發生變化，一定程度上反映真實世界的狀況。微博社交的即時即地性能夠更好地反映網絡與現實世界的關聯。社會性網絡中普遍存在群體現象，可以把網絡結構中連接緊密的節點集命名為群體，類似于“好友圈”的顯示群體，群體與群體之間通過關鍵節點互聯被稱為稀疏網絡，社交性網絡中的群體挖掘主要有相似度計算和圖聚類兩方面的研究熱點。

（1）基于相似度的社會群體挖掘

網絡在時間維度上的動態性，文獻[1]提出的網絡相似性度量方法，在基于圖形結構的基礎上計算用戶的概要信息與語義信息，用戶的概要信息主要以標簽記錄為主，通常在用戶申請賬號時生成靜態的文本，這樣計算出的相似度與網絡拓撲結構缺乏動態性。相似度計算就是計算用戶之間的相似情況，依靠計算每兩個用戶之間的相似度來構建網絡拓撲結構，將大型網絡社區分割成一個個具有關聯性的小型的群體。在文獻[2]中提出了一種新的協同過濾的用戶相似度計算算法，但沒有將其擴展到社交網絡。文獻[3]用監督式學習方法構建了一個關系相似度模型，利用關系特性與非關系特性以及兩個核心用戶與其所在的社區信息，實現高度準確的好友推薦。

（2）社交網絡的圖聚類技術

圖挖掘方法是社會性復雜網絡分析的重要方法，主要是將網絡中的個體分別用節點表示，形成復雜的網絡圖。節點之間采用直線連接的通常表示節點之間的某種關系，節點之間的距離計算公式直接影響到聚類的結果。歐幾里德距離與曼哈坦距離不能直接用在節點距離的計算中，坐標的缺少使得節點間的距離不能直接采用歐幾里得距離和曼哈坦距離。實驗證明采用k-medoids算法時，相比隨即漫步距離算法與最短路徑算法，在數據庫系統和邏輯編程（DBLP）數據集形成的網絡圖的子圖中最短距離算法的聚類結果更為合理[4]。Kohout與Nerda認為可以通過一個有向圖模型將社交網絡中的用戶分到集群中去，他們分析了幾個不同的遺傳算子，并提出了一種遺傳算法用于直接加權圖的聚類[5]。基于熵的聚類方法是獲取局部最優簇的隨機種子成長的方式，最大限度地減少圖熵。基于熵的方法比競爭方法在計算精度和效率上有更好的性能[6]。文獻[7]研究了集群圖中社群交互的關鍵作用節點的發現。一個廣義馬爾可夫圖模型被提出并用在在社交網絡的分類上。該模型揭示了度分布、聚類系數分布。該擁擠系數分布給出了社會網絡特征。

2 微博社交網絡中的用戶

群體關系挖掘

大多數文獻都采用圖聚類算法來挖掘緊密聯系的群體。文獻[8]介紹了一種群體挖掘方法，在圖聚類算法的基礎上，加入了節點屬性的因素，使得群體分類更加精確。但是該文獻采用了二進制的方式對節點屬性進行描述。所有的屬性都采用0和1的方式進行表示。這種方式過于簡化了屬性的取值范圍，并且不具有代表性。endprint

本文在此基礎上，提出了基于親密度的網絡拓撲結構圖，并對節點屬性的取值進行了改進。采用對微博的博文分詞的方式，提取其中的關鍵字，并對關鍵字進行歸類，關鍵字分屬于不同的屬性。對同一種屬性的關鍵字出現的次數進行統計，看該屬性占總值的比例，來作為節點屬性的具體數值。同時，考慮到群體聚類的不同目的，本文還對屬性的權值進行了設置，根據群體劃分目的的不同，來分配屬性權重的大小，從而達到更好劃分群體的目的。

2.1 問題描述

微博社交網絡中用戶采用相互關注、評論博文、轉發與@好友等形式形成節點之間的關聯，本文主要在由親密度構建的網絡拓撲圖上進行圖聚類的修正。

在群體挖掘中，挖掘目的直接影響著網絡群體的組合，親密度的計算可以將具有現實關系的博友聚集起來，形成拓撲結構。用有向帶權圖G（V，E，X）來表示微博網絡中用戶關系。V表示微博網絡中的節點集合；E表示用戶節點的有向邊，即用戶之間的親密行為；X為有向邊的權值，值小就代表不怎么親密，很少有親密舉動。考慮到親密需要雙方互動，故采用節點間雙向的權值的較小值E（X，Y）=min（W（X，Y），W（Y，X））表示親密度。依據親密程度可以構建起類似于圖1的網絡拓撲結構。

由上述方案獲得的網絡拓撲結構還不具有較強的群體特性，需要進一步計算才能獲得社交網絡中的群體結構圖。根據網絡拓撲圖，修改拓撲圖的表示方法，將節點屬性值作為參數重新描述拓撲圖：G（V，E，X），其中V={V1，V2，V3…Vn}是節點集合，n=|V|代表圖中的節點數量。E?V×V是邊的集合。E={（Vi，Vj）}：Vi，Vj∈V}，并且X∈R|V|×d是一個頂點屬性矩陣。圖1顯示了的是一個基于親密度組成的社會性網絡，每個節點代表一個用戶，用戶存在若干屬性，假設存在n個屬性值（T1，T2…Tn），下文將建立屬性矩陣，利用相似度函數計算出節點的相似矩陣，進而對圖1進行修正。

2.2 節點集的屬性矩陣

本文以一個12個頂點的簡單拓撲網絡為例，研究基于屬性舉證重構的拓撲網絡，為其尋找新的邊界。圖2中的拓撲結構中有3個小型群體，可以看出這3個小群體存在一個閉環關系。

由于每個屬性的重要程度不同，為屬性集（T1，T2…Tn）分別分配權值P1，P2…Pn，Pi的取值采用機器學習的方式，根據不同的聚類和挖掘目的，根據屬性的重要程度動態地為屬性分配權值，P1，P2…Pn需滿足條件P1+P2…Pn=1。

對微博的博文采用分詞的方法，提取其中的關鍵字，對關鍵字進行歸類，分屬于不同的屬性，對同一種屬性的關鍵字出現的次數進行統計，設為k，所有關鍵字出現的總次數設為P，那么每個節點該屬性的屬性值a_ij=k/P。節點集屬性矩陣如圖3所示。矩陣給出了拓撲結構中每個節點的屬性。

上述矩陣給出了節點的屬性值，y1表示單純的屬性矩陣，y2依據屬性在割邊中的關鍵程度加入了權值計算，期中假設屬性權重向量為[T→]（1/2，1/4，1/4），接下來就可以依據加權的屬性矩陣求節點的相似度。

2.3 基于相似度的拓撲圖修正

根據屬性矩陣y2采用類余弦相似性計算公式：

可以計算得到每兩個節點的相似性值，從而得到節點集的相似度矩陣，如圖4所示。

根據矩陣圖可以發現節點集（V1，V2，V3，V4，V5，V6）存在屬性高度相關性，但是該節點集中的節點分布在A、B兩個集合內，在節點集C中，很明顯節點集（V7，V8，V10）屬性一樣，但與節點集（V9，V11，V12）中節點的余弦相似度在0.53左右，為了尋找高度相似的節點集，采用閥值為0.95對圖2中的網絡拓撲圖進行修正，得到原拓撲圖的重構，如圖5所示。圖5中虛線表示節點間屬性向量的余弦相似值極高，從而具有相似性，根據虛線的密集程度，對原始的拓撲結構進行了群體的進一步修正，一個藍色區域表示一個親密度基礎上，屬性值極似的群體。

基于網絡親密度所構造的網絡拓撲圖根據用戶與用戶之間的親密關系劃分出來的群體，但是通過這樣的方式聚合出來的群體未必真正有內在的聯系。為此，本文采用加入每個單個節點的內在屬性的方式，這里的屬性可以是每個用戶的興趣愛好，又或者是用戶的需求等因素，根據不同的挖掘目的和要求，動態地給這些屬性分配權重，來挖掘群體的內在關聯。通過加入屬性并對它們分配權重的方式，把看似有聯系的群體分割成了兩個不同的群體，而看似沒有聯系的群體聚合在了一起。

3 結束語

本文提出了一種基于節點屬性的圖聚類算法，原有的網絡拓撲圖是基于微博用戶的網絡親密度進行挖掘的，本文提出的算法對原有的網絡拓撲圖進行了修正，加入了節點屬性的概念，并根據不同的挖掘目的，為屬性分配不同的權值，用來表示不同屬性的重要程度。數據表明這種修正算法更符合實際的社群聚類方式。

參考文獻

[1] AKCORA C G， CARMINATI B， FERRARI E. Network and profile based measures for user similarities on social networks [C]//Proceedings of the Information Reuse and Integration， 2011 IEEE International Conference on， 3-5 Aug. 2011. Las Vegas， 2011： 292-298.

[2] SHEN L， ZHOU Y M. A New User Similarity Measure for Collaborative Filtering Algorithm. [C]//Proceedings of the Computer Modeling and Simulation， 2010. Second International Conference on， 22-24 Jan. 2010， Sanya， Hainan， 2010： 375-379. doi： 10.1109/ICCMS.2010.67.endprint

[3] MOHAJIREEN M， ELLEPOLA C， PERERA M， et al. Relational similarity model for suggesting friends in online social networks [C]//Proceedings of the Industrial and Information Systems （ICIIS）， 2011 6th IEEE International Conference on. 16-19 Aug. 2011， Kandy， 2011：334-339. doi： 10.1109/ICIINFS.2011.6038090.

[4] 溫菊屏， 鐘勇. 圖聚類的算法及其在社會關系網絡中的應用 [J].計算機應用與軟件， 2012，25（2）：161-163.

[5] KOHOUT J， NERUDA R. Two-Phase Genetic Algorithm for Social Network Graphs Clustering [C]//Proceedings of the Advanced Information Networking and Applications Workshops （WAINA）， 2013 27th International Conference on， 25-28 March 2013， Barcelona， 2013：197-202.

[6] KENLEY E C， CHO Y R. Entropy-Based Graph Clustering： Application to Biological and Social Networks [C]//Proceedings of the Data Mining （ICDM）， 2011 IEEE 11th International Conference on， 11-14 Dec. 2011， Vancouver， BC， 2011：1116-1121. doi： 10.1109/ICDM.2011.64.

[7] CRUZ J D， BOTHOREL C， POULET F. Layout Algorithm for Clustered Graphs to Analyze Community Interactions in Social Networks [C]//Proceedings of the Advances in Social Networks Analysis and Mining （ASONAM）， 2012 IEEE/ACM International Conference on， 2012， Washington， DC， USA. 2012：704-705. doi： 10.1109/ASONAM.2012.120.

[8] SALEM S， BANITAAN S， ALJARAH I， et al. Discovering Communities in Social Networks Using Topology and Attributes [C]//Proceedings of the Machine Learning and Applications and Workshops， 2011 10th International Conference on， 18-21 Dec. 2011， Honolulu， HI， 2011：40-43. doi： 10.1109/ICMLA.2011.57.

作者簡介

黃涵霞，南京郵電大學物聯網學院物流工程專業在讀碩士研究生；主要研究方向為信息網絡技術及其在物流中的應用。

胡燕萍，南京郵電大學物聯網學院物流工程專業在讀碩士研究生；主要研究方向為信息網絡技術及其在物流中的應用。

孫知信，南京郵電大學教授、博士生導師；主要研究領域為計算機網絡與安全；已主持和參加基金項目10余項；已發表論文50余篇，其中被SCI/EI檢索40余篇。endprint

[3] MOHAJIREEN M， ELLEPOLA C， PERERA M， et al. Relational similarity model for suggesting friends in online social networks [C]//Proceedings of the Industrial and Information Systems （ICIIS）， 2011 6th IEEE International Conference on. 16-19 Aug. 2011， Kandy， 2011：334-339. doi： 10.1109/ICIINFS.2011.6038090.

[4] 溫菊屏， 鐘勇. 圖聚類的算法及其在社會關系網絡中的應用 [J].計算機應用與軟件， 2012，25（2）：161-163.

[5] KOHOUT J， NERUDA R. Two-Phase Genetic Algorithm for Social Network Graphs Clustering [C]//Proceedings of the Advanced Information Networking and Applications Workshops （WAINA）， 2013 27th International Conference on， 25-28 March 2013， Barcelona， 2013：197-202.

[6] KENLEY E C， CHO Y R. Entropy-Based Graph Clustering： Application to Biological and Social Networks [C]//Proceedings of the Data Mining （ICDM）， 2011 IEEE 11th International Conference on， 11-14 Dec. 2011， Vancouver， BC， 2011：1116-1121. doi： 10.1109/ICDM.2011.64.

[7] CRUZ J D， BOTHOREL C， POULET F. Layout Algorithm for Clustered Graphs to Analyze Community Interactions in Social Networks [C]//Proceedings of the Advances in Social Networks Analysis and Mining （ASONAM）， 2012 IEEE/ACM International Conference on， 2012， Washington， DC， USA. 2012：704-705. doi： 10.1109/ASONAM.2012.120.

[8] SALEM S， BANITAAN S， ALJARAH I， et al. Discovering Communities in Social Networks Using Topology and Attributes [C]//Proceedings of the Machine Learning and Applications and Workshops， 2011 10th International Conference on， 18-21 Dec. 2011， Honolulu， HI， 2011：40-43. doi： 10.1109/ICMLA.2011.57.

作者簡介

黃涵霞，南京郵電大學物聯網學院物流工程專業在讀碩士研究生；主要研究方向為信息網絡技術及其在物流中的應用。

胡燕萍，南京郵電大學物聯網學院物流工程專業在讀碩士研究生；主要研究方向為信息網絡技術及其在物流中的應用。

孫知信，南京郵電大學教授、博士生導師；主要研究領域為計算機網絡與安全；已主持和參加基金項目10余項；已發表論文50余篇，其中被SCI/EI檢索40余篇。endprint

[3] MOHAJIREEN M， ELLEPOLA C， PERERA M， et al. Relational similarity model for suggesting friends in online social networks [C]//Proceedings of the Industrial and Information Systems （ICIIS）， 2011 6th IEEE International Conference on. 16-19 Aug. 2011， Kandy， 2011：334-339. doi： 10.1109/ICIINFS.2011.6038090.

[4] 溫菊屏， 鐘勇. 圖聚類的算法及其在社會關系網絡中的應用 [J].計算機應用與軟件， 2012，25（2）：161-163.

[5] KOHOUT J， NERUDA R. Two-Phase Genetic Algorithm for Social Network Graphs Clustering [C]//Proceedings of the Advanced Information Networking and Applications Workshops （WAINA）， 2013 27th International Conference on， 25-28 March 2013， Barcelona， 2013：197-202.

[6] KENLEY E C， CHO Y R. Entropy-Based Graph Clustering： Application to Biological and Social Networks [C]//Proceedings of the Data Mining （ICDM）， 2011 IEEE 11th International Conference on， 11-14 Dec. 2011， Vancouver， BC， 2011：1116-1121. doi： 10.1109/ICDM.2011.64.

[7] CRUZ J D， BOTHOREL C， POULET F. Layout Algorithm for Clustered Graphs to Analyze Community Interactions in Social Networks [C]//Proceedings of the Advances in Social Networks Analysis and Mining （ASONAM）， 2012 IEEE/ACM International Conference on， 2012， Washington， DC， USA. 2012：704-705. doi： 10.1109/ASONAM.2012.120.

[8] SALEM S， BANITAAN S， ALJARAH I， et al. Discovering Communities in Social Networks Using Topology and Attributes [C]//Proceedings of the Machine Learning and Applications and Workshops， 2011 10th International Conference on， 18-21 Dec. 2011， Honolulu， HI， 2011：40-43. doi： 10.1109/ICMLA.2011.57.

作者簡介

黃涵霞，南京郵電大學物聯網學院物流工程專業在讀碩士研究生；主要研究方向為信息網絡技術及其在物流中的應用。

胡燕萍，南京郵電大學物聯網學院物流工程專業在讀碩士研究生；主要研究方向為信息網絡技術及其在物流中的應用。

孫知信，南京郵電大學教授、博士生導師；主要研究領域為計算機網絡與安全；已主持和參加基金項目10余項；已發表論文50余篇，其中被SCI/EI檢索40余篇。endprint