Triangle Transitivity in dominance hierarchies & directed graphs

The study of dominance hierarchies dates back to the 1920s, when Schjelderup-Ebbe (1922) first described the emergence of linear dominance hierarchies in flocks of chickens (this is also the origin of the expression ‘peck order’ or ‘pecking order’). Subsequently, mathematicians like Kendall & Babington Smith (1940) and Landau (1951) derived formulas to describe the structures of such hierarchies (for a good overview of these methods, see de Vries (1995–Animal Behaviour) as well as Appleby (1983–Animal Behaviour).

The methods by Kendall and Landau, however, were derived in the context of tournaments–a specific type of networks in which all asymmetric dyadic relations (e.g., dominant-subordinate) are known. This contrasts with most data on animal dominance hierarchies. Most of the time, there are pairs that are not observed to interact. To deal with this problem, various methods have been used to ‘fill in’ these unknown relations. The most common method was pioneered by de Vries (1995), in which randomization procedures are used to fill in unknown relations. Linearity indices, such as Landau’s h and Kendall’s K can then be calculated using these ‘filled’ tournaments.

However, we (Shizuka & McDonald 2012) recently showed that randomization procedures to fill in dominance data sets can obscure true patterns of transitivity of dominance relations that actually occurred. In this study, we introduced a measure we called ‘triangle transitivity’, based on the proportion of actual three-way relations that were established (i.e., triangles) that were transitive (i.e., if A beats B and B beats C, then A also beats C). We show that the random expectation of this proportion is 0.75, no matter the size or density of the network. Using this, we can evaluate how orderly dominance relations are, and whether these values correspond to existing linearity measures.

The following codes will take a dominance data set (in the form of binary dominant-subordinate relations in a matrix) and generate the relevant indices (P_t: the proportion of triangles that are transitive, and t_tri: this proportion scaled so that it is 0 for the random expectation and 1 for maximum transitivity). It also conducts a ‘conditional uniform graph test’ (think of it as a Monte Carlo procedure for testing network metrics) to test whether the given dominance set is more orderly than expected by chance.

This set of codes is published as supplemental materials in this study:
Shizuka, D. and D. B. McDonald. 2012. A social network perspective on transitivity and linearity in dominance hierarchies. Animal Behaviour.

DOI:10.1016/j.anbehav.2012.01.011

You can (hopefully) find all the details you need in that paper. Please email me if you would like me to send you the pdf, and please cite the paper if you end up using these codes in your work.

***UPDATE (9/30/2014)***

I have updated this script in two ways: (i) You can now start the script using a raw interaction matrix–i.e., you don’t have to convert the matrix to binary dominants=1 and subordinates=0; (2) I incorporated the changes from the errata in Animal Behavior, in which I point out that randomizations of very sparse dominance networks can result in some networks that contain no triangles (i.e., triangle transitivity = NA). The updated script will throw out such no-triangle random networks. Special thanks to James Curley for pointing out a simple way to convert interaction matrices into dominance (0/1) matrices.

Here are the codes:

library(statnet) 

dat=read.csv(file.choose(),header=TRUE,row.names=1,check.names=FALSE) #start with raw interaction matrix, with rows as winners/aggressors and columns as losers/receivers 

int.to.dom=function(x){ ((x>t(x)) & (x+t(x)>0))+0}

m=int.to.dom(as.matrix(dat))

g=network(m,directed=TRUE)

# We calculate P.t and t.tri for this empirical network.

tri=triad.census(g) #The full triad census as an 16-element vector 

w=as.vector(c(0,0,0,0,0,0,0,0,1,0,0,1,1,0.5,0.75,0.75)) # The weighting vector for transitivity 

N.triangle=sum(tri*as.vector(c(0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,1))) #Count and sum the number of triangles

Pt=sum(tri*w)/N.triangle 

t.tri=4*(Pt-0.75) 

Pt 

t.tri

## We now conduct 1,000 simulations of random networks with the same number of mutual, asymmetric and null dyads as the empirical dominance matrix. We calculate Pt from each of these simulated networks (r.P.t). I use a while() loop because randomizations of some sparse matrices will produce networks with no triangles. For simplicity, we just throw these out. 

dyads=dyad.census(g) 

r.p.t=vector(length=1000)

j=1

while(j<1001){

r=rguman(1,nv=nrow(m),mut=dyads[1],asym=dyads[2],null=dyads[3])

r.triad=triad.census(r)

r.p.t[j]=r.triad[9]/(r.triad[10]+r.triad[9])

if (is.na(r.p.t[j])) next else j=j+1

}

p=length(r.p.t[r.p.t>=Pt])/1000

p

Share this: