社区检测算法中权重的含义
meaning of weights in community detection algorithms
igraph here 中提供了社区检测算法的出色比较。但是，在可以与加权边一起应用的算法中，权重的使用存在一些歧义。
通常，边缘权重将被定向，以便更高的权重建议将节点保持在一起（例如友谊强度）。通过比较内部和外部的平均加权密度，这与模块化分数很好地配合。
但是，Newman-Girvan 社区检测算法使用基于距离的介数。在这种情况下，我希望边权重应该反映节点之间的距离，以便计算最短路径时计算路径上的权重。也就是说，权重是成本或距离分数，其中较高的值应该分成不同的社区。
当使用 Newman-Girvan 时，我期望更高的权重和更远的距离是否正确？如果是这样，那么这如何与使用模块化来决定在何处削减社区数量相协调？
我的答案将基于 R 中的 igraph 包。情况确实很混乱，问题也很相关，因为正如 Newman (2004) 所说，
Since the publication of that work, the author has been asked a number
of times whether an appropriate generalization of the algorithm exists
for weighted networks.
在他的论文中，他推导出 Newman-Girvan 算法对加权网络的适当推广。
权重
你对 Newman-Girvan 算法中权重的解释是正确的。 edge_betweenness 使用类似于 (Brandes, 2001) 中的公式，其中路径的长度定义为其边的权重之和。 （您也可以检查 source code 但它非常复杂）。在 ?edge_betweenness 中，特别是 ?cluster_edge_betweenness 它说
Edge weights are used to calculate weighted edge betweenness. This
means that edges are interpreted as distances, not as connection
strengths.
含义如下。令 b(e, w) 为权重为 w 的边 e 的边介数。然后可以证明（如果你愿意，我可以详细说明）
b(e, w) <= b(e, w*) 当且仅当 w >= w*.
即边介数与e的权重成反比关系。主要思想是给定，例如，w* >> w，那些现在穿过 e 的最短路径很可能被一些不包括 e 的其他路径支配。因此，较大的权重意味着（弱）较低的介数，而较低的介数使得 e 不太可能被识别为连接两个社区的边缘。因此，如果我们将权重视为距离，这听起来很奇怪。另一方面，如果 e 在某个社区内并且我们降低了它的权重，那么通过该边的最短路径的数量可能会增加并且它更有可能被视为连接两个社区。不过，我还没有对相应的模块化分数提出任何要求。
现在让我们假设权重实际上对应于连接强度。那么连接越强，经过那条边的最短路径就越少（因为我们还需要计算它们），它的边介数越低，被移除的可能性就越小。所以这是有道理的。
不好的，或者更奇怪的是，现在路径的长度被定义为其连接强度的总和。但是，我们可以重新解释算法。假设社区内的权重 >> 1，社区之间的权重 << 1。那么我们可以将一条路径的长度解释为这条路径的隐私（例如，社区内的一条路径会包含很多密切的互动，而连接两个社区的边缘有点public, 打开)。给定这样的解释，该算法将寻找最不私有/最开放的路径并计算相应的介数。然后我们将删除属于许多最开放路径的边缘。
所以也许我在某处犯了错误，但看起来将权重视为连接强度更有意义。
纽曼 (2004) 做了一些相关的事情：
...we will consider specifically those networks in which the weights
on edges take greater values for vertex pairs that have closer
connections or are more similar in some way.
看来应该是有道理的。然而，为了保持最短路径的更自然定义，他写道：
One can define paths on a weighted network by assuming the “length” of
an edge to vary inversely with its weight, so that two vertices that
are connected twice as strongly will be half as far apart.
也就是说，最短路径长度现在与权重成反比。由于不这样做似乎会产生良好的结果，现在我们有一个问题：
To see this, notice that any two vertices that are particularly
strongly connected to one another will have a particularly short
distance along the edge between them. Geodesic paths will thus, all
other things being equal, prefer to flow along such an edge than along
another longer edge between two less well connected vertices, and
hence closely connected pairs will tend to attract a lot of paths and
acquire high betweenness. This means that, as a general rule, we are
more likely to remove edges between well connected pairs than we are
between poorly connected pairs, and this is the precise opposite of
what we would like the algorithm to do.
这就是我描述的当我们把权重看成距离时的结果。正如我在答案开头提到的，为了解决这个问题，Newman (2004) 建议将加权图映射到未加权的多图，然后与标准情况非常相似地进行处理。我相信这个多图的想法可以通过设置 weighted = NULL 但没有二元邻接矩阵来实现（定义图时；参见 ?graph_from_adjacency_matrix 中的 weighted）。
模块化
首先，可以像 Newman (2004) 那样对加权图使用模块化，这不是问题。一般来说，使用权重如何影响使用模块化作为选择社区数量的方式并不明显。我也许会用 R 添加一些例子。当解释与算法的工作方式一致时，似乎应该对未加权的情况进行改进，正如 Newman (2004) 发现的那样。否则，我认为图形结构和权重本身对于描述我们得到的真实程度有多远非常重要。
参考资料
Newman, M.E., 2004. 加权网络分析。物理评论 E, 70(5).
Brandes, U., 2001。一种更快的中介中心性算法。数理社会学杂志, 25(2), pp.163-177.
igraph here 中提供了社区检测算法的出色比较。但是，在可以与加权边一起应用的算法中，权重的使用存在一些歧义。
通常，边缘权重将被定向，以便更高的权重建议将节点保持在一起（例如友谊强度）。通过比较内部和外部的平均加权密度，这与模块化分数很好地配合。
但是，Newman-Girvan 社区检测算法使用基于距离的介数。在这种情况下，我希望边权重应该反映节点之间的距离，以便计算最短路径时计算路径上的权重。也就是说，权重是成本或距离分数，其中较高的值应该分成不同的社区。
当使用 Newman-Girvan 时，我期望更高的权重和更远的距离是否正确？如果是这样，那么这如何与使用模块化来决定在何处削减社区数量相协调？
我的答案将基于 R 中的 igraph 包。情况确实很混乱，问题也很相关，因为正如 Newman (2004) 所说，
Since the publication of that work, the author has been asked a number of times whether an appropriate generalization of the algorithm exists for weighted networks.
在他的论文中，他推导出 Newman-Girvan 算法对加权网络的适当推广。
权重
你对 Newman-Girvan 算法中权重的解释是正确的。 edge_betweenness 使用类似于 (Brandes, 2001) 中的公式，其中路径的长度定义为其边的权重之和。 （您也可以检查 source code 但它非常复杂）。在 ?edge_betweenness 中，特别是 ?cluster_edge_betweenness 它说
Edge weights are used to calculate weighted edge betweenness. This means that edges are interpreted as distances, not as connection strengths.
含义如下。令 b(e, w) 为权重为 w 的边 e 的边介数。然后可以证明（如果你愿意，我可以详细说明）
b(e, w) <= b(e, w*) 当且仅当 w >= w*.
即边介数与e的权重成反比关系。主要思想是给定，例如，w* >> w，那些现在穿过 e 的最短路径很可能被一些不包括 e 的其他路径支配。因此，较大的权重意味着（弱）较低的介数，而较低的介数使得 e 不太可能被识别为连接两个社区的边缘。因此，如果我们将权重视为距离，这听起来很奇怪。另一方面，如果 e 在某个社区内并且我们降低了它的权重，那么通过该边的最短路径的数量可能会增加并且它更有可能被视为连接两个社区。不过，我还没有对相应的模块化分数提出任何要求。
现在让我们假设权重实际上对应于连接强度。那么连接越强，经过那条边的最短路径就越少（因为我们还需要计算它们），它的边介数越低，被移除的可能性就越小。所以这是有道理的。
不好的，或者更奇怪的是，现在路径的长度被定义为其连接强度的总和。但是，我们可以重新解释算法。假设社区内的权重 >> 1，社区之间的权重 << 1。那么我们可以将一条路径的长度解释为这条路径的隐私（例如，社区内的一条路径会包含很多密切的互动，而连接两个社区的边缘有点public, 打开)。给定这样的解释，该算法将寻找最不私有/最开放的路径并计算相应的介数。然后我们将删除属于许多最开放路径的边缘。
所以也许我在某处犯了错误，但看起来将权重视为连接强度更有意义。
纽曼 (2004) 做了一些相关的事情：
...we will consider specifically those networks in which the weights on edges take greater values for vertex pairs that have closer connections or are more similar in some way.
看来应该是有道理的。然而，为了保持最短路径的更自然定义，他写道：
One can define paths on a weighted network by assuming the “length” of an edge to vary inversely with its weight, so that two vertices that are connected twice as strongly will be half as far apart.
也就是说，最短路径长度现在与权重成反比。由于不这样做似乎会产生良好的结果，现在我们有一个问题：
To see this, notice that any two vertices that are particularly strongly connected to one another will have a particularly short distance along the edge between them. Geodesic paths will thus, all other things being equal, prefer to flow along such an edge than along another longer edge between two less well connected vertices, and hence closely connected pairs will tend to attract a lot of paths and acquire high betweenness. This means that, as a general rule, we are more likely to remove edges between well connected pairs than we are between poorly connected pairs, and this is the precise opposite of what we would like the algorithm to do.
这就是我描述的当我们把权重看成距离时的结果。正如我在答案开头提到的，为了解决这个问题，Newman (2004) 建议将加权图映射到未加权的多图，然后与标准情况非常相似地进行处理。我相信这个多图的想法可以通过设置 weighted = NULL 但没有二元邻接矩阵来实现（定义图时；参见 ?graph_from_adjacency_matrix 中的 weighted）。
模块化
首先，可以像 Newman (2004) 那样对加权图使用模块化，这不是问题。一般来说，使用权重如何影响使用模块化作为选择社区数量的方式并不明显。我也许会用 R 添加一些例子。当解释与算法的工作方式一致时，似乎应该对未加权的情况进行改进，正如 Newman (2004) 发现的那样。否则，我认为图形结构和权重本身对于描述我们得到的真实程度有多远非常重要。
参考资料
Newman, M.E., 2004. 加权网络分析。物理评论 E, 70(5).
Brandes, U., 2001。一种更快的中介中心性算法。数理社会学杂志, 25(2), pp.163-177.