我的回答将基于R中的igraph包。情况确实令人困惑,问题是相关的,因为正如Newman(2004)所说:
自那项工作发表以来,作者已经被问了很多次是否存在适当的算法推广来处理加权网络。
在他的论文中,他推导出了Newman-Girvan算法在加权网络中的适当推广。
权重
你对Newman-Girvan算法中权重的解释是正确的。edge_betweenness使用类似于Brandes(2001)的公式,其中路径的长度定义为其边缘权重的总和。 (您还可以检查源代码,但这非常复杂)。在?edge_betweenness和特别是?cluster_edge_betweenness中,它说:
边缘权重用于计算加权边缘介数。 这意味着边缘被解释为距离,而不是连接强度。
以下是含义。假设b(e, w)是边缘e的边缘介数,其权重为w。则可以证明(如果您愿意,我可以详细说明):
当且仅当w> = w*时,b(e,w)<= b(e,w*)。
也就是说,边界介数和e的权重成反比关系。主要思想是,例如,给定w * >> w,那些通过e的最短路径现在很可能被一些不包括e的其他路径所支配。因此,更大的权重意味着(弱)较低的介数,而较低的介数使得不太可能将e识别为连接两个社区的边缘。因此,如果我们将权重视为距离,则听起来很奇怪。另一方面,如果e位于某个社区中,并且我们降低了它的权重,则通过该边的最短路径数量可能会增加,并且更有可能被视为连接两个社区。不过,我还没有声称与相应的模块化分数有关的任何内容。
现在假设权重实际上对应连接强度。那么,连接越强,通过该边的最短路径就越少(因为我们仍需要计算它们),其边介数就越低,被移除的可能性也就越小。这种解释有些道理。
但不好的是,现在路径长度被定义为其连接强度之和。然而,我们可以重新解释算法。假设社区内的权重>>1,社区间的权重<<1。那么我们可以将路径长度解释为此路径的隐私性(例如,社区内的路径将包含许多紧密的交互,而连接两个社区的边则相对公开)。在这样的解释下,算法将寻找最不私密/最公开的路径并计算相应的介数。然后我们将删除属于许多最公开路径的这样的边。
所以也许我在某个地方犯了错误,但看起来将权重视为连接强度更有意义。
Newman(2004)做了一些相关工作:
我们将专门考虑那些边权值对于连接更紧密或在某种程度上更相似的顶点对而言取得更大值的网络。这似乎是有意义的。然而,为了保持最短路径的更自然定义,他写道:“可以通过假设边的“长度”与其权重成反比来定义加权网络上的路径,因此,两个连接强度增加一倍的顶点之间的距离将减少一半。”也就是说,最短路径长度现在与权重成反比关系。由于不这样做似乎会产生良好的结果,现在我们面临一个问题。
为了理解这一点,请注意,任何两个相互强烈连接的顶点之间的距离都会特别短。地理路径因此更倾向于沿着这样的边流动,而不是沿着两个连接较弱的顶点之间的另一个较长的边流动,因此密切相关的对将倾向于吸引许多路径并获得高介数。这意味着,通常情况下,我们更有可能删除连接良好对之间的边缘,而不是连接较差的对之间的边缘,这正好与我们希望算法执行的相反。
当我们将权重视为距离时,这就是我所描述的结果。正如我在答案开头提到的那样,为了处理这个问题,Newman(2004)建议将加权图映射到无权多图中,然后进行与标准情况非常相似的操作。我认为可以通过设置weighted = NULL
来实现这个多图想法,但是在定义图时没有二进制邻接矩阵(请参见?graph_from_adjacency_matrix
中的weighted
)。
模块性
首先,可以像Newman(2004)所做的那样使用加权图进行模块化,这并不是问题。总的来说,使用权重如何影响使用模块性作为选择社区数量的方法并不明显。我可能会添加一些R的示例。当解释与算法工作方式一致时,似乎应该比未加权的情况有所改进,就像Newman(2004)所发现的那样。否则,我认为图形结构和权重本身可以相当重要,以描述我们离真相有多远的程度。
参考文献:
Newman,M.E.,2004。Analysis of weighted networks. Physical review E,70(5)。
Brandes,U.,2001。A faster algorithm for betweenness centrality. Journal of mathematical sociology,25(2),pp.163-177。
weighted = NULL
。然后会创建一个无权图,邻接矩阵的元素表示顶点之间的边数。这也意味着邻接矩阵的元素应该是非负整数(否则它们将被四舍五入)。 - Julius Vainora