社区检测算法中权重的含义

Question

还有就是在现有的igraph社区检测算法的比较优秀这里.然而,在算法中使用加权边缘可以应用权重存在一些模糊性.

通常,边缘权重将被定向,使得较高权重建议将节点保持在一起(例如,友谊的强度).通过比较内部和外部的平均加权密度,这与模块化分数很好地协作.

然而,Newman-Girvan社区检测算法使用基于距离的中间性.在这种情况下,我希望边权重应该反映节点之间的距离,以便计算最短路径对路径上的权重求和.也就是说,权重是成本或距离得分,其中较高的值应该分成不同的社区.

在使用Newman-Girvan时,我是否正确期望更高的权重,如果是这样,那么如何通过使用模块化来决定在哪里削减社区数量？

Answer 1

我的回答将基于igraphR中的一揽子计划.情况确实令人困惑,问题是相关的,因为正如Newman(2004)所说,

自该作品发表以来,已多次询问作者加权网络是否存在适当的算法推广.

在他的论文中,他推导出Newman-Girvan算法对加权网络的适当推广.

权重

你对Newman-Girvan算法中权重的解释是正确的.edge_betweenness使用类似于(Brandes,2001)中的公式,其中路径的长度被定义为其边缘权重的总和.(您也可以查看源代码,但它非常复杂).在?edge_betweenness,特别是,?cluster_edge_betweenness它说

边缘权重用于计算加权边缘之间.这意味着边缘被解释为距离,而不是连接强度.

其含义如下.设b(e,w)为边e与权重w的边缘.然后它可以显示(如果你愿意,我可以详细说明)

b(e,w)<= b(e,w*)当且仅当w> = w*时.

也就是说,边缘中介与e的权重成反比关系.主要思想是,给定例如w*>> w,那些现在交叉的最短路径可能由不包括e的其他路径支配.因此,较大的权重意味着(弱)较低的中介性,较低的中间性使得e不太可能被识别为连接两个社区的边缘.因此,如果我们将权重视为距离,这听起来很奇怪.另一方面,如果e在某个社区内并且我们减少了它的权重,那么通过该边缘的最短路径的数量可能会增加,并且它更可能被视为连接两个社区.不过,我还没有就相应的模块化分数提出任何要求.

现在让我们假设权重实际上对应于连接强度.然后连接越强,通过该边缘的最短路径越少(因为我们仍然需要计算它们),它的边缘间距越低,并且它被移除的可能性越小.所以那是有道理的.

不好或者很奇怪的是,现在路径的长度被定义为其连接强度的总和.但是,我们可以重新解释算法.假设权重在社区内是>> 1,在它们之间是<< 1.然后我们可以将路径的长度解释为该路径的隐私(例如,社区内的路径将包含许多紧密的交互,而连接两个社区的边缘在某种程度上是公开的,开放的).给定这样的解释,算法将寻找最不私有/最开放的路径并计算相应的中介.然后我们将删除属于许多最开放路径的边缘.

所以也许我在某个地方犯了一个错误,但看起来将权重视为连接优势会更有意义.

纽曼(2004)做了一些相关的事情:

...我们将特别考虑这样的网络,其中边缘上的权重对于具有更紧密连接或以某种方式更相似的顶点对采用更大的值.

它似乎应该有意义.但是,为了保持他写的最短路径的更自然的定义:

可以通过假设边缘的"长度"与其权重成反比来定义加权网络上的路径,使得两次连接强度相同的两个顶点将相隔一半.

也就是说,现在最短路径长度与权重成反比.由于没有这样做似乎给出了好的结果,现在我们遇到了一个问题:

要看到这一点,请注意,任何两个彼此特别紧密相连的顶点沿着它们之间的边缘将具有特别短的距离.因此,在所有其他条件相同的情况下,测地路径将优选沿着这样的边缘而不是沿着两个连接不良的顶点之间的另一个较长边缘流动,因此紧密连接的对将倾向于吸引许多路径并获得高中介性.这意味着,作为一般规则,我们更有可能消除连接良好的对之间的边缘,而不是在连接不良的对之间,这与我们希望算法要做的完全相反.

当我们将权重视为距离时,我描述的结果是什么.正如我在答案的开头所提到的,处理这个Newman(2004)提出将加权图映射到未加权的多图,然后与标准情况非常相似地进行.我相信,这种多重图想法可以通过设置来实现weighted = NULL,但具有不二进制邻接矩阵(限定的曲线图;参见weighted在?graph_from_adjacency_matrix).

模块化

首先,人们可以使用带有加权图的模块化,正如Newman(2004)所做的那样,这不是问题.一般来说,使用权重如何影响使用模块化作为选择社区数量的方式并不明显.我可能会用R添加一些例子.正如Newman(2004)发现,当解释符合算法的工作方式时,似乎应该对未加权的情况有所改进.否则,我认为图形结构和权重本身对描述我们得到的真实程度有多么重要.

参考

Newman,ME,2004.加权网络分析.物理评论E,70(5).

布兰德斯,美国,2001年.一种更快的中介中心性算法.数学社会学杂志,25(2),pp.163-177.