Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space

Abstract

The idea of minimum curvilinearity (MC) is that the hidden geometry of complex networks, in particular when they are sufficiently sparse, clustered, small-world and heterogeneous, can be efficiently navigated using the minimum spanning tree (MST), which is a greedy navigator. The local topological information drives the global geometrical navigation and the MST can be interpreted as a growing path that greedily maximizes local similarity between the nodes attached at each step by globally minimizing their overall distances in the network. This is also valid in absence of the network structure and in presence of only the nodes geometrically located over the network generative manifold in a high-dimensional space. We know that random geometric graphs in the hyperbolic space are an adequate model for realistic complex networks: the explanation of this connection is that complex networks exhibit hierarchical, tree-like organization, and in turn the hyperbolic geometry is the geometry of trees. Here we show that, according to a mechanism that we define similarity attachment, the visited node sequence of a network automaton can efficiently approximate the nodes' angular coordinates in the hyperbolic disk, that actually represent an ordering of their similarities. This is a consequence of the fact that the MST, during its greedy growing process, at each step sequentially attaches the node most similar (less distant) to its own cohort. Minimum curvilinear automata (MCA) displays embedding accuracy which seems superior to HyperMap-CN and inferior to coalescent embedding, however its link prediction performance on real networks is without precedent for methods based on the hyperbolic space. Finally, depending on the data structure used to build the MST, the MCA's time complexity can also approach a linear dependence from the number of edges.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1707.07325, arXiv:1707.09496

References in corpus (11)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Self-similar community structure in organisations
• What's in a crowd? Analysis of face-to-face behavioral networks
• Popularity versus Similarity in Growing Networks
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Network Mapping by Replaying Hyperbolic Growth
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction

Cited by in corpus (6)

• Network Geometry
• Progresses and Challenges in Link Prediction
• Link prediction with hyperbolic geometry
• Link persistence and conditional distances in multiplex networks
• Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks