雅乐网

计算机技术、学习成长

数学 » 社团检测 » Modularity的计算方法——社团检测中模块度计算公式详解

Modularity的计算方法——社团检测中模块度计算公式详解


Modularity,中文称为模块度,是 Community Detection(社区发现/社团检测) 中用来衡量社区划分质量的一种方法。要理解Modularity,我们先来看社团和社团检测的概念。

社团检测

社团检测,就是要在一个图(包含顶点和边)上发现社团结构,也就是要把图中的结点进行聚类,构成一个个的社团。关于社团(community),目前还没有确切的定义,一般认为社团内部的点之间的连接相对稠密,而不同社团的点之间的连接相对稀疏。

社团检测算法的输入是一张图:

scrn20170308214823

上图可以用边表(edge list)文件表示:

在计算机中,也可能以邻接矩阵的方式存储这张图:

邻接矩阵A,\(A_{ij} = 1\)表示 结点i 和 结点j 之间有一条边, \(A_{ij} = 0\)表示 结点i 和 结点j 之间没有边。特别的,这里结点自己和自己的连接是0,即\(A_{ii} = 0\),不考虑结点自己和自己的连边。

输入图后,社团检测算法会输出一种社团划分,例如下面这个样子

scrn20170308214716

具体的输出文件可能这样:

每行表示一个社团,里面的数字表示属于该社团的结点编号。

公式中用到的字母

在不同的文献中,可能用不同的字母表示相同的东西,这样就给理解造成了一定困难。本文中的所有公式都使用下面的字母定义。

和图相关的

n 表示图的结点个数,这里n=14(结点编号0到13)

m 表示图中边的个数,这里m=23(上图中共23条边)

k 表示图中结点的度(degree),无向图中一个结点的度就是该结点连出去的边的条数。显然图中14个结点都有自己的度,我们用\(k_i\)来表示结点i的度。例如:\(k_0 = 3, k_5 = 4, k_6 = 2\)。

A 表示图的邻接矩阵。邻接矩阵A,\(A_{ij} = 1\)表示 结点v 和 结点w 之间有一条边, \(A_{ij} = 0\)表示 结点i 和 结点j 之间没有边。无向图的邻接矩阵是对称的,即\(A_{ij} = A_{ji}\)。特别的,这里结点自己和自己的连接是0,即\(A_{ii} = 0\),不考虑结点自己和自己的连边。

Modularity第一版

Newman 在2003年的论文 “Finding and evaluating community structure in networks” 中首次提出了modularity的定义,在论文中用来度量自己的社团检测算法的好坏。

Consider a particular division of a network into k communities. Let us define a k×k symmetric matrix e whose element \(e_{ij}\) is the fraction of all edges in the network that link vertices in community i to vertices in community j [49].

假设社团划分把一个网络划分为k个社团,定义一个k*k的矩阵e。\(e_{ij}\)表示连接 社团i 和 社团j 的边的数目 占 总边数 的比例。特别的,\(e_{ii}\)表示的是社团i和社团i之间的边占总边数的比例,也就是社团i内部的边占总边数的比例。

结合我们的例子

scrn20170308230905

例子中,边数m=23 。社团1内部有5条边,于是有 \(e_{11} = \frac{5}{23}\)。

社团2和社团3之间有2条边,这样看来 \(e_{23} = \frac{2}{23}\) 。那么\(e_{32}\)等于多少?如果你没有看这句话后面的注释,也许你会以为\(e_{32} = e_{23} = \frac{2}{23}\) 。但其实不是的,我们看后面的注释:

[49] As discussed in [33], it is crucial to make sure each edge is counted only once in the matrix eij—the same edge should not appear both above and below the diagonal. Alternatively, an edge linking communities i and j can be split, half-and-half, between the ij and ji elements, which has the advantage of making the matrix symmetric. Either way, there are a number of factors of 2 in the calculation that must be watched carefully, lest they escape one’s attention and make mischief.

这里说,在矩阵e中,每条边要确保只计数了1次。一条边的计数不能同时出现在e矩阵的对角线上方和下方。如果\(e_{32} = e_{23} = \frac{2}{23}\),那么连接社团2和社团3的两条边就分别计数了2次。因此,可以的情况是:

\(e_{32} = \frac{2}{23}, e_{23} = \frac{0}{23}\) 或者 \(e_{32} = \frac{0}{23}, e_{23} = \frac{2}{23}\) 或者\(e_{32} = \frac{1}{23} , e_{23} = \frac{1}{23}\)

一种可行的方法是,把社团i和j之间的边分成2份,分别计入\(e_{ij}\) 和 \(e_{ji}\),这样可以保证e是对称的。这样计算\(e_{ij}\)时,分母上就会多一个2 。

我们这个图中,社团1内部有5条边,社团2内部有7条边,社团3内部有8条边。社团1和社团2之间有1条边,社团1和社团3之间有0条边,社团2和社团3之间有2条边。可以得到e矩阵如下:

1 2 3
1 \(\frac{5}{23}\) \(\frac{1}{2} \times \frac{1}{23}\) \(\frac{1}{2} \times \frac{0}{23}\)
2 \(\frac{1}{2} \times \frac{1}{23}\) \(\frac{7}{23}\) \(\frac{1}{2} \times \frac{2}{23}\)
3 \(\frac{1}{2} \times \frac{0}{23}\) \(\frac{1}{2} \times \frac{2}{23}\) \(\frac{8}{23}\)

这样,矩阵e的迹 \(tr(e) = \sum_{i}{e_{ii}}\),也就是矩阵对角元素的和,就表示了社团内部的边的比例。这个值越大,代表社团内部联系越紧密。然而这样有一个缺陷,如果把整张图分成1个社团,这个值就是最大值1 。

So we further define the row (or column) sums \(a_i = \sum_{j}{e_{ij}}\) , which represent the fraction of edges that connect to vertices in community i.

因此定义了一个e的行和a, \(a_i = \sum_{j}{e_{ij}}\),它表示连接到 社团i 中的边占总边数的比例。这句话是不准确的。

因为上面e矩阵中,我们对不同社团之间的边要除以2,因此这里连接到 社团i 中的边是有不同权重的,完全在社团i中的边权重为1,而只有一端在社团i中的边权重就是\(\frac{1}{2}\)。

由于权重的不同,如果把一条边看做有两个端点,准确的说法是

\(a_i = \sum_{j}{e_{ij}}\),它表示连接到 社团i 中的边的端点数(相当于社团中所有点的度相加) 占总端点数(2m) 的比例 ,即

$$a_i = \frac{k_{C_i}}{2m}$$

\(k_{C_i}\)表示社团i内部所有点的度数之和。

例子里我们的a如下:

a
1 \(\frac{5}{23} + \frac{1}{2} \times \frac{1}{23} + \frac{1}{2} \times \frac{0}{23}\) = \(\frac{11}{46}\)
2 \(\frac{1}{2} \times \frac{1}{23} + \frac{7}{23} + \frac{1}{2} \times \frac{2}{23}\) = \(\frac{17}{46}\)
3 \(\frac{1}{2} \times \frac{0}{23} + \frac{1}{2} \times \frac{2}{23} + \frac{8}{23}\) = \(\frac{18}{46}\)

In a network in which edges fall between vertices without regard for the communities they belong to, we would have \(e_{ij} = a_ia_j \).

这句话我还没看懂,看懂的可以再评论区教下博主0.0

Thus we can define a modularity measure by

$$Q = \sum_i{(e_{ii} – a_i^2)} = Tr e – ||e^2||$$

where ||x|| indicates the sum of the elements of the matrix x.

模块度的公式,定义是:

$$Q = \sum_i{(e_{ii} – a_i^2)} = \sum_i{e_{ii}} – \sum_i{ a_i^2}$$

