IEEE Circuits and Systems Magazine - Q2 2019 - 27

~ ~ ~
G (V, E )

G (V, E )
a

b

a
c

d

b

(a)

c1
c3

c2

d

a+

a-

b+

b-

c+1

c-1

c+2

c-2

c+3
d+

c-3
d-

(b)

(c)

Figure 12. Illustration of the relation between the mdset and the structural controllability. (a) the original network and its mdset,
where the mdset is denoted by double circle. (b) the transformed network. (c) the constructed bipartite network, where green
lines correspond to maximum matching.

is an MDSet if every node v ! V is either an element of
S or adjacent to an element of S. For a given network
G (V, E ) and an MDSet S, construct a directed network
as follows. For each node v ! S, split this node into k
nodes, v 1, v 2, f, v k, where k is the degree of node v, and
create a directed edge from each v i to a node adjacent
to v such that the out-degree of each v i is 1. For each
pair of nodes (u, v) such that u, v " S and (u, v) ! E, create directed edges (u, v) and (v, u) . Let Gu (Vu, Eu ) denote
the resulting network (Fig. 12(b)). Next, construct a bipartite graph from Gu (Vu, Eu ) as follows (Fig. 12(c)). For
each node v ! Vu, create two nodes v + and v -. For each
edge (u, v) ! Eu , create an edge between u + and v -. Beu
cause S is a dominating set, there exists a matching M
u
v
M
;
(ii)
appears in
satisfying (i) for each node v " S,
u . Here, M
u
for each node v ! S, none of v -i appears in M
is maximum because no v -i with v ! S has an edge in
the bipartite graph. Therefore, by choosing {v i v ! S }
as the set of driver nodes, the above conclusion follows
from the minimum inputs theorem (Theorem 7).
Motivated by the work of Nacher and Akutsu [74],
Wuchty [73] identified MDSet in human and yeast
protein interaction networks, where an MDSet is defined as an optimized subset of proteins from where
each remaining (i.e., non-MDSet) protein can be immediately reached through one interaction. Such proteins play a key role in the control of the underlying
networks. The findings suggest that MDSet proteins
are enriched with cancer-related and virus-targeted
genes. Furthermore, MDSet proteins have a higher
impact on the network resilience than hub proteins.
Indicating their relevance to the controllability of biological networks, a strong involvement was found in
bottleneck interactions, regulatory and phosphorylation events, as well as genetic interactions. Specifically, Wuchty [73] determined the MDSet by solving
a binary integer programming problem, where each
protein v ! V in a protein interaction network G (V, E )
sEcOnd QuartEr 2019

f (x) = min (x1 + x2 + x3 + x4 + x5)
1

2

x1 + x2 +

x5 ≥ 1

x1 + x2 + x3 +

x5 ≥ 1

x2 + x3 + x4
≥1
x3 + x4 + x5 ≥ 1

5

x1 + x2 +

3
xi =

4

+ x4 + x5 ≥ 1

1

1

0

0

1

1

1

1

0

1

0

1

1

1

0 x≥1

1, if xi ∈ MDSet

0

0

1

1

1

0, if xi ∉ MDSet

1

1

0

1

1

(a)

(b)

Figure 13. concept of binary integer programming problems.
(a) an undirected network. (b) Formulation of the binary integer programming problem for identifying mdset.

is assigned a binary variable, x v . If v ! S, then x v =1,
and x v = 0 otherwise. The computation of the MDSet
is performed on min / v ! V x v, subject to the constraint
of x v + / ~ ! Nv x ~ $ 1, where N v is the set of neighbors
of protein v. In Fig. 13, the concept of binary integer
programming problems is illustrated.
5.2 Interbank Networks
The network of interbank loans represents a building
block of modern financial economies, which also represents a crucial gear for the transmission of monetary
policies to the real economy. It is known that targeted intervention on individual banks could be more effective
in guaranteeing and restoring the efficient allocation of
credits. This suggests the need for monitoring the system and keeping track of the banks that are systemically
relevant, from a control perspective.
IEEE cIrcuIts and systEms magazInE

27
IEEE Circuits and Systems Magazine - Q2 2019

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2019
