Which Connections Matter? Edge Importance Depends on What the Network Is Doing

Johannes Falk on April 30, 2025 · 13 min read

How important is a single edge for what a network does? We compare the dynamics on a network with and without that edge, aligning the random events so that the missing link, not the noise, drives the difference. The answer depends strongly on the dynamics: excitable processes lean on central edges, pattern formation is largely decoupled from topology, and the macaque cortex has an unusual set of edges that matter for short transients.

Which edges in a network matter most? Network science has a quick answer: compute an edge centrality, such as betweenness, and rank the edges by it. But that answer treats the network as pure topology.

Most networks are not. A brain network carries activity, a supply chain carries goods, a social network carries opinions and rumours. If the question is how much an edge matters for what the network does, static measures are at best a proxy. Removing one link can have no effect at all, or it can change the long-term behaviour of the entire system, and which of the two happens depends on the dynamics running on top.

In work led by Dzmitry Rumiantsau, together with Piotr Nyczka and Marc-Thorsten Hütt, we developed a way to measure this dynamical edge importance directly. We tested it on two very different kinds of dynamics and on the cortical network of the macaque.

Measuring importance by taking an edge away

The basic procedure is simple. Take a network $G$ and a dynamical model. Pick an initial state and run the dynamics twice: once on $G$, once on $G$ with a single edge removed. Then compare the two runs, node by node and time step by time step. The fraction of nodes that are in a different state, averaged over time and over many initial states, is the dynamical importance of that edge. Repeat this for every edge whose removal does not split the network, and you obtain a distribution of edge importance.

What sounds simple in theory quickly runs into practical problems, and which problems arise depends on the dynamics. To show this, we used two models that differ in almost every respect:

1. The SER model is a minimal model of excitable dynamics, widely used as a caricature of neural activity. Each node is susceptible (S), excited (E) or refractory (R). A susceptible node becomes excited if a neighbour is excited (or spontaneously with a small probability $f$), an excited node becomes refractory, and a refractory node recovers with probability $p$. The model is stochastic.
2. A totalistic cellular automaton (CA) is a minimal model of pattern formation. Each node is 0 or 1 and flips its state whenever the fraction of active neighbours exceeds a threshold $\kappa$. The model is deterministic, and depending on $\kappa$ it either converges to a fixed point or cycle, or behaves chaotically.

Each model brings its own difficulty. The SER model is stochastic, so two runs differ even if nothing about the network has changed; how we deal with this is the subject of the next section. The cellular automaton is deterministic, but in its convergent regime a step-by-step comparison misses the point: two runs can pass through different transients and still reach the same attractor, or settle into the same cycle shifted by a few time steps. What matters there is where the dynamics end up. We therefore compare the two attractors, using a distance that treats shifted versions of the same cycle as identical and does not reward long cycles just for being long. In the chaotic regime, where the dynamics do not settle in practice, we compare the trajectories directly, as for the SER model.

Aligning the noise

For the stochastic SER model the naive comparison fails. Two runs from the same initial state on two networks will drift apart after a few steps simply because different random numbers are drawn, and after a while the difference between them says nothing about the edge any more.

We therefore record every random decision in the original run (which node recovers when, and which node fires spontaneously) and replay these decisions in the modified run wherever the rules of the model allow it. If a node is refractory in both runs, it recovers in both runs at the same time. If it is susceptible in both and has no excited neighbour in either, it fires spontaneously in both or in neither. Only where the missing edge has already changed the local situation does the modified run draw its own random numbers. Because this cannot remove every trace of noise, each edge and initial state is simulated several times on the modified network.

This alignment is what makes long time courses usable at all. Without it, a meaningful comparison is only possible over short transients before noise takes over. With it, we can ask two different questions of the same network: what an edge does to the immediate response of the system, and what it does to its long-term behaviour.

What makes an edge important

We applied the method to 120 Erdős–Rényi (ER) random networks with 50 nodes and 100 links, and to 120 Barabási–Albert (BA) scale-free networks with 50 nodes. We then compared the resulting importance with seven classical topological properties of the edges, from degree and betweenness centrality to clustering and topological overlap.

A single edge can matter a lot. For SER dynamics on ER networks, removing one edge leaves, on average, more than 30% of the nodes in a different state in some parameter regions. On BA networks the effect never exceeds 20%.

In excitable dynamics, central edges are important, but which centrality depends on the dynamics. When nodes recover slowly ($p = 0.1$), long-term edge importance on ER networks correlates with betweenness centrality (correlation 0.4). When they recover quickly, it correlates more strongly with the degree and eigenvector centrality of the edge’s endpoints (correlation above 0.6). Our hypothesis: fast recovery lets hubs pass on the differences caused by the missing edge more frequently, spreading them through the network.

Transients see different edges. Based on short transients, about 2.5% of the edges in ER networks are more than two standard deviations above the mean importance. Based on long time courses, it is 0.7%. The immediate response of a network is carried by a small set of sensitive edges that the long-term behaviour does not reveal.

In pattern formation, topology explains little. For the cellular automaton, edge importance on ER networks is largely decoupled from all the topological measures we tested. The range of importance values is set by the degree distribution, but which individual edge is important cannot be read off its topological position. The exception is the high-$\kappa$ regime on BA networks, where importance correlates with the degree of the endpoints at about 0.9: removing a link between two hubs makes them switch one step earlier, and the difference propagates through the network into a different attractor.

Different dynamics, different important edges. In an intermediate range of the CA threshold $\kappa$, SER and CA edge importance show no significant correlation. Outside this window they do correlate, positively or negatively, and in those cases both are driven by the same topological property. Which edges a network depends on is therefore not a property of the network alone. It is a property of the network together with the process running on it.

The macaque cortex

To see whether the method gives meaningful answers on real data, we applied it to the network of cortical areas of the macaque monkey. We kept a connection only if it exceeds a strength threshold in both directions, which leaves 29 areas and 89 connections. As a reference we used 60 randomized versions of the network, in which the edges are rewired while every node keeps its degree.

For long-term excitable dynamics, the real network looks similar to its randomized counterparts, with somewhat more edges of very low importance. In other words, the long-term activity of the real cortex network is slightly more robust against losing a link.

For short transients the picture changes.

The real network contains a group of edges with much higher importance than the randomized networks typically produce. Edges more than two standard deviations above the mean are on average 44% more frequent in the real cortex, and the difference between the real and randomized distributions is significant for every recovery probability. These edges have high betweenness and low topological overlap: they are bridges between parts of the network that are otherwise not tightly connected.

This is consistent with a network that is robust in its ongoing activity and, at the same time, sensitive in its immediate response to a stimulus, two plausible features of a system whose job is to process inputs. One caveat matters here: the randomization preserves degrees but not clustering. The real network has 88 triangles, the randomized versions only about 38. A strongly clustered network naturally consists of dense groups linked by few bridges, so part of the effect may be a consequence of clustering rather than a feature specific to the cortex. Separating the two would require null models that also preserve clustering.

The cellular automaton shows how strongly this matters. Its edge importance in the real network is shifted to lower values than in the randomized networks, and the gap grows with $\kappa$. The likely reason is again the triangles: the comparison reveals how strongly the cellular automaton depends on them.

What this is good for

Edge importance is not a number that can be computed once for a network and then used for everything. Looking beyond the models studied in the paper: whether one wants to protect the links of a power grid, block the paths of an epidemic or understand a brain network, the useful question is always important for which dynamics, on which time scale. Static centrality measures answer that question for some dynamics and fail for others.

The method also works the other way round. Instead of removing an existing edge, one can add an edge that is not yet there and measure how much it changes the dynamics. This connects directly to our earlier work on structural insulators and promotors, where a single added shortcut could speed up a distributed coordination task or block it entirely.

Our study is a first step: the networks are small (50 nodes for the model networks, 29 for the macaque cortex), unweighted and undirected, and an analytical version of the approach is still out of reach even for specific models. But the differences between dynamics are themselves informative. In the macaque network, edge importance under excitable dynamics is lower than under the cellular automaton, which fits a network that evolved to handle excitations. With a well-chosen set of dynamical models, comparing their importance distributions could lead to a definition of network function that is rooted in dynamics, a way to determine what a network is actually for.

Frequently Asked Questions

What is dynamical edge importance?

It quantifies how much a single edge matters for a specific process running on a network. We run the same dynamics from the same initial state on the original network and on the network without that edge, and measure how different the two runs are, either as the average fraction of nodes in different states or as the distance between the attractors the two runs end up in.

Why not just use betweenness or degree centrality?

Because they answer a different question. For excitable dynamics, central edges are indeed important, but which centrality matters depends on the model parameters. For pattern-forming cellular automata, edge importance is largely unrelated to any of the seven topological measures we tested. Static measures can be a good proxy for some dynamics and a poor one for others.

How can two runs of a stochastic network model be compared fairly?

By aligning their random events. Every recovery and every spontaneous excitation in the original run is recorded and reused in the run on the modified network, wherever the model rules permit it. This keeps the two runs close, so that their difference mainly reflects the missing edge rather than the noise. Without alignment, only very short time courses could be compared meaningfully.

How robust is the macaque cortical network to losing a single connection?

In the network of cortical areas of the macaque (29 areas, 89 connections), it depends on the time scale. For long-term excitable dynamics, the real cortical network is slightly more robust against edge removal than randomized networks with the same degrees. For short transients, it contains about 44% more highly important edges, typically bridges with high betweenness and low topological overlap. This is consistent with a network that is stable in its ongoing activity and sensitive in its immediate response to input, although part of the effect may stem from the network’s strong clustering.

Do the same edges matter for every process?

No. In an intermediate parameter range, edge importance under excitable dynamics and under cellular automata is uncorrelated, and where the two do correlate, it is because both depend on the same topological property. Even within one model, short transients and long-term behaviour highlight different edges. Which edges are important is a property of the network together with the dynamics, not of the network alone.

References

• Rumiantsau, D., Falk, J., Nyczka, P., Hütt, M.-T., 2025. Categories of important edges in dynamics on graphs. R. Soc. Open Sci. 12, 241086. https://doi.org/10.1098/rsos.241086
• Messé, A., Hütt, M.-T., König, P., Hilgetag, C. C., 2015. A closer look at the apparent correlation of structural and functional connectivity in excitable neural networks. Sci. Rep. 5, 7870. https://doi.org/10.1038/srep07870
• Marr, C., Hütt, M.-T., 2005. Topology regulates pattern formation capacity of binary cellular automata on graphs. Physica A 354, 641–662. https://doi.org/10.1016/j.physa.2005.02.019
• Markov, N. T. et al., 2014. A weighted and directed interareal connectivity matrix for macaque cerebral cortex. Cereb. Cortex 24, 17–36. https://doi.org/10.1093/cercor/bhs270