### Hyperbolic-Graph-Generator


The Hyperbolic-Graph-Generator is a package of tools to generate
graphs embedded in the hyperbolic plane, and to compute the efficiency
of greedy forwarding in these graphs.

More details on the graph models implemented in the package are available
at http://arxiv.org/abs/1503.05180/.

This standalone package is also a core component of the hyperbolic
routing package that is going to be integrated into the NDNSim (http://ndnsim.net).
Hyperbolic routing is greedy geometric routing in a
hyperbolically embedded network. Hyperbolic routing has attractive
scalability and efficiency characteristics. In particular, applied to
the AS Internet, hyperbolic routing is nearly optimal, i.e., maximally
scalable (http://dx.doi.org/10.1038/ncomms1063/). The NDN testbed has
been recently mapped to the hyperbolic plane yielding similar routing
efficiency (http://www.caida.org/research/routing/greedy_forwarding_ndn/).
Because of its exceptional scalability and efficiency characteristics,
hyperbolic routing is one of the routing strategies in the NDN
architecture.

The software package includes three tools (see README_INSTALL for
information on installation details):
- hyperbolic_graph_generator
- graph_properties
- greedy_routing




### Description:

1) hyperbolic_graph_generator: a tool to generate synthetic graphs embedded
   into a hyperbolic space.

NAME: 
	hyperbolic_graph_generator -- generate an hyperbolic graph compatible with user parameters 

SYNOPSIS: 
	hyperbolic_graph_generator [parameters]  

DESCRIPTION:
	The program generates a file (graph.hg is the default file name) that
	describes the geometric coordinates and the links of a hyperbolic graph
	compatible with the parameters provided by the user. The program generates
	random hyperbolic graphs according to the models in:
	            http://dx.doi.org/10.1103/PhysRevE.82.036106
	A description of how the hyperbolic graph generator works can be found at:
	            http://arxiv.org/abs/1503.05180

PARAMETERS:
	-n	graph size (number of nodes)
		default value is 1000
	-k	expected average degree
		default value is 10
	-g	expected power-law exponent gamma
		default value is 2 (infinite gamma = 10)
	-t	temperature
		default value is 0 (infinite temperature = 10)
	-z	square root of curvature zeta=sqrt(-K)
		or ratio eta=zeta/T in Soft Configuration Model
		default value is 1
	-s	random seed
		default value is 1
	-o	output folder
		default value is current folder
	-f	graph file name
		default value is graph (.hg extension is always added)
	-h	print help menu
	-q	quiet (no information print on standard output)

OUTPUT:
	The program generates a file (./graph.hg unless the -o or -f options are turned on)
	that lists the coordinates of each node in the hyperbolic space as well as the 
	adjacency list. The file format is the following:

	# The first line describes the main graph parameters:
	N <num nodes> T <temperature> G <gamma> K <avg.degree> Z <zeta> S <seed> I <initial_node_id>

	# A line for each node and its polar coordinates:
	<node_id>	<radial coordinate>	<angular coordinate>

	# A line for each link:
	<node_id>	<node id> 

	Example:
	N	100	T	0	G	2	K	10	Z	2	S	1    I  1
	1	0.000301382	0.826476
	2	0.093611	2.88178
	3	0.0786131	1.37576
	... 
	99	0.10503	3.97561
	100	0.0713906	5.18173
	1	2
	1	3
	1	4
	...
	97	98
	98	99

EXAMPLE:

	# Generate a graph of 10,000 nodes with average degree 10,
 	# whose degrees follow a power-law distribution P(k) ~ k^{-2.5}
	# The graph is written in graph_example.hg
 	# All other parameters take default values
 
	hyperbolic_graph_generator -n 10000 -k 10 -g 2.5 -f graph_example




2) graph_properties: a tool to compute some basic graph properties of the generated
   hyperbolic graphs.

NAME: 
	graph_properties -- compute properties of hyperbolic graphs

SYNOPSIS: 
	graph_properties [parameters] 

DESCRIPTION:
	The program computes some graph  properties associated with nodes of the
	hyperbolic graph provided as input (./graph.hg is default), in detail: 
	the polar coordinates of each node, its degree, its average neighbor
	degree, and its clustering coefficient.

PARAMETERS:
	-i	graph file (in hg format)
		default value is ./graph.hg
	-o	output folder
		default value is current folder
	-h	print help menu

OUTPUT:
	The program generates five text files having the following format:

	radial.txt
			<node id> <radial coordinate>
	angular.txt
			<node id> <angular coordinate>
	degree.txt
			<node id> <node degree>
	knn.txt
			<node id> <node avg. neigh. degree>
	cc.txt
			<node id> <node clustering coefficient>


EXAMPLE:
	
	graph_properties -i graph_example.hg





3) greedy_routing: a tool to test the greedy routing on hyperbolic graphs.

NAME: 
	greedy_routing -- compute the greedy routing success ratio 

SYNOPSIS: 
	greedy_routing [parameters] 

DESCRIPTION:
	The program loads in memory a hyperbolic graph (./graph.hg by default),
	it simulates the greedy routing on a set of random source-destination node
	pairs belonging to the same connected component (default is 10,000  random
	pairs), and finally outputs the success ratio (i.e. the percentage of times
	the information sent by the source node would have reached the destination
	if each node would adopt the greedy routing rules.

PARAMETERS:
	-i	input graph file (in hg format)
		default value is ./graph.hg
	-a	number of attempts
		default value is 10000
	-s	random seed
		default value is 1
	-h	print help menu

OUTPUT:
	The program print the success ratio to standard output.

EXAMPLE:

	# Test geometric greedy routing in the graph located in graph_example.hg
	# using 20,000 random pairs of nodes.
	# The seed for the random generator is 12345
	
	greedy_routing -i graph_example.hg -a 20000 -s 12345


