transitivity {igraph}R Documentation

Transitivity of a graph

Description

Transitivity measures the probability that the adjacent vertices of a vertex are connected. This is sometimes also called the clustering coefficient.

Usage

transitivity(graph, type=c("undirected", "global", "globalundirected",
       "localundirected", "local", "average", "localaverage",
       "localaverageundirected", "barrat", "weighted"), vids=NULL,
       weights=NULL, isolates=c("NaN", "zero"))

Arguments

graph

The graph to analyze.

type

The type of the transitivity to calculate. Possible values:

global

The global transitivity of an undirected graph (directed graphs are considered as undirected ones as well). This is simply the ratio of the triangles and the connected triples in the graph. For directed graph the direction of the edges is ignored.

local

The local transitivity of an undirected graph, this is calculated for each vertex given in the vids argument. The local transitivity of a vertex is the ratio of the triangles connected to the vertex and the triples centered on the vertex. For directed graph the direction of the edges is ignored.

undirected

This is the same as global.

globalundirected

This is the same as global.

localundirected

This is the same as local.

barrat

The weighted transitivity as defined A. Barrat. See details below.

weighted

The same as barrat.

vids

The vertex ids for the local transitivity will be calculated. This will be ignored for global transitivity types. The default value is NULL, in this case all vertices are considered. It is slightly faster to supply NULL here than V(graph).

weights

Optional weights for weighted transitivity. It is ignored for other transitivity measures. If it is NULL (the default) and the graph has a weight edge attribute, then it is used automatically.

isolates

Character scalar, defines how to treat vertices with degree zero and one. If it is ‘NaN’ then they local transitivity is reported as NaN and they are not included in the averaging, for the transitivity types that calculate an average. If there are no vertices with degree two or higher, then the averaging will still result NaN. If it is ‘zero’, then we report 0 transitivity for them, and they are included in the averaging, if an average is calculated.

Details

Note that there are essentially two classes of transitivity measures, one is a vertex-level, the other a graph level property.

There are several generalizations of transitivity to weighted graphs, here we use the definition by A. Barrat, this is a local vertex-level quantity, its formula is

weighted C_i = 1/s_i 1/(k_i-1) sum( (w_ij+w_ih)/2 a_ij a_ih a_jh, j, h)

s_i

is the strength of vertex i, see graph.strength, a_ij are elements of the adjacency matrix, k_i is the vertex degree, w_ij are the weights.

This formula gives back the normal not-weighted local transitivity if all the edge weights are the same.

The barrat type of transitivity does not work for graphs with multiple and/or loop edges. If you want to calculate it for a directed graph, call as.undirected with the collapse mode first.

Value

For ‘global’ a single number, or NaN if there are no connected triples in the graph.

For ‘local’ a vector of transitivity scores, one for each vertex in ‘vids’.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

Wasserman, S., and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

Alain Barrat, Marc Barthelemy, Romualdo Pastor-Satorras, Alessandro Vespignani: The architecture of complex weighted networks, Proc. Natl. Acad. Sci. USA 101, 3747 (2004)

Examples

g <- graph.ring(10)
transitivity(g)
g2 <- erdos.renyi.game(1000, 10/1000)
transitivity(g2)   # this is about 10/1000

# Weighted version, the figure from the Barrat paper
gw <- graph.formula(A-B:C:D:E, B-C:D, C-D)
E(gw)$weight <- 1
E(gw)[ V(gw)[name == "A"] %--% V(gw)[name == "E" ] ]$weight <- 5
transitivity(gw, vids="A", type="local")
transitivity(gw, vids="A", type="weighted")

# Weighted reduces to "local" if weights are the same
gw2 <- erdos.renyi.game(1000, 10/1000)
E(gw2)$weight <- 1
t1 <- transitivity(gw2, type="local")
t2 <- transitivity(gw2, type="weighted")
all(is.na(t1) == is.na(t2))
all(na.omit(t1 == t2))

[Package igraph version 0.6.5-1 Index]