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