基于圖論算法的微博好友圈及消息發布方案研究

李冬梅，簡國明，王尚九，李少勇，杜磊，周碧江

（韶關學院 數學與統計學院，廣東 韶關 512005）

?

基于圖論算法的微博好友圈及消息發布方案研究

李冬梅，簡國明，王尚九，李少勇，杜磊，周碧江

（韶關學院 數學與統計學院，廣東 韶關 512005）

摘要：以微博用戶為頂點，建立用戶關注關系的頂點賦權有向圖模型，把尋找微博中的最大好友圈問題轉化為有向圖的最大有向完全子圖問題，而選擇發布某消息的用戶數最少的方案問題轉化為尋找有向圖的最小支配集問題.采取用戶間關注關系0-1矩陣及好友關系的無向圖，應用啟發式著色算法求解無向圖中的最大完全子圖，計算出最大好友圈.根據消息傳播關聯的0-1矩陣，應用有向圖的最小支配集的優化算法，求解最小支配集，得出了發布某消息的用戶數最少的方案.

關鍵詞：微博；圖論算法；好友圈；最大完全子圖；最小支配集

微博，作為一種新興的交流工具，以簡單快捷的操作方式和隨時隨地發布信息的互動形式，在各類網絡社交服務中獨樹一幟［1-2］.在微博中，相互關注的用戶被稱為好友，對于一個群體，如果他們相互之間均為好友，則稱為好友圈.文獻［3］討論了微博用戶、微博消息的各影響因子及影響力問題，并給出了相關計算結果.本文采用南京師范大學2014年數學建模競賽題相關數據（其中，數據文件data1.xls包含了這些用戶的相互關注數據，每一行為該行號對應的用戶對其它用戶的關注信息；數據文件data2.xls為若干消息數據，每一行為用戶發布或轉發的消息編號），并假設一微博用戶發布的消息，其粉絲都會看到（不考慮轉發），考慮某微博有N個（如N =10 000）用戶群體，已知每個用戶關注其它用戶的關注數據，同時已知每個用戶發布或轉發的具體消息數據，消息總數為M個（如M =500），運用圖論算法，計算出最大好友圈人數最多的好友圈，得出了發布某消息的用戶數最少的方案.

1　微博好友及消息問題的圖論表示

本文假設：各個用戶間在短時間內沒有關注新的用戶和取消對其他用戶的關注；用戶在發布或者轉發微博消息后在短時間內不會再去刪除此消息；用戶間不存在僵尸粉現象.

對于有N個用戶的微博群體，以每個微博用戶作為頂點，若微博用戶A關注微博用戶B，則A到B連一條有向邊，得到一個有向圖D（V，E），其中：V是頂點集；E是有向邊集.有向圖D（V，E）是微博用戶群體的關注（關系）有向圖.頂點A的出度d+（ A）是對應用戶A的關注數，而頂點B的入度d-（ B）是對應用戶B的被關注數［4-5］.每個微博用戶發布或轉發消息數視為頂點的權，得到頂點賦權有向圖D（V，E）（見圖1）.在D（V，E）中考慮兩頂點相互連邊（即好友）的群體，稱為好友圈，好友圈就是一個有向完全圖，尋找人數最多的好友圈實質上就是尋找有向圖D（V，E）的極大有向完全圖中的最大有向完全子圖；而選擇發布某消息的用戶數最少的方案問題就是尋找有向圖D（V，E）的最小支配集問題.

圖1 有向圖D（V，E）

2　微博最大好友圈的求解

2.1 關注關系的矩陣表示

在有向圖D（V，E）中，考慮兩頂點相互連邊的子圖，得到一個無向圖，尋找人數最多的好友圈實質上就是尋找有向完全圖中的最大有向完全子圖.令aij表示用戶i關注用戶j情況，即當用戶i關注用戶j時，aij=1；當用戶i沒關注用戶j時，aij=0（i，j=1，2，…，10000）.得到用戶間關注關系的0-1矩陣A=（aij） .

2.2 啟發式著色算法求解最大完全子圖的基本步驟

啟發式著色算法求解最大完全子圖的基本步驟為：

