A Benchmarking Framework for Network Classification Methods
Joao V. Merenda, Gonzalo Travieso, Odemir M. Bruno · 2025
Read A Benchmarking Framework for Network Classification Methods by Joao V. Merenda, Gonzalo Travieso, Odemir M. Bruno (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06513.txt.
Introduction
Joao Merenda, Gonzalo Travieso, and Odemir Bruno present in 2025 a benchmark for methods that classify networks into kinds. Network classification matters in biology, sociology, and computing, but testing methods fairly is hard. Their data set is built from synthetic networks in set classes and subclasses, with added structural noise at varied types and levels.
Five ways of extracting features from a network were tested, from classic structural measures to walk based and embedding methods. An improved walk method won on both classes and subclasses, even under heavy noise. Automated pattern methods also did well. Classic topological measures, despite wide use, consistently scored weakest, which stresses the need for robust feature methods.
Catalog record
| CREATOR | Joao V. Merenda, Gonzalo Travieso, Odemir M. Bruno |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06513
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Benchmarking Framework for Network Classification Methods Joao V. Merenda, Gonzalo Travieso, Odemir M. Bruno Abstract Network classification plays a crucial role in the study of complex systems, impacting fields like biology, sociology, and computer science. In this research, we present an innovative benchmark dataset made up of synthetic networks that are categorized into various classes and subclasses. This dataset is specifically crafted to test the effectiveness and resilience of different network classification methods. To put these methods to the test, we also introduce various types and levels of structural noise. We evaluate five feature extraction techniques: traditional structural measures, Life-Like Network Automata (LLNA), Graph2Vec, Deterministic Tourist Walk (DTW), and its improved version, the Deterministic Tourist Walk with Bifurcation (DTWB). Our experimental results reveal that DTWB surpasses the other methods in classifying both classes and subclasses, even when faced with significant noise. LLNA and DTW also perform well, while Graph2Vec lands somewhere in the middle in terms of accuracy. Interestingly, topological measures, despite their simplicity and common usage, consistently show the weakest classification performance. These findings underscore the necessity of robust feature extraction techniques for effective network classification, particularly in noisy conditions. 1 Introduction Complex networks have emerged as a powerful way to understand the structure and dynamics of interconnected systems. Ranging from theoretical physics and mathematics to real-world applications in biology, sociology, and technology, studying complex networks offers valuable insights into how different elements interact within these intricate systems. Many natural and artificial systems, like social interactions, neural networks, and transportation systems, can be effectively modeled as networks, where nodes represent entities and edges illustrate their relationships [ 1 ] . In theoretical science, complex network analysis contributes to the understanding of fundamental principles governing large-scale connectivity, resilience, and emergence of collective behavior. The study of network topology, centrality measures, and community structures has provided key insights on many types of systems, such as ecosystems, financial markets, and epidemiological models [ 2 , 3 , 4 ] . On the applied side, network science has proven essential for designing efficient communication infrastructures, optimizing transportation logistics, and improving recommendation systems, among other fields. One of the main challenges in network analysis is extracting useful information from large, often noisy datasets. This is where pattern recognition techniques become essential. By utilizing feature extraction methods, machine learning models can uncover underlying patterns, detect anomalies, and classify networks based on their characteristics. The intersection of complex networks and pattern recognition has led to significant progress in areas such as network-based classification, link prediction, and graph representation learning. In this study, we evaluate the performance of various feature extraction methods on a newly developed benchmark network dataset. By systematically comparing these methods, we aim to contribute to a deeper understanding of how different techniques capture relevant patterns in network structures. Our findings provide valuable insights for both theoretical and applied research in network science and pattern recognition. 1.1 Background The study of complex networks has significantly evolved since the introduction of the Erdos-Rényi model in the 1960s, which led the foundation for understanding random graphs [ 5 ] . This model posited that networks are formed by connecting nodes randomly, leading to a Poisson degree distribution. While insightful, it became evident that many real-world networks exhibit properties not captured by this model. In 1999, László Barabási and Réka Albert unveiled the concept of scale-free networks, which are marked by a power-law degree distribution. Their findings revealed that networks, including the World Wide Web and biological systems, contain hubs with a far greater number of connections, contradicting the randomness that previous models had assumed. This idea of preferential attachment gave us a better understanding of the inherent diversity in complex systems [ 6 ] . The early 2000s marked a significant exploration into small-world networks, led by researchers Duncan Watts and Steven Strogatz. These networks are notable for their high clustering coefficients and short path lengths, much like social networks where people are interconnected through mutual friends. This model offered a deeper understanding of how information flows efficiently in both social and biological systems [ 7 ] . As the field progressed, researchers began integrating pattern recognition techniques with complex network analysis. This interdisciplinary approach enabled the extraction of meaningful patterns from intricate datasets, enhancing tasks such as classification, anomaly detection, and prediction within interconnected systems. For instance, the application of machine learning algorithms to network data has facilitated the identification of community structures and the prediction of missing links, thereby enriching our understanding of the underlying processes governing complex networks. This research expands on a well-established history by assessing different feature extraction methods against a newly developed benchmark network dataset. By conducting a systematic comparison, it strives to enhance our understanding of how various techniques detect relevant patterns in network structures, thereby aiding both theoretical progress and practical applications in the fields of complex networks and pattern recognition. 2 Feature extraction methods Over the years, numerous feature extraction methods have emerged. The most traditional and straightforward approach involves computing topological measures, such as mean degree, global clustering coefficient, average shortest path length, and various centrality metrics, and using them as a feature vector. More recently, advanced methods have been developed, including Deterministic Tourist Walk (DTW), Life-Like Network Automata (LLNA), and Graph Neural Networks (GNNs), which offer more powerful representations of complex network structures. In this section, we present the feature extraction methods evaluated in this study. 2.1 Structural measures In this first method, we extract structural measures from the networks to generate a feature vector. The measures used include: average degree, hierarchical degree (levels 2 and 3), global clustering coefficient, and average shortest path length. This method is the most traditional approach for pattern recognition in networks and serves as a gold standard for benchmarking other pattern recognition methods. 2.2 Life-Like Network Automata The Life-Like Network Automata (LLNA) method is a network-based extension of cellular automata designed for pattern recognition and classification tasks. In LLNA, a network serves as the underlying structure where each vertex represents a cell with a binary state (alive or dead). The automaton evolves over discrete time steps, generating a time-evolution pattern (TEP) that encodes the system’s dynamic behavior. These TEPs capture the temporal evolution of states across the network, providing a rich source of information about its structural and functional properties. By analyzing these patterns, LLNA enables the classification and characterization of different networks, making it a powerful tool for network science applications [ 8 ] . The evolution of each cell’s state in LLNA is governed by a transition function that depends on its neighborhood density, which is the proportion of alive neighbors relative to its total degree as shown in equation 1 . \sigma(v_{i},t)=\frac{1}{k_{i}}\sum_{j=1}^{N}A_{ij}s(v_{j},t) (1) where, v_{i} is the i-th vertex, k_{i} is the i-th vertex degree, A_{ij} is the adjacency matrix, and s(v_{j},t) represents the state of j-th vertex at time t The transition function follows Life-Like rules, denoted as Bx-Sy in the form BX_{0}X_{1}\cdots X_{x}-SY_{0}Y_{1}\cdots Y_{y} , where Bx defines the conditions under which a dead cell becomes alive (birth), and Sy specifies the conditions for a living cell to remain alive (survival). s(c_{i},t+1)=\begin{cases}1,&\text{if }s(c_{i},t)=0\text{ and }\frac{X_{x}}{r}\leq\sigma(c_{i},t)<\frac{X_{x}+1}{r}\Rightarrow\text{born (B)}\\ 1,&\text{if }s(c_{i},t)=1\text{ and }\frac{Y_{y}}{r}\leq\sigma(c_{i},t)<\frac{Y_{y}+1}{r}\Rightarrow\text{survive (S)}\\ 0,&\text{otherwise}.\end{cases} (2)