Contents - Index

NETWORK > COHESION > DISTANCE

PURPOSE Constructs a distance or generalized distance matrix between all nodes of a graph and gives some cohesion measures based on this matrix. The routine also provides the facility to transform this matrix from distance to nearness.

DESCRIPTION The length of a path is the number of edges it contains.  The distance between two nodes is the length of the shortest path.  The generalized distance is the length of an optimum path.  

This optimum can be any of the following:
The cost of a path is the sum of all values on the edges of a path.  The optimum is the cheapest cost.

The strength of a path is the strength of its weakest link.  The optimum is the strongest path.

The probability of a path is the product of the probabilities of its edges.  The optimum is the most probable path.

If there is more than one optimum path then the algorithm uses the shortest optimum path.  For a binary adjacency matrix distance and generalized distance will be equivalent.

The distance matrix can be converted to a nearness matrix by means of a nearness transformation.  This transformation can be achieved by taking reciprocals, linear transformations, exponentiation or frequency decays.
 
The harmonic mean of the entries in the distance matrix (that is the normalized sum of the reciprocal of all the distances) is a distance based cohesion measure called compactness. This has a value of 1 when the network is a clique (everyone is adjacent) and zero when the network is entirely made up of isolates. The distance weighted fragmentation is 1 minus compactness. The routine also calculates  the average distance between all reachable pairs of vertices, the compactness and the distance weighted fragmentation on the non-transformed distance matrix.That is the matrix of distances and not the matrix of optimum values.

PARAMETERS
Input dataset
Name of file containing dataset to be analyzed. Data type: Valued graph.

Type of Data: (Default = ADJACENCY)
Choices are:

Adjacency - standard binary data, distance corresponds to graph theoretic geodesic.
Strengths - values indicate cost or lengths of links between nodes. Optimum is strongest path.
Costs - values indicate strengths, capacities or cost. Optimum is the cheapest cost.
Probabilities - values indicate probability of link and restricted to [0,1].  Optimum is most probable path.

Nearness transformation: (Default = NONE)
Converts distance matrix to a nearness matrix by a variety of methods.
Choices are:

None - no transformation is applied and raw distances are given as output.

Multiplicative - distances between nodes are divided into the largest possible distance.  New values are given by Yij = (N-1)/Dij.

Additive - distances between nodes are subtracted from the total number of nodes.  New values are given by Yij = N - Dij.

Linear - distances between nodes are transformed linearly into [0,1].  New values are given by Yij = 1 - (Dij - 1)/(N-1).^

Exponential - distances between nodes are transformed using exponential decay.  New values are given by Yij = b^Dij.  The attenuating factor b is selected by the user and should satisfy 0 < b < 1.

Freq Decay - Uses Burt's 1976 frequency decay function.  The nearness of i and j is one minus the proportion of actors that are as close to i as j is.

Attenuation Factor: (Default = 0.5)
Value of the attenuation factor b when exponential is chosen.  Larger values give slower decay.

Output dataset: (Default = 'GeodesicDistance')
Name of data file containing distance matrix.

LOG FILE Average value of distances, compactness and distance weighted fragmentation. Table of frequencies giving geodesic length, frequency it occurred and proportion of pairs of each distance followed by the matrix of distances (or nearness if transformation applied) between all pairs of nodes.

TIMING O(N^3)

COMMENTS Note the distances correspond to the number of links and not the optimum values.
Optimum values are calculated by NETWORK>COHESION>REACHABILITY

REFERENCES Doreian P (1974).  'On the connectivity of social networks'. Journal of Mathematical Sociology, 3, 245-258.

Burt R (1976).  'Positions in networks'.  Social Forces, 55, 93-122.