基于模塊度的社交網絡分形維度計算方法*

鄭 巍，鄧宇凡，潘 倩

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

0 引 言

社交網絡是一個信息交流的開放平臺，國內外盛行的社交網絡包括Facebook，Twitter，Google+和新浪微博等都擁有著成千上萬的用戶。目前，有關社交網絡的研究很多，其中，有動機調查［1］、社區分析［2］、推薦系統［3］、微博和用戶排名［4］以及高質量的數據挖掘［5］等。

社交網絡中的行為預測和解釋是社交網絡研究的熱點內容［6］。社交網絡的分形結構研究是社交網絡的一種重要的結構特征，對網絡行為的預測和解釋有著重要的意義［7］，社交網絡的分形結構體現了網絡整體與局部間具有相似的關系，一般用分形維度來度量分形結構［8］。

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

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

1 算法設計

1.1 模塊度定義

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

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

1.2 詳細設計

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

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

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

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

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

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

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

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

2 仿真實驗

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

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

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

圖2 Zclub 網絡的分形維度Fig 2 Fractal dimension of Zclub network

圖3 Dolphin 網絡的分形維度Fig 3 Fractal dimension of Dolphin network

圖4 Book 網絡的分形維度Fig 4 Fractal dimension of Book network

圖5 Football 網絡的分形維度Fig 5 Fractal dimension of Football network

圖6 E.coli 網絡的分形維度Fig 6 Fractal dimension of E.coli network

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

表1 不同盒數法下的網絡分形維度Tab 1 Fractal dimension on different box-covering algorithm

3 結 論

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

［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.