This folder contains code and data from the paper
"Network Geometry Inference Using Common Neighbors"
F. Papadopoulos, R. Aldecoa and D. Krioukov
Physical Review E 92, 022807 (2015)

Specifically, it contains the following:

1) HyperMap-v1.tar.gz: First release of HyperMap using common-neighbors inference.

2) src/: HyperMap embedding source code implementing the common-neighbors
inference for high degree nodes, the link-based inference for the rest of the nodes, 
and the speedup heuristic (i.e., it is the fast hybrid method--default value for 
k_speedup is 0, please see the running instructions below).

3) AS_topologies/: Folder containing the six AS Internet topology snapshots from
Sept. 2009-Dec. 2010, along with their inferred coordinates as described in
Section VI of the paper.

(For the code implementing the E-PSO model described in the paper please see the 
corresponding code available for


HyperMap is a C++ program implementing the fast hybrid method described in
"Network Geometry Inference Using Common Neighbors". 


Download the compressed .tar.gz file containing the latest version of HyperMap, extract and enter the directory:

tar -xvzf HyperMap-v1.tar.gz
cd HyperMap-v1

To compile, use:


To run:

./hypermap -i graph.txt -g gamma -t temperature

- graph.txt: File containing the network to embed. Each line must be of the form

    id_1 id_2

    if node with id_1 is connected with node with id_2. Links are assumed
    bidirectional, so that if id_1 id_2 is present in graph.txt then id_2 id_1
    should not be present (see for example the AS topologies under the
    AS_topologies folder.)

- gamma: Value of the exponent of the power-law degree distribution

- temperature: Temperature of the network to embed (see paper).

Optional command line parameters:

 - '-z zeta': Curvature of the hyperbolic space (default: 1).
 - '-k k_speedup': The speedup heuristic is run for all nodes with degree k < k_speedup (default: 0, i.e., the speedup heuristic is not run by default, see paper).
 - '-m m_in': Expected initial node degree (default: 1, see paper).
 - '-L L_in': Internal link rate (default: L = (kbar-2*m)/2, where kbar is the average node degree in the input graph, see paper).

 - '-o outFile': Name for the output file that will contain the inferred node coordinates (default: coordinates_embedding.txt).

 - '-c yes/no': Activate/Deactivate the correction steps detailed in the paper (default: yes).
The output of the program is the file coordinates_embedding.txt, which contains
the inferred angular and radial coordinates of each node in graph.txt. Each
line is of the form

  id angular_coordinate radial_coordinate

where id is the node label, angular_coordinate is the node’s angular coordinate
(in [0, 2*pi]) and radial_coordinate is the node’s radial coordinate.

There are some more comments at places inside the code, clearly separating the
blocks of code where the inference is performed using the common-neighbors and
link-based methods, as well as the sections where the speedup heuristic is
implemented, and where "correction steps" are also implemented. Please see the
paper for more details.