如果用\(e_i\)表示社团i内部的边数,则\(e_ii = \frac{e_i}{m}\) 。然后把\(a_i = \frac{k_{C_i}}{2m}\)代入,就可以得到计算modularity最常用的公式

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

我们用定义算一下我们这个例子中划分的模块度:

$$Q = \frac{5}{23} + \frac{7}{23} + \frac{8}{23} – (\frac{11}{46})^2 – (\frac{17}{46})^2 – (\frac{18}{46})^2 = \frac{553}{1058} = 0.52268431$$

还可以推导一下,得到矩阵公式:

$$Q = \sum_i{(e_{ii} – a_i^2)} = \sum_i{e_{ii}} – \sum_i{ a_i^2} = Tr e – ||e^2||$$

要证明这个,就是要\(\sum_i{ a_i^2} = ||e^2||\) 。 由于\(a_i = \sum_{j}{e_{ij}} \),也就是

$$\sum_i{ ( \sum_{j}{e_{ij}} )^2} = ||e^2||$$

注意到e是对称的。也就是e矩阵的每行求和,然后平方,再相加 等于 e矩阵平方再求和。(我还没看懂,看懂的可以再评论区教下博主0.0

可以验证用矩阵公式算也会得到同样的Q。

这里顺便比较一下\(\sum_i{a_i^2 }\) 和 \( ||e^2||\)

$$\sum_i{ a_i^2} = (\frac{5}{23} + \frac{1}{46} + 0)^2 + (\frac{1}{46} + \frac{7}{23} + \frac{1}{23})^2 + (0 + \frac{1}{23} + \frac{8}{23})^2$$

$$e^2 = \begin{pmatrix}
\frac{5}{23} & \frac{1}{46} & 0 \\
\frac{1}{46} & \frac{7}{23} & \frac{1}{23} \\
0 & \frac{1}{23} & \frac{8}{23} \\
\end{pmatrix} \times
\begin{pmatrix}
\frac{5}{23} & \frac{1}{46} & 0 \\
\frac{1}{46} & \frac{7}{23} & \frac{1}{23} \\
0 & \frac{1}{23} & \frac{8}{23} \\
\end{pmatrix} = $$

我感觉第一个式子拆开后,正好就是后一个式子里面矩阵中的元素两两相乘。最后累加结果也相同。

Modularity第二版

Newman论文中的定义

2006年,Newman 在论文“Modularity and community structure in networks”中重新定义了modularity,目的是为了满足spectral properties。原话为:

Here we take a different approach based on a reformulation of the modularity in terms of the spectral properties of the network of interest.

Suppose our network contains n vertices.

n 表示图的结点个数

For a particular division of the network into two groups let s_i = 1 if vertex i belongs to group 1 and s_i = -1 if it belongs to group 2. Observing that the quantity \(\frac{1}{2} (s_i s_j + 1)\)  is 1 if i and j are in the same group and 0 otherwise

论文中的例子是分为了2个社区。然后定义了\(s_i\),\(s_i = 1\) 表示结点i属于社团1,\(s_i = -1\) 表示结点i属于社团2 。那么 \(\frac{1}{2} (s_i s_j + 1)\) 的值就可以表示结点i和j是否在同一个社团,在同一个社团时值是1,在不同社团时值是0.

And let the number of edges between vertices i and j be \(A_{ij}\), which will normally be 0 or 1, although larger values are possible in networks where multiple edges are allowed.(The quantities \(A_{ij}\) are the elements of the so-called adjacency matrix.)

让\(A_{ij}\) 表示 结点i 和 结点j 之间边的数目, 一般无权图中\(A_{ij}\) 的取值是0或者1。但可以扩展到两点之间多条边的情形。

这里有2点文中没到的:

1. 无向图的邻接矩阵是对称的,即\(A_{ij} = A_{ji}\)。因此,如果把矩阵A的所有元素相加,得到的值是图中边的数目的2倍:\(2m = \sum{A_{ij}}\)。

2. 自己和自己的连接在矩阵中是0,即\(A_{ii} = 0\)。

At the same time, the expected number of edges between vertices i and j if edges are placed at random is \(\frac{k_ik_j}{2m}\), where \(k_i\) and \(k_j\) are the degrees of the vertices and \(m = \frac{1}{2} \sum_i{k_i}\) is the total number of edges in the network.

同时,如果把同一个图中的边随机放置,则结点i和结点j之间边数的期望值是\(\frac{k_ik_j}{2m}\)(解释见下一节)。其中\(k_i\) 和 \(k_j\) 表示结点i和结点j的度, \(m = \frac{1}{2} \sum_i{k_i}\) 是图中边的个数。

Thus the modularity Q is given by the sum of \(A_{ij} – \frac{k_ik_j}{2m}\)   over all pairs of vertices i, j that fall in the same group.

\(A_{ij} – \frac{k_ik_j}{2m}\) 表示的是结点i和结点j之间的连边数,减去 随机情况下 结点i和结点j之间的期望连边数。(关于随机情况的讨论在下面)

we can then express the modularity as

$$Q = \frac{1}{4m} \sum_{ij}{(A_{ij} – \frac{k_ik_j}{2m})(s_is_j+1)}$$

The leading factor of \(\frac{1}{4m}\) is merely conventional: it is included for compatibility with the previous definition of modularity (17).

Q计算公式前面的\(\frac{1}{4m}\)仅仅是为了和之前第一版的modularity计算公式相兼容。

把这个公式变形一下:

$$Q = \frac{1}{2m} \sum_{ij}{(A_{ij} – \frac{k_ik_j}{2m})\frac{(s_is_j+1)}{2}}$$

这样就可以看出,后面的因子\(\frac{1}{2} (s_i s_j + 1)\)是为了确保求和时只对i和j属于同一个社团的情况进行求和。由于用s=1和-1只能表示有2个社团的情况,在多个社团时,我们可以引入记号\(\delta(i,j)\) ,\(\delta(i,j) = 0\) 表示结点i 和 j 不在同一个社团,\(\delta(i,j) = 1\) 表示结点 i 和 j 在同一个社团。这样计算公式就变成了

$$Q = \frac{1}{2m} \sum_{ij}{(A_{ij} – \frac{k_ik_j}{2m}) \delta(i, j)}$$

其实就是下面的意思:

$$Q = \frac{1}{2m} \sum_{i,j在同一社团}{(A_{ij} – \frac{k_ik_j}{2m}) }$$

再来看一下这个式子中各个项的意义:

\(A_{ij}\) 表示 结点i 和 结点j 之间边的数目

\(\frac{k_ik_j}{2m}\) 表示 随机放置边的情况下,结点i和结点j 之间边数的期望值

带上前面的求和号,

\(\sum_{i,j}{A_{ij}}\) 就表示 社团内部实际的 边 的数目 的2倍(2倍是因为ij和ji会计算2次)

\(\sum_{i,j}{\frac{k_ik_j}{2m}}\) 就表示 随机放置边的情况下,社团内部边数的期望值 的2倍(2倍是因为ij和ji会计算2次)

最后除以2m,之所以是2m,就是因为前面的边数都是2倍,这样一除就可以得到边的比例。(其实有没有\(\frac{1}{2m}\)是无所谓的,乘以常数并不影响求最值的问题)

\(\frac{1}{2m} \sum_{i,j}{A_{ij}}\) 就表示 社团内部实际的边数的比例

\(\frac{1}{2m} \sum_{i,j}{\frac{k_ik_j}{2m}}\)就表示 随机情况下社团内部期望的边数的比例

因此,Modularity的定义可以看做:

在社区内部的边的比例,减去边随机放置时社区内部期望边数的比例。

期望边数\(\frac{k_ik_j}{2m}\)的来源

参考论文Finding community structure in networks using the eigenvectors of matrices

每个结点的度不变,边重新连接,这就需要一个已知每个结点的度,来随机生成图的模型。图生成模型最重要的特征就是两个点i和j之间连边的概率(或者叫边的数目的期望值),记为\(P_{ij}\),那么\(P_{ij}\)会满足什么性质呢?

1.每个结点度不变,最终总边数也不会变。因此随机连边后,图中的边数期望值等于原来真实图中的边数

$$\sum_{i,j}{P_{ij}} = \sum_{i,j}{A_{ij}} = 2m$$

2.对每个节点来说,它的度也不会变,就有

$$\sum_{j}{P_{ij}} = k_i$$

在满足这两个式子的情况下,随机的进行连边。这样在选定了一个点(边的一个端点)后,选另一个点(边的另一个端点)时,会选到结点i的概率,就只与结点i的度\(k_i\)有关。而一条边的两个端点进行选择的时候都是独立随机的。因此\(P_{ij}\),选到i的概率与\(k_i\)有关,选到j的概率与\(k_j\)有关,就可以写成

$$P_{ij} = f(k_i)f(k_j)$$

由于\(P_{ij} = P_{ji}\),因此上面两个函数f是相同的。

$$\sum_{j}{P_{ij}} = \sum_{j}{f(k_i)f(k_j)} = f(k_i) \sum_{j}{f(k_j)} $$

根据上面性质中的第二个式子\(\sum_{j}{P_{ij}} = k_i\),就有

$$f(k_i) \sum_{j}{f(k_j)} = k_i$$

由于\(\sum_{j}{f(k_j)}\)并不包含i,可以看出\(f(k_i)\)和\(k_i\)之间是倍数关系,不妨设

$$f(k_i) = C k_i$$

C是常量。代入上面性质的第一个式子\(\sum_{i,j}{P_{ij}} = \sum_{i,j}{A_{ij}} = 2m\) ,有

$$\sum_{i,j}{P_{ij}} = 2m$$

$$\sum_{i,j}{f(k_i)f(k_j)} = 2m$$

$$\sum_{i,j}{C k_i C k_j} = 2m$$

$$C^2 \sum_{ij}{k_ik_j} = 2m$$

\(\sum_{ij}{k_ik_j}\)是可以用m表示的。假设结点编号从1到n,则

$$2m = k_1 + k_2 + … + k_n$$

$$(2m)^2 = (k_1 + k_2 + … + k_n)^2$$

平方展开,正好等于n个k值两两相乘,这正好等于\(\sum_{ij}{k_ik_j}\)。即

$$(2m)^2 = (k_1 + k_2 + … + k_n)^2 = \sum_{ij}{k_ik_j}$$

再回到上面的式子,\(C^2 \sum_{ij}{k_ik_j} = 2m\)就变成了

$$C^2 (2m)^2 = 2m$$

$$C = \frac{1}{\sqrt{2m}}$$

因此求得\(P_{ij}\)

$$P_{ij} = f(k_i)f(k_j) = C^2 k_i k_j = \frac{k_ik_j}{2m}$$

这个结果,当m非常大的时候,就等于configuration model中的概率

configuration model

configuration model是一种生成图的模型,它已知每个结点的度\(k_i\),然后随机生成边。

结点i的度\(k_i\)可以看做结点i有\(k_i\)个端点(stub)可以连接

所有结点的端点的个数为 \(l_n = \sum_{i}{k_i} = 2m\)

我们的图来说就是这样:

scrn20170309165401

因为我们的原图有23条边,因此有46个端点。然后端点之间随机相连,每个端点连1次。例如连接5次后可能这样

scrn20170309165607

现在的问题是,这样把边随机放置后,结点v和结点w之间边数的期望值是多少。

可以这样考虑,在一次随机选择两个末梢连边时,选定结点i的末梢后,选择另一个端点时共有2m-1中选择,而i和j连接的选择共有\(k_j\)种,概率就是\(\frac{k_j}{2m-1}\)。而结点i共有\(k_i\)个端点,也就是这样的选择机会有\(k_i\)次。因此i和j相连的概率为

$$P_{ij} = \frac{k_ik_j}{2m-1}$$

当m很大的时候,2m-1中的-1可以去掉,这样就和modularity中的概率一致了。

版本二和版本一的关系

版本二从不同的角度定义了modularity,但是两个版本其实是相等的。也就是说

版本一:(c是社团个数)

$$Q = \sum_i^c{(e_{ii} – a_i^2)} = \sum_i{e_{ii}} – \sum_i{ a_i^2}$$

版本二:

$$Q = \frac{1}{2m} \sum_{i,j在同一社团}{(A_{ij} – \frac{k_ik_j}{2m}) } $$

这两个相等,也就是

$$\sum_i{e_{ii}} – \sum_i{ a_i^2} = \frac{1}{2m} \sum_{i,j在同一社团}{(A_{ij} – \frac{k_ik_j}{2m}) }$$

先看第一项

$$ \sum_i^c{e_{ii}} = \frac{1}{2m} \sum_{i,j在同一社团}{(A_{ij} )}$$

\(e_{ii}\)表示的是社团i内部边的比例,求和后就是所有社团内部的边的比例。右边的求和\(\sum{(A_{ij} }\)就等于内部边数的2倍,除以2m也就是社团内部边的比例。这两个相等是容易看出的。

再看第二项

$$\sum_i^c{ a_i^2} = \frac{1}{2m} \sum_{i,j在同一社团}{(\frac{k_ik_j}{2m}) }$$

在版本一中,\(a_{i}\)表示连接到 社团i 中的边占总边数的比例。这里连接到 社团i 中的边是有不同权重的,完全在社团i中的边权重为1,而只有一端在社团i中的边权重就是1/2。

乘以2的话,\(2 * a_i\)就正好是社团i内结点的度数之和 占总边数的比例(完全在社团i中的边权重为2,而只有一端在社团i中的边权重就是1,正好是度数之和)

在乘以m,就可以去掉比例,\(2m * a_i\)是社团i内结点的度数之和。也就是,\(a_i\) = 社团i内结点的度数之和 / 2m

\(a_i^2\)就是社团i内结点的度数之和的平方 / \((2m)^2\)

$$右边= \frac{1}{2m} \sum_{i,j在同一社团}{(\frac{k_ik_j}{2m}) } = \frac{1}{(2m)^2} \sum_{i,j在同一社团}{(k_ik_j) }$$

度数之和的平方,展开正好就是右边的 社团内部的度数两两相乘再相加\(\sum_{i,j在同一社团}{(k_ik_j) }\)

因此这两个是相等的

$$Q = \sum_i{e_{ii}} – \sum_i{ a_i^2} = \frac{1}{2m} \sum_{i,j在同一社团}{(A_{ij} – \frac{k_ik_j}{2m}) }$$

针对有权图和重叠社团的推广

参考论文:Identification of overlapping community structure in complex networks using fuzzy c-means clustering

上面的Modularity公式,可以写成下面的形式:

$$Q = \sum_k{(\frac{e_{kk}}{m} – (\frac{d_k}{2m})^2)} $$

其中, \(e_kk\)表示社团k内部的边数,\(d_k\) 表示社团i内部所有点的度数之和,m表示图中边的个数。

在有权图中,相当于把原来有一条边算作1,现在算作权值w的。

而针对重叠社团的情况,根据所属社团的个数,给边的贡献加一个权值:

若 结点i 属于 n 个社团(其中包括社团k),则定义 \(w_{ik} = \frac{1}{n}\) 。而在无重叠的情况下,\(w_{ik} = 1\),且k仅有一个

$$e_{kk} = \frac{1}{2} \sum_{i,j \in C_k} \frac{w_{ik} + w_{jk}}{2} A_{ij}$$

系数 1/2 是因为社团内的一条边 ij和ji 会计算两次

\(A\)是图的邻接矩阵,\(A_{ij}\)也就是对应边的权值。

为了求得社团内部边的度数,先计算社团连出去的边数:

$$e_{k_out} = \sum_{i \in C_k, j \notin C_k} (w_{ik} + (1 – w_{jk})) A_{ij}$$

$$d_k = 2e_{kk} + e_{k_out}$$

C++代码计算

Modularity计算的C++代码 | 雅乐网

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

版权声明:

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

上一篇:

下一篇:

文章《Modularity的计算方法——社团检测中模块度计算公式详解》共有30条评论:

  1. 有没有关于有向图的计算例子?

  2. 匿名

    牛逼,看其他的推导都有一些关键地方比较模糊,到这里总算是弄会了

  3. 熊同学

    请问模块度第一版,为啥是矩阵迹的和 减去 行和的平方?这个行和的平方代表啥意思?

    • yalewoo 作者

      你好,我毕业很多年了这个忘得差不多了。。。这是我的理解,如有错误欢迎指出:可以结合第二版的定义来理解第一版的公式,前面的eii表示的是社团i内部的边占总边数的比例,行和a_i是社团i连接到内部和外部的边占总边数的比例,那a_i的平方就是按概率论计算在总边数不变但是连边随机放置时社团i内部的边的比例。这样相减,就是第二版的解释:在社区内部的边的比例,减去边随机放置时社区内部期望边数的比例。

    • 匿名

      我認為trace-行和的平方只是一種整合過的結果,理解上應該通過每個社團內部的邊數的比例減去圖中所有鏈接到該社團的比例的平方(norm)來判斷社團內部相對於整個圖的緊密程度以及社區分群結果的好壞。只不過所有社群的結果相加剛好符合trace-行和的平方這種形式,當然有可能有其在其他方面的解釋意涵。

  4. Shijun Dai

    大佬这文真棒! 有个不懂的地方:在推到期望边数来源的时候,引入了常量C,但是节点i的C和节点j的C,能直接变成C^2的形式,然后开根吗?我觉得这两个C不一定相同啊。(当然就算写成Ci*Cj的形式,也是不影响后续推导的)

  5. berwin

    全网最牛逼推导,感谢老哥

  6. 匿名

    楼主,那个 e矩阵的每行求和,然后平方,再相加 等于 e矩阵平方再求和 我会证了,你需要不?

  7. 羊梨酥

    hallo 我想问一下我在用python的networkx中有个comunity的包划分网络后,计算得出的modularity>1,会有这种特殊情况嘛? 作者大大有没有看到过类似的情况?
    代码如下:
    part=community.best_partition(G)#用 lovain社区检测算法划分模块
    modular=community.modularity(part,G)#计算modularity

    我输入的网络是无向带权重图 但是权重是浮点数 不知道会不会影响他的计算结果

  8. TONG WU

    请问,矩阵相乘不是对应元素两两相乘吧?

    • yalewoo 作者

      hi,相乘应该是第一个的第一行点乘第二个的第一列,你是说||e^2||那里吗,前面(a+b+c)^2拆开后也会有别的项应该正好对应矩阵相乘的法则

  9. 匿名

    全网最赞 真的

  10. 征兆

    太棒了,比其他解释都清楚明白!

  11. six-archer

    如果按照这个算法去算Q的值的话,把每一个点都当成一个群的话算出来不是负的值吗?但是Q的范围不是应该在0-1之间的吗?求大佬解释一下

  12. HCaffrey

    In a network in which edges fall between vertices without regard for the communities they belong to, we would have eij=aiaj

    把这个式子代入ai = sum_j(eiej),式子等价于sum_j(aj) = 1
    Meaning it is a random network regarding all of its nodes as individual community

    sum_j 表示连加符号,抱歉没能插入公式

我要评论

验证码*: 2 + 1 =