Pattern recognition on networks using bifurcated deterministic self-avoiding walks

Joao V. Merenda

doi:10.1016/j.chaos.2025.116100

2025-05-01

PRE

Joao V. Merenda

Gonzalo Travieso

Odemir Martinez Bruno *

DOI：10.1016/j.chaos.2025.116100

原文链接

原文求助

摘要

En 中文

许多研究已专注于理解和探索网络行为及其节点的分类。另一方面，鲜有工作集中对整个网络进行分类。鉴于大数据和数据科学的时代以及海量可用信息，这项任务在当今日益重要。许多分类问题已被建模为网络，而对这些网络的正确分类有助于生物学、社会科学、技术等多个领域。已开发出多种用于提取网络特征的算法，包括确定性游客行走（DTW）算法。DTW算法是一种基于代理的方法，采用一个行走者（游客）根据确定性行走规则遍历网络。然而，传统DTW算法存在显著局限性：它允许游客在每次迭代中仅访问一个节点，即使多个节点满足行走规则标准。这一限制减少了收集的信息量，并降低了该方法捕捉网络完整复杂性的有效性。为解决此问题，我们基于DTW算法提出了一种新颖的网络特征提取方法：带分叉的确定性游客行走（DTWB）。DTWB方法通过在确定性行走规则中引入分叉，允许游客同时访问多个节点。这使得网络结构能更高效地被探索，并提取更全面的特征。此外，该方法得出的统计量揭示了重要模式。我们的结果表明，DTWB方法在分类合成（理论）网络和真实网络方面均表现出卓越性能，合成网络的准确率超过97%，在采用特定特征组合时接近100%。对于真实网络，性能因数据集而异，介于85.9%至99.4%之间。与其他方法的比较显示，DTWB方法在节点数量方差较大的数据集上表现更优，而这正是大多数真实网络的特征。

Keyword:

Networks classification

Network characterization

Pattern recognition

Self-avoid deterministic walker