1
2#   IGraph R package
3#   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
4#   334 Harvard street, Cambridge, MA 02139 USA
5#
6#   This program is free software; you can redistribute it and/or modify
7#   it under the terms of the GNU General Public License as published by
8#   the Free Software Foundation; either version 2 of the License, or
9#   (at your option) any later version.
10#
11#   This program is distributed in the hope that it will be useful,
12#   but WITHOUT ANY WARRANTY; without even the implied warranty of
13#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14#   GNU General Public License for more details.
15#
16#   You should have received a copy of the GNU General Public License
17#   along with this program; if not, write to the Free Software
18#   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
19#   02110-1301 USA
20#
21###################################################################
22
23#' Graph motifs
24#'
25#' Graph motifs are small connected subgraphs with a well-defined
26#' structure.  These functions search a graph for various motifs.
27#'
28#' \code{motifs} searches a graph for motifs of a given size and returns a
29#' numeric vector containing the number of different motifs. The order of
30#' the motifs is defined by their isomorphism class, see
31#' \code{\link{isomorphism_class}}.
32#'
33#' @aliases graph.motifs
34#' @param graph Graph object, the input graph.
35#' @param size The size of the motif, currently 3 and 4 are supported only.
36#' @param cut.prob Numeric vector giving the probabilities that the search
37#' graph is cut at a certain level. Its length should be the same as the size
38#' of the motif (the \code{size} argument). By default no cuts are made.
39#' @return \code{motifs} returns a numeric vector, the number of occurrences of
40#' each motif in the graph. The motifs are ordered by their isomorphism
41#' classes. Note that for unconnected subgraphs, which are not considered to be
42#' motifs, the result will be \code{NA}.
43#' @seealso \code{\link{isomorphism_class}}
44#'
45#' @export
46#' @family graph motifs
47#'
48#' @examples
49#' g <- barabasi.game(100)
50#' motifs(g, 3)
51#' count_motifs(g, 3)
52#' sample_motifs(g, 3)
53
54motifs <- function(graph, size=3, cut.prob=rep(0, size)) {
55
56  if (!is_igraph(graph)) {
57    stop("Not a graph object")
58  }
59  cut.prob <- as.numeric(cut.prob)
60  if (length(cut.prob) != size) {
61    cut.prob <- c(cut.prob[-length(cut.prob)],
62                  rep(cut.prob[-length(cut.prob)], length(cut.prob)-1))
63  }
64
65  on.exit( .Call(C_R_igraph_finalizer) )
66  res <- .Call(C_R_igraph_motifs_randesu, graph, as.integer(size),
67               as.numeric(cut.prob))
68  res[is.nan(res)] <- NA
69  res
70}
71
72#' Graph motifs
73#'
74#' Graph motifs are small connected subgraphs with a well-defined
75#' structure.  These functions search a graph for various motifs.
76#'
77#' \code{count_motifs} calculates the total number of motifs of a given
78#' size in graph.
79#'
80#' @aliases graph.motifs.no
81#' @param graph Graph object, the input graph.
82#' @param size The size of the motif, currently 3 and 4 are supported only.
83#' @param cut.prob Numeric vector giving the probabilities that the search
84#' graph is cut at a certain level. Its length should be the same as the size
85#' of the motif (the \code{size} argument). By default no cuts are made.
86#' @return \code{count_motifs} returns  a numeric scalar.
87#' @seealso \code{\link{isomorphism_class}}
88#'
89#' @export
90#' @family graph motifs
91#'
92#' @examples
93#' g <- barabasi.game(100)
94#' motifs(g, 3)
95#' count_motifs(g, 3)
96#' sample_motifs(g, 3)
97
98count_motifs <- function(graph, size=3, cut.prob=rep(0, size)) {
99
100  if (!is_igraph(graph)) {
101    stop("Not a graph object")
102  }
103  cut.prob <- as.numeric(cut.prob)
104  if (length(cut.prob) != size) {
105    cut.prob <- c(cut.prob[-length(cut.prob)],
106                  rep(cut.prob[-length(cut.prob)], length(cut.prob)-1))
107  }
108
109  on.exit( .Call(C_R_igraph_finalizer) )
110  .Call(C_R_igraph_motifs_randesu_no, graph, as.integer(size),
111        as.numeric(cut.prob))
112}
113
114#' Graph motifs
115#'
116#' Graph motifs are small connected subgraphs with a well-defined
117#' structure.  These functions search a graph for various motifs.
118#'
119#' \code{sample_motifs} estimates the total number of motifs of a given
120#' size in a graph based on a sample.
121#'
122#' @aliases graph.motifs.est
123#' @param graph Graph object, the input graph.
124#' @param size The size of the motif, currently 3 and 4 are supported only.
125#' @param cut.prob Numeric vector giving the probabilities that the search
126#' graph is cut at a certain level. Its length should be the same as the size
127#' of the motif (the \code{size} argument). By default no cuts are made.
128#' @param sample.size The number of vertices to use as a starting point for
129#' finding motifs. Only used if the \code{sample} argument is \code{NULL}.
130#' @param sample If not \code{NULL} then it specifies the vertices to use as a
131#' starting point for finding motifs.
132#' @return A numeric scalar, an estimate for the total number of motifs in
133#'   the graph.
134#' @seealso \code{\link{isomorphism_class}}
135#'
136#' @export
137#' @family graph motifs
138#'
139#' @examples
140#' g <- barabasi.game(100)
141#' motifs(g, 3)
142#' count_motifs(g, 3)
143#' sample_motifs(g, 3)
144
145sample_motifs <- function(graph, size=3, cut.prob=rep(0, size),
146                             sample.size=vcount(graph)/10, sample=NULL) {
147
148  if (!is_igraph(graph)) {
149    stop("Not a graph object")
150  }
151  cut.prob <- as.numeric(cut.prob)
152  if (length(cut.prob) != size) {
153    cut.prob <- c(cut.prob[-length(cut.prob)],
154                  rep(cut.prob[-length(cut.prob)], length(cut.prob)-1))
155  }
156
157  on.exit( .Call(C_R_igraph_finalizer) )
158  .Call(C_R_igraph_motifs_randesu_estimate, graph, as.integer(size),
159        as.numeric(cut.prob), as.integer(sample.size), as.numeric(sample))
160}
161
162
163#' Dyad census of a graph
164#'
165#' Classify dyads in a directed graphs. The relationship between each pair of
166#' vertices is measured. It can be in three states: mutual, asymmetric or
167#' non-existent.
168#'
169#'
170#' @aliases dyad.census dyad_census
171#' @param graph The input graph. A warning is given if it is not directed.
172#' @return A named numeric vector with three elements: \item{mut}{The number of
173#' pairs with mutual connections.} \item{asym}{The number of pairs with
174#' non-mutual connections.} \item{null}{The number of pairs with no connection
175#' between them.}
176#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
177#' @seealso \code{\link{triad_census}} for the same classification, but with
178#' triples.
179#' @references Holland, P.W. and Leinhardt, S. A Method for Detecting Structure
180#' in Sociometric Data. \emph{American Journal of Sociology}, 76, 492--513.
181#' 1970.
182#'
183#' Wasserman, S., and Faust, K. \emph{Social Network Analysis: Methods and
184#' Applications.} Cambridge: Cambridge University Press. 1994.
185#' @keywords graphs
186#' @examples
187#'
188#' g <- sample_pa(100)
189#' dyad_census(g)
190#' @export
191
192dyad_census <- dyad_census
193
194
195#' Triad census, subgraphs with three vertices
196#'
197#' This function counts the different subgraphs of three vertices in a graph.
198#'
199#' Triad census was defined by David and Leinhardt (see References below).
200#' Every triple of vertices (A, B, C) are classified into the 16 possible
201#' states: \describe{ \item{003}{A,B,C, the empty graph.} \item{012}{A->B, C,
202#' the graph with a single directed edge.} \item{102}{A<->B, C, the graph with
203#' a mutual connection between two vertices.} \item{021D}{A<-B->C, the
204#' out-star.} \item{021U}{A->B<-C, the in-star.} \item{021C}{A->B->C, directed
205#' line.} \item{111D}{A<->B<-C.} \item{111U}{A<->B->C.} \item{030T}{A->B<-C,
206#' A->C.} \item{030C}{A<-B<-C, A->C.} \item{201}{A<->B<->C.}
207#' \item{120D}{A<-B->C, A<->C.} \item{120U}{A->B<-C, A<->C.}
208#' \item{120C}{A->B->C, A<->C.} \item{210}{A->B<->C, A<->C.}
209#' \item{300}{A<->B<->C, A<->C, the complete graph.} }
210#'
211#' This functions uses the RANDESU motif finder algorithm to find and count the
212#' subgraphs, see \code{\link{motifs}}.
213#'
214#' @aliases triad.census triad_census
215#' @param graph The input graph, it should be directed. An undirected graph
216#' results a warning, and undefined results.
217#' @return A numeric vector, the subgraph counts, in the order given in the
218#' above description.
219#' @author Gabor Csardi \email{csardi.gabor@@gmail.com}
220#' @seealso \code{\link{dyad_census}} for classifying binary relationships,
221#' \code{\link{motifs}} for the underlying implementation.
222#' @references See also Davis, J.A. and Leinhardt, S.  (1972).  The Structure
223#' of Positive Interpersonal Relations in Small Groups.  In J. Berger (Ed.),
224#' Sociological Theories in Progress, Volume 2, 218-251.  Boston: Houghton
225#' Mifflin.
226#' @keywords graphs
227#' @examples
228#'
229#' g <- sample_gnm(15, 45, directed = TRUE)
230#' triad_census(g)
231#' @export
232
233triad_census <- triad_census
234