Simple MWCS
Simple maximum weight connected subgraph (MWCS) problem can be
defined as follows. Let \(G = (V, E)\)
be an undirected graph and \(\omega : V
\rightarrow \mathbb{R}\) is a weight function defined on the
vertices. Then MWCS problem consists in finding a connected subgraph
\(\widetilde{G} = (\widetilde{V},
\widetilde{E})\) with a maximal total sum of vertex weights:
\[\Omega(\widetilde{G}) = \sum_{v \in
\widetilde{V}} \omega(v) \rightarrow max.\]
An important property of MWCS is that solution can always be
represented as a tree.
In mwcsr an MWCS instance is defined as an
igraph with weight vertex attribute (and
without weight edge attribute).
## IGRAPH f86c56f UN-- 194 209 --
## + attr: name (v/c), label (v/c), weight (v/n), label (e/c)
## + edges from f86c56f (vertex names):
## [1] C00022_2--C00024_0 C00022_0--C00024_1 C00025_0--C00026_0
## [4] C00025_1--C00026_1 C00025_2--C00026_2 C00025_4--C00026_4
## [7] C00025_7--C00026_7 C00024_1--C00033_0 C00024_0--C00033_1
## [10] C00022_0--C00041_0 C00022_1--C00041_1 C00022_2--C00041_2
## [13] C00036_0--C00049_0 C00036_1--C00049_1 C00036_2--C00049_2
## [16] C00036_4--C00049_4 C00037_1--C00065_0 C00037_0--C00065_1
## [19] C00022_0--C00074_5 C00022_1--C00074_6 C00022_2--C00074_7
## [22] C00024_0--C00083_0 C00024_1--C00083_1 C00026_1--C00091_0
## + ... omitted several edges
summary(V(mwcs_example)$weight)
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## -0.7379 -0.7379 1.9294 5.9667 7.2931 38.1546
Budget MWCS
Budget MWCS is a slight modification of the original problem. While
the objective function remains the same, an additional constraint is
introduced. In this problem nonnegative values called budget costs are
assigned to vertices. The sum of budget costs of the vertices in the
solution is then constrained to not exceed a predefined budget.
More formally, let \(c: V \rightarrow
R^+\) be the function of the budget costs. \(B \in R^+\) is a budget of the problem. In
this terms Budget MWCS is defined as a problem where the following
conditions are satisfied:
\[
\Omega(\widetilde{G}) = \sum\limits_{v \in \widetilde{V}} \omega(v)
\rightarrow max.\\
\text{subject to} \sum\limits_{v \in \widetilde{V}} c(v) \leq B
\]
In mwcsr a Budget MWCS instance is an
igraph object with weight vertex attribute as
in original MWCS problem and additional budget_cost vertex
attribute. Value of the budget not the part of the instance itself but
rather a parameter to be passed to a function that solves an
instance.
budget_mwcs_example <- mwcs_example
set.seed(42)
V(budget_mwcs_example)$budget_cost <- runif(vcount(budget_mwcs_example))
get_instance_type(budget_mwcs_example)
## $type
## [1] "Budget MWCS"
##
## $valid
## [1] TRUE
Generalized MWCS (GMWCS)
Generalized MWCS (GMWCS) is similar to MWCS, but edges are also
weighted. More formally, let \(G = (V,
E)\) be an undirected graph and \(\omega : (V \cup E) \rightarrow
\mathbb{R}\) is a weight function defined on the vertices and the
edges. Then GMWCS problem consists in finding a connected subgraph \(\widetilde{G} = (\widetilde{V},
\widetilde{E})\) with a a maximal total sum of vertex and edge
weights:
\[
\Omega(\widetilde{G}) = \sum_{v \in \widetilde{V}} \omega(v) +
\sum_{e \in \widetilde{E}} \omega(e) \rightarrow max.
\]
An important consequence of edge weights is that the optimal solution
can contain cycles.
A GMWCS instance is defined as an igraph with
weight attribute defined for both vertices and edges.
data(gmwcs_example)
gmwcs_example
## IGRAPH f86c56f UNW- 194 209 --
## + attr: name (v/c), label (v/c), weight (v/n), label (e/c), weight
## | (e/n)
## + edges from f86c56f (vertex names):
## [1] C00022_2--C00024_0 C00022_0--C00024_1 C00025_0--C00026_0 C00025_1--C00026_1
## [5] C00025_2--C00026_2 C00025_4--C00026_4 C00025_7--C00026_7 C00024_1--C00033_0
## [9] C00024_0--C00033_1 C00022_0--C00041_0 C00022_1--C00041_1 C00022_2--C00041_2
## [13] C00036_0--C00049_0 C00036_1--C00049_1 C00036_2--C00049_2 C00036_4--C00049_4
## [17] C00037_1--C00065_0 C00037_0--C00065_1 C00022_0--C00074_5 C00022_1--C00074_6
## [21] C00022_2--C00074_7 C00024_0--C00083_0 C00024_1--C00083_1 C00026_1--C00091_0
## [25] C00042_2--C00091_0 C00026_0--C00091_1 C00042_1--C00091_1
## + ... omitted several edges
summary(V(gmwcs_example)$weight)
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## -0.7379 -0.7379 1.9294 5.9667 7.2931 38.1546
summary(E(gmwcs_example)$weight)
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## -1.2715 -0.5762 -0.1060 0.5452 1.0458 8.5829
Signal generalized MWCS (SGMWCS)
The signal generalized MWCS (SGMWCS) variant continues to generalize
MWCS problem and introduces a concept of signals. Instead of
specifying vertex and edge weights directly, the weights are defined for
a set of signals, and vertices and edges are marked with these signals.
The difference from GMWCS is that the signals can be repeated in the
graph, while the weight of the subgraph is defined as a sum of weights
of its unique signals.
Formally, let \(G = (V, E)\) be an
undirected graph, \(S\) – a set of
signlas with weights \(\omega: S \rightarrow
\mathbb{R}\), and \(\sigma: (V \cup E)
\rightarrow 2^S\) – markings of the vertices and edges with
signals. An SGMWCS problem consists in finding a connected subgraph,
with a maximal total sum of its unique signals:
\[
\Omega(\widetilde{G}) =
\sum_{s \in \sigma(\widetilde{V} \cup \widetilde{E})} \omega(s)
\rightarrow max,
\] where \(\sigma(\widetilde{V} \cup
\widetilde{E}) = \bigcup_{x \in (\widetilde{V} \cup \widetilde{E})}
\sigma(x)\).
SGMWCS instances can arise when the data, from which the weights are
inferred, map to the graph ambigously. For example, when m/z peak from
mass-spectrometry data is assigned to multiple isomer metabolites, or
when the same enzyme catalyze multiple reactions, and so on.
Practically, it is usually assumed that the signals with negative
weights are not repeated.
An SGMWCS is represented as an igraph object, with
signal attribute defined for both vertices and edges and a
signals attribute defined for the graph, containing the
signal weights. Specification of multiple signals per node or edge is
not yet supported.
data("sgmwcs_example")
sgmwcs_example
## IGRAPH f86c56f UN-- 194 209 --
## + attr: signals (g/n), name (v/c), label (v/c), signal (v/c), label
## | (e/c), signal (e/c)
## + edges from f86c56f (vertex names):
## [1] C00022_2--C00024_0 C00022_0--C00024_1 C00025_0--C00026_0 C00025_1--C00026_1
## [5] C00025_2--C00026_2 C00025_4--C00026_4 C00025_7--C00026_7 C00024_1--C00033_0
## [9] C00024_0--C00033_1 C00022_0--C00041_0 C00022_1--C00041_1 C00022_2--C00041_2
## [13] C00036_0--C00049_0 C00036_1--C00049_1 C00036_2--C00049_2 C00036_4--C00049_4
## [17] C00037_1--C00065_0 C00037_0--C00065_1 C00022_0--C00074_5 C00022_1--C00074_6
## [21] C00022_2--C00074_7 C00024_0--C00083_0 C00024_1--C00083_1 C00026_1--C00091_0
## [25] C00042_2--C00091_0 C00026_0--C00091_1 C00042_1--C00091_1
## + ... omitted several edges
str(V(sgmwcs_example)$signal)
## chr [1:194] "s1" "s1" "s1" "s2" "s3" "s4" "s4" "s4" "s4" "s4" "s5" "s5" ...
str(E(sgmwcs_example)$signal)
## chr [1:209] "s103" "s104" "s105" "s106" "s107" "s108" "s109" "s110" "s110" ...
head(sgmwcs_example$signals)
## s1 s2 s3 s4 s5 s6
## 5.008879 -0.737898 -0.737898 20.112627 19.890279 2.069292
Constructing SGMWCS instances
Sometimes, construction of SGMWCS instances can be simplified using
normalize_sgmwcs_instance function.
Let consider an example graph obtained from gatom package.
data("gatom_example")
print(gatom_example)
## This graph was created by an old(er) igraph version.
## Call upgrade_graph() on it to use with the current igraph version
## For now we convert it on the fly...
## IGRAPH f86c56f UNW- 194 209 --
## + attr: name (v/c), metabolite (v/c), element (v/c), label (v/c), url
## | (v/c), pval (v/n), origin (v/n), HMDB (v/c), log2FC (v/n), baseMean
## | (v/n), logPval (v/n), signal (v/c), signalRank (v/n), score (v/n),
## | weight (v/n), label (e/c), pval (e/n), origin (e/n), RefSeq (e/c),
## | gene (e/c), enzyme (e/c), reaction_name (e/c), reaction_equation
## | (e/c), url (e/c), reaction (e/c), rpair (e/c), log2FC (e/n), baseMean
## | (e/n), logPval (e/n), signal (e/c), signalRank (e/n), score (e/n),
## | weight (e/n)
## + edges from f86c56f (vertex names):
## [1] C00022_2--C00024_0 C00022_0--C00024_1 C00025_0--C00026_0 C00025_1--C00026_1
## + ... omitted several edges
In this graph, the signals graph attributed is absent
with weights specified directly as vertex or edge attributes along with
signal attributes, which is a very practical intermediate
representation. However, it is recognized as a GMWCS instance:
get_instance_type(gatom_example)
## $type
## [1] "GMWCS"
##
## $valid
## [1] TRUE
Let convert this representation into a valid SGMWCS instance using
normalize_sgmwcs_instance function:
gatom_instance <- normalize_sgmwcs_instance(gatom_example)
get_instance_type(gatom_instance)
## $type
## [1] "SGMWCS"
##
## $valid
## [1] TRUE
And let call the same function with explicit arguments:
gatom_instance <- normalize_sgmwcs_instance(gatom_example,
nodes.weight.column = "weight",
edges.weight.column = "weight",
nodes.group.by = "signal",
edges.group.by = "signal",
group.only.positive = TRUE)
The function does the following:
- It extracts signal weights from the specified columns.
NULL can be specified as a value of
nodes.group.by or edges.group.by if there are
no corresponding signals in the data, in which case zero signals will be
created.
- It splits input signals with negative weights into multiple unique
signals, unless
group.only.positive is set to
FALSE.
