Towards the science of paths in networks
On what tracks are thoughts travelling in our brain? How does the Internet remain operational during disasters? What effects and side effects can a drug produce when introduced into our body? The Science of Paths on the horizon may give more accurate answers to such questions soon!
Even though most complex systems that surround us, like the human brain, the Internet, or the human society, are built over entirely different foundations (biology, technology, social interactions etc.), their underlying abstract structure, the very interconnection network, was found to be stunningly similar. Today, the research of such intricately connected networked systems is approaching a new stage: instead of studying the structure (nodes and links) of networks, researchers are questioning the fundamental ways information flows inside them, i.e., the paths over which information propagates between nodes. The reaction of cells to stress, the stability of airport networks, or the large-scale behavior of the Internet, are all fundamentally determined by the operational paths signals/passengers/packets travel through the network. Even the effects and side effects of drugs are mainly characterized by the sequence of molecules the drug interacts with.
An early-bird study concerning the system of operational paths has been published recently in Scientific Reports. The authors have built massive datasets describing traffic flows in the Human Brain, the Internet, the Airport network and a Word-morph game called "fit-fat-cat" (https://play.google.com/store/apps/details?id=hu.bme.tmit.lendulet.wordnavigationgame) and analysed information-propagation paths extracted from these datasets. Due to the wide spectrum of analysed networks, researchers of interdisciplinary origin and from multiple institutions (Department of Telecommunications and Media Informatics at Budapest University of Technology and Economics, Institute of Hungarian Linguistics and Finno-Ugric Studies at Eötvös Loránd University, Psychological and Brain Sciences at Indiana University, Brain Center Rudolf Magnus at University Medical Center Utrecht, Department of Radiology at Centre Hospitalier Universitaire Vaudois and University of Lausanne, Signal Processing Laboratory 5 at École Polytechnique Fédérale de Lausanne) have contributed to the project.
The empirically-founded study challenges the most widely adopted hypothesis about the structure of operational paths inside networks, the shortest path assumption. This venerable rule dictates that information between two nodes must flow over the shortest path between the nodes. This assumption dominates the network science research community and most fundamental network metrics (diameter, average path length, centrality, etc.) are computed accordingly. Strikingly, the empirical data gathered by the authors supports the observation that paths in various networks may be significantly "stretched" compared to the shortest ones. Moreover, the distribution of stretch is also found to be extremely similar across different networks. The authors also characterize the rules of path selection nature seems to apply when picking a path; in particular, the proposed "conform hierarchy rule" dictates that real paths must comply with the underlying hierarchy of the network. This informally means that higher-level nodes do not exchange information through lower-level ones, even if there are short paths available through them. Then the "prefer downstream" rule ensures that "traffic" avoids the network core whenever possible. Based on these simple rules the authors finally set up a synthetic algorithm which predicts traffic flows in a much more realistic fashion than shortest paths do.
Immediate application of these findings is the more accurate estimation of the network's response to various stimuli. How new tasks are being coordinated within a company? What paths rumors choose to spread out? At which airports do you change flights during your holidays? The Science of Paths is coming to help us out.
More information:
Scientific Reports 7, Article number: 7243 (2017) doi:10.1038/s41598-017-07412-4
Provided by Budapest University of Technology and Economics
