基于DynamicRank的重要节点集挖掘算法

为了更为有效地挖掘复杂网络中综合影响力高的节点集、提高重要节点集挖掘算法的准确性,针对节点集中各节点在信息传播中不同程度的相互促进和相互抑制作用,基于DynamicRank算法设计了一种新的级联概率计算模型。通过增强贪心策略,优先从种子集邻居以外的节点中选取备选节点,减小种子集内重叠邻居对信息传播引发的抑制作用;利用级联概率计算模型,增强种子集对信息传播的级联促进作用。在4个实际网络上采用SIR模型进行了测试,实验结果表明,相较于已有重要节点挖掘方法H-index、Degree、DynamicRank、VoteRank和EnRenew,提出的算法挖掘出的节点集具有更高影响力。特别地,在Grid数据集上,本文方法挖掘出的种子集的传播范围比对比算法平均提升了49.3%。提出的算法针对信息传播概率和贪心策略的改进有利于重要节点集的挖掘和识别。     

基于电阻网络的节点重要性判别

节点中心性是复杂网络研究的关键问题之一.我们从电阻网络出发,基于基尔霍夫电流定律,定义了一种新的中心性指标KL(G),该指标由通过节点的电流和基于度的电流方差构成.这个指标在网络流的基础上考虑了网络的全局信息和节点所处位置的局部信息.我们将指标应用于实际网络中,发现其可以识别出对于社团结构来说重要的节点,结合辅助指标w还可以区分社团重叠节点和桥节点.     

基于单步添加团的重叠社团检测算法

基于局部扩充的重叠社团检测算法由单个节点或团出发,不断添加新的节点而获得最终的社团划分,但现有算法均为每次添加一个节点,没有充分考虑所添加节点的局部信息,从而影响了社团检测结果的准确性.为此,文中提出了一种基于单步添加团的重叠社团检测算法,该算法从一个团开始,通过不断添加此团邻居内适应度增值最大的团,使算法在局部扩充时不仅考虑了所添加节点与已有社团的连接紧密性,而且考虑了所添加节点内部的连接情况.在真实网络和计算机生成网络上的实验结果表明,与现有基于局部扩充的重叠社团检测算法相比,文中算法可以更准确地检测出复杂网络中的重叠社团.     

一种基于极大完全图扩展的社区挖掘算法

社区挖掘是复杂网络分析中一项重要工作.目前已有许多好的社区挖掘算法,但这些算法大多基于节点间的连接关系发现内聚的社会团体,而实际网络中节点大多具有不同的行为和影响力.基于此,充分考虑社区内节点相互连接紧密以及节点具有不同影响力的特性,提出一种基于极大完全图扩展的社区挖掘两阶段算法.第一阶段:从内聚的子团和度中心性节点的影响力出发,从网络中选取分散的k个内聚的且有影响力的极大完全图作为初始社区;第二阶段,基于局部社区模块度扩展方法,将重叠节点和初始社区外节点扩展到与其连接紧密的相应社区内.最后通过仿真实验验证了该算法的有效性.     

基于二步邻居拓扑的E-Burt结构洞检测算法

连接多个不同社团的节点称为结构洞节点,部分已有的结构洞节点检测方法虽然可以检测到关键节点,但存在一些不足:基于局部的测量方法忽略了网络拓扑结构;对于大规模复杂的网络来说,基于全局的测量方法可扩展性差,等等。为了高效准确地检测社会网络中具有影响力的节点,提出了一种新的结构洞度量方法E-Burt,用来寻找结构洞节点。该方法利用节点与其二步邻居构成的拓扑关系来计算节点的有效规模,用该结果作为结构洞节点重要性的评价指标,计算每个节点的结构洞度量值,并给出了形式化定义。E-B算法基于网络拓扑结构,每次模拟迭代将选中的结构洞节点度量值置为零,下一次迭代只计算该节点二步邻居的有效规模,大大降低了时间复杂度。最后通过实验验证了算法的时间效率,分析了算法的精确度,对算法的正确性进行了证明,并与存在的经典结构洞发现算法进行了对比。     

基于局部稠密度的社团划分算法

社团划分是研究复杂网络结构与功能之间关系的基础,提出了一种基于局部稠密度的社团划分算法。算法首先计算网络中节点的局域密度,从局域密度最大的节点v开始,找出以节点v及其邻居如果αlocal(vi)≥γin则将其设为初始社团S。首次定义了节点的入团率β,并且使用整体和单个入团的方式将节点加入到初始社团中,直到αlocalγout时算法停止。然后再使用内部连接P来检测社团划分的效果,并将错误划分的节点重新归类。把这个算法用在三个社会网络中,都得到了正确的划分。并用MATLAB仿真结果表明:划分出的社团内部连接相当紧密,从而达到了内部连接紧外部连接稀疏的划分社团的要求。此算法不需要计算模块度,在找到初始社团后,并不需要对整个网络的所有节点进行计算,只需计算其一阶邻居节点。这样算法所占用时间少,结果精确率高。     

网络社团结构对路由策略的影响

研究了网络社团结构对路由策略的影响,通过实验发现具有模糊社团结构网络的路由效率要比具有清晰社团结构网络的路由效率更高,由此提出了两种基于网络社团结构信息的局部路由策略,并与没有利用社团信息的路由策略进行了对比,发现为节点提供网络社团信息能够帮助节点更加有效地进行路由.     

非稳态拓扑下的机会网络分层模型

为了解决在消息敏感的机会网络中社团划分结果不可重用的问题,提出了一种与消息类型相匹配的机会网络分层模型.首先,将机会网络的物理节点集映射为与消息类型匹配的虚拟节点集,并以此为基础建立虚拟机会网络层;然后,在虚拟机会网络层上,建立虚拟节点集的社会关系;最后,对虚拟节点集的社会关系进行社团划分.实验结果表明:在消息数量相同的条件下,当消息序列中相邻位置消息的类型差异度分别为40%和100%时,在虚拟层上进行社团划分的时间与在物理机会网络上直接进行社团划分的时间相比分别减少约58%和89%;基于分层模型的社团划分的运行次数仅依赖于消息类型的数量,而不会随消息数量或消息序列中不同类型消息交错方式的变化而变化.     

一种基于核心节点扩展的社区挖掘算法

在充分考虑网络中节点间的连接关系和节点的影响力的基础上,提出一种基于核心节点扩展的社区挖掘算法。算法分为三个阶段:首先,网络中的前k个核心节点逐层向外扩展,直至覆盖网络中大部分节点,各核心节点与其多层邻居节点组成候选初始社区;然后,对候选初始社区进行重叠处理,计算候选初始社区两两之间的重叠度,将重叠度高于阈值的两个社区中相对小的社区删掉,形成初始社区;最后,计算初始社区间的重叠节点和不在初始社区中的节点到各个初始社区的连接度,将连接度最大的节点加入相应社区,不断迭代,直到网络中所有节点都划入到相应社区内,形成最终社区结构。试验结果说明了本文方法的有效性和灵活性,相比GN算法和FN算法,能够实现准确的网络划分;相比Hub算法和Top Leaders算法,由于对候选初始社区间进行了重叠处理,对预置的社区数量k在一定范围内不敏感。     

一种信任关系网络中的社团结构检测算法

针对群智计算和感知服务中不可信服务节点可能引入的安全威胁问题,提出了一种基于节点间信任关系网络的社团结构检测算法。该算法通过分析信任关系网络的功能和结构特点,引入连接的方向和权值因素,建立有向加权网络模型,定义最优路径相似度作为节点聚合标准,提出社团离散指数作为评价函数控制检测过程,从而准确识别信任关系网络中的可信节点集合,为服务节点选择提供参考。算法引入节点相似度阈值和归属判定指数控制社团聚合,与误分类节点再筛选环节配合,有效降低了检测过程中的节点误判概率,有针对性地设计社团离散指数作为评价函数,动态评估检测结果并调节聚合参数,保证了社团结构检测结果的准确率及合理性。实验结果表明:该算法能够有效实现信任关系网络中社团结构的检测与识别,与已有算法相比,检测准确率提高了5.88%。