基于模块度的社交网络分形维度计算方法*

郑 巍，邓宇凡，潘 倩

(南昌航空大学 软件学院，江西 南昌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.