当前位置:   article > 正文

影响力最大化算法:AOGC:一种基于自适应截断半径和全信道路径的改进重力中心性方法,用于识别复杂网络中的关键节点

aogc

0.说明

新人第二篇博客,宣我的点点关注不迷路,研究方向为社交网络分析-影响力最大化。

1.简介

Chaos, Solitons and Fractals的一篇文章,doi:10.1016/j.chaos.2022.112974。title:《AOGC: An improved gravity centrality based on an adaptive truncation radius and omni-channel paths for identifying key nodes in complex networks》

该论文的灵感来源于万有引力公式,F=G*\frac{M*m}{r^{2}},两节点之间的引力值本文定义为:相对应的带进去,很好理解。

2.计算

该算法主要分为三步进行

2.1计算节点质量

作者定义节点质量为 Neighborhood Structure-based Centrality 邻居结构中心性,简称NSC值,NSC值的计算如下:

其中,H(v_p)就是节点的H-index值,很好算。ks(v_p)就是节点的kshell值,<H>是网络所有节点的H-index平均值,<ks>是网络中所有结点的ks 平均值。为了简便计算,简化为:

其中,\mu=\frac{<H>}{<ks>} 

2.2计算节点间的相对距离

为了方便理解,先定义一个L_{max},定义如下:

其中,<d>是平均度,大\theta=6 。

然后,定义了一个Dynamic Quasi-local Similarity 动态局部相似性来计算节点间的距离,也就是半径。DQS定义如下:

其中,\sigma \in (0,1),作者在本文并没有说明sigma的具体值,(A^l)_{pq}表示节点p和q之间路径长度为l的路径数量。放心,networkx包里的 nx.all_simple_paths 方法能算出两个节点之间的所有路径, 然后在给个l参数,就可以算出来了。

最后,就可以计算节点之间的距离了,作者定义为松动距离 Looseness Distance,定义如下:

简简单单,不多说。 

2.3计算节点在网络中所受到的引力或重力和

2.3.1计算两个节点之间的吸引系数

这个做法我记得适合KSGC一样的。

2.3.2计算两个节点之间的引力

,把上面计算的带进去就行

2.3.3 节点节点在网络中受到的引力和

节点在网络中收到的所有力,就可以算出来了,这个也就是节点的AOGC值。

3.代码复现

由于作者没给sigma的值,只知道是0到1的数。跑了一个Jazz数据集,不得不说,时间复杂度巨大。

我用的sigma=0.0009。耗时接近五分钟。

4.总结

时间复杂度太高,然后对比了一下其他算法,效果也不好,作者别打我。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/773892
推荐阅读
相关标签
  

闽ICP备14008679号