New method revolutionises network analysis

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 that 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. 
 

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.

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.