Contents - Index

NETWORKS > COHESION > TRANSITIVITY

PURPOSE Gives the density of transitive triples in a network. For valued networks the density of transitive triples defined more generally is given.

DESCRIPTION Three vertices u,v,w taken from a directed graph are transitive if whenever vertex u is connected to vertex v and vertex v is connected to vertex w then vertex u is connected to vertex w.  The density of transitive triples is the number of triples which are transitive divided by the number of paths of length 2, i.e. the number of triples which have the potential to be transitive.

This definition can be extended to valued data.  Strong transitivity occurs only if the final edge is stronger than the two in the original path.  This can be relaxed so that the user can define the minimum value of the final edge (weak transitivity).  For distances transitivity can be defined in terms of the number of triples satisfying the triangle inequality, and for probabilities in terms of the product of probabilities of the edges.

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

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

Adjacency - A triple xik,xij,xjk is transitive if xik is 1 whenever xij and xjk are both 1.

Strong - A triple xik,xij,xjk is transitive if xik ³ min(xij,xjk).

Weak - A triple xik,xij,xjk is transitive if whenever min(xij,xjk) ³ s then xik ³ w for user-specified s and w. s is the strong tie value and w the weak tie value.

Euclidean - A triple xik,xij,xjk is transitive if xik £ xij + xjk.

Stochastic - A triple xik,xij,xjk is transitive if xik ³ xij * xjk.

Min  value of Strong tie:
Value of  s for WEAK option described above.

Min value of Weak tie:
Value of w for WEAK option described above.

Output Dataset: (Default = 'Transitivity')
Name of file which will contain value of density of transitivity triples, where the density is the number of transitive triples divided by the number of triples.

LOG FILE Number of non-vacuous transitive triples, number of triples, number of triples in which i -j-k is a path, then the number of non-vacuous transitive triples expressed as a percentage of  number of triples and number of triples in which i -j-k is a path.

TIMING O(N^3).

COMMENTS For valued data the following choices are recommended:

Similarities - STRONG, WEAK.
Distances, costs, dissimilarities - EUCLIDEAN.
Probabilities, correlations - STOCHASTIC.

REFERENCES None.