September 1973

Preliminary Clarification of Some Problems of Processing Networks of Entities

in Order Meaningfully to Map Psycho-social Relationships

- / -


[also searchable [PDF version]


Introduction

There are a series of problems to be solved in order to process sequentially ordered entities whose interrelationships are given
into    

  1. A three-dimensional spherical volume in which the entities should be positioned with minimum distortion of their relationships;
    followed by  
  2. Reduction of the three-dimensional projection to a projection onto the surface of a sphere;
    followed by  
  3. Reprojection to permit plotting of the sphere surface on a planar surface.

The solution to such problems, adapted to the processing of relationships held on magnetic tape, should be used to supply meaningful maps of relationships between psycho-social entities, such as described in the following papers by the author, namely:

or even between all three as suggested in

Generalization of problem situation

We have a series of sequentially labelled nodes

P1, P2........Pn

where n is known and not a large number.

There are directed arcs either PiPj or PjPi linking some of these nodes.  There may be many arcs linking to a particular node

The arcs may be of two main types:

PiPj'

PiPj"

(Arcs of the second type have several sub-types:

PiPj"a, PiPj"a

PiPj"e, PiPj"d

whose differences do not affect the problems discussed here but may affect the data formats and the mapping symbols used to plot the results .)

PROBLEM 1  : Allocation of the nodes to positions in a 3-dimensional sphere

1.  It is desired that the more connected nodes should be positioned more towards the centre of the sphere relative to the less connected nodes.  This rule is however modified by seven considerations:

1.1 The arcs of the type PiPj indicate that Pj is dependent upon Pi.
Pi should therefore be located more towards the centre than Pj.

1.2 If Pj is otherwise relatively poorly connected, it may be positioned anywhere on a rough sphere around the location of Pi.  The latter needs only be done if there are several such nodes equally dependent upon Pi whose non-arc relationship to each other in the 3-D space need to be most equitably distributed in relation to Pi  This applies not only to nodes directly dependent on Pi but also to those nodal complexes dependent upon Pj . Although in such a case the nodal complex is treated as a whole (and not decomposed) in positioning it in relation to Pi.  It may however be decomposed to position its components in relation to Pj.

1.3 A node may not be as close to the centre as any node on which it is dependent, except when there are nodes almost
solely dependent on it as in 1.2. (in which case the distance separating the locations of Piand Pj should be relatively
small). 

1.4 The extent to which Pi is displaced towards the centre is increased if other nodes linked to Pi are in relation of
dependency to it,  Each node may thus have a constituency of successive sub-nodes at several removes (in a tree-type
relationship to it).  The extent of the increase in the displacement towards the centre is proportional to the relative importance of the constituency of sub-nodes.

1.5 On a similar basis to 1.4, if the constituency of nodes linked  to Pi by arcs of the type PiPj" is strong relative to otherwise equivalent nodes (i.e. those located the same distance from the centre), the displacement of Pi towards the centre is increased -- otherwise it is displaced outwards in proportion to any relative weakness.

1.6 It is not required that the positioning of nodes in the spherical volume give rise to a uniformly decreasing density gradient from the centre outwards.  The core of the sphere may be relatively less dense, just as there may be localized volumes of high density further out.

1.7 Rather than work in terms of "nodal constituencies" which requires complex searches of the network of nodes, it is preferable that the nodes should be weighted according to their degree of connectedness.  Starting from a unit value, the node should be weighted upwards by the number of nodes to which it is connected, other than those to which it is connected by dependency relations of the form PjPi'. This gives an initial weighting differential as a basis for iteration, so that the relative importance of a nodes constituency is finally represented by the nodal weighting after iteration.  (Since each additional iteration effectively represents sensitivity to arcs at one further remove, the value of this additional weighting of each successive iteration should be decreased to achieve convergence.)

2.  The nodes must be well distributed around the three dimensional space.  This suggests the introduction of other rules concerning the distance between nodes.

2.1 The network of nodes will tend to pull in towards the centre due to the rules outlined in points 1.1. to 1.7.  Initial
positioning can be arbitrary on the surface of concentric spheres.  A particular node being allocated arbitrarily on
a sphere the relative length of whose radius is proportional to the relative value of the nodal weighting.

2.2 The initial situation of 2.1. will be fairly distorted.  There will be a "cramping" effect on some nodes.  Clearly there
must be a certain tolerance of distortion but when this is exceeded a node, or nodal complex, must be repositioned.
The following rule seems fairly appropriate.  The larger the number of (or nodal weighting due to nodes dependent on a
given node (PiPj'), the longer the average distance of separation from nodes to which it is linked by relationships
of the form PiPj" or PjPi' (i.e. on which it is dependent).

2.3 When the above constraints prevent repositioning around the centre, the whole nodal complex may be positioned with
less distortion further outwards -- as a volume of relatively high nodal density.

PROBLEM 2 : Allocation of nodes in a three-dimensional spherical volume to positions on the surface of a sphere with minimum distortion

2.4.  The solution to Problem 1 gives for each node a

latitude
longitude
distance from centre

which is in effect the optimum relative weighting of the node.  Information on the 

distances between nodes
angular separation of nodes is also available.

2.5.  One approach to the solution of Problem 2 is to move, outwards from the centre of the spherical volume, a spherical surface which would "collect" the most central nodes first.  Each such node may be assumed to generate a circular area which may or may not be contiguous with that of other nodes encountered at the same time.  The node may be considered to remain at the centre point of each such area. As each successive layer of nodes is encountered, these must be converted, according to the following rules, into areas on the surface. (N.B.  When performing this exercise on computer options required may be to map one sector of the volume

as a sector
as a complete spherical surface.)

2.6 If the node is a direct dependent of a node previously encountered, then it generates a sub-region within the area of the node on which it is dependent.

2.7 If a node is not a direct dependent of another node, then it generates a new area, positioned in relation to the other
according to its position in the 3-D volume.

2.8.  If a network connection (arc of type PiPj") is encountered, then it is mapped onto the surface as a line between area
centres. (N.B.  This must probably be performed as a second operation, since network connections to a not yet-encountered node further out would not be possible.)

2.9.  If a node at the same level is encountered which is unconnected to those previously encountered (at a higher level), then the area created should be contiguous with only those areas representing nodes with which it is directly connected.

2.10.  The increase in relative size of areas as the surface moves out is governed by the following:

If an area encounters many dependent nodes its size increase is increased relative to the average

In the exceptional case that directly dependent nodes are encountered before the node on which they centre, the centre node area should grow to include all the dependent nodes.

2.11.  Clearly as the sphere moves out, it will encounter nodal complexes which are relatively unconnected to nodes represented by areas on which they would otherwise be projected.  Such new areas must be displaced away from the already existing area. In effect such new areas enter at an appropriate interstice, and are contiguous or not with previous areas according to rules above.

3. In case of conflict of the previous rules, an arbitrary rule is requested to determine whether there should be contiguity of areas.

3.1.  When a new area could be a component of two or more major areas, it is allocated by comparison of the relative strengths of the arcs or the nodal weightings pulling it to different positions. If the comparison shows

one very strong, one or more very minor, then it goes as a component area of the stronger

one very strong, one relatively strong, then it becomes an "enclave" of the weaker in the stronger

two or more equally strong, then it becomes an independent "condominium" area, contiguous  if possible with all the areas on which it is dependent, otherwise non-contiguous with all of them and subject to whatever other rules may apply.

two or more equally weak, then it behaves as for the previous case.

3.2.  The original degree of angular separation of the centre node (of an area) and the new point encountered weights the probability of the new area being contiguous:  High angular separation, low probability.

4.1 Gaps between areas increase in area in same way as areas themselves.

4.2 Gaps are inserted at places on the line between contiguous areas if the number of low-level (local) links across the boundary falls below the average as the sphere moves out. These increase in size, if the linking does not compensate.

PROBLEM 3a : Projection of a mapping on the surface of a sphere to permit it to be plotted on a planar surface. A simple algorithm is required to permit production of the plot of the surface of the sphere into lozenge-shaped sectors.  These can then be cut out and folded onto the surface of a sphere.

PROBLEM 3b : Projection of a mapping on the surface of a sphere onto a planar surface with minimum distortion This is the standard problem of geographers concerned to produce world maps with minimum distortion.


creative commons license
this work is licenced under a creative commons licence.