多网络随机游走
本文综述了在网络上的随机游走的理论和应用,突出了单个和非自适应随机漫步器的简单情况。它探讨了随机游走的三种主要类型 —— 离散时间随机游走、节点中心的连续时间随机游走和边缘中心的连续时间随机游走,并深入讨论了一些应用,包括节点排名、社区检测、应答式抽样和选民模型等。
Dec, 2016
提出了一种适用于具有多个共同体的带符号网络的随机游走算法,其结果是一个相似性矩阵,可用于将节点聚类成对立的共同体。通过一系列实验表明,相较于基于强型游走的相似性矩阵,基于弱型游走的相似性矩阵在具有多个共同体或在链接密度上不对称的图中能够更好地进行无监督和半监督聚类。这些结果暗示,在带符号网络中,通过用弱型游走代替强型游走来运行其他基于随机游走的算法可能会得到改进。
Jun, 2024
本研究提出了一种基于监督随机游走的算法,结合网络结构和节点 / 边缘级属性信息进行边缘强度估计,并在 Facebook 社交图和大型协作网络上得到了验证。
Nov, 2010
本文提出了一种新的算法 Waddling Random Walk(WRW),用于估计任意大小的图相对浓度,并通过在可访问的节点路径上进行随机游走来采样子图以提高计算效率、精度与准确性。通过使用广泛使用的图形数据集,该算法在速度、精度和准确性方面都优于当前最先进的挖掘子图统计算法。
May, 2016
本篇研究提出了一种基于高阶网络结构的新型随机游走模型,探究高阶网络中的扩散过程及其对信息扩散的影响,旨在揭示复杂网络系统中偏向性信息传播机制并成功应用于多特征对象分类任务中。
Nov, 2019
通过对图的随机游走产生机器可读的记录,并通过深度神经网络处理这些记录,直接进行顶点级或图级的预测,我们重新审视了图上机器学习的一个简单思想。我们称这些随机机器为随机游走神经网络,并表明我们可以设计它们成为同构不变并具备概率下图函数的通用逼近能力。一个有用的发现是,只要顶点匿名,几乎任何种类的随机游走记录都保证了概率不变性。这使得我们能够以纯文本的形式记录随机游走,并采用语言模型读取这些文本记录以解决图任务。我们进一步使用马尔科夫链理论中的工具,建立了与消息传递神经网络的并行性,并表明随机游走神经网络在构建过程中减轻了消息传递中的过度平滑,而概率性不达到则表现为概率性不足。我们展示了基于预训练模型的随机游走神经网络能够解决图上的一些难题,如分离三阶通用 WL 测试失败的强正则图、计数子结构和在 arXiv 引用网络上进行传导分类,而无需训练。代码可在此链接中获取。
Jul, 2024
该论文提出了一个基于随机游走的图嵌入分析框架,包括三个组件:随机游走过程、相似性函数和嵌入算法,该框架不仅可以分类许多现有方法,而且自然地激发新方法,通过它,我们演示了改进下游任务性能的多个尺度嵌入的新方法。此外,我们还发现,基于自协方差相似性的嵌入,在与点积排名进行链路预测时,比基于点互信息相似性的最先进方法表现提高了多达 100%。
Oct, 2021
本研究探讨在具有任意度数分布的随机不相关网络中的有偏随机游走过程,并推导了平稳占据概率和两个节点间的平均传输时间的精确表达式,同时探讨了循环搜索对传输时间的影响,为复杂网络上与运输相关问题的理论处理以及关键的数据包生成率的定量估计提供基础。
Sep, 2007
本文提出了一种基于随机行走的 LART 算法,用于在多层次网络中检测出共享的社区结构,并基于此导出一个节点不相似度度量,最终采用分层聚类的方法得出节点分类。实验证明,相较于其他相关的社区检测算法,LART 在模拟多种情景时表现优异。
Jul, 2015