Go to Google Home
Go
A data-code-compute resource for research and education in information visualization
InfoVis Home Learning Modules Software Databases Compute Resources References

Software > Hypergrid Network Model

Description | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments

line
Description

The Hypergrid model for Peer-to-Peer (P2P) systems [1] builds a graph topology that enforces low graph diameter and fixed node degree. The Hypergrid graph grows as a simple k-ary tree with nodes on the leaf level of the tree having their k-1 free edges randomly connected to other nodes on the same level in the tree with degree less than k.

Initially graph consists of a single node with no edges. For a new node N to join the graph, it looks for a parent node in the graph which has free edges. A horizontal edge between the parent node and another node, on the same level as that of parent node, is removed. The new node then connects to this parent node and also to k-1 other nodes on the same level in the graph. A typical hypergrid network layout is given above.


line
Pros & Cons

Applicable to network graphs only.  Hypergrid model imposes minimal network growth policies. It focuses on growing a network with the desirable low diameter of small world systems using only local information. It strives for complete decentralization of network growth and is topologically more robust. But the search cost on Hypergrid network models is very high.


line
Applications

These algorithms can be used to generate unstructured P2P graphs based on Hypergrid topology. These graphs can then be visualized and analyzed using Pajek or any other network visualization program.


line
Details

Pseudo code:

1. Identify the innermost member maintaining “horizontal” connections.
2. Request one of these links to be terminated and reallocated (becoming 
   “vertical” in the process)
3. Attempt to initiate k 1 horizontal links with other nodes belonging 
   to the same layer and advertising a spare connection.

line
Usage Hints

In the IVC Software Framework, simply select Modeling > P2P > Unstructured > Hypergrid to generate a network. Recommended degree = 2log M + c, where M is the network size and c is a constant (c < 6). Use any search algorithms via the Analysis > Search menu to analyze the network.


line
References
  • Saffre, Fabrice and Robert Ghanea-Hercock. Beyond Anarchy: Self-Organized Topology for Peer-to-Peer Networks. Complexity, 9(2):49:53, 2003.


line
Acknowledgments

This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework.

line

Information Visualization Cyberinfrastructure @ SLIS, Indiana University
Last Modified July 10th, 2004