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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
|
# IGraph R package
# Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com>
# 334 Harvard street, Cambridge, MA 02139 USA
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
# 02110-1301 USA
#
###################################################################
#' Graph motifs
#'
#' Graph motifs are small connected subgraphs with a well-defined
#' structure. These functions search a graph for various motifs.
#'
#' \code{motifs} searches a graph for motifs of a given size and returns a
#' numeric vector containing the number of different motifs. The order of
#' the motifs is defined by their isomorphism class, see
#' \code{\link{isomorphism_class}}.
#'
#' @aliases graph.motifs
#' @param graph Graph object, the input graph.
#' @param size The size of the motif, currently 3 and 4 are supported only.
#' @param cut.prob Numeric vector giving the probabilities that the search
#' graph is cut at a certain level. Its length should be the same as the size
#' of the motif (the \code{size} argument). By default no cuts are made.
#' @return \code{motifs} returns a numeric vector, the number of occurences of
#' each motif in the graph. The motifs are ordered by their isomorphism
#' classes. Note that for unconnected subgraphs, which are not considered to be
#' motifs, the result will be \code{NA}.
#' @seealso \code{\link{isomorphism_class}}
#'
#' @export
#' @family graph motifs
#'
#' @examples
#' g <- barabasi.game(100)
#' motifs(g, 3)
#' count_motifs(g, 3)
#' sample_motifs(g, 3)
motifs <- function(graph, size=3, cut.prob=rep(0, size)) {
if (!is_igraph(graph)) {
stop("Not a graph object")
}
cut.prob <- as.numeric(cut.prob)
if (length(cut.prob) != size) {
cut.prob <- c(cut.prob[-length(cut.prob)],
rep(cut.prob[-length(cut.prob)], length(cut.prob)-1))
}
on.exit( .Call("R_igraph_finalizer", PACKAGE="igraph") )
res <- .Call("R_igraph_motifs_randesu", graph, as.integer(size),
as.numeric(cut.prob),
PACKAGE="igraph")
res[is.nan(res)] <- NA
res
}
#' Graph motifs
#'
#' Graph motifs are small connected subgraphs with a well-defined
#' structure. These functions search a graph for various motifs.
#'
#' \code{count_motifs} calculates the total number of motifs of a given
#' size in graph.
#'
#' @aliases graph.motifs.no
#' @param graph Graph object, the input graph.
#' @param size The size of the motif, currently 3 and 4 are supported only.
#' @param cut.prob Numeric vector giving the probabilities that the search
#' graph is cut at a certain level. Its length should be the same as the size
#' of the motif (the \code{size} argument). By default no cuts are made.
#' @return \code{count_motifs} returns a numeric scalar.
#' @seealso \code{\link{isomorphism_class}}
#'
#' @export
#' @family graph motifs
#'
#' @examples
#' g <- barabasi.game(100)
#' motifs(g, 3)
#' count_motifs(g, 3)
#' sample_motifs(g, 3)
count_motifs <- function(graph, size=3, cut.prob=rep(0, size)) {
if (!is_igraph(graph)) {
stop("Not a graph object")
}
cut.prob <- as.numeric(cut.prob)
if (length(cut.prob) != size) {
cut.prob <- c(cut.prob[-length(cut.prob)],
rep(cut.prob[-length(cut.prob)], length(cut.prob)-1))
}
on.exit( .Call("R_igraph_finalizer", PACKAGE="igraph") )
.Call("R_igraph_motifs_randesu_no", graph, as.integer(size),
as.numeric(cut.prob),
PACKAGE="igraph")
}
#' Graph motifs
#'
#' Graph motifs are small connected subgraphs with a well-defined
#' structure. These functions search a graph for various motifs.
#'
#' \code{sample_motifs} estimates the total number of motifs of a given
#' size in a graph based on a sample.
#'
#' @aliases graph.motifs.est
#' @param graph Graph object, the input graph.
#' @param size The size of the motif, currently 3 and 4 are supported only.
#' @param cut.prob Numeric vector giving the probabilities that the search
#' graph is cut at a certain level. Its length should be the same as the size
#' of the motif (the \code{size} argument). By default no cuts are made.
#' @param sample.size The number of vertices to use as a starting point for
#' finding motifs. Only used if the \code{sample} argument is \code{NULL}.
#' @param sample If not \code{NULL} then it specifies the vertices to use as a
#' starting point for finding motifs.
#' @return A numeric scalar, an estimate for the total number of motifs in
#' the graph.
#' @seealso \code{\link{isomorphism_class}}
#'
#' @export
#' @family graph motifs
#'
#' @examples
#' g <- barabasi.game(100)
#' motifs(g, 3)
#' count_motifs(g, 3)
#' sample_motifs(g, 3)
sample_motifs <- function(graph, size=3, cut.prob=rep(0, size),
sample.size=vcount(graph)/10, sample=NULL) {
if (!is_igraph(graph)) {
stop("Not a graph object")
}
cut.prob <- as.numeric(cut.prob)
if (length(cut.prob) != size) {
cut.prob <- c(cut.prob[-length(cut.prob)],
rep(cut.prob[-length(cut.prob)], length(cut.prob)-1))
}
on.exit( .Call("R_igraph_finalizer", PACKAGE="igraph") )
.Call("R_igraph_motifs_randesu_estimate", graph, as.integer(size),
as.numeric(cut.prob), as.integer(sample.size), as.numeric(sample),
PACKAGE="igraph")
}
#' Dyad census of a graph
#'
#' Classify dyads in a directed graphs. The relationship between each pair of
#' vertices is measured. It can be in three states: mutual, asymmetric or
#' non-existent.
#'
#'
#' @aliases dyad.census dyad_census
#' @param graph The input graph. A warning is given if it is not directed.
#' @return A named numeric vector with three elements: \item{mut}{The number of
#' pairs with mutual connections.} \item{asym}{The number of pairs with
#' non-mutual connections.} \item{null}{The number of pairs with no connection
#' between them.}
#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
#' @seealso \code{\link{triad_census}} for the same classification, but with
#' triples.
#' @references Holland, P.W. and Leinhardt, S. A Method for Detecting Structure
#' in Sociometric Data. \emph{American Journal of Sociology}, 76, 492--513.
#' 1970.
#'
#' Wasserman, S., and Faust, K. \emph{Social Network Analysis: Methods and
#' Applications.} Cambridge: Cambridge University Press. 1994.
#' @keywords graphs
#' @examples
#'
#' g <- sample_pa(100)
#' dyad_census(g)
#' @export
dyad_census <- dyad_census
#' Triad census, subgraphs with three vertices
#'
#' This function counts the different subgraphs of three vertices in a graph.
#'
#' Triad census was defined by David and Leinhardt (see References below).
#' Every triple of vertices (A, B, C) are classified into the 16 possible
#' states: \describe{ \item{003}{A,B,C, the empty graph.} \item{012}{A->B, C,
#' the graph with a single directed edge.} \item{102}{A<->B, C, the graph with
#' a mutual connection between two vertices.} \item{021D}{A<-B->C, the
#' out-star.} \item{021U}{A->B<-C, the in-star.} \item{021C}{A->B->C, directed
#' line.} \item{111D}{A<->B<-C.} \item{111U}{A<->B->C.} \item{030T}{A->B<-C,
#' A->C.} \item{030C}{A<-B<-C, A->C.} \item{201}{A<->B<->C.}
#' \item{120D}{A<-B->C, A<->C.} \item{120U}{A->B<-C, A<->C.}
#' \item{120C}{A->B->C, A<->C.} \item{210}{A->B<->C, A<->C.}
#' \item{300}{A<->B<->C, A<->C, the complete graph.} }
#'
#' This functions uses the RANDESU motif finder algorithm to find and count the
#' subgraphs, see \code{\link{motifs}}.
#'
#' @aliases triad.census triad_census
#' @param graph The input graph, it should be directed. An undirected graph
#' results a warning, and undefined results.
#' @return A numeric vector, the subgraph counts, in the order given in the
#' above description.
#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
#' @seealso \code{\link{dyad_census}} for classifying binary relationships,
#' \code{\link{motifs}} for the underlying implementation.
#' @references See also Davis, J.A. and Leinhardt, S. (1972). The Structure
#' of Positive Interpersonal Relations in Small Groups. In J. Berger (Ed.),
#' Sociological Theories in Progress, Volume 2, 218-251. Boston: Houghton
#' Mifflin.
#' @keywords graphs
#' @examples
#'
#' g <- sample_gnm(15, 45, directed = TRUE)
#' triad_census(g)
#' @export
triad_census <- triad_census
|
