IEEE Circuits and Systems Magazine - Q2 2019 - 17

control of the whole network. They called it the minimum inputs theorem. To introduce this theorem, some
concepts and notations are introduced first.
u is a matching
In a directed graph, an edge subset M
u share a common starting node or
if no two edges in M
a common ending node. A node is matched if it is the
ending node of an edge in the matching; otherwise, it
is unmatched. A matching of maximum size is called a
maximum matching. A maximum matching is perfect if all
nodes are matched.
Example 6
In Fig. 6(a), all but the starting node are matched (see
Fig. 6(a1)). In Fig. 6(b), one can find multiple maximum
matchings (Figs. 6(b1) and (b2)). In a directed cycle, the
maximum matching is perfect (Fig. 6(c1)).
■
Theorem 7 (Minimum Inputs Theorem) [24]
To fully control a directed network G (A), the minimum
number N I of independent inputs, or equivalently the
minimum number N D of driver nodes, is given by
N I = N D = max " N - ; M * ;, 1 ,,

(12)

where ; M * ; is the size of a maximum matching in G (A);
that is, the driver nodes correspond to the unmatched
nodes. If all nodes in the network are matched, i.e.,
; M * ; = N, a single input is sufficient to fully control the
network, hence N I = N D =1. In this case, any node can
be chosen as the driver node.
The minimum inputs theorem maps the structurally
controllability of a large-scale directed network into a
purely graph-theoretical problem of finding a maximum
matching of a diagraph. More importantly, it avoids the
trouble in exhaustively searching for all node combinations in a minimum driver node set, since the driver nodes
can be obtained from a solution of the matching problem.
Combining techniques from network science, control
theory and statistical physics, Liu et al. [24] showed that
the minimum number of driver nodes is mainly determined by the degree distribution of the network, and
that the driver nodes tend to avoid high-degree nodes.
They also found that sparse and heterogeneous networks are the most difficult ones to control, but dense
and homogeneous networks can be controlled using
only a few driver nodes.
Note that degree distribution alone is not sufficient
to characterize many basic properties of a complex
network, including the controllability. Also, the effects
of different structural properties cannot be separated
from each other in order to determine the network controllability. Thus, the effects of other network characteristics on the controllability were investigated from
sEcOnd QuartEr 2019

various perspectives. Pósfai et al. [25] found that clustering and modularity have no discernible impacts on
the controllability, but the symmetries of the underlying matching problem can produce linear, quadratic or
no dependence on the degree correlation coefficients,
depending on the nature of the underlying correlations.
Menichetti et al. [26] showed that the density of nodes
with in-degree and out-degree equal to one or two already determines the number of driver nodes needed
for a network. They also showed that random networks
with minimum in-degree and out-degree greater than
two are always fully controllable by an infinitesimal fraction of driver nodes, regardless of many other properties of the degree distribution.
3.3.2 Edge Dynamics
Most existing works focused on linear time-invariant
(LTI) nodal dynamics, for which the nodal controllability
is investigated based on the state variables of individual
node systems. However, in many real-world networks,
edge dynamics could also be important [27]-[30]. For
example, in social networks, a node (person) constantly
processes the information received from its upstream
neighbors and makes decisions that are communicated
to its downstream neighbors. In this process, nodes are
not only passive components (receiving information)
but also active components with information processing capabilities (identifying and transmitting information). One node can receive different information from
different upstream neighbors through different inbound
edges and then transmit the information or decisions
to different downstream neighbors through outbound
edges. Regarding the internal information of the node
being mutually mixed and even being eliminated, it is
more reasonable and accurate to assume that the information received and passed by a node is represented by
the state variables on its incoming and outgoing edges,
respectively. The node itself acts like a switchboard,
mapping the signals from the incoming edges onto the
outgoing edges. This is also the case in an urban transport network, where the edges represent road connections and the state variables on the edges represent the
amount of traffic flow along a particular conjunction in
a given direction. To model such systems, Nepusz and
Vicsek [31] developed a switchboard dynamics (SBD)
model by introducing a dynamical process on the edges
of a directed network. The equation governing the LTI
edge dynamics of a directed complex network is
yo +i (t) = M i y -i (t) - x i 7 y +i (t) + d i u i (t), i =1, 2, f, N,

(13)

where y +i and y -i are vectors of outbound and inbound
edges of node i, respectively; M i is the mixing (or
IEEE cIrcuIts and systEms magazInE

IEEE Circuits and Systems Magazine - Q2 2019

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