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