1 2#' Graphlet decomposition of a graph 3#' 4#' Graphlet decomposition models a weighted undirected graph via the union of 5#' potentially overlapping dense social groups. This is done by a two-step 6#' algorithm. In the first step a candidate set of groups (a candidate basis) 7#' is created by finding cliques if the thresholded input graph. In the second 8#' step these the graph is projected on the candidate basis, resulting a weight 9#' coefficient for each clique in the candidate basis. 10#' 11#' igraph contains three functions for performing the graph decomponsition of a 12#' graph. The first is \code{graphlets}, which performed both steps on the 13#' method and returns a list of subgraphs, with their corresponding weights. 14#' The second and third functions correspond to the first and second steps of 15#' the algorithm, and they are useful if the user wishes to perform them 16#' individually: \code{graphlet_basis} and \code{graphlet_proj}. 17#' 18#' @aliases graphlets graphlets.project graphlet_proj graphlet_basis 19#' graphlets.candidate.basis 20#' @param graph The input graph, edge directions are ignored. Only simple graph 21#' (i.e. graphs without self-loops and multiple edges) are supported. 22#' @param weights Edge weights. If the graph has a \code{weight} edge attribute 23#' and this argument is \code{NULL} (the default), then the \code{weight} edge 24#' attribute is used. 25#' @param niter Integer scalar, the number of iterations to perform. 26#' @param cliques A list of vertex ids, the graphlet basis to use for the 27#' projection. 28#' @param Mu Starting weights for the projection. 29#' @return \code{graphlets} returns a list with two members: \item{cliques}{A 30#' list of subgraphs, the candidate graphlet basis. Each subgraph is give by a 31#' vector of vertex ids.} \item{Mu}{The weights of the subgraphs in graphlet 32#' basis.} 33#' 34#' \code{graphlet_basis} returns a list of two elements: \item{cliques}{A list 35#' of subgraphs, the candidate graphlet basis. Each subgraph is give by a 36#' vector of vertex ids.} \item{thresholds}{The weight thresholds used for 37#' finding the subgraphs.} 38#' 39#' \code{graphlet_proj} return a numeric vector, the weights of the graphlet 40#' basis subgraphs. 41#' @examples 42#' 43#' ## Create an example graph first 44#' D1 <- matrix(0, 5, 5) 45#' D2 <- matrix(0, 5, 5) 46#' D3 <- matrix(0, 5, 5) 47#' D1[1:3, 1:3] <- 2 48#' D2[3:5, 3:5] <- 3 49#' D3[2:5, 2:5] <- 1 50#' 51#' g <- simplify(graph_from_adjacency_matrix(D1 + D2 + D3, 52#' mode="undirected", weighted=TRUE)) 53#' V(g)$color <- "white" 54#' E(g)$label <- E(g)$weight 55#' E(g)$label.cex <- 2 56#' E(g)$color <- "black" 57#' layout(matrix(1:6, nrow=2, byrow=TRUE)) 58#' co <- layout_with_kk(g) 59#' par(mar=c(1,1,1,1)) 60#' plot(g, layout=co) 61#' 62#' ## Calculate graphlets 63#' gl <- graphlets(g, niter=1000) 64#' 65#' ## Plot graphlets 66#' for (i in 1:length(gl$cliques)) { 67#' sel <- gl$cliques[[i]] 68#' V(g)$color <- "white" 69#' V(g)[sel]$color <- "#E495A5" 70#' E(g)$width <- 1 71#' E(g)[ V(g)[sel] %--% V(g)[sel] ]$width <- 2 72#' E(g)$label <- "" 73#' E(g)[ width == 2 ]$label <- round(gl$Mu[i], 2) 74#' E(g)$color <- "black" 75#' E(g)[ width == 2 ]$color <- "#E495A5" 76#' plot(g, layout=co) 77#' } 78#' @export 79 80graphlet_basis <- function(graph, weights=NULL) { 81 ## Argument checks 82 if (!is_igraph(graph)) { stop("Not a graph object") } 83 if (is.null(weights) && "weight" %in% edge_attr_names(graph)) { 84 weights <- E(graph)$weight 85 } 86 if (!is.null(weights) && any(!is.na(weights))) { 87 weights <- as.numeric(weights) 88 } else { 89 weights <- NULL 90 } 91 92 ## Drop all attributes, we don't want to deal with them, TODO 93 graph2 <- graph 94 graph2[[9]] <- list(c(1,0,1), list(), list(), list()) 95 96 on.exit( .Call(C_R_igraph_finalizer) ) 97 ## Function call 98 res <- .Call(C_R_igraph_graphlets_candidate_basis, graph2, weights) 99 100 res 101} 102 103#' @rdname graphlet_basis 104#' @export 105 106graphlet_proj <- function(graph, weights=NULL, cliques, niter=1000, 107 Mu=rep(1, length(cliques))) { 108 # Argument checks 109 if (!is.igraph(graph)) { stop("Not a graph object") } 110 if (is.null(weights) && "weight" %in% edge_attr_names(graph)) { 111 weights <- E(graph)$weight 112 } 113 if (!is.null(weights) && any(!is.na(weights))) { 114 weights <- as.numeric(weights) 115 } else { 116 weights <- NULL 117 } 118 Mu <- as.numeric(Mu) 119 niter <- as.integer(niter) 120 121 on.exit( .Call(C_R_igraph_finalizer) ) 122 # Function call 123 res <- .Call(C_R_igraph_graphlets_project, graph, weights, cliques, Mu, niter) 124 125 res 126} 127 128################# 129## Example code 130 131function() { 132 library(igraph) 133 134 fitandplot <- function(g, gl) { 135 g <- simplify(g) 136 V(g)$color <- "white" 137 E(g)$label <- E(g)$weight 138 E(g)$label.cex <- 2 139 E(g)$color <- "black" 140 plot.new() 141 layout(matrix(1:6, nrow=2, byrow=TRUE)) 142 co <- layout_with_kk(g) 143 par(mar=c(1,1,1,1)) 144 plot(g, layout=co) 145 for (i in 1:length(gl$Bc)) { 146 sel <- gl$Bc[[i]] 147 V(g)$color <- "white" 148 V(g)[sel]$color <- "#E495A5" 149 E(g)$width <- 1 150 E(g)[ V(g)[sel] %--% V(g)[sel] ]$width <- 2 151 E(g)$label <- "" 152 E(g)[ width == 2 ]$label <- round(gl$Muc[i], 2) 153 E(g)$color <- "black" 154 E(g)[ width == 2 ]$color <- "#E495A5" 155 plot(g, layout=co) 156 } 157 } 158 159 D1 <- matrix(0, 5, 5) 160 D2 <- matrix(0, 5, 5) 161 D3 <- matrix(0, 5, 5) 162 D1[1:3, 1:3] <- 2 163 D2[3:5, 3:5] <- 3 164 D3[2:5, 2:5] <- 1 165 166 g <- graph_from_adjacency_matrix(D1 + D2 + D3, mode="undirected", weighted=TRUE) 167 gl <- graphlets(g, iter=1000) 168 169 fitandplot(g, gl) 170 171 ## Project another graph on the graphlets 172 set.seed(42) 173 g2 <- set_edge_attr(g, "weight", value=sample(E(g)$weight)) 174 gl2 <- graphlet_proj(g2, gl$Bc, 1000) 175 fitandplot(g2, gl2) 176 177} 178 179