1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/structural.properties.R
\name{transitivity}
\alias{transitivity}
\title{Transitivity of a graph}
\usage{
transitivity(
graph,
type = c("undirected", "global", "globalundirected", "localundirected", "local",
"average", "localaverage", "localaverageundirected", "barrat", "weighted"),
vids = NULL,
weights = NULL,
isolates = c("NaN", "zero")
)
}
\arguments{
\item{graph}{The graph to analyze.}
\item{type}{The type of the transitivity to calculate. Possible values:
\describe{ \item{"global"}{The global transitivity of an undirected
graph. This is simply the ratio of the count of triangles and connected triples
in the graph. In directed graphs, edge directions are ignored.}
\item{"local"}{The local transitivity of an undirected graph. It is
calculated for each vertex given in the \code{vids} argument. The local
transitivity of a vertex is the ratio of the count of triangles connected to the
vertex and the triples centered on the vertex. In directed graphs, edge
directions are ignored.}
\item{"undirected"}{This is the same as \code{global}.}
\item{"globalundirected"}{This is the same as \code{global}.}
\item{"localundirected"}{This is the same as \code{local}.}
\item{"barrat"}{The weighted transitivity as defined by A.
Barrat. See details below.}
\item{"weighted"}{The same as \code{barrat}.} }}
\item{vids}{The vertex ids for the local transitivity will be calculated.
This will be ignored for global transitivity types. The default value is
\code{NULL}, in this case all vertices are considered. It is slightly faster
to supply \code{NULL} here than \code{V(graph)}.}
\item{weights}{Optional weights for weighted transitivity. It is ignored for
other transitivity measures. If it is \code{NULL} (the default) and the
graph has a \code{weight} edge attribute, then it is used automatically.}
\item{isolates}{Character scalar, for local versions of transitivity, it
defines how to treat vertices with degree zero and one.
If it is \sQuote{\code{NaN}} then their local transitivity is
reported as \code{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 \code{NaN}. If it
is \sQuote{\code{zero}}, then we report 0 transitivity for them, and they
are included in the averaging, if an average is calculated.
For the global transitivity, it controls how to handle graphs with
no connected triplets: \code{NaN} or zero will be returned according to
the respective setting.}
}
\value{
For \sQuote{\code{global}} a single number, or \code{NaN} if there
are no connected triples in the graph.
For \sQuote{\code{local}} a vector of transitivity scores, one for each
vertex in \sQuote{\code{vids}}.
}
\description{
Transitivity measures the probability that the adjacent vertices of a vertex
are connected. This is sometimes also called the clustering coefficient.
}
\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
\deqn{C_i^w=\frac{1}{s_i(k_i-1)}\sum_{j,h}\frac{w_{ij}+w_{ih}}{2}a_{ij}a_{ih}a_{jh}}{
weighted C_i = 1/s_i 1/(k_i-1) sum( (w_ij+w_ih)/2 a_ij a_ih a_jh, j, h)}
\eqn{s_i}{s_i} is the strength of vertex \eqn{i}{i}, see
\code{\link[=strength]{strength()}}, \eqn{a_{ij}}{a_ij} are elements of the
adjacency matrix, \eqn{k_i}{k_i} is the vertex degree, \eqn{w_{ij}}{w_ij}
are the weights.
This formula gives back the normal not-weighted local transitivity if all
the edge weights are the same.
The \code{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 \code{\link[=as_undirected]{as_undirected()}} with the \code{collapse} mode first.
}
\examples{
g <- make_ring(10)
transitivity(g)
g2 <- sample_gnp(1000, 10 / 1000)
transitivity(g2) # this is about 10/1000
# Weighted version, the figure from the Barrat paper
gw <- graph_from_literal(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 <- sample_gnp(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))
}
\references{
Wasserman, S., and Faust, K. (1994). \emph{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)
}
\seealso{
Other structural.properties:
\code{\link{bfs}()},
\code{\link{component_distribution}()},
\code{\link{connect}()},
\code{\link{constraint}()},
\code{\link{coreness}()},
\code{\link{degree}()},
\code{\link{dfs}()},
\code{\link{distance_table}()},
\code{\link{edge_density}()},
\code{\link{feedback_arc_set}()},
\code{\link{girth}()},
\code{\link{is_acyclic}()},
\code{\link{is_dag}()},
\code{\link{is_matching}()},
\code{\link{k_shortest_paths}()},
\code{\link{knn}()},
\code{\link{reciprocity}()},
\code{\link{subcomponent}()},
\code{\link{subgraph}()},
\code{\link{topo_sort}()},
\code{\link{unfold_tree}()},
\code{\link{which_multiple}()},
\code{\link{which_mutual}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{structural.properties}
\keyword{graphs}
|
