雅乐网

计算机技术、学习成长

数学 » 社团检测 » Modularity计算的C++代码

Modularity计算的C++代码

Modularity的定义和公式推导可以参考Modularity的计算方法——社团检测中模块度计算公式详解 | 雅乐网

使用公式

$$Q = \sum_i{(\frac{e_i}{m} – (\frac{k_{C_i}}{2m})^2)} $$

其中, \(e_i\)表示社团 i 内部的边数,\(k_{C_i}\) 表示社团i内部所有点的度数之和,m表示图中边的个数。

不妨先看一下手动的计算过程:

$$Q = \sum_i{(\frac{e_i}{m} – (\frac{k_{C_i}}{2m})^2)} $$

这个式子的i是要遍历所有的社团,例子中有3个社团,所以,Q就是3个部分的和,每个部分是

$$\frac{e_i}{m} – (\frac{k_{C_i}}{2m})^2$$

上图有23条边,m=23

先来计算社团1,这个社团 内部有5条边 ,所以 \(e_1 = 5\) ,内部结点4个,度数之和是 \(k_{C_1} = 11\),这样求和的第一项就是

$$\frac{e_1}{m} – (\frac{k_{C_1}}{2m})^2 = \frac{5}{23} – (\frac{11}{2*23})^2 = \frac{339}{2116}$$

社团2和3也是这样计算:

$$\frac{e_2}{m} – (\frac{k_{C_2}}{2m})^2 = \frac{7}{23} – (\frac{17}{2*23})^2 = \frac{355}{2116}$$

$$\frac{e_3}{m} – (\frac{k_{C_3}}{2m})^2 = \frac{8}{23} – (\frac{18}{2*23})^2 = \frac{412}{2116}$$

最终的Q值就是这三个部分加起来:

$$Q =\frac{339}{2116} +\frac{355}{2116} + \frac{412}{2116}   = \frac{1106}{2116}=0.52268431$$

在代码中,我们的图是用边表示的,为了得到社团内部的边,可以遍历所有的边一次,每次看这条边的两个结点是否位于同一个社团内,是的话该社团内部边数+1

为了得到社团内部结点的度数之和,可以先得到图中所有结点的度,然后按照社团内部的点累加即可。

C++代码

下面的示例代码中,图是按照边表的形式存在一个 vector<pair<int,int>>  graph 中,社团文件存在 vector<vector<int>> communities; 中

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/calc_modularity_cpp.html

上一篇:

下一篇:

我要评论

验证码*: 0 + 3 =