Pattern recognition on networks using bifurcated deterministic self-avoiding walks

Joao V. Merenda, Gonzalo Travieso and Odemir M. Bruno

Chaos, Solitons & Fractals, 2025, vol. 194, issue C

Abstract: Many studies have focused on understanding and exploring network behaviors and classifying their nodes. On the other hand, few works have concentrated on classifying networks as a whole. This task is increasingly important today, given the era of big data and data science, as well as the substantial amount of available information. Many classification problems have been modeled as networks, and properly classifying these networks can assist various fields such as biology, social sciences, and technology, among others. Several algorithms have been developed for extracting network features, including the deterministic tourist walk (DTW) algorithm. The DTW algorithm is an agent-based method that employs a walker (tourist) to traverse the network according to a deterministic walking rule. However, the traditional DTW algorithm has a significant limitation: it allows the tourist to visit only one node at each iteration, even if multiple nodes meet the walking rule criteria. This constraint restricts the amount of information collected and reduces the method’s effectiveness in capturing the full complexity of the network. To address this limitation, we introduce a novel method for network feature extraction based on the DTW algorithm: the deterministic tourist walk with bifurcations (DTWB). The DTWB method allows the tourist to visit multiple nodes simultaneously by introducing bifurcations into the deterministic walking rule. This enables a more efficient exploration of the network structure and the extraction of more comprehensive features. Furthermore, the statistics derived from this approach have revealed important patterns. Our results demonstrate that the DTWB method achieves remarkable performance in classifying both synthetic (theoretical) and real-world networks, with accuracy rates above 97% for synthetic networks and close to 100% when using certain feature combinations. For real-world networks, the performance varies by dataset, ranging from 85.9% to 99.4%. A comparison with other methods shows that the DTWB method performs better on datasets with greater variance in the number of nodes, which is characteristic of most real-world networks.

Keywords: Networks classification; Network characterization; Pattern recognition; Self-avoid deterministic walker (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077925001134
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:194:y:2025:i:c:s0960077925001134

DOI: 10.1016/j.chaos.2025.116100

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().