Finding the backbones of complex networks: from theory to computation

By designing novel methods to extract backbones from networks, researchers hope to gain new insight on how complex systems work and how redundancy underpins them.
Finding the backbones of complex networks. Joana Carvalho © IGC 2021. Original network provided by Rion Brattig Correia.

Networks are everywhere. When you drive your car, the road you are on is part of a network. Residential streets connect to avenues, which in turn connect to highways leading to different cities. Each with a distinct set of features, roads impact differently the network as a whole. Streets and avenues have slow speed limits when compared to highways for example, which have more lanes and heavier traffic.

The pervasiveness of networks in the world is central to the research done at the Complex Adaptive Systems and Computational Biology laboratory led by Luis M. Rocha. “We see networks in transportation, from roads to airplanes; in society, from friendship to social media; and in nature, from how genes interact with proteins inside our cells, to how distinct species are linked in the same environment”, exemplifies the principal investigator. “Finding connections everywhere made us curious to understand how simple rules of interactions can lead to complex system patterns in all these domains, or how what is often referred to as the whole, or the network, is greater than the sum of its parts”, adds Rion Brattig Correia, a postdoctoral researcher from the lab.

In a recent study published in the Journal of Complex Networks, the researchers formalize a method that extracts the backbones of networks, which define how to reach every other point in a network through their shortest path. Looking back at the grid of a city, this methodology would uncover the main group of roads that connects every neighborhood, defining the shortest distances to efficiently reach any destination. But the method was built to be applicable far beyond roads. “Understanding fundamental features such as this can affect how networks are perceived and studied across different domains”, Rion says.

The core concepts of the distance backbone method were introduced decades ago with the work of Luis M. Rocha. The mathematical theory was later further developed with Tiago Simas, now a professor at Universidade Lusófona, in Lisbon. Since then, it has been used in a variety of studies, mostly in the fields of artificial intelligence and neuroscience. Rion translated the mathematical language of the theory into computational language to further explore the method’s applications. Their work can now be found freely accessible in the form of a package, ready to use by other scientists. “There are other backbone methods available, but they have the caveat of breaking the network into disconnected islands, making some parts unreachable. A strong point of our method is that it avoids that”, Rion explains.

But the most important aspect of this method is how it extracts information on redundancy within the network. By computing the backbone, the interactions that are likely more important than others appear, revealing the system’s robustness. In the road network example, this redundancy means that some roads could be entirely removed from the grid because there are better, shorter distance alternatives to them.  “We were very surprised by the amount of redundancy present in the networks we assessed. The majority of them needs only near 10% of their connections to preserve all shortest distances. We checked and rechecked our mathematical proofs and computational analysis to make sure the results were correct—they were!”, reveals Luis M. Rocha, leader of the team that conducted the study.

Unraveling fundamental features of networks, such as their backbones and the redundancy they contain, can translate into discovering core gene interactions of cancer signaling, essential communication pathways in the brain or how to organize society to suppress the spreading of viruses, improving epidemic spread predictions. “Just like every driver on a road wants to reach their destination on time, our hope is that this backbone can contribute to speeding up our understanding of the complex networked world we live in. This pandemic has been proof of how interconnected we all are, and how simple rules of interactions can have profound consequences in our lives”, Rion remarks.

The study was developed at Instituto Gulbenkian de Ciência. Funding was granted by CAPES Foundation, Fundação para a Ciência e a Tecnologia, National Institutes of Health, National Library of Medicine Program, Fulbright Commission fellowship, and NSF-NRT.

 

Read Paper