Collective navigation of complex networks: Participatory greedy routing
arXiv:1611.04395 · doi:10.1038/s41598-017-02910-x
Abstract
Many networks are used to transfer information or goods, in other words, they are navigated. The larger the network, the more difficult it is to navigate efficiently. Indeed, information routing in the Internet faces serious scalability problems due to its rapid growth, recently accelerated by the rise of the Internet of Things. Large networks like the Internet can be navigated efficiently if nodes, or agents, actively forward information based on hidden maps underlying these systems. However, in reality most agents will deny to forward messages, which has a cost, and navigation is impossible. Can we design appropriate incentives that lead to participation and global navigability? Here, we present an evolutionary game where agents share the value generated by successful delivery of information or goods. We show that global navigability can emerge, but its complete breakdown is possible as well. Furthermore, we show that the system tends to self-organize into local clusters of agents who participate in the navigation. This organizational principle can be exploited to favor the emergence of global navigability in the system.
arXiv commentSupplementary Information and Videos: https://koljakleineberg.wordpress.com/2016/11/14/collective-navigation-of-complex-networks-participatory-greedy-routing/
References in corpus (23)
- Evolutionary games on graphs
- Hyperbolic Geometry of Complex Networks
- Popularity versus Similarity in Growing Networks
- Navigability of Complex Networks
- The outbreak of cooperation among success-driven individuals under noisy conditions
- Sustaining the Internet with Hyperbolic Mapping
- Self-similarity of complex networks and hidden metric spaces
- Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
- Network Mapping by Replaying Hyperbolic Growth
- Hidden geometric correlations in real multiplex networks
- Emergence of Soft Communities from Geometric Preferential Attachment
- Network Geometry Inference using Common Neighbors
- Humans display a reduced set of consistent behavioral phenotypes in dyadic games
- Communicability reveals a transition to coordinated behavior in multiplex networks
- Navigable Networks as Nash Equilibria of Navigation Games
- A stochastic behavioral model and a `microscopic' foundation of evolutionary game theory
- Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks
- Evolutionary dynamics of time-resolved social interactions
- Evolution of the digital society reveals balance between viral and mass media influence
- A "Social Bitcoin" could sustain a democratic digital world
- Layer-layer competition in multiplex complex networks
- Competition between global and local online social networks
- Digital Ecology: Coexistence and Domination among Interacting Networks