论文研究-基于节点属性的社群结构探测算法改进.pdf

所需积分/C币:10 2019-09-20 18:05:54 635KB .PDF
收藏 收藏
举报

论文研究-基于节点属性的社群结构探测算法改进.pdf,  对Vincent D. Blondel等提出的B算法的特点及机理进行了分析, 讨论了节点属性对社群结构探测的可能影响. 进而通过重构初始化网络, 控制节点(社群)合并过程两个方面, 对B算法进行了改进, 获得更优的模块性指标及对应的社群划分. 经计算机模拟网络与实际网络的社群结构探测, 结果表明所提改进算法有效可用, 能在获得较大模块
第11期 张锴琦,等:基于节点属性的社群结构探测算法改进 2881 间复杂度取决于网终规模η;而随着迭代次数的增多,网络规模会成指数趋势缩小,这使得B算法快速探测 大规模网络结枃成为可能.此外,B算法的运算过程能够清晰地展示社群探测的层次结构,为社群结枃特征 的进一步分析与研究提供一定的支持 B算法作为一种社群探测算法,其本质是将同属性节点归并到合适社群,对网络结构进行重新表达的过 程;但同时作为一种模块性优化算法,其社群合并过程却又仅通过节点度值控制完成,忽略了其他节点信息 因此,在实际网络探测过程中,单纯依靠模块性指标作为社群合并标准将使得求解过程面临诸多的不确定性. 以图1中表示的网络结构为例,虽然节点A与节点B其度值相同,但其所处的社群结构位置不尽相同: 如果完仝忽略其他节点属性,单纯依靠模块性指标变化来判断此类节点(社群)的归属,将可能导致社群归并 的失效从而引起社群探测结果的不确定.因此,为了清晰表达社群结构的特征,有效区别节点度值属性相同 的节点(社群),有必要在社群判断归并的过程中引入相关节点属性等先验知识作为补充因而,本文试图在 B算法中引入节点属性特征等先验知识,探索一种貝有正改进效果的基于节点属性的网络结构表达方式,进 而针对B算法提出一种改进型的优化策略 3基于节点属性的算法改进 本文从社群结构探测本质是网络结构重新表达这一基本思路出发,综合节点相关属性与B算法的设计 特点,探素节点属生与社群位置的关系特征.进而实现对B算法的改进. 网络无标度特征表眀度債越大的节点,其居于网络中心的可能性越大.然而如图2所示,虽然节点A的 度值大于节点B的度值,但其社群结构特征并不如节点B凊晰.因此,单纯依靠节点度值分布并不能确定节 点在社群的中心位置 C2 图1社群节点关系示意图 图2网络节点度值分布示意图 社群结构特征物理意义上的社群内部联系稠密,可以 解释为社群内的节点间总是通过较少的边进行联系,亦可 理解为节点间逻辑上的相邻”,而如果一个节点完全与其 他社群内节点存在这种关系,则其应完全位于社群之中,理 论上接近社群的中心位置.以图1为例,节点A与社群内 其他节点都具有直接的相邻关系,而这一属性是节点B所 不具备的,因而虽然两个节点度值属性一致,但节点A与节 点B相比更可能位于社群的中心.一般而言,在节点邻接 关系存在的基础上,节点共有的邻接节点集可以衡量了邻 接关系的“亲密”程度.如图3所示,节点C与节点D直 接相邻外,还通过节点a联系,随着这种联系的不断增多 C-D间的联系更为紧密,也更为邻近.因此,节点间共有邻 接节点集的大小成为衡量节点间联系密切程度的指标 图3节点密切关系示意图 为了方便计算节点间的邻接节点集的大小,本文以节点连接边为底的三角形数量来度量,即节点间三角 形的数量表明其邻接关系的密集程度.而对于每一个节点而言,与其相连的三角形数量则反映了其总体上与 其他节点关系的密集程度,即“相郐”程度.“相邻”程度越高,节点越可能居于社群的中心.因此,在消除节 2882 系统工程理论与实践 第33卷 点度值规模影响的前提下,节点居于社群中心位置的特征属性可以定义为 2E2 式中F表示节点相连的三角形数量,k(k-1)表示节点相连的三元组数量.公式(2)与节点聚类系数的定 义相同,而聚类系数的定义反映的是节点“吸附”其他节点的聚类能力,显然‘吸附”能力越强的节点越可能 位于社群中心.传统的聚类系数概念大多用于描述网络的凝聚程度而很少用于描述节点的相对位置.以上的 推论则在一定程度上拓宽了聚类系数的应用的范围,丰富了其应用意义 基于这一节点特征,本文对B算法的改进策略分为以下两个部分:其一是对B算法初始网络的重新划 分;其二是对B算法合并过程的控制.具体地,在B算法中首先基于节点聚类系数获得一个初始的网络结构, 即将居于社群中心的节点先确定为独立社群;然后沿用B算法的设计理念,对与之相邻的,相对位于社群边 缘的节点逃行合并;并且在合并过程引入以下节点筛选机制 对公式(1)化简可得: △Q k∑ 式中模块性增益效果△Q与k;mn正相关,与节点度k;负相关;而根据 Raddicclii等对强社群-弱社群 的定义.对于社群C中的任意节点i,如果满足 ki(c)> ki(c 即当社群内任意节点与社群内部节点连接比与社群外部的节点连接要紧密时,则称社群C为该网络的强社 群结构.而 kin (c)t ho(c)= ki 因此.当节点满足 k:(C) 6 即可认为节点是位于社群之中的,且α值越大节点并入社群对模块性增益影响越大.以上推论为B算法中 节点的筛选提供了一种节点优选机制,一定程度上消除节点合并过程的不确定性,同时可以先验性地剔除不 符合条件节点,提高算法的运行效率 基于以上改进思路,本文给出一种基于节点属性特征的改进型B算法,记为K算法,其步骤可以描述如 第一阶段 step1计算网络节点的聚类系数,并按聚类系数对网络进行排序调整; Step2设初始网络中每个节点作为一个社群结构进行计算; Stepυ3选择节点讠并统计其邻接节点j的集合,并按规则排列节点集合; Step4遍历节点集合,根据ΔQ增益情况,合并节点; Step5判断是否遍历结束,未结束重复步骤24;结束开始下一阶段: 第二阶段 Step1根据第一阶段的结果,将合并的节点作为一个新的节点(社群),新节点(社群)间的杖重是原节 点联系权重之和 Step2计算新节点(社群)内原节点的权重和,作为新节点(社群)的自身权重;输出新网络,重新开始 第一阶段 判断所探测结构是否稳定,结束算法 K算法在合并节点的过程中与B算法过程相反;B算法是以社群作为合并目标,通过节点选择不同的社 群完成该过程;而K算法山于考虑到节点属性的影响,这一过程是通过社群选择邻接节点完成.K算法引入 的这种较为简单的改进思路,将原始无序的网络结构按照节点属性特征提供的先验知识进行了重新表达;在 合并过程中,K算法加入一种基于节点属性筛选机制,一定程度上消除了合并顺序对探测结果的影响.在时 间复杂度方面,引入聚类系数计算其时间复杂度为O(mm)(n是网络规模、m是最大的邻接节点集的规模) 节点筛选机制的时间复杂度为αη)(π是网络规模,l是符合公式(6)的最大节点集数目,l<π),因此总体 上K算法与B算法的时间复杂度相仿. 第11期 张锴琦,等:基于节点属性的社群结构探测算法改进 2883 4实验与结果讨论 本文实验利用两组数据对K算法的有效性与可用性进行检验,其一为已知社群结构的计算机生成基准 网络数据,其二为实际网络数据、通过两组数据就B算法与K算法探测结果及算法计算时间等特征的相 关差异进行对比分析,并对个别特殊结果进行集中讨论.实验均在 Intel( R)Core(TM2 Quad CPu Q8400 2.66GHz的PC机上用 Matlab70实现测试 41计算机生成数据 本文采用的基准网络结构是由 Lancichinetti等19设计的计算机模拟网络结构.该网终包含128个节 点,4个社群,每个节点平均的度值为16;并通过μ来分配节点社群内连接与社群外连接,即: 其定义与本文公式(6)相似,当μ<0.5时节点社群内邻接节点多于社群外邻接节点.本文实验采用NMI ( normalized mutual information)指数2来衡量K算法对于社群结构划分的改进效果其公式表示为 I(A, B) 2∑:=1∑7=1Ni;log(MN/NNj) g(N/N)+∑ CB I Nj log(Ni/N) 式中A,B表示需要比较的两种社群探测结果,cA、cB分别表示不同结果中社群数量,Nz是探测结果A的 社群与探测结果B的社群j含有的共同节点数量,N(N)则是上述数量在社群(社群y)中的节点总 数,N表示整个网络节点总数.NMI指数是比较探测社群结构与实际社群结构差异的评价指标;NM指数 越接近1,探测社群结构与实际社群结构越相似,反之差异越大.实验数据由9组不同的计算机生成数据组 成,的取值范围为0到0.5;为了消除随机性差异,每个μ对应的NMI指数通过6次独立计算的平均生成; 其实验结果如图4所示 算法 a-算法 图4模拟数据实验对比效果 实验结果表明,当μ值较小(μ≤0.25),社群结构比较清晰时,B算法与K算法都能获得与实际结果相 同的探测结果(NMI等于1);随着μ值的増大社群结构开始模糊,当μ>0.31时,两种算法开始岀现明显差 异,但K算法始终较B算法拥有较大的NMI值.因此,K算法所划分的社群结构相对B算法的划分结果更 接近真实的网络社群结构 42实际网络数据 实际网络数据测试包括15组数据,表1出的是相关实际网络的基本特征(其中的非对称0-1网络已 经进行了对称化处理) 测试的对比结果如表2所示,表中B算法与K算法的模块性指标分别使用QB和Qk表示,9ap是用 米表示二者算法的差异性,其定义为 9ap=(QK-Q)/QB)×100% 当g0=0时,表明两种算法没有明显的差异性;当g0>0时表示K算法探测效果更优,反之则改进 B算法效果更优.同时,表2中给出了两种算法的平均CPU时间TB和Tk,用于衡量两种算法的运算速度, S为“+”,表明K算法运算速度优于B算法,反之B算法速度更优 2884 系统工程理论与实践 第33卷 表1测试实际网络结构特征 表2实验测试结果 网络 规模平均度密度来源 网络 Q QK / TB(S) TK(S) 44.58820.139U Za 0.41880.41880 0.11810.07 crn 3272.06120.0063 Pajek Icrn 0.88210.8820.01360.5560.495+ ADF073 2622.04580.0078 Pajek ADFo73 0.88280.87870.46060.30820.302+ bkfart 5820.55170.3606 Ucinet 0.62950.6:3230.44580.06510.072 111 3.4775 0.0316 Pajek bkfart 0.10830.11546.55750.098400683+ BKHAM 444.04550.0941 Pajek BKHAM 0.20480.20570.46250.04840.0327+ BKOFF 406.150.1577 Pajek BKOFF 0.37480.37480 0.03150.0411 653.84620.0601 Pajek 0.57850.58110.4480.05330.0531+ 624.64520.0762 Pajek 0.67260.67770.75290.084500683+ CENPROD1319.60310.0739 Pajek CENPROD0.29650.30151.6890.14970.1276+ celegansneural 297 14.4646 0.0489 I celegansneural0.38760.39411.67540.64230.5076+ GD2001 3114.11580.01332 GD2001 0.62830.63651.30310.46950.3365+ Roget 0221.60080.00162 roget 0.63760.64370.952425.270922.3421+ EVA 30001.1610.00042 EVA 0.91770.91770.00351580704176.6939 P2P 20001.430.00072 P2P 0.68070.68130.0934154.74331289242+ 从表2中结果可以得出,对于表1中73%的网络中K算法都具有优于B算法的搡测效果;14%的网 络二者探测效果一致;从算法运行时间米看,在相同网络规模的情况下,K算法对于67%的网络运算时间都 快于B算法,且都能获得较好的探测结果,因此K算法较B算法而言具有更快的运算速度 在上述的网络结构中,本文所改进的K算法对ADF073网络和1crn两个网络并未产生有效的改进通 过对网络结构的分析,ADF073整个网络结构天然地存在两个大的社群—社群A和社群B(图5) 自然社样 自然社样 图5ADF073网络社群结构图 通过统计分析,K算法对ADF073网络失效的原因可能存在以下几点原因: 1)ADF073网络中并不存在三角形,K算法按照节点聚类系数排序的改进设计思路失效; 2)该网络的平均度值为2,可以认为每个节点都保持了出度与入度相平衡的状态,因而K算法选择邻接 节点的概率也趋于平衡,该部分改进同样失效; 3)从ADF73的网络结构而言,其社群关系相对比较清晰.根据对计算机模拟数据的分析,对于此类网 络,K算法与B算法并没有明显差异; 基于以上分析,可以发现ADF073网络是一个K算法的失效结构.K算法在探测过程中,设计节点属性 的相关特征没有发挥应有的效果;相反,在该失效结构中,设计思路中的节点顺序反而会造成一定的不确定 1.该数据来源于http://www.casos.cs.cmu.edu/computational-tools/datasets/external/ 2.该数据来源于ht:/ snap. stanford. edu/data/ index. html 第11期 张锴琦,等:基于节点属性的社群结构探测算法改进 2885 性,从而导致算法改进的失效.lcrn网络其结构也不冇在三角形,且网络平均度趋近于2;因此,其失效原因 与ADF073网络相同,此处不再详细分析 5结论与展望 B算法是一种针对大型网络有效的社群结杓探测策略,其通过模块性指标的增益值变化,压缩网络中的 节点并凝聚成相应的社群,不断缩小网络规模,从丽达到快速探测网络社群结构的效果.本文在B算法的基 础上引入了节点的属性特征,从节点的度值分析出发,将节点的聚类系数引申为节点社群中心位置的参照指 标,并对网络结构的初始重新表达;通过重新排序,改进的B算法的算法过程即成为先确定社群中心节点再 合并压缩周围相对边缘节点的探测过程;同时,从B算法的合并机理出发,节点的度值比例关系能够直观地 判断节点与合并社群内的关系程度;并且这种关系亲密程度还能在社群合并的过程中剔除部分节点,提高算 法效率.基于以上改进思路,本文提出的基于节点属性的改进型B算法(即K算法),在继承B算法的算法 设计思想的同时,突出∫节点属性对社群探测结果的影响;同时,算法理论上优化∫B算法的探测结果,提 高了B算法的运算速度,且改进思路简单,便于实现.从两种算法的对比实验结果而言,对于一般0-1对称网 络,K算法相比B算法能够得到更优的模块性指标与探测结果且具有更快的探测速度 通过对B算法的改进探索发现,节点属性对于社群结构的探测存在着不可忽视的影响,这种影响尤其表 现在节点在社群结构中的相对位置的差异性上.而根据本文的研究,节点的聚类系数可能反映了节点在社群 中的位置这一属性,相对于节点中心性而言,其补充了中心性对社群中心位置的解释,也为社群结构探测算 法的改进提供了新的思路 然而.仅本文的研究还不足以揭示节点属性与社群结构探测的直接关系,如何完善节点属性特征的考察, 进而提出更加有效的改进算法以及节点属性与社群结构特征影响作用成为进一步研究工作的主要内容.以目 前的研究来看,从网络同步性的角度对节点属性特征的考察已经取得了一定的研究成果21-2.通过在网络 同步实验过程中获得的节点关联矩阵,可以对节点属性特征间的相互关系进行归纳,而这些研究成果可以帮 助本文在后续的工作中解释节点属性和社群结构特征之间的联系;从而拓本文K算法的应用沱围和适用 性,为加权网络、动态网络等网络社群结构的探测提供新的方法. 参考文献 1 Newnan MEJ Detecting conmunity structure in networks J. The European Physical Journal B- Condensed Matter and Complex Systems, Springer, 2004, 38(2): 321-330 2 Girvan M, Newman M EJ. Community structure in social and biological networksJ. Proceedings of the National Academy of Sciences of the United States of America, The National Academy of Sciences, 2002, 99(12 ):7821 7826 3 Fortunato S, Barthelemy M. Resolution limit in community detectionJ. Proceedings of the National Academy Sciences,2007,104(1):36-41. 14 Newman ME J, Barabasi A L, Watts D J. The structurc and dynamic of nctworks M]. New Jersey: Princeton University Press, 2006 5 Flake G W, Lawrence S R, Giles C L: et al. Self-organization and identification of Web communities[J]. IEEE Computer,2002,35:6671 6 Adamic L A, Adar E. Friends and neighbors on the Web[J. Social Networks, 2003, 25: 211-230 [7 Zhao M, Zhou C, Li J, et al. Competition between intra-community and inter-community synchronization and relevance in brain cortical networks[J. Physical Review E Statistical, Nonlinear and Soft Matter Physics 2011,84(1-2):016109 8 Chen Y, Li J, Han F, et al. On the cluster consensus of discrete-time multi-agent systemsJ. Systems Control Letters.2011,60(7):517-523 9 Redner S. How popular is your paper? An empirical study of the citation distribution J. European Physics Journal B,1998,4:131-134 [10 Albert R, Jeong H, Barabasi A L Internet: Diameter of the world-wide web J]. Nature, 1999, 401: 130-131 [11 Kapferer B Strategy and transaction in an African factory [M]. Manchester: University of Manchester Press, 1972 [12 Kilduff M, Tsai W. Social networks and organizations[M. London: Sage Publications Ltd, 2003 13 Duda R O, Hart P E, Stork D G. Pattern classification M. New York: John Wiley Sons, InIC, 2001 2886 系统工程理论与实践 第33卷 14杜海峰,蔡萌,袁婷婷,等.社群结构硏究进展与展望冋.浙江社会科学,2011(2):116-122 Du H F, Cai M, YuanT T, et al. Development and prospect of community structureJ. Zhejiang Social Sciences 2011(2):11612 15BrandesU,DellingD,gaErtlerm,etal.Maximizingmodularityishardj/ol.2011-9-15.http:/arxiv.org/ bs /physics / 0608255v2 16 Blondel V D, Guillaumel J L, Lambiotte R, et aL. Fast unfolding of communities in large networks/OL 2011-08-07.http://arxiv.org/abs/0803.0476v2 [17 Fortunato S. Community detection in graphs[J. Physics Reports, Elsevier BV, 2010. 486(35):75 174 18 Radicchi F Castellano C. Cecconi F, et al. Defining and identifying communities in networks Cl// proceedings of the National Academy Sciences of the United States of America, 2004, 101: 26558-2663 19 Lancichinetti A, Fortunato S, Radicchi F Benchmark graphs for testing community detection algorithmsJ/OL 2011-10-131.htp:// arxIv.org/abs/0805.4770v4. 20 Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identificationJ/OL].2011-10-13 http://arxiv.org/abs/cond-mat/0505245v2 21 Lu J, Yu X, Chen G, et al. Characterizing the synchronizability of small-world dynamical networksJ. IEEE Transactions on Circuits and Systems I: Regular, 2004, 51(4):787-796 22 Arenas A, Diaz-Guilera A. Synchronization and modularity in complex networks[J]. The European Physical Journal Special Topics, 2007, 143: 19-25

...展开详情
试读 8P 论文研究-基于节点属性的社群结构探测算法改进.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744207 你的留言是对我莫大的支持
2019-09-20
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于节点属性的社群结构探测算法改进.pdf 10积分/C币 立即下载
1/8
论文研究-基于节点属性的社群结构探测算法改进.pdf第1页
论文研究-基于节点属性的社群结构探测算法改进.pdf第2页

试读结束, 可继续读1页

10积分/C币 立即下载 >