鄭 巍，鄧宇凡，潘 倩

(南昌航空大學(xué) 軟件學(xué)院，江西 南昌330063)

0 引 言

社交網(wǎng)絡(luò)是一個信息交流的開放平臺，國內(nèi)外盛行的社交網(wǎng)絡(luò)包括Facebook，Twitter，Google+和新浪微博等都擁有著成千上萬的用戶。目前，有關(guān)社交網(wǎng)絡(luò)的研究很多，其中，有動機調(diào)查［1］、社區(qū)分析［2］、推薦系統(tǒng)［3］、微博和用戶排名［4］以及高質(zhì)量的數(shù)據(jù)挖掘［5］等。

社交網(wǎng)絡(luò)中的行為預(yù)測和解釋是社交網(wǎng)絡(luò)研究的熱點內(nèi)容［6］。社交網(wǎng)絡(luò)的分形結(jié)構(gòu)研究是社交網(wǎng)絡(luò)的一種重要的結(jié)構(gòu)特征，對網(wǎng)絡(luò)行為的預(yù)測和解釋有著重要的意義［7］，社交網(wǎng)絡(luò)的分形結(jié)構(gòu)體現(xiàn)了網(wǎng)絡(luò)整體與局部間具有相似的關(guān)系，一般用分形維度來度量分形結(jié)構(gòu)［8］。

Song C 等人提出了一種改進盒子定義的方法即緊湊盒子燃燒(compact box burning，CBB)算法來計算網(wǎng)絡(luò)的分形維度，并利用該方法確認了網(wǎng)絡(luò)的自相似性［9］。之后，文獻［10］又提出了貪婪圖著色算法和最大排除質(zhì)量燃燒(maximum excluded mass burning，MEMB)算法來獲得更低的網(wǎng)絡(luò)分形維度。Schneidev C M 等人提出了一種基于模擬退火的盒子計數(shù)法［11］，Sun Yuanyuan 等人還提出了重疊盒子的覆蓋算法進一步優(yōu)化了原始的盒子覆蓋算法［12］。

但是以上方法都沒有考慮到網(wǎng)絡(luò)同配性和異配性對分形結(jié)構(gòu)的影響。研究表明，分形結(jié)構(gòu)明顯的網(wǎng)絡(luò)具有異配性［13］，社團結(jié)構(gòu)明顯的網(wǎng)絡(luò)具有同配性，在表現(xiàn)出分形結(jié)構(gòu)的網(wǎng)絡(luò)當中通常都具有較小的模塊度。因此，本文提出了基于模塊度增量構(gòu)造緊湊盒子(box compact based on modularity，BCM)的算法，該方法利用最小模塊度增量來構(gòu)建盒子并計算分形維度。仿真實驗表明:BCM 比CBB 得到更為精準的分形維度。

1 算法設(shè)計

1.1 模塊度定義

定義 一個無向圖G=(N，E)來描述社交網(wǎng)絡(luò)，其中，N=(1，2，...，n)表示所有節(jié)點的集合，E=(1，2，...，m)表示所有邊的集合。模塊度Q 的定義［14］如下

其中，A 為網(wǎng)絡(luò)的鄰接矩陣，ci為頂點i 的所在模塊的序號，δ(m，n)為克羅內(nèi)克δ 函數(shù)，若m 和n 在同一個模塊，則δ(m，n)=1，ki為節(jié)點i 的度。為了描述網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的變化，模塊度增量［15］定義如下

1.2 詳細設(shè)計

在CBB 算法中，采用隨機選擇的方法選擇節(jié)點加入盒子，該隨機選擇的方式會破壞網(wǎng)絡(luò)的整體結(jié)構(gòu)，使得需要更多的盒子才能覆蓋整個網(wǎng)絡(luò)，導(dǎo)致得到的分形維度較大，且不能保證節(jié)點的連通性。

針對以上方法的缺陷，本文提出了BCM 算法。該算法的具體步驟如下:

1)構(gòu)造空盒，構(gòu)建集合C 包含所有的未覆蓋節(jié)點，在C中選出度最大的節(jié)點i，作為中心節(jié)點加入盒子，并標記為已覆蓋，從C 中移出。

2)在C 中移除到中心節(jié)點距離大于lb的節(jié)點。

3)在C 中選擇與中心節(jié)點合并后模塊度增量最小的點j(按照式(2)進行選取)，將其作為中心節(jié)點加入盒子，并標記為已覆蓋，從C 中移出。

4)重復(fù)步驟(2)，(3)直到C 為空。

5)如果還有未覆蓋節(jié)點，重復(fù)步驟(1)～(4)。

圖1 演示了BCM 算法構(gòu)造盒子的過程。在圖1 中，有6 個節(jié)點，且lb=3，圖1(a)中所有的節(jié)點都為候選節(jié)點并且未覆蓋;(b)其中網(wǎng)絡(luò)中度最大的節(jié)點作為中心節(jié)點，構(gòu)造新的盒子;(c)，(d)將距離小于邊長的節(jié)點作為候選節(jié)點，從中選出與中心點合并后使得模塊度增量最小的點為下一個中心節(jié)點，標記為已覆蓋并將與中心節(jié)點距離大于等于邊長的點移出盒子;(e)直到?jīng)]有候選節(jié)點，將此輪盒子已覆蓋節(jié)點保存;(f)將盒外節(jié)點作為新的候選節(jié)點重新進行盒覆蓋。最終可用2 個盒子覆蓋此模擬網(wǎng)絡(luò)。

2 仿真實驗

本文采用Matlab 8.0 軟件進行仿真，選取5 個典型社交網(wǎng)絡(luò)進行分析:Zachary’s karate club，Dolphins social network，American college football，Books about US politics，E.coli。

