Strong and Weak Random Walks on Signed Networks

随机游走在探索复杂网络结构方面扮演着重要角色。在传统网络上，可以使用随机游走来提取社区结构、理解节点中心性、进行链接预测或者捕捉节点之间的相似性。在带权边可以是正或负的带符号网络上，设计一种可以用于提取网络带符号结构信息的随机游走是非常困难的，特别是将图形划分为具有正边的社区和具有负边的社区之间的能力。先前的带符号网络随机游走工作集中于仅有两个这样的社区（强平衡）的情况，而这在实际网络中很少出现。在本文中，我们提出了一种带符号网络随机游走，可以捕捉具有多个这样的社区（弱平衡）的网络结构。该随机游走产生的相似性矩阵可以用于将节点聚类成对抗性社区。我们比较了所谓的强随机游走和弱随机游走的特征，包括游走长度和平稳性。通过一系列的合成和实际网络实验，我们表明基于弱随机游走的相似性矩阵可用于无监督和半监督聚类，当图形具有多个社区或者展现出链接密度的不对称性时，弱随机游走的相似性矩阵优于基于强随机游走的相似性矩阵。这些结果表明，其他基于随机游走的带符号网络算法可以通过简单地使用弱随机游走来改进。

解决问题：本论文试图提出一种能够在带权有向图中提取社区结构的随机游走算法，特别是针对边权为正负的情况。

关键思路：本论文提出了一种基于弱平衡的随机游走算法，能够更好地捕捉带权有向图中的社区结构，并得到更好的聚类效果。

亮点：本论文提出的算法在合成和实际网络中进行了实验验证，结果表明该算法在聚类效果上优于传统的基于强平衡的算法。此外，本论文提供了开源代码。

相关研究：最近的相关研究包括：1. 'Finding and evaluating community structure in networks'；2. 'Random walks on signed networks'；3. 'Community detection in networks: A survey'。