Growing Homophilic Networks Are Natural Navigable Small Worlds
By Yu A. Malkov, Alexander Ponomarenko. 2015
10 citations recorded by the source corpus.
Navigability, an ability to find a logarithmically short path between elements using only local information, is one of the most fascinating properties of real-life networks. However, the exact mechanism responsible for the formation of navigation properties remained unknown. We show that navigability can be achieved by using only two ingredients present in the majority of networks: network growth and local homophily, giving a persuasive answer how the navigation appears in real-life networks. A very simple algorithm produces hierarchical self-similar optimally wired navigable small world networks with exponential degree distribution by using only local information. Adding preferential attachment produces a scale-free network which has shorter greedy paths, but worse (power law) scaling of the information extraction locality (algorithmic complexity of a search). Introducing saturation of the preferential attachment leads to truncated scale-free degree distribution that offers a good tradeoff between these parameters and can be useful for practical applications. Several features of the model are observed in real-life networks, in particular in the brain neural networks, supporting the earlier suggestions that they are navigable.
Subfields: Cognitive Neuroscience, Computational Theory and Mathematics, Statistical and Nonlinear Physics, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Cognitive Neuroscience
In Computational Theory and Mathematics
In Statistical and Nonlinear Physics
In Graph Learning
Citations in the corpus
- Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “One can avoid the described problem in NSW by starting the search from a node with the maximum degree (good candidates are the first nodes inserted in the NSW structure [44]), directly going to the “zoom-in” phase of the search.”
- A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, background): “An improvement direction is put forth by [19, 66] to overcome NSW’s poly-logarithmic search complexity.”