Transform - Relative Neighborhood Network

Given a set of points, builds a relative neighborhood network on that point set by adding lines.

 

A relative neighborhood network is a subnetwork of a Gabriel network (see the Gabriel Network topic). The links of a Gabriel network are drawn based on no points being within the circle defined by any pairwise point comparison, where the diameter of the circle is given by the distance between the points in the pair. In contrast, the relative neighborhood network draws a link if no other points appear in the area of intersection of two circles drawn centered on the points of the pair where the radius of the circles is the distance between the points of the pair.

 

images\sc_relneigh.gif

 

In the figure above, the inner red circle shows the exclusion circle applied when drawing a Gabriel network. The area indicated in gray color shows the exclusion area applied when drawing a relative neighborhood network. Note that since the relative neighborhood network excludes links to nodes in a larger prohibited area, the relative neighborhood network will have fewer links than the Gabriel network.

 

The lines created by this operator will be selected after they are created. It's a good idea to move them to a new drawing to keep the map well organized.

 

Relative neighborhood networks are very useful because they not only consider the distance between two points considered as a pair, they also take into account the distance between that pair of points and all of the rest of the points. The two points are "relative neighbors" only if they are as least as close to each other as they are to all of the other points. Relative neighborhood networks therefore include a built-in reckoning of the overall arrangement of the point set in addition to local considerations. For this reason, they tend to reveal better cluster relationships than do simple local measurements such as nearest neighbors.

 

Example

 

images\sc_nets_points.gif

 

Using the set of points above, we can create the relative neighborhood network seen below.

 

images\sc_nets_relneigh.gif

 

Note that a superset of a relative neighborhood network is created by the Gabriel Network transform operator as seen below:

 

images\sc_nets_gabriel.gif

 

 

See Also

 

Spanning Tree - The transform operator that creates minimum spanning trees.

 

Clusters - The transform operator that uses relative neighborhood networks to find clusters.

 

Notes

 

In graph theory, networks are called graphs. When searching Internet for information on these topics try searching for words like "relative neighborhood", "graph", "spanning tree", "cluster" and similar. These ideas are applied in an astonishing range of disciplines, from fungal spore distribution patterns to the characterization of finds in archeological sites.

 

The points for the examples above were created by making centroids for provinces in Mexico using the Centroids (Weight) transform operator. The points and results of the transform operators are shown in a map with a drawing of Mexico as a backdrop. We used the centroids as a source set of points because they are dispersed in a geographically interesting way. There is no meaning to the map of Mexico; however, if we were to place one antenna in the geographic center of each province and then we wished to link the antennas in a network we would likely create and study maps such as these.