Step1（構造出無向圖G（V，E）） 由數據data1.xls，得到10 000個頂點的有向圖D（V，E）及用戶間關注關系的0-1矩陣A，通過Matlab軟件編程，在10 000個頂點的有向圖D（V，E）中尋找好友對，共找到3 935對好友，對每一對好友進行有向邊連接，就形成了無向圖G（V，E）.

Step2（精簡預處理） 由于無向圖的較大完全子圖往往存在于度數較高的一定數量的頂點之間.因此，可以合理地刪除掉無向圖中較低度數頂點及邊.

Step3（初始化） 記Fd表示未著色頂點的已著色鄰接頂點個數，Ud表示未著色頂點的未著色鄰接頂點個數.找出初始狀態時每個頂點的Fd和Ud，并按照一定的順序放置顏色c1，c2，…，ck；對于無向圖G（V，E），初始狀態時，每個頂點的Fd=0，每個頂點的Ud等于每個頂點的度數，并賦顏色初始值為0.

Step4（頂點著色） 對Fd最大的頂點V著色；若每個Fd相同，則對Ud最大的頂點V著色；若Fd，Ud都相同，則從編號較小的頂點開始著色.

著色的顏色ck選擇原則：k為顏色的編號，若ck這種顏色已經出現過，則著ck這種顏色的頂點只能落在已著色頂點V的鄰接頂點范圍內.若在頂點V的鄰接頂點范圍內，出現某一鄰接頂點不與已著ck這種顏色的其他鄰接頂點相鄰，則選擇下一種顏色ck+1為該鄰接頂點著色.

Step5 重復步驟4，直到頂點V的所有鄰接頂點都著色為止.

Step6 回到Step3，找出每個未著色頂點的Fd和Ud，重復Step4、Step5，直到所有頂點都已著色為止.這樣就實現了無向圖G（V，E）劃分為其極大完全子圖的并集，即G（V，E）=G1（V1，E1）∪G2（V2，E2）∪…∪Gk（Vk，Ek）∪…，且Gi（Vi，Ei）∩Gj（Vj， Ej）=?（i≠j）；V（G）=V（G1）∪V（G2）∪…∪V（Gk）∪…，且V（Gi）∩V（Gj）=?（i≠j），Gi（Vi，Ei）=Gi（i=1，2，3，…）表示無向圖G（V，E）的極大完全子圖.

Step7 通過比較所有的極大完全子圖，得到最大完全子圖［6］.

2.3 啟發式著色算法求解最大完全子圖的求解結果

根據啟發式著色算法求解最大完全子圖的基本步驟，運用Matlab編程求解，得到由13個用戶所構成的好友圈為最大好友圈，分別是用戶867，2 529，2 886，3 077，3 206，3 222，3 646，4 012，4 831，5 630，6 241，7 408，8 857.而最大完全子圖見圖2.

圖2 最大完全子圖

3　微博消息用戶最少的發布方案求解

考慮消息傳播關系的有向圖D（V，E），這樣求用戶最少的發布方案問題就是求有向圖的最小支配集問題［7］.令bij表示用戶i是否看到用戶j發布的信息，即當用戶i能看到用戶j發布的信息時，bij=1；當用戶i不能看到用戶j發布的信息時，bij=0（i，j=1，2，…，10000）.得到0-1關聯關系矩陣B=（bij），頂點v的出度越大，表示頂點v能支配的頂點越多，頂點v成為最小支配集中的元素的可能性越大，而0-1關聯矩陣中的每一列之和分別表示對應頂點的出度，每一行之和分別表示對應頂點的入度.

用戶最少發布方案的算法步驟為［8］：

Step1 讀取文件data2.xls的數據，通過Matlab軟件編程，得到消息傳播過程中用戶之間的關聯矩陣B .

Step2 找出粉絲數最多的用戶.對Step1得出的0-1矩陣B的每一列進行求和，求和值記為sj（j=1，2，3，…，10 000），表示用戶j發布消息能讓sj個之前未看到此消息的用戶看到此消息，再從sj（j =1，2， 3， …，10 000）中找出最大的一列，表示能讓最多之前未看到此消息的用戶看到該消息，并將sj最大的列對應的用戶列入最小支配集作為消息的發布用戶.

