Newman 的网络模块化是否适用于有符号的加权图?

机器算法验证 聚类 数据可视化 网络 分区 模块化
2022-03-19 13:29:06

图的模块化在其Wikipedia 页面上定义。一篇文章中,有人解释说,加权网络的模块化可以很容易地计算(和最大化),因为邻接矩阵也可以包含有价值的联系。但是,我想知道这是否也适用于有符号、有值的边缘,例如,从 -10 到 +10。你能提供关于这个问题的直觉、证据或参考吗?Aij

3个回答

如果对这些权重进行签名,则加权网络的模块化直接推广将不起作用直截了当,我的意思是:只使用权重矩阵而不是邻接矩阵,就像纽曼在(Newman 2004)中所做的那样。您需要一个特定的版本,例如 BenjaminLind 引用的版本,或(Gomez et al. 2009)的版本。

在这两篇文章中,他们解释了这样做的原因。总而言之:模块化依赖于一些归一化程度(或加权网络情况下的强度)可以被视为概率的事实。估计之间存在链接的概率,其中是节点的各自强度,是所有网络节点的总强度。如果某些权重为负,则原始归一化不再保证中的值,因此上述ijpipj=wiwj/(2w)2wiwjijw[0,1]pipj数量不能被视为概率。

为了解决这个问题,Gomez等人分别考虑正面和负面的联系。他们获得两个不同的模块化值:一个用于正链接,一个用于负链接。他们从前者中减去后者以获得整体模块化。

是的,它可以。用于社区检测的自旋玻璃模型可以从加权签名图计算模块化。您需要 Traag 和 Bruggeman的“具有正负链接的网络中的社区检测”作为参考。igraph 中的函数“spinglass.community()”可以找到社区并返回图的模块化。

我们已经在本文中指出了带符号网络的模块化[-alike] 函数问题随着网络中负链接的绝对数量增加,他们倾向于更多地忽略社区的正密度。

另外,这里是我们用于加权签名网络的开源 java 项目,它基于Constant Potts 模型(类似于 Modularity)、快速Louvain 算法和基于Map Equation扩展的社区评估。

Esmailian, P. 和 Jalili, M.,2015 年。签名网络中的社区检测:不同规模的负面联系的作用。科学报告,5,p.14339