New method revolutionises network analysis

It shows the shortest path even when 90% of the network is hidden.

News - 17 January 2023 - Communication EWI

How do you find the fastest route if you can't see all possible links? For example when "routing" Internet traffic – something which is now done based on trust – or protein pathways in the body, insights wherein can lead to completely new understandings diseases and medicines? Scientists have been racking their brains over the question since the 1950s. Maksim Kitsak (TU Delft) is revolutionizing network analysis with his new method.  

A complex network

"Our ability to build secure Internet protocols, cure complex diseases or predict pandemics is limited by our ability to find that shortest route." - Maksim Kitsak 
Kitsak has developed a new method to find the shortest path nodes in a network, even when 90% of the network is hidden, or even polluted with fake links. He publishes his results this week in Nature Communications. 
 

Imagine I tell you that I have a friend who is the yoga instructor of Ivanka Trump, the daughter of the well-known former U.S. president. Who in turn maintains close ties with Vladimir Putin. If you have a message for Putin, just give it to me and it will get to him via the chain above. Would you trust me? Because that, in a nutshell, is how routers for Internet traffic currently work.

Maksim Kitsak

On the basis of trust

An important application of the new method is the detection of network anomalies and routing irregularities. Ideally, a router always takes the shortest path to its target router. This path is established on the basis of trust, so without systematic checks. As a result, due to a misconfiguration, or even malicious intent, internet traffic can easily take a detour, for example through a country such as Russia or Iran. Due to the organic, distributed and therefore cluttered Internet topology, a solution to this well-known problem was difficult to formulate. The method that Maksim developed together with his colleagues now lays the foundation for a solution. In this way, unnecessary deviations can be quickly detected or even prevented in the future – resulting in a safer Internet.

Finding shortest and nearly shortest path nodes in large substantially incomplete networks by hyperbolic mapping – Maksim et al. – DOI 10.1038/s41467-022-35181-w

The breakthrough can be considered the next major step in the field since the pioneering work of computer scientist Edsger Dijkstra, who in the 1950s first developed an algorithm for finding the shortest path between two nodes in a network. However, this algorithm works only under the assumption that the entire network is visible in advance, something that is almost never the case in reality.

"This is one of those problems that is easy to formulate, but extremely hard to solve. The basic idea is this: we find that shortest paths in many real networks are localized. If you can find a mapping of network nodes to points in a suitable geometric space, then the shortest paths are geometrically close to geodesic curves connecting shortest path endpoints. If so, you do not need to know all the links in a network to find shortest path nodes. You can simply draw a geodesic curve in the space connecting A and B, and nodes close to geodesic are very likely to be the shortest path nodes." - Maksim Kitsak

Of course, the new approach is not a "free lunch." Finding shortest paths in an incomplete network first requires a good geometric representation. Machine-learning provides the solution here. Even without supervision, using a method called "network embedding," a network can be mapped geometrically. And although these Machine Learning techniques need to be specified for each different network, good 'embeddings' already exist for the internet, social networks, and networks of protein interactions, allowing the geometric path-finding method to be quickly applied to each of these network types. 
Thus, Maksim's new geometric method also has applications in other areas where networks need to be analyzed, such as thus exploring protein pathways in the body, leading to a better understanding of both diseases and their treatment. It can also help analyze the spread of pandemics, such as a new COVID-19 outbreak, for example. In these analyses, often only a small part of the network is visible.
 

Digital society

We are creating a responsible digital society which will increase our wellbeing and make our world a better place. The digital society has been with us for a long time, from satellites orbiting in space, smartphones and traffic lights to robots that rid the ocean floor of plastic. The question is how to design and manage this society responsibly. A responsible digital society is based on human values, is healthy, just, inclusive and safe. It is also clean and sustainable and able to field the major complex challenges of today. At TU Delft we design and engineer both the digital technology and its social use.

Marc de Kool

Science information officer Digital Society

Available: Monday through Thursday