Combining graphlets and random walks for capturing complex network topology

Why the shape of connections matters

From social media friendships to airline routes and protein interactions in our cells, many systems can be described as networks of nodes linked by connections. A popular way to study such webs is to send out "random walkers" that hop from node to node and see which ones they visit together. This approach powers tools from web search to recommender systems. But in many real situations, a node’s role depends not only on who it is linked to, but also on the small patterns formed by groups of neighbours. This study asks a simple question with big consequences: are today’s random walk methods really seeing the full picture of these patterns, or only a blurry version?

Two lenses for looking at a network

The authors compare two ways of describing how nodes sit inside a network. The first, familiar view uses random walks. Imagine dropping a token on a node and repeatedly choosing a neighbouring node at random; by counting how often pairs of nodes appear along these walks, one can map which nodes are close in the network. The second, newer view focuses instead on small building blocks of the network, called graphlets. These are tiny sub-networks of three or four nodes that can form shapes like chains, triangles, or squares. By noting how often two nodes share specific positions in these shapes, the authors capture not just that nodes are connected, but how they jointly participate in local patterns.

A finer map of who does what

To turn this graphlet idea into a practical tool, the study introduces "orbit adjacency". Rather than only counting whether two nodes appear together in a small pattern, orbit adjacency records the exact roles they play in that pattern: for example, whether one node sits at the center of a triangle while the other sits at a corner of a chain. The team also develops a fast algorithm, GRADCO, that can compute all of these counts in minutes even for networks with tens of thousands of nodes. This makes it possible to feed orbit adjacency information into modern machine learning methods, treating each node as a point in a low-dimensional space that reflects its structural role in the network.

What random walks miss

Armed with this finer description, the authors perform a theoretical autopsy on random walks. They show that for walks of a given length, such as two or three steps, only certain small wiring patterns ever influence how often pairs of nodes co-occur. Many other graphlet patterns simply never show up in the random walk statistics. Even among the patterns that do appear, random walks always blend several of them together into a single combined signal, with fixed weightings set by the walk length rather than by the needs of a specific task. This means potentially useful structural clues may be drowned out or mixed with less relevant ones, limiting how well random-walk-based methods can distinguish different node roles.

Testing on real-world networks

The authors then put both approaches to the test on 40 networks drawn from social, technological, and biological domains. For each network, nodes carry labels such as user interests, airport activity types, scientific fields, or biological functions. The goal is to predict these labels from the network alone. Across most datasets, representations built from orbit adjacency either match or outperform those based on random walks, including popular methods like LINE and DeepWalk. Notably, orbit adjacency does well even when it only considers very small patterns of up to four nodes, while random walks are allowed to roam much farther through the network. This suggests that carefully capturing and separating local wiring patterns is often more valuable than simply looking further away.

What this means for future network tools

In everyday terms, this work shows that current random walk tools see networks in broad strokes: they know which nodes tend to be near each other, but not precisely how they share local structures. Orbit adjacency acts like a higher-resolution lens, revealing which pairs of nodes occupy similar roles inside triangles, chains, and other basic shapes. Because many real systems link structure to function, this sharper structural view leads to better predictions of what nodes do in the network. The study therefore argues that analysts should move beyond random walks when they care about the detailed wiring of complex networks, and that orbit-based descriptions offer a powerful and interpretable way to do so.

Citation: Windels, S.F.L., Malod-Dognin, N. & Pržulj, N. Combining graphlets and random walks for capturing complex network topology. Sci Rep 16, 14902 (2026). https://doi.org/10.1038/s41598-026-44410-x

Keywords: network topology, random walks, graphlets, network embedding, node classification