您当前的位置:悬赏问答

2017-11-12 08:46

作业八:什么是快速算法? 10

如题,在复杂网络社团划分中,什么是快速算法?有哪些使用情况?

提问者采纳

2017-11-12 08:46

复杂网络理论及其应用P184

GN算法虽然准确度比较高,分析社团结构的效果比原有的一些算法也要好,但是它的算法复杂度比较大,仅局限于研究中等规模的复杂网络。现在对于Internet、WWW和电子邮件网络等的研究越来越多,而这些网络通常都包含百万级以上的节点。在这种情况下,传统的GN算法就不能满足需求。基于这个原因,Newman在GN算法的基础上提出了一种快速算法Fast algorithm for detecting community structure in networks,其可以用于分析节点数叨叨100万的复杂网络。

这种快速算法实际上是基于贪婪算法的一种凝聚算法,算法如下:

1.初始化网络为n个社团,即每个节点就是一个独立社团。初始的eij和ai满足

其中,ki为系欸但i的度;m为网络中的总的边数。

2.依次合并有边相连的社团对,并计算合并后的模块度增量

Q=eij+eji-2aiaj=2(eij-aiaj)根据贪心算法的原理,每次合并之后应该沿着使Q增大最多或者减少最小的方向进行。

3.重复执行步骤2,不断合并社团,直到整个网络都合并成一个社团,此时最多执行n-1次合并

整个算法完成之后可以得到一个社团结构分解的树状图。再通过不同位置段卡可以得到不同的网络社团结构。在这些社团结构中,选择一个对应着局部最大Q值的,就得到最好的网络社团结构。如利用空手道数据集分析的结果如下

由Newman快速算法可得,当网络被分为两个大小都为17的子网络时,Q有最大值,图中利用不同的形状表示其所属的社团,可见只有一个节点10没有被正确的划分到它所属的书团。实际上,GN算法中同样有一个节点3没有被正确归类。但是,时间上已经有了很大改善。

其他 0 条回答




登录 后查看个人信息