基于社区的动态网络节点介数中心度更新算法

作者:网站采编
关键词:
摘要：挖掘网络中的重要节点是图分析领域中的基础问题,例如在社交网络中,找到那些影响力大的用户节点可以更有效地实现病毒营销等任务.衡量节点自身重要性的标准有很多,比如点度中心度

挖掘网络中的重要节点是图分析领域中的基础问题,例如在社交网络中,找到那些影响力大的用户节点可以更有效地实现病毒营销等任务.衡量节点自身重要性的标准有很多,比如点度中心度(degree centrality)、接近中心度(closeness centrality)、特征向量中心度(eigenvector centrality)和介数中心度(betweenness centrality)[1]等.其中,节点的介数中心度(betweenness centrality)量化了一个节点作为其他节点之间最短路径上桥梁的能力,刻画出了社会网络中一个用户对于其他用户之间交流的影响能力,是一种非常重要的度量指标.于是,节点介数中心度(本文以下简称为介数中心度)经常被应用于供应链管理、恐怖分子发现和艾滋病网络等诸多领域[2].

近些年来,作为网络图分析领域的一个研究热点,涌现出了一批介数中心度计算的优秀成果[2-8].然而,因为介数中心度的精确计算依赖于图中所有点对间的最短路径,所以其计算效率依然不高.对于介数中心度精确计算任务,目前公认的最快方法在无权图上的时间复杂度为 Ο(mn),在有权图上的时间复杂度为 Ο(mn+n2logn)[3].显然,上述效率无法满足现实生活中的大量需求.例如,在以微博为代表的主流社交网络中,用户关系是不断变化的.网络中一方面持续产生大量新“网红”;另一方面,绝大多数“网红”过一段时间后就人气滑落,甚至消失.这些“网红”节点的重要性往往存在一个急速上升而后又急速下降的过程.如果在网络每次变化时,都重新计算所有节点的介数中心度,那么时间开销显然是巨大的.因此,本文对动态网络中节点介数中心度的更新进行研究,尝试寻找一种快速更新的方法,提高介数中心度精确计算的效率.

除了节点和边,网络图中通常还存在社区的概念.社区[9]是复杂网络的普遍特征,可以认为一个网络是由许多社区组成的.社区本身还没有公认的形式化定义.一般认为,社区就是由一些节点组成的聚合体,其中,同一社区内的节点关系相对密切,而不同社区间的节点关系相对而言比较松散.

社区发现(community detection)对于研究网络的特性具有重要意义.找到那些属于同一社区的相似节点,可以更加细化地进行用户的特征挖掘、喜好推荐等工作.因此,近些年许多学者投入到复杂网络中社区的发现与研究中,并提出了不少社区发现的算法,社区发现的研究成果也被成功应用于好友推荐、个性化商品推荐、蛋白质功能预测、舆情分析与处理等众多领域[10].受社区概念的启发,我们考虑借助社区自身的特性,即社区间、社区内节点的联系,尝试在动态图上快速、精准地进行节点介数中心度的更新计算.

针对前述问题,本文提出一种基于社区的节点介数中心度的快速更新算法,能够有效减少节点介数中心度的计算量,提高节点介数中心度的更新效率.

本文的主要贡献包括:

(1)提出了社区与社区间最短距离集合、社区与节点的最短距离集合的概念,并基于这些概念快速找到图结构变化过程中最短路径改变的点对;

(2)提出了一种基于社区间最短距离集合的节点介数中心度的快速更新算法 CBU(community based node betweenness centrality updating).利用上述概念,只需要计算那些最短路径改变的点对,即可提高节点介数中心度的更新效率;

(3)在真实数据集和合成数据集上进行了大量实验.实验结果表明,本文所提算法具有良好的加速效果.

本文第1节介绍节点介数中心度计算和社区发现领域的相关研究工作.第2节给出CBU算法所用到的基本概念.第3节给出最短路径数量的计算方法和CBU算法的社区过滤策略.第4节提出基于社区的介数中心度更新算法CBU,并分析其时间和空间复杂度.第5节给出实验测试结果及分析.第6节总结全文.

1 相关工作

1.1 介数中心度

介数中心度是网络图中节点中心度度量的一项重要指标,它受图中所有点对的最短路径影响.在图中常用的计算所有点对最短路径的Floyd-Warshall算法的时间复杂度为Ο(n3),这导致基于Floyd-Warshall算法进行节点介数中心度计算的方法时间复杂度均不低于 Ο(n3).显然,这样的计算速度太慢,无法满足动态网络的需求.因此,如何减少介数中心度所依赖的最短路径计算量,从而提高介数中心度的计算效率,也就成为了研究的重点.具体地,有如下两种基本的加速思路:

第1种,减少冗余的计算量.Brandes等人[3]提出了一种基于改进的广度优先搜索和点对依赖的算法,减少了最短路径不必要的计算,使无权图上的时间复杂度降低为 Ο(mn),有权图上的时间复杂度也降为 Ο(mn+n2logn).这也是目前最常用的介数中心度计算方法.然而,Brandes算法本身仍旧依赖于所有点对间最短路径的计算,效率依然有限.如何进一步减小介数中心度对于点对最短路径的依赖性,成为加快介数中心度更新的首要策略.Sariyüce等人[4]提出了一种将图拆分压缩的策略,通过将复杂的网络图拆分成多个简单的子图,并将许多作用等价的节点合并,大大简化原有的网络,从而加快介数中心度的计算.Lee等人[5,6]提出了一种利用无向图中的环路的方法,过滤介数中心度不受边增减操作影响的节点,从而提高了更新效率.

文章来源：《中国社区医师》 网址: http://www.zgsqyszzs.cn/qikandaodu/2021/0419/1437.html

上一篇：学习者社会网络交互情绪表征与学习成效的关系
下一篇：广州市社区老人衰弱情况与社会支持度自我感受