Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.14279/9363
Title: Network geometry inference using common neighbors
Authors: Papadopoulos, Fragkiskos 
Aldecoa, Rodrigo 
Krioukov, Dmitri 
Major Field of Science: Engineering and Technology
Field Category: Electrical Engineering - Electronic Engineering - Information Engineering
Keywords: Complex networks;Emergence;Internet
Issue Date: 24-Feb-2015
Source: Physical Review E, 2015, vol. 92, no. 2, pp. 022807-1 - 022807-16.
Volume: 92
Issue: 2
Start page: 022807-1
End page: 022807-16
Journal: Physical Review E 
Abstract: We introduce and explore a new method for inferring hidden geometric coordinates of nodes in complex networks based on the number of common neighbors between the nodes. We compare this approach to the HyperMap method, which is based only on the connections (and disconnections) between the nodes, i.e., on the links that the nodes have (or do not have). We find that for high degree nodes the common-neighbors approach yields a more accurate inference than the link-based method, unless heuristic periodic adjustments (or "correction steps") are used in the latter. The common-neighbors approach is computationally intensive, requiring $O(t^4)$ running time to map a network of $t$ nodes, versus $O(t^3)$ in the link-based method. But we also develop a hybrid method with $O(t^3)$ running time, which combines the common-neighbors and link-based approaches, and explore a heuristic that reduces its running time further to $O(t^2)$, without significant reduction in the mapping accuracy. We apply this method to the Autonomous Systems (AS) Internet, and reveal how soft communities of ASes evolve over time in the similarity space. We further demonstrate the method's predictive power by forecasting future links between ASes. Taken altogether, our results advance our understanding of how to efficiently and accurately map real networks to their latent geometric spaces, which is an important necessary step towards understanding the laws that govern the dynamics of nodes in these spaces, and the fine-grained dynamics of network connections.
URI: https://hdl.handle.net/20.500.14279/9363
ISSN: 15393755
DOI: 10.1103/PhysRevE.92.022807
Rights: © American Physical Society.
Attribution-NonCommercial-NoDerivs 3.0 United States
Type: Article
Affiliation : Cyprus University of Technology 
Northeastern University 
Publication Type: Peer Reviewed
Appears in Collections:Άρθρα/Articles

CORE Recommender
Show full item record

SCOPUSTM   
Citations

65
checked on Nov 9, 2023

WEB OF SCIENCETM
Citations

58
Last Week
0
Last month
1
checked on Oct 29, 2023

Page view(s) 50

435
Last Week
1
Last month
5
checked on Dec 22, 2024

Google ScholarTM

Check

Altmetric


This item is licensed under a Creative Commons License Creative Commons