Slashdot Mirror
Snowflake-Shaped Networks Are Easiest To Mend
Z00L00K sends this report from New Scientist:
Networks shaped like delicate snowflakes are the ones that are easiest to fix when disaster strikes. Power grids, the internet and other networks often mitigate the effects of damage using redundancy: they build in multiple routes between nodes so that if one path is knocked out by falling trees, flooding or some other disaster, another route can take over. But that approach can make them expensive to set up and maintain. The alternative is to repair networks with new links as needed, which brings the price down – although it can also mean the network is down while it happens.
As a result, engineers tend to favor redundancy for critical infrastructure like power networks, says Robert Farr of the London Institute for Mathematical Sciences. So Farr and colleagues decided to investigate which network structures are the easiest to repair. They simulated a variety of networks, linking nodes in a regular square or triangular pattern and looked at the average cost of repairing different breaks, assuming that expense increases with the length of a rebuilt link. ... They found the best networks are made from partial loops around the units of the grid, with exactly one side of each loop missing (abstract). All of these partial loops link together, back to a central source. ... These networks have three levels of hierarchy – major arms sprouting from a central hub that branch and then branch again, but no further. When drawn, they look remarkably like snowflakes, which have a similar branching structure.
As a result, engineers tend to favor redundancy for critical infrastructure like power networks, says Robert Farr of the London Institute for Mathematical Sciences. So Farr and colleagues decided to investigate which network structures are the easiest to repair. They simulated a variety of networks, linking nodes in a regular square or triangular pattern and looked at the average cost of repairing different breaks, assuming that expense increases with the length of a rebuilt link. ... They found the best networks are made from partial loops around the units of the grid, with exactly one side of each loop missing (abstract). All of these partial loops link together, back to a central source. ... These networks have three levels of hierarchy – major arms sprouting from a central hub that branch and then branch again, but no further. When drawn, they look remarkably like snowflakes, which have a similar branching structure.
When drawn, they look remarkably like snowflakes, which have a similar branching structure.
Except that the there's no basis for the hexagonal outline, except when remarkably trying to make them look like snowflakes.
assuming that expense increases with the length of a rebuilt link
Sounds like a pretty unlikely assumption to me - when something breaks a power line don't they usually splice in a localized repair rather than replacing the entire length between nodes? Which suggests that all broken links would be roughly the same price to repair (barring terrain difficulties, etc) regardless of length, completely invalidating the results of the study.
--- Most topics have many sides worth arguing, allow me to take one opposite you.
Wouldn't a snowflake shaped network be susceptible to rapid meltdown?
Modest doubt is called the beacon of the wise. - William Shakespeare
The aim was not to find the "best network", but the "best network without redundancy".
The point was that most networks are designed with redundancy in mind, but not all networks require that degree of reliability. For those networks where reliability is not necessary, it would be helpful to know what the lowest cost configurations are.