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
- A
three-dimensional spherical volume
in which the entities should be positioned with minimum distortion of their
relationships;
followed by
- Reduction
of the three-dimensional projection to a projection onto the surface of
a sphere;
followed by
- 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:
- organizations
- problems
- World problems and human development, Brussels, Union
of International Associations, 1972
- concepts
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. |
|
