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
|
#' Graphlet decomposition of a graph
#'
#' Graphlet decomposition models a weighted undirected graph via the union of
#' potentially overlapping dense social groups. This is done by a two-step
#' algorithm. In the first step a candidate set of groups (a candidate basis)
#' is created by finding cliques if the thresholded input graph. In the second
#' step these the graph is projected on the candidate basis, resulting a weight
#' coefficient for each clique in the candidate basis.
#'
#' igraph contains three functions for performing the graph decomponsition of a
#' graph. The first is \code{graphlets}, which performed both steps on the
#' method and returns a list of subgraphs, with their corresponding weights.
#' The second and third functions correspond to the first and second steps of
#' the algorithm, and they are useful if the user wishes to perform them
#' individually: \code{graphlet_basis} and \code{graphlet_proj}.
#'
#' @aliases graphlets graphlets.project graphlet_proj graphlet_basis
#' graphlets.candidate.basis
#' @param graph The input graph, edge directions are ignored. Only simple graph
#' (i.e. graphs without self-loops and multiple edges) are supported.
#' @param weights Edge weights. If the graph has a \code{weight} edge attribute
#' and this argument is \code{NULL} (the default), then the \code{weight} edge
#' attribute is used.
#' @param niter Integer scalar, the number of iterations to perform.
#' @param cliques A list of vertex ids, the graphlet basis to use for the
#' projection.
#' @param Mu Starting weights for the projection.
#' @return \code{graphlets} returns a list with two members: \item{cliques}{A
#' list of subgraphs, the candidate graphlet basis. Each subgraph is give by a
#' vector of vertex ids.} \item{Mu}{The weights of the subgraphs in graphlet
#' basis.}
#'
#' \code{graphlet_basis} returns a list of two elements: \item{cliques}{A list
#' of subgraphs, the candidate graphlet basis. Each subgraph is give by a
#' vector of vertex ids.} \item{thresholds}{The weight thresholds used for
#' finding the subgraphs.}
#'
#' \code{graphlet_proj} return a numeric vector, the weights of the graphlet
#' basis subgraphs.
#' @examples
#'
#' ## Create an example graph first
#' D1 <- matrix(0, 5, 5)
#' D2 <- matrix(0, 5, 5)
#' D3 <- matrix(0, 5, 5)
#' D1[1:3, 1:3] <- 2
#' D2[3:5, 3:5] <- 3
#' D3[2:5, 2:5] <- 1
#'
#' g <- simplify(graph_from_adjacency_matrix(D1 + D2 + D3,
#' mode="undirected", weighted=TRUE))
#' V(g)$color <- "white"
#' E(g)$label <- E(g)$weight
#' E(g)$label.cex <- 2
#' E(g)$color <- "black"
#' layout(matrix(1:6, nrow=2, byrow=TRUE))
#' co <- layout_with_kk(g)
#' par(mar=c(1,1,1,1))
#' plot(g, layout=co)
#'
#' ## Calculate graphlets
#' gl <- graphlets(g, niter=1000)
#'
#' ## Plot graphlets
#' for (i in 1:length(gl$cliques)) {
#' sel <- gl$cliques[[i]]
#' V(g)$color <- "white"
#' V(g)[sel]$color <- "#E495A5"
#' E(g)$width <- 1
#' E(g)[ V(g)[sel] %--% V(g)[sel] ]$width <- 2
#' E(g)$label <- ""
#' E(g)[ width == 2 ]$label <- round(gl$Mu[i], 2)
#' E(g)$color <- "black"
#' E(g)[ width == 2 ]$color <- "#E495A5"
#' plot(g, layout=co)
#' }
#' #' @export
graphlet_basis <- function(graph, weights=NULL) {
## Argument checks
if (!is_igraph(graph)) { stop("Not a graph object") }
if (is.null(weights) && "weight" %in% edge_attr_names(graph)) {
weights <- E(graph)$weight
}
if (!is.null(weights) && any(!is.na(weights))) {
weights <- as.numeric(weights)
} else {
weights <- NULL
}
## Drop all attributes, we don't want to deal with them, TODO
graph2 <- graph
graph2[[9]] <- list(c(1,0,1), list(), list(), list())
on.exit( .Call("R_igraph_finalizer", PACKAGE="igraph") )
## Function call
res <- .Call("R_igraph_graphlets_candidate_basis", graph2, weights,
PACKAGE="igraph")
res
}
#' @rdname graphlet_basis
#' @export
graphlet_proj <- function(graph, weights=NULL, cliques, niter=1000,
Mu=rep(1, length(cliques))) {
# Argument checks
if (!is.igraph(graph)) { stop("Not a graph object") }
if (is.null(weights) && "weight" %in% edge_attr_names(graph)) {
weights <- E(graph)$weight
}
if (!is.null(weights) && any(!is.na(weights))) {
weights <- as.numeric(weights)
} else {
weights <- NULL
}
Mu <- as.numeric(Mu)
niter <- as.integer(niter)
on.exit( .Call("R_igraph_finalizer", PACKAGE="igraph") )
# Function call
res <- .Call("R_igraph_graphlets_project", graph, weights, cliques, Mu, niter,
PACKAGE="igraph")
res
}
#################
## Example code
function() {
library(igraph)
fitandplot <- function(g, gl) {
g <- simplify(g)
V(g)$color <- "white"
E(g)$label <- E(g)$weight
E(g)$label.cex <- 2
E(g)$color <- "black"
plot.new()
layout(matrix(1:6, nrow=2, byrow=TRUE))
co <- layout_with_kk(g)
par(mar=c(1,1,1,1))
plot(g, layout=co)
for (i in 1:length(gl$Bc)) {
sel <- gl$Bc[[i]]
V(g)$color <- "white"
V(g)[sel]$color <- "#E495A5"
E(g)$width <- 1
E(g)[ V(g)[sel] %--% V(g)[sel] ]$width <- 2
E(g)$label <- ""
E(g)[ width == 2 ]$label <- round(gl$Muc[i], 2)
E(g)$color <- "black"
E(g)[ width == 2 ]$color <- "#E495A5"
plot(g, layout=co)
}
}
D1 <- matrix(0, 5, 5)
D2 <- matrix(0, 5, 5)
D3 <- matrix(0, 5, 5)
D1[1:3, 1:3] <- 2
D2[3:5, 3:5] <- 3
D3[2:5, 2:5] <- 1
g <- graph_from_adjacency_matrix(D1 + D2 + D3, mode="undirected", weighted=TRUE)
gl <- graphlets(g, iter=1000)
fitandplot(g, gl)
## Project another graph on the graphlets
set.seed(42)
g2 <- set_edge_attr(g, "weight", value=sample(E(g)$weight))
gl2 <- graphlet_proj(g2, gl$Bc, 1000)
fitandplot(g2, gl2)
}
|
