科学网 › 标签 › 社群发现

标签: 社群发现

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

Girvan-Newman社群发现算法: 热度 1 bruisefree 2013-12-17 15:01; 直观来看，在社群内部节点之间相互连接的边密度较大，因此，通过边来识别社群是一种较为直观的社群发现算法。 Girvan-Newman 算法即在该启示下发展而言，如果去除社群之间连接的边，留下的就是社群。对于社群而言，较先去除的边，中心性较低，而中介中心性则较大。因此，逐步去除中介中心性最大的边，直至结束 (Girvan andNewman 2002) 。 Girvan-Newman 算法的详细步骤：（ 1 ）计算网络中所有边的中介中心性；（ 2 ）去除中介中心性最高的边；（ 3 ）重新计算去除边后的网络中所有边的中介中心性；（ 4 ）跳至步骤 2 ，重新计算，直至网络中没有边存在。 Girvan-Newman 算法所得到的结果实质上是网络中节点的树图（ dendrogram ）如下所示：该算法给出了如何去除边得到社群结构。但在得到最终的社群数之前，还有一个问题没有得到解决，即如何确定合适的社群数，使社群划分结果最优。在他们随后的文章 (Newman and Girvan 2004) 中提出了 Modularity Q 的概念，并形成一个更为完整的方法。 Q 值能够体现网络划分为社群后社群结构的质量，该值逼近于 1 ，说明社群结构越明显，该值逼近于 0 则社群结构不明显。对于同一个网络而言，不同算法可能得到的 Q 值不同， Q 值高则代表了该算法较优。利用 Q 值寻找合适的社群数的思路如下：在上面 Girvan-Newman 算法中每去除一次边，则计算一下所得社群结构的 Q 值，寻找到 Q 值最大时的社群数量。一般而言，计算时不可能会在所有去边过程中都计算 Q 值，往往是寻找某一区间的 Q 值，取得局部最大值即可。 Q 一般有 1-2 次局部最大值。在下面的示例图中，当边去除后，社群数量为 4 时，所得 Q 值最大，因此该网络划分为 4 个社群最优。 References: Girvan, M., and Newman, M. E. (2002). Communitystructure in social and biological networks. Proceedings of theNational Academy of Sciences , 99(12), 7821-7826. Newman, M. E. J., and Girvan, M. (2004). Findingand evaluating community structure in networks. Phys Rev E , 69(2),26113.; 个人分类: 复杂网络算法|28820 次阅读|2 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 社群发现

相关帖子

相关日志

关闭安全验证