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

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

（韶關(guān)學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 韶關(guān) 512005）

?

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

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

（韶關(guān)學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 韶關(guān) 512005）

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

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

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

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

本文假設(shè)：各個(gè)用戶間在短時(shí)間內(nèi)沒有關(guān)注新的用戶和取消對其他用戶的關(guān)注；用戶在發(fā)布或者轉(zhuǎn)發(fā)微博消息后在短時(shí)間內(nèi)不會(huì)再去刪除此消息；用戶間不存在僵尸粉現(xiàn)象.

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

圖1 有向圖D（V，E）

2　微博最大好友圈的求解

2.1 關(guān)注關(guān)系的矩陣表示

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

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

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

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

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

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

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

著色的顏色ck選擇原則：k為顏色的編號，若ck這種顏色已經(jīng)出現(xiàn)過，則著ck這種顏色的頂點(diǎn)只能落在已著色頂點(diǎn)V的鄰接頂點(diǎn)范圍內(nèi).若在頂點(diǎn)V的鄰接頂點(diǎn)范圍內(nèi)，出現(xiàn)某一鄰接頂點(diǎn)不與已著ck這種顏色的其他鄰接頂點(diǎn)相鄰，則選擇下一種顏色ck+1為該鄰接頂點(diǎn)著色.

Step5 重復(fù)步驟4，直到頂點(diǎn)V的所有鄰接頂點(diǎn)都著色為止.

Step6 回到Step3，找出每個(gè)未著色頂點(diǎn)的Fd和Ud，重復(fù)Step4、Step5，直到所有頂點(diǎn)都已著色為止.這樣就實(shí)現(xiàn)了無向圖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 啟發(fā)式著色算法求解最大完全子圖的求解結(jié)果

根據(jù)啟發(fā)式著色算法求解最大完全子圖的基本步驟，運(yùn)用Matlab編程求解，得到由13個(gè)用戶所構(gòu)成的好友圈為最大好友圈，分別是用戶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　微博消息用戶最少的發(fā)布方案求解

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

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

Step1 讀取文件data2.xls的數(shù)據(jù)，通過Matlab軟件編程，得到消息傳播過程中用戶之間的關(guān)聯(lián)矩陣B .

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

Step3 找出看過消息的用戶.將sj最大的列中的1轉(zhuǎn)化為0，表示sj最大的列對應(yīng)的用戶的粉絲已看過此消息，同時(shí)將sj最大的列對應(yīng)的用戶所對應(yīng)的行中的1也轉(zhuǎn)化為0，表示此用戶已發(fā)布過此消息.至此，得到一個(gè)新的0-1矩陣B .

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

在確保所有用戶都能看到（不考慮轉(zhuǎn)發(fā)）的條件下，得到發(fā)布某消息的用戶數(shù)最少的發(fā)布方案.該方案需要251個(gè)用戶發(fā)布此消息，具體結(jié)果省略.

4　結(jié)束語

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

針對消息發(fā)布用戶進(jìn)行最優(yōu)化，通過將問題轉(zhuǎn)化為有向圖的頂點(diǎn)支配問題，列出相關(guān)的0-1矩陣，基于有向圖的最小支配集的優(yōu)化算法尋找最優(yōu)方案.本文在新聞傳播、信息推薦、民意調(diào)查、電子商務(wù)、網(wǎng)絡(luò)營銷或網(wǎng)絡(luò)代購等領(lǐng)域有一定的借鑒作用和應(yīng)用價(jià)值.

參考文獻(xiàn)：

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

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

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

［4］徐俊明.圖論及其應(yīng)用［M］.合肥：中國科學(xué)技術(shù)大學(xué)出版社，1998

［5］王桂平，王衍，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用［M］.北京：北京大學(xué)出版社，2011

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

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

［8］高文宇.有向圖連通支配集求解算法［J］.計(jì)算機(jī)工程與應(yīng)用，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

文獻(xiàn)標(biāo)識碼：A

doi：10.3969/j.issn.1007-9831.2016.05.005

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

收稿日期：2016-03-01

基金項(xiàng)目：2015年度廣東大學(xué)生科技創(chuàng)新培育專項(xiàng)資金項(xiàng)目（團(tuán)粵聯(lián)發(fā)［2015］50號，pdjh2015b0477）；2014年廣東省本科高校教學(xué)質(zhì)量與教學(xué)改革工程項(xiàng)目（粵教高函［2014］97號）

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

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