Step3 找出看過消息的用戶.將sj最大的列中的1轉化為0，表示sj最大的列對應的用戶的粉絲已看過此消息，同時將sj最大的列對應的用戶所對應的行中的1也轉化為0，表示此用戶已發布過此消息.至此，得到一個新的0-1矩陣B .

Step4 重復Step2和Step3，直到對矩陣B的任意一列和行求和都為0為止.

在確保所有用戶都能看到（不考慮轉發）的條件下，得到發布某消息的用戶數最少的發布方案.該方案需要251個用戶發布此消息，具體結果省略.

4　結束語

本文在建立確定最大好友圈模型時，將實際問題轉化為圖的最大完全子圖，利用啟發式著色算法求解最大完全子圖，該算法思路清晰，提出了精簡措施，不僅提高算法運行效率，而且適用于多頂點的無向圖.

針對消息發布用戶進行最優化，通過將問題轉化為有向圖的頂點支配問題，列出相關的0-1矩陣，基于有向圖的最小支配集的優化算法尋找最優方案.本文在新聞傳播、信息推薦、民意調查、電子商務、網絡營銷或網絡代購等領域有一定的借鑒作用和應用價值.

參考文獻：

［1］朱文俊，張寧，聶雨薇.基于圖論的微博消息傳播對微博影響力的研究［J］.廣角，2015（17）：267-269

［2］原福永，馮靜，符茜茜.微博用戶的影響力指數模型［J］.情報分析與研究，2012（6）：60-64

［3］簡國明，李冬梅，李少勇，等.微博用戶及消息的影響力研究與建模［J］.佛山科學技術學院學報，2016，34（3）：1-5

［4］徐俊明.圖論及其應用［M］.合肥：中國科學技術大學出版社，1998

［5］王桂平，王衍，任嘉辰.圖論算法理論、實現及應用［M］.北京：北京大學出版社，2011

［6］李建新.求最大完全子圖的啟發式著色算法［J］.滁州學院學報，2010，12（2）：9-11

［7］董敏，湯建鋼.求解最大完全子圖的一種DNA算法［J］.江漢大學學報：自然科學版，2012，40（1）：20-23

［8］高文宇.有向圖連通支配集求解算法［J］.計算機工程與應用，2010，46（21）：9-13

Research on micro-blogging friends circle and news release scheme based on graph theory algorithm

LI Dong-mei，JIAN Guo-ming，WANG Shang-jiu，LI Shao-yong，DU Lei，ZHOU Bi-jiang
（School of Mathematics and Statistics，Shaoguan University，Shaoguan 512005，China）

Abstract：With micro-blogging users as the vertex，the micro-blogging biggest problem is translated into the largest complete sub-graph problem of directed graph through building vertex weighted directed graph model between the relationship of user attention，and the number of users in a news release minimal solution problems is translated into looking for the smallest dominating set problem of directed graph.Taking attention to the 0-1 matrix of relationship between user attention and friendships of undirected graph，the maximum friends circle is calcutated by the heuristic coloring algorithm for undirected graph the maximum complete sub-graph.According to correlation 0-1 matrix of the message spread and the minimum dominating set of optimization algorithms of a directed graph，the minimum dominating set is solved，then the least number users of a news release program is obtained.

Key words：micro-blogging；graph theory algorithm；friends circle；largest complete sub-graph；minimum dominating set

中圖分類號：O157.6

文獻標識碼：A

doi：10.3969/j.issn.1007-9831.2016.05.005

文章編號：1007-9831（2016）05-0015-04

收稿日期：2016-03-01

基金項目：2015年度廣東大學生科技創新培育專項資金項目（團粵聯發［2015］50號，pdjh2015b0477）；2014年廣東省本科高校教學質量與教學改革工程項目（粵教高函［2014］97號）

作者簡介：李冬梅（1992-），女，廣東英德人，在讀本科生.

通信作者：簡國明（1958-），男，江西南昌人，教授，碩士，從事代數圖論、數學模型和數學教育研究.E-mail：527775876@qq.com