如圖2 ～圖6 所示，對以上網(wǎng)絡(luò)分別用兩種方法進行了1000 次仿真實驗結(jié)果均符合冪律分布，呈現(xiàn)顯著分形特征，本文提出BCM 算法的曲線斜率更小，計算得到的分形維度更加符合實際情況。在CBB 算法中，由于沒有到考慮同配性與異配性對網(wǎng)絡(luò)的影響，機械地對網(wǎng)絡(luò)中的節(jié)點進行分割，破壞了網(wǎng)絡(luò)的原始結(jié)構(gòu)特征，使得需要覆蓋網(wǎng)絡(luò)的盒子數(shù)量增加，從而計算得到的分形維度的結(jié)果偏大。BCM 利用最小模塊度增量作為標度對節(jié)點進行覆蓋保留了分形結(jié)構(gòu)具有異配性這一特征。

圖1 基于模塊度的盒子構(gòu)造策略Fig 1 Strategy of box construction based on modularity

圖2 Zclub 網(wǎng)絡(luò)的分形維度Fig 2 Fractal dimension of Zclub network

圖3 Dolphin 網(wǎng)絡(luò)的分形維度Fig 3 Fractal dimension of Dolphin network

圖4 Book 網(wǎng)絡(luò)的分形維度Fig 4 Fractal dimension of Book network

圖5 Football 網(wǎng)絡(luò)的分形維度Fig 5 Fractal dimension of Football network

圖6 E.coli 網(wǎng)絡(luò)的分形維度Fig 6 Fractal dimension of E.coli network

將BCM 算法與CBB 和MEMB 算法進行比較，從表1可看出:BCM 算法得出的分形維度值最小。因為BCM 算法從網(wǎng)絡(luò)的整體結(jié)構(gòu)考慮，網(wǎng)絡(luò)的異配性越強，其模塊度越小，BCM 算法基于模塊度最小的原則構(gòu)造盒子，能夠消除節(jié)點選擇的不確定性，得到最小盒子數(shù)，其結(jié)果不僅能保證網(wǎng)絡(luò)的連通性，而且取得了更加精確的分形維度。

表1 不同盒數(shù)法下的網(wǎng)絡(luò)分形維度Tab 1 Fractal dimension on different box-covering algorithm

3 結(jié) 論

利用盒子計數(shù)法對網(wǎng)絡(luò)進行分形維度的計算，本質(zhì)是在改變盒子邊長時，盡可能用最少的盒子數(shù)量對網(wǎng)絡(luò)中的節(jié)點進行覆蓋。本文提出了一種基于模塊度的社交網(wǎng)絡(luò)分形維度的計算方法。不同于傳統(tǒng)盒數(shù)法對節(jié)點的隨機選擇，本文方法考慮了網(wǎng)絡(luò)分形特征與異配性的關(guān)系，利用模塊度最小的原則對節(jié)點進行選擇，最大程度地保留了網(wǎng)絡(luò)結(jié)構(gòu)的完整性，并通過仿真實驗驗證了算法的有效性。

［1］ Park S，Hong K－EM，Park E J，et al.The association between problematic Internet use and depression，suicidal ideation and bipolar disorder symptoms in Korean adolescents［J］.Australian and New Zealand Journal of Psychiatry，2013，47(2):153－159.

［2］ Li Shenghong，Lou Hao，Jiang Wen，et al.Detecting community structure via synchronous label propagation［J］.Neurocomputing，2015，151(3):1063－1075.

［3］ Hossein Tabari，Mark E Grismer，Trajkovic S.Comparative analysis of 31 reference evapotranspiration methods under humid conditions［J］.Irrigation Science，2013，31(2):107－117.

［4］ Chen Wenlong，Cheng Shaoyin，He Xing，et al.InfluenceRank:An efficient social influence measurement for millions of users in microblog［C］∥Proceedings of the 2012 Second International Conference on Cloud and Green Computing:IEEE Computer Society，2012:563 －570.

［5］ Liu Yang，Wu Bin，Wang Hongxu，et al.BPGM:A big graph mining tool［J］.Journal of Tsinghua University:Science and Technology，2014，19(1):33－38.

［6］ Schall D.Link prediction in directed social networks［J］.Social Network Analysis and Mining，2014，1:1－14.

［7］ Kuang Li，Zheng Bojin.A fractal and scale－free model of complex networks with hub attraction behaviors［J］.Science China Information Sciences，2010，53:1－18.

［8］ Liu H，Lu J，Lü J，et al.Structure identification of uncertain general complex dynamical networks with time delay［J］.Automatica，2009，45:1799－1807.

［9］ Song C，Havlin S，Makse H A.Self－similarity of complex networks［J］.Nature，2005，433:392－395.

［10］Song C，Lazaros K G，Havlin H A.How to calculate the fractal dimension of a complex network:The box covering algorithm［J］.Journal of Statistical Mechanics:Theory and Experiment，2007，2007(3):1742－5468.

［11］Schneider C M，Kesselring T A，Andrade J S Jr，et al.Boxcovering algorithm for fractal dimension of complex networks［J］.Physical Review E，2012，86(1):3461－3463.

［12］Sun Yuanyuan.Overlapping box covering method for the fractal dimension of complex networks［J］.Physical Review E，2014，89:1－7.

［13］Song C，Havlin S，Makse H.Origins of fractality in the growth of complex networks［J］.Nat Phys，2006，2:275－281.

［14］Newman M E J，Girvan M.Finding and evaluating community structure in networks［J］.Physical Review E，2004，69(2):292－313.

［15］Newman M E.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69(6):279－307.