1

Optimality of Fast Matching Algorithms for
Random Networks with Applications to Structural
Controllability
arXiv:1503.08019v2 [cs.DS] 24 Mar 2016

Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis

Abstract
Network control refers to a very large and diverse set of problems including controllability of linear time-invariant dynamical
systems, where the objective is to select an appropriate input to steer the network to a desired state. There are many notions of
controllability, one of them being structural controllability, which is intimately connected to finding maximum matchings on the
underlying network topology. In this work, we study fast, scalable algorithms for finding maximum matchings for a large class
of random networks. First, we illustrate that degree distribution random networks are realistic models for real networks in terms
of structural controllability. Subsequently, we analyze a popular, fast and practical heuristic due to Karp and Sipser as well as a
simplification of it. For both heuristics, we establish asymptotic optimality and provide results concerning the asymptotic size of
maximum matchings for an extensive class of random networks.
Index Terms
Maximum Matching, Karp-Sipser, Structural Controllability, Network Control, Random Networks.

I. I NTRODUCTION

N

ETWORKS are capable of capturing relationships between a set of entities (vertices) and have found applications in
diverse scientific fields including biology, engineering, economics and the social sciences [1], [2], [3]. Network control

refers to a very large and diverse set of problems that involve control actions over a network (see for example, [4], [5], [6],
[7], [8], [9], [10], [11], [12], [13] and references therein).
A class of control problems involves dynamical systems evolving over time that have inputs and outputs and many results
exist for systems that exhibit linear and time-invariant dynamics [11]. One particular notion of control is that of structural
controllability [1], [14], which was recently explored by Liu et al. [12]. Under this notion, the structural controllability problem
reduces to find maximum matchings on appropriate matrices as reviewed in Section I-A. The problem of obtaining maximum
matchings has been extensively studied in the computer science literature both for deterministic [15] as well as random networks
[16]. However, the focus in the literature has been on special classes of undirected random networks [17], [18]. For example,
using the results of Tao and Vu [19], one can infer that for dense Erdos-Renyi random networks, a single controller is sufficient
to ensure controllability. Little is known about the performance of matching algorithms in other interesting classes of random
networks [20], with an exception of the recent work of Balister and Gerke [21]. We focus on degree distribution random

2

network models, and establish results on the minimum number of controllers needed to guarantee structural controllability. We
also show that these models are realistic representations for real world applications.
A popular, fast and practical algorithm for matchings on undirected random networks is due to Karp and Sipser [22], which
represents the cornerstone of our theoretical investigations and through it we provide generalizations of previous work in the
literature to broader classes of undirected random networks. Further, we also extend the results for directed variants of the
same classes of random networks.

A. Structural Controllability and Maximum Matchings
Next, we review some key concepts in structural controllability for linear dynamical systems. Consider a system described
by a n-dimensional state vector x(t) = (x1 (t), ..., xn (t))T ∈ Rn , whose dynamical evolution is described by
dx
= Ax(t) + Bu(t),
dt
where A ∈ Rn×n is the system transition matrix, u(t) = (u1 (t), ..., uk (t))T ∈ Rk captures control actions and B ∈ Rn×k
is the input matrix. Assuming that the n-dimensional system can be represented by vertices on a network G = (V, E) with
V = {1, 2, ..., n} denoting the set of vertices and E ⊂ V × V the set of edges, it can be seen that the non-zero entries in the
transition matrix A correspond to the directed edges in E. Indeed, for i, j ∈ V the edge i → j exists if and only if vertex i
influences vertex j, i.e. Aji 6= 0. Such a system is called controllable if for any initial state x(0) = x0 and any desired state
xd for some T < ∞ one can find an input matrix B and control vectors {u(t)}0≤t≤T so that the system reaches state xd i.e.
x(T ) = xd . The minimum k for which system can be controllable is called the minimum number of controllers.
The magnitude of the entries in the transition matrix A captures the interaction strength between the vertices in the network;
for example, the traffic on individual communication links in a communications network or the strength of a regulatory
interaction in a biological network. The time invariant matrix B indicates which vertices are controlled by an outside controller.
Hence, the set of vertices that when applying controllers to them makes the system controllable needs to be identified.
Note that we don’t assume any constraint on the number of nonzero elements in the columns of input matrix B, i.e. one
controller ui (t) can influence multiple vertices. The case where every controller can be applied to only one vertex in the
network (which in turn implies that the goal is to find the minimum number of vertices the controllers can be applied to) is
studied by Olshevsky [23]. He shows that finding the exact solution to the problem is NP hard.
The algebraic criterion to check controllability of a time invariant linear dynamical system is Kalman’s controllability rank
condition, that states that controllability can be achieved, if and only if the matrix C = [B, AB, ..., An−1 B] is full rank; i.e.
rank(C) = n. Note that C ∈ Rn×nk . This algebraic criterion is computationally hard to check, especially for large systems.
Further, in many applications, obtaining exact values of A may not be feasible and hence a tractable alternative is needed.
Thus, we say that a time invariant linear dynamical system is structurally controllable, if it is possible to select the non-zero
values of A, B, so that Kalman’s rank condition is satisfied [1]. A structurally controllable system is controllable for almost all
A, B; i.e. the pathological cases for which a structurally controllable network is not controllable has zero Lebesgue measure.
The relation between the minimum number of controllers needed to structurally control a network and the size of its maximum

3

matching has been presented in several forms (see [24]). The version used in the current work is the one appearing in Liu et al.
[12] “minimum inputs theorem” (stated below). Moreover, similar equivalence between structural controllability and maximum
matching when every controller can be applied to only one vertex, is studied by Assadi et al. [25].
Furthermore, Commault and Dion [26] study the problem of using only a single controller applied to as few vertices as
possible. More general results regarding the control configuration selection can be found in the work of Pequito et al. [27]
which discusses relations to maximum matching problem as well. Other considerations must be taken into account for deciding
which approach is most suitable for the practical application under consideration. Finally, we have no assumption regarding
self-loops in the network. Cowan et al. [28] study networks, where every vertex influences itself.
Algorithms to find a maximum matching are well studied in the literature and exhibit polynomial time complexity (with

respect to the size of the network). A popular one developed by Micali and Vazirani [29] has running time O |V |0.5 |E| .
Next, for completeness we provide a definition of maximum matching and also state the minimum inputs theorem.
Definition 1. For a directed network G = (V, E), a subset of edges M is a matching, if no two edges in M share a common
starting or a common ending vertex. A maximum matching corresponds to a matching of maximum size.
Definition 2. Given a matching M for directed network G = (V, E), a vertex is matched, if it is an ending vertex of an edge
in the matching M . Otherwise, it is unmatched.
Minimum Inputs Theorem [12]: Let M ∗ be a maximum matching of the network G = (V, E). The minimum number
of controllers needed for structural controllability of the network is max{1, n − |M ∗ |}. Moreover, for any matching M , the
network is struturally controllable using max{1, n − |M |} controllers.
The upshot of this result is that in order to find the minimum number of required controllers for structural controllability we
can equivalently find the size of a maximum matching. Furthermore, one can explicitly find the structure of the input matrix
B according to the proof of minimum inputs theorem. In fact, one can see that a matching is formed of a set of directed loops
and a set of directed paths. The first vertex of each path is unmatched, while all other vertices are matched. According to
Lin’s work [1], one controller is used to actuate every unmatched vertex. Amongst matched vertices, some might need to be
actuated by a controller, but no new controller is needed, as it suffices to apply any of the previously used controllers to one
arbitrary vertex of each loop. So the number of nonzero components in B ∈ Rn×k , or equivalently the total number of the
connections between the inputs and vertices in the network, is at most n. More details are provided by Liu et al. (Supplementary
Information of [12]).
As the problem of finding the minimum number of controllers needed for structural controllability of a network reduces to
maximum matching type of problems, henceforth we use the (minimum) number of unmatched vertices and the (minimum)
number of controllers interchangeably. In this work, we provide results about the size of matchings obtained by different fast
algorithms for classes of random networks. In fact, Karp and Sipser [22] proved that, for the classical undirected Erdos-Renyi
random network, the KS algorithm is optimal. We generalize their results to a larger class of random networks. The remainder
of the paper is organized as follows. In Section II we introduce different classes of random networks subsequently studied in
this work. Furthermore, some probabilistic results needed for technical developments are summarized. The main algorithms

4

studied are introduced in Section III and connections to real networks using some numerical examples are provided in Section
IV. The key results of the paper are presented in Sections V (analysis and optimality of the algorithms).

n
n!
Notations: For set S, let |S| be the number of elements in S. n1 ,...,n
= n1 !...n
. For vertices u, v ∈ V in the network
r
r!
G = (V, E), {u, v} ((u, v) or (v, u) in directed or bipartite networks) denotes an edge, so N = M ∪ {{u, v}} means adding
the edge {u, v} to M gives N . G − {u, v} means removing vertices u, v (and so all edges connected to them) from network G.
Further, degG (v) denotes the degree of v in G i.e. the number of edges in G connected to v. When there is no subscript, the
n
P
|xi |.
network G is identifiable from the context. Finally, for x ∈ Rn , n ∈ {0, 1, 2, ...}∪{∞}, kxk1 is `1 norm of x: kxk1 =
i=1

II. R ANDOM N ETWORKS
In this section, we introduce different classes of random network models and then present some general results about
convergence and concentration of real-valued functions on networks. In order to have a general framework which includes
both directed and undirected networks, we note that every undirected network G = (V, E) can be considered as a directed
network in which, for all vertices i, j, both edges i → j and j → i exist, if and only if the edge i ↔ j exists in the original
undirected network. All statements presented are true for both directed and undirected networks unless explicitly mentioned.
For a comprehensive discussion on constructions and properties of (undirected) random networks, see chapter 3 in Durrett
[30].
The first model for random networks we consider is the Erdos-Renyi (ER) model. A directed network G = (V, E),
V = {1, 2, ..., n} is (drawn from) ER if every edge i → j for i, j = 1, 2, ..., n is present in the network independently
with probability p(n) . Analogously, an undirected network G = (V, E), V = {1, 2, ..., n} is ER if every edge i ↔ j for
i, j = 1, 2, ..., n, i ≤ j is present in the network independently with probability p(n) . Henceforth, for λ ∈ [0, ∞], ER(λ) is a
Erdos-Renyi random network, for which np(n) → λ as n → ∞. In ER(λ) random networks, the parameter λ corresponds to
the average degree.
The next model we consider is the Uniform Fixed-Size (U F S) model. A directed network G = (V, E), V = {1, 2, ..., n} is
U F S when the cardinality of the edge set |E| = kn for some fixed kn , and the kn directed edges are drawn uniformly among
all n2 possible edges. The construction for the undirected network is similar, but the kn edges are chosen uniformly among
all

n(n+1)
2

possible edges. For λ ∈ [0, ∞], we denote by U F S(λ) a random network of the UFS class, for which

directed and

kn
n

→

λ
2

kn
n

→ λ for

for the undirected case, as n → ∞. Once again, the λ parameter corresponds to the average degree.

Finally, we introduce the class of Degree Distribution (DD) random networks. There are a couple of reasons for considering
this class. First, it lets us consider networks with degree distributions commonly found in real networks that simpler models
such as ER (where the degree distribution is Poisson) cannot model. For example, as shown in Fig. 1, the degree distribution
of real world networks can be any arbitrary non-parametric distribution.
Histograms demonstrating input and output degree distributions of some other real world networks can be found in Fig. 2.
Second, as empirically shown in Section IV, the number of controllers for structural controllability of a network is, to a
large extent, determined by its degree distribution. More details can be found in Section IV as well as the work of Liu et al.
[12].

5

Figure 1: Degree distribution histogram of the social network between prison inmates. For more information see Table I. (blue:
input degree, red: output degree). As shown here, it is difficult to model degree distributions of real networks using standard
parameteric distributions.

Figure 2: Degree distribution histogram of some networks. For more information see Table I. (blue: input degree, red: output
degree).

An undirected random network is a member of the DD class, if for a given degree distribution the attachment of edges
is random. Specifically, let p be a probability distribution with support on the set {0, 1, 2, . . .} of nonnegative integers. We
then construct an undirected network DD(p) = (V, E) as follows. Let V = {1, 2, ..., n} and for i ∈ V , let vertex i have Di

6

undirected half-edge(s) (one-half of an edge is connected to vertex i). Note that D1 , . . . , Dn are the corresponding degrees
which are assumed to be independent and identically distributed (iid) with distribution p; P(Di = k) = p(k). To complete the
n
P
Di 
possible attachments of half-edges have equal probability.
construction, we then pair all half-edges randomly; i.e. all i=1
2,...,2

When the number of half-edges
be

1
2

n
P

n
P

Di is an even number, the construction is straightforward and the number of edges will

i=1

Di . When it is an odd number, we pair the half-edges randomly to obtain the network and omit the last single half-edge

i=1

for which no pairing was established at the end of the construction, so that the number of edges will be 21 (

n
P

Di − 1). Note

i=1

that the omission or presence of multiple edges will lead to a difference between D1 , . . . , Dn and the actual observed degrees
deg(1), . . . , deg(n) once the network construction is completed. However, as Lemma 1 below establishes, the asymptotic
empirical degree distribution will be the original degree distribution from which the network was constructed, as long as the
expected value of Di , EDi is finite.
Viewing an undirected network DD(p) as a directed one, both input and output degrees of vertex i are deg(i). To construct
a directed DD random network, denoted by DD(pin , pout ), with distinct input (degin ) and output (degout ) degrees, we do the
(in)

following: once we have iid draws Di

(out)

and Di

from the input and output degree probability distributions pin and pout

respectively:
(in)

P(Di

(out)

= k) = pin (k), P(Di

(in)

= k) = pout (k),
(out)

let vertex i ∈ V have Di

directed half-edges pointing into vertex i and Di
directed half-edges pointing out from vertex
n
n
P
P
(in)
(out)
i. Next, we pair directed half-edges randomly to have min{ Di ,
Di
} edges and omit the remaining half-edges.
i=0
i=0


n
n
P
(in) P
(out)
The random pairing of half-edges implies that all max
Di ,
Di
! possible pairings of half-edges are equally
i=0

(in)

likely. Note that Di

(out)

, Di

i=0

do not need to be independent.

Furthermore, in general, the degrees do not need to be iid. In fact, as shown later in the paper, the key asymptotic
results we establish are based on the empirical degree distributions which are, by the following lemma, same as the original
degree distributions when vertex degrees are iid. However, as long as for all k = 0, 1, . . ., lim

n→∞

(in)

|{i∈V :Di
lim
n
n→∞

=k}|

(out)

|{i∈V :Di
, lim
n
n→∞

=k}|

|{i∈V :Di =k}|
n

(equivalently

) are deterministic, our results hold using the resulting asymptotic empirical degree

distributions.
Lemma 1. For an undirected network G = (V, E), define the asymptotic empirical degree distribution as
p̂(k) = lim

n→∞

If G = DD(p) is a random network and µ =

∞
P

|{i ∈ V : deg(i) = k}|
.
n

kp(k) < ∞, then the limit above exists and we have p̂(k) = p(k) for all

k=0

k = 1, 2, . . .. In general for a network G = (V, E), define the asymptotic empirical input and output degree distributions as
p̂in (k) = lim

n→∞

p̂out (k) = lim

n→∞

|{i ∈ V : degin (i) = k}|
n
|{i ∈ V : degout (i) = k}|
.
n

7

If G = DD(pin , pout ) is a random network and µ =

∞
P

∞
P

kpin (k) =

k=0

kpout (k) < ∞, then for all k = 1, 2, . . . the limits

k=0

above exist and we have p̂in (k) = pin (k), p̂out (k) = pout (k).
Henceforth, for all networks by pin , pout we mean asymptotic empirical degree distributions p̂in , p̂out respectively.
Next, we define the Lipschitz property for real valued functions defined over networks.
Definition 3. Let f be a real-valued function on the set of directed networks. We say f has the Lipschitz property, if
|f (G1 ) − f (G2 )| ≤ 1 whenever G1 = (V, E1 ), G2 = (V, E2 ), E2 = E1 ∪ {e}; i.e. the value of f will change at most by 1 if
one new edge is added to the network.
Remark 1. Properly defining the norm k · k on the networks, one can see the Lipschitz property is the same as the classic
notion |f (G1 ) − f (G2 )| ≤ kG1 − G2 k. Indeed, for every network G = (V, E), letting A(G) be the adjacency matrix of G
|V
P|
(A(G) ∈ R|V |×|V | , for i, j ∈ V if i → j, A(G)ji = 1 and A(G)ji = 0 otherwise), define kGk = kA(G)k1 =
|A(G)ij |.
i,j=1

Then G1 , G2 differ by only one edge if and only if kA(G1 )−A(G2 )k1 = 1. So f has the Lipschitz property if |f (G1 )−f (G2 )| =
|f (A(G1 )) − f (A(G2 )) | ≤ kA(G1 ) − A(G2 )k1 .
Next, we present convergence and concentration inequalities for functions of random networks which have the Lipschitz
property. Specifically, the number of unmatched vertices (or equivalently the number of controllers) obtained by a matching
algorithm, has the Lipschitz property as shown in Section V. The consequence of the Lipschitz property for a function defined
on a “not too dense” random network, is that it concentrates around its expected value. Further, if the average degree of the
network is finite, then the concentration occurs exponentially fast. These results are summarized in the following theorem.
Theorem 1 (Convergence of real-valued functions for random networks). Let G = (V, E) belong to the ER, U F S, DD(pin , pout )
or DD(p) class. For a real-valued function f which has the Lipschitz property, if
lim sup
n→∞

then

f (G)−E(f (G))
n

→P 0 as n → ∞. If in addition,
lim sup
n→∞

then

f (G)−E(f (G))
n

E (|E|)
= 0,
n2

E (|E|) log n
= 0,
n2

→ 0 a.s. as n → ∞. When sup E(|E|)
< ∞ the rate of convergence is exponential; i.e. there is C > 0
n
n≥1

such that for every 0 <  < 1 :
P(

|f (G) − E(f (G))|
> ) ≤ 2 exp(−nC2 ).
n
III. M ATCHING A LGORITHMS

Before studying the algorithms, we provide a description of networks which will be useful later. As mentioned before, every
undirected network can be considered as a directed one. Now to have a better understanding of how the algorithms work we
view every directed network as a bipartite network G = (L, R, E) where L = R = V , E ⊂ L × R, L and R are respectively
the left and the right side of the bipartite network, and for l ∈ L, r ∈ R there is an edge (l, r) ∈ E if and only if in the original
directed network there is an edge from l to r: l → r. Henceforth we will only deal with bipartite networks.

8

Matching algorithms take a network as input and produce a matching as output. Maximum matching algorithms will give
a matching of maximum size. Algorithm 1 is the well known Greedy Algorithm that produces a suboptimal matching MG in
general. For an arbitrarily chosen vertex v on the right side, Greedy tries to find an arbitrary vertex u on the left side which
is connected to v and has not been used before by any other vertex on the right side. Note that as mentioned above, networks
can be assumed to be bipartite. Moreover, clearly the time complexity of Greedy is O(n).
Algorithm 1 : Greedy
Input: G = (L, R, E)
Output: matching MG (G)
MG ← ∅
while E 6= ∅ do
let v ∈ R
if deg(v) = 0 then
G ← G − {v}
else if for u ∈ L, (u, v) ∈ E then
G ← G − {u, v}
MG ← MG ∪ {(u, v)}
end if
end while
return MG

Note that Greedy picks an arbitrary vertex v ∈ R in every iteration. Because the goal is to find a matching of largest
possible size, this strategy for picking a vertex can be improved. First note that for every vertex v ∈ R of degree one, there
is a matching of maximum size in which v is matched. The logic is as follows. Let u ∈ L be the vertex on the left side
connected to v, (u, v) ∈ E. There must exist a vertex on the right side, w ∈ R, such that (u, w) ∈ E, such that w is matched
to u by a matching M of maximum size; since, if not, adding (u, w) to it leads to a matching of larger size. Now defining a
new matching M 0 which is exactly M with (u, w) removed and (u, v) added, i.e. M 0 = M ∪ {(u, v)} − {(u, w)}, we have
|M | = |M 0 | i.e. M 0 is a maximum matching as well. Hence as long as we can find a vertex of degree one, we can find
a matching of exactly maximum size. In other words: no mistake occurs as long as a degree one vertex is picked in every
iteration of Greedy (a mistake occurs if in an iteration, the algorithm adds an edge to the matching which is not optimal, i.e.
leads to a deviation from maximum matching).
Algorithm 2 : Karp-Sipser
Input: G = (L, R, E)
Output: matching MKS (G)
MKS ← ∅
while E 6= ∅ do
let v = arg min deg(w)
w∈L∪R

if deg(v) = 0 then
G ← G − {v}
else if for u ∈ L ∪ R, {u, v} ∈ E then
G ← G − {u, v}
MKS ← MKS ∪ {{u, v}}
end if
end while
return MKS

9

This fact is the idea behind Algorithm 2, called the Karp-Sipser Algorithm (KS) [22], which produces a matching MKS .
In every iteration of KS, among all vertices a vertex of minimum degree is picked.
Regarding time complexity of the KS algorithm, note the following connection with the Greedy one: in every iteration, KS
picks a vertex of minimum degree and by using a “Heap” data structure, finding a vertex of minimum degree has complexity
O(1) [31]; therefore, the running time of KS is linear. Further, since for real networks, the average degree is finite, for each
iteration of the KS algorithm (i.e. excluding up to o(n) iterations) there are O(n) many vertices of degree one, which implies
that determining a degree one vertex takes on average in O(1) steps.
We can simplify the KS algorithm and search for a minimum degree vertex among vertices on only one side to derive
Algorithm 3 that we call the One-sided Karp-Sipser (OKS) Algorithm and whose output we denote by MOKS . As we will
see later in the analysis of real networks, the size of the matching given by OKS is usually less than or equal to the size of
the matching given by KS. The intuition behind this is as follows. It is possible to make a mistake in OKS because of lack
of degree one vertices on the right side, but if degree one vertices exist on the left side, KS can still work optimally. Yet,
later we will prove (asymptotic) optimality of both algorithms.
Algorithm 3 : One-Sided Karp-Sipser
Input: G = (L, R, E)
Output: matching MOKS (G)
MOKS ← ∅
while E 6= ∅ do
let v = argmin deg(w)
w∈R

if deg(v) = 0 then
G ← G − {v}
else if for u ∈ L, (u, v) ∈ E then
G ← G − {u, v}
MOKS ← MOKS ∪ {(u, v)}
end if
end while
return MOKS

IV. N UMERICAL E XAMPLES
In this section, we present the results of selected numerical analyses on real world networks. We study the number of
controllers, or equivalently the number of unmatched vertices for 10 different networks. This provides support to studying DD
random networks as a realistic model for control applications. In other words, using Fig. 4, to find the number of controllers
needed to structurally control a network, one can assume real networks are in fact DD random networks.
The full description of these networks can be found in Table I.

Table II contains the results for 10 networks, including social, internet, web, electronic, neuronal, power grid and transcriptional regulatory networks, enumerated by the first row of the table. The second (third and fourth respectively) row is the
number of controllers needed for structural controllability of the corresponding network if OKS (KS and Maximum Matching
respectively) algorithm will be used.

10

number
1
2
3
4
5
6
7
8
9
10

network
leader2inter-st-collegestudent [32]
celegansneural [33]
p2p-Gnutella06 [34]
polblogs [35]
prisoninter-st-prisoninmates [32]
s208-st [36]
s420-st [36]
s838-st [36]
USpowergrid-n4941 [33]
yeastinter-st [36]

type

|V |

|E|

description

Social

32

96

directed

Neuronal
Internet
WWW

297
8717
1490

2345
31525
19025

directed
directed
directed

Social

67

182

directed

Electronic Circuits
Electronic Circuits
Electronic Circuits
Power Grid
Transcriptional Regulatory

122
252
512
4941
688

189
399
819
13188
1079

directed
directed
directed
undirected
directed

Table I: Real networks used in this paper

Algorithms
|V | − |MOKS |
|V | − |MKS |
|V | − |M ∗ |
average of |V |−|MOKS | for
random network
|V | = n

1
6
6
6

2
51
49
49

3
5033
5033
5033

4
703
702
702

5
10
9
9

5.6 29.8

5006.8

616.5

32

8717

1490

297

Networks
6
29
29
29

7
59
59
59

8
119
119
119

9
610
577
575

10
565
565
565

10.1 24.7

48.6

100.5

454.9

557.7

67

252

512

4941

688

122

Table II: The number of controllers given by different algorithms for different networks as well as the average number of
controllers for equivalent degree distribution random network and the size of the networks.

The fifth row shows the average number of controllers for a random network generated by degree distribution model for
random networks, i.e. input and output degrees of all vertices are the same as the original real-world network but the attachment
of half-edges is random. This random attachment is based on a simple fact that every random permutation is superposition of
large enough number of random swaps. Finally, the last row of the table shows the size of the networks. As seen in the table,
OKS and KS perform very close to Maximum Matching for all networks. Moreover, network 9 is the only one for which
the performance of OKS is significantly different than KS. We suspect that this is because network 9 is the only undirected
network.
The numerical results in Table II can be understood better by the following figures. Fig. 3 shows the performance of
OKS and KS versus Maximum Matching, i.e. rows 2,3 of the Table II versus row 4. The similarity in performance between
OKS, KS and maximum matching algorithms is better depicted in Fig. 3.
The number of controllers for equivalent degree distribution random network versus the original network, i.e. row 5 of the
Table II versus row 4 is shown in Fig. 4. According to this plot, degree distribution random networks are sufficiently realistic
models for real-world networks in terms of the number of controllers needed for structural controllability.

V. M ATCHING A LGORITHMS IN R ANDOM N ETWORKS
In this section, we present results about the asymptotic size of matchings produced by the algorithms presented above.
We first consider the general case where the asymptotic degree distribution of the random network is any arbitrary degree
distribution with finite mean. Then, more detailed results regarding the special case for a Poisson asymptotic empirical degree

11

Figure 3: The number of controllers given by OKS ( ◦ ) and KS ( × ) versus the number of controllers given by Maximum
Matching for 10 different real networks.

Figure 4: The number of controllers for randomly rewired networks versus the number of controllers for the original networks.

distribution will be provided. Even though as seen before, the latter case is not common among real networks, because of
classical interests on ER and U F S random networks and the KS algorithm, as well as comprehensiveness, we also study it.
Before proceeding with the analysis of matching algorithms in an extensive class of random networks, we must ensure
that the size of the matchings provided by either Greedy, KS, OKS algorithms or any maximum matching algorithm has the
Lipschitz property in order to have convergence of

|MG (G)| |MKS (G)| |MOKS (G)|
,
,
n
n
n

and

|M ∗ (G)|
n

for random network G where

M ∗ (G) is a maximum matching of network G. The following lemma establishes the desired Lipschitz property. The size of
the matching provided by any of the above algorithms has the Lipschitz property due to the recursive nature of the algorithms.
The Lipschitz property for the size of maximum matchings comes from their maximality regardless of the algorithm used to
obtain the maximum matching (this follows easily from the definition of maximum matching).
Lemma 2. The real-valued functions |MG |, |MKS |, |MOKS | and |M ∗ | which are the size of matchings provided by Greedy,
KS, OKS and maximum matching algorithms, respectively, have the Lipschitz property.

A. Arbitrary Degree Distribution
We establish the optimality of OKS algorithm which immediately yields optimality of KS as well, for reasons explained
before. For this purpose, we follow in the footsteps of Karp and Sipser [22] and embed the dynamics of both input and output
degree sequences as the algorithm proceeds in continuous time. This embedding provides differential equations governing the
degree sequence vectors. However, in the general degree distribution case, unlike the classic Erdos-Renyi case, the differential

12

equations are defined in arbitrarily high dimensions. So there is little hope of working in fixed small dimension as Karp and
Sipser [22] did (their differential equations were 3 dimensional) and new ideas are needed. The key idea in our proof is to
use the differential equations to show that the number of iterations when there is no degree one vertex (and so the algorithm
can possibly make a mistake) is sublinear (in n) which means the fraction of unmatched vertices (or equivalently the relative
size of the number of controllers) given by OKS is asymptotically the same as that of maximum matching. Finally, a set of
equations for the relative size of maximum matching according to asymptotic empirical input and output degree distributions
is provided.

Theorem 2 (Asymptotic optimality of OKS algorithm). For network G = (L, R, E), |R| = |L| = n let |MOKS (G)| and
|M ∗ (G)| be the size of matching given by OKS algorithm and the size of maximum matching respectively. Let G be either
∞
∞
P
P
ER, U F S or DD random network with finite average degree, i.e. lim |E|
ipin (i) =
ipout (i) < ∞ (where pin , pout
n =
n→∞

i=0

i=0

are asymptotic empirical degree distributions). Then
|M ∗ (G)|
|MOKS (G)|
= lim
.
n→∞
n→∞
n
n
lim

Remark 2. Under the assumptions of Theorem 2, one can show the asymptotic optimality of KS as well: lim

n→∞

∗
lim |M n(G)| .
n→∞

|MKS (G)|
n

=

We omit the proof here as it is very similar to the proof of Theorem 2.

Note that in Theorem 1 letting  = n−r for every r > 21 the convergence holds. So the difference between |MOKS | and
√
|M ∗ | is O( n). Now the following questions arise: (i) what is the size of maximum matching? (ii) how can we compute the
answer (asymptotically) without running the algorithm? The following theorem gives the size of maximum matching in terms
of input and output degree distributions. For u ∈ [0, 1) define moment generating functions:
Φin (u) =

∞
X

pin (i)ui , Φout (u) =

i=0

∞
X

pout (i)ui ,

i=0
∞

X ipin (i)
1
φin (u) = Φ0in (u) =
ui−1 ,
µ
µ
i=1
∞

φout (u) =

where µ =

∞
P

ipin (i) =

i=0

∞
P

X ipout (i)
1 0
Φout (u) =
ui−1 ,
µ
µ
i=1

ipout (i) is the average degree.

i=0

Theorem 3 (Size of Maximum Matching). For (either ER, U F S or DD) random network G = (L, R, E), |R| = |L| = n if
µ < ∞ let U ∗ be
U∗

=
+

1h
Φin (1 − w1 ) + Φin (w2 ) + Φout (1 − w3 ) − 2
2
i
Φout (w4 ) + µ (w3 (1 − w2 ) + w1 (1 − w4 ))

(1)

13

4

where (w1 , w2 , w3 , w4 ) ∈ [0, 1) is the smallest solution of
φout (1 − w3 ) = 1 − w2 , φin (w2 ) = w3 ,
φin (1 − w1 ) = 1 − w4 , φout (w4 ) = w1 ,
then the asymptotic fraction of unmatched vertices is U ∗ :
lim 1 −

n→∞

|M ∗ (G)|
= U ∗.
n

Note that the formula (1) first appeared in Liu et al.’s work [12] and was supported by numerical experiments. The result
above formally proves its validity.

B. Poisson Degree Distribution
We first present selected asymptotic and non-asymptotic results about the fraction of matched vertices for the matching given
by Greedy. Subsequently we generalize the results provided by Karp and Sipser [22] on the performance of KS.
Studying a simple algorithm (Greedy) on a simple random network G (drawn from directed ER where every edge i → j
exists with probability p) allows us to obtain explicitly the non-asymptotic probability mass function for |MG (G)|. The following
theorem also provides the asymptotic behavior of |MG (G)| for directed ER.
Theorem 4 (Greedy for directed ER). Let the network G be directed ER of size n. Then:
P(|MG (G)| = n − k) =
where q = 1 − p and αi (q) =

i
Q

2
αn (q)2
qk ,
2
αk (q) αn−k (q)

(1 − q j ). For ER(λ) (i.e. np → λ) if λ = 0 then lim

n→∞

j=1

lim

n→∞

|MG (G)|
n

|MG (G)|
n

= 0. If λ = ∞ then

= 1. For λ ∈ (0, ∞), |MG (G)| is asymptotically normal:

N

λ − log(2 − e−λ )
1
n
,n
λ
4λ


.

Some of the results in Theorem 4 remain valid for a larger class of random networks including directed and undirected
networks.
Theorem 5 (Greedy for asymptotically Poisson degree distributions). Assume G is one of ER(λ), U F S(λ), DD(p) and
DD(p, p) where probability distribution p is Poisson(λ). If λ = 0 (respectively λ = ∞) then lim

n→∞

1). For λ ∈ (0, ∞), lim

n→∞

|MG (G)|
n

=1−

log(2−e
λ

−λ

)

|MG (G)|
n

= 0 (respespectively

.

Similar results hold for KS. In fact, Karp and Sipser [22] proved that, for the classical undirected Erdos-Renyi random
network (denoted by undirected ER(λ), λ ∈ (0, ∞) here), KS is optimal. They split the running of the algorithm into two
phases. Phase 1 begins when the algorithms starts and finishes the first time there is no vertex of degree one in the network,
when phase 2 starts and proceeds until the algorithm removes all edges from the network. For network G let U (G), U1 (G)
and U2 (G) be the number of vertices left unmatched (became of degree zero before being removed from the network) when

14

running maximum matching, phase 1 and phase 2 respectively, H = (V 0 , E 0 ) be the remaining network at the beginning of
phase 2. Hence |M ∗ (G)| = n − U (G), |MKS (G)| = n − U1 (G) − U2 (G), |MKS (H)| = |V 0 | − U2 (G). Since there is no
deviation from maximum matching as long as vertices of degree one exists, we have U1 (G) ≤ U (G) ≤ U1 (G) + U2 (G). Karp
and Sipser show
U1 (G)
n

U2 (G)
n

→ k(λ) and

|V 0 |
n

→ 0 as n → ∞ so the algorithm is optimal, i.e. lim
→ h(λ) and find functions k, h as k(λ) =

|MKS (G)|
n

n→∞
γ∗ +γ ∗ +γ∗ γ ∗
λ

= lim

− 1, h(λ)

|M ∗ (G)|

. Further, they show

n
n→∞
(1−γ∗ )(γ ∗ −γ∗ )
=
λ

where γ∗ is the

smallest root of γ = λ exp(−λe−γ ) and γ ∗ = λe−γ∗ . For λ ≤ e we have h(λ) = 0 because of γ∗ = γ ∗ . In the following
theorem, we generalize these results to a larger class of random networks.
Theorem 6 (KS for asymptotically Poisson degree distributions). Assume G is one of ER(λ), U F S(λ), DD(p) and DD(p, p)
|MKS (G)|
n
n→∞

where probability distribution p is Poisson(λ). If λ = 0 then lim
lim

n→∞

|MKS (G)|
n

= lim

n→∞

∗

|M (G)|
n

|M ∗ (G)|
n
n→∞

= lim

= 0. If λ = ∞ then

= 1. For λ ∈ (0, ∞), we have
|M ∗ (G)|
|MKS (G)|
= lim
= 1 − k(λ).
n→∞
n→∞
n
n
lim

Furthermore,

U2 (G)
n

→0,

U1 (G)
n

→ k(λ) and

|V 0 |
n

→ h(λ) as n → ∞.

Remark 3. Note that the results in Theorem 6 are consistent with Theorem 3 as follows. Letting pin , pout be Poisson(λ),
calculations show U ∗ = k(λ) because of µ = λ, Φin (u) = Φout (u) = φin (u) = φout (u) = exp (λ(u − 1)).
Results presented in Theorems 5 and 6 are based on the fact that in all mentioned random networks, the asymptotic empirical
degree distribution is Poisson.
VI. C ONCLUSION
We proved that the OKS algorithm is (asymptotically) optimal for determining a set of vertices where controllers should be
applied to. Indeed, first benefiting from the connection between structural controllability of networks and maximum matching
problems (minimum inputs theorem) we introduced simple fast matching algorithms OKS and KS. Further, using topologies
extracted from real networks, we empirically showed that the minimum number of controllers for structural controllability
heavily depends on the degree distribution of the network, which in turn implies that the assumption of a random network
with specified degree distribution is reasonable for many real world networks. Finally, new proof techniques introduced in this
study enable the rigorous analysis of the the performance of a class of fast matching algorithms for random networks.
Ruths and Ruths [37] showed that existing random network models, while capturing the key features for predicting the
minimum number of controllers, are not predicting more detailed control profiles of real networks. This calls for the development
of new random network models that match control profiles, and associated fast control algorithms.
A PPENDIX A
P ROOF OF L EMMA 1
For an arbitrary  > 0, let N be large enough such that

∞
P
k=N +1

kp(k) < 2 . Further, for random network G = (V, E), |V | = n,

remove some edges from G in order to have no vertex of degree larger than N to get network G0 = (V, E 0 ). Now for every
vertex i ∈ V there are possibly two reasons for the difference between Di and degG0 (i):

15

•

the set of edges we removed from G to get G0

•

multiple edges in the network G0

so,
|{i ∈ V : Di = k}| − |{i ∈ V : degG0 (i) = k}| ≤ |E| − |E 0 | +

n
X

1Mi 6=0

(2)

i=1

where Mi is the number of multiple edges in G0 connected to vertex i. There are at most

N
2



pairs of half-edges connected

to vertex i and for every two of them the probability of the outcome Aj that they both are connected to vertex j is at most
(N2 )
where D = 2|E 0 |. So,
(D2 )

 X
n
N
N
2
Mi ≤
1Aj , P(Aj |D) ≤ D
.
2 j=1
2
By Markov’s inequality for any δ > 0 we have:
!
2
n
n
n
n
2n N2
1X
1 X
1 X
1 X
P
.
1Mi 6=0 > δ D ≤
P(Mi 6= 0 D) =
P(Mi ≥ 1 D) ≤
E(Mi D) ≤
n i=1
nδ i=1
nδ i=1
nδ i=1
δ(D − 1)2
|E|
n→∞ n

But lim

= µ and

|E| − |E 0 |
<
n→∞
n
2
lim

(since

∞
P

kp(k) <

k=N +1


2

) imply lim

n→∞

D−1
n

(3)

> µ −  i.e.
n

1X
1Mi 6=0 →P 0
n i=1

(4)

On the other hand, for all k = 1, 2, . . . by the Law of Large Numbers:
lim

n→∞

|{i ∈ V : Di = k}|
= p(k)
n

(5)

Finally, because the only reason for the difference between degG (i) and degG0 (i) is the set of edges we removed from G to
get G0 we have:
|{i ∈ V : degG (i) = k}| − |{i ∈ V : degG0 (i) = k}| ≤ |E| − |E 0 |

(6)

Putting (2), (3), (4), (5), (6) all together:

lim P

n→∞


|{i ∈ V : degG (i) = k}|
− p(k) >  = 0
n

Since the function f (G) = |{i ∈ V : degG (i) = k}| has the Lipschitz property by Theorem 1, a.s. convergence holds as well
i.e. p̂(k) = p(k)

16

For DD(pin , pout ), the changes in the asymptotic empirical degree distributions due to omission of
n
n
n
n
X
X
X
X
(in)
(out)
(in)
(out)
max{
Di ,
Di
} − min{
Di ,
Di
}
i=0

additional half-edges is at most
n
P

(out)
lim 1
D
n→∞ n i=0 i

1
n|

n
P

i=0

(in)

i=0

Di

n
P

−

i=0
(out)

i=0

Di

i=0
n
P
(in)
1
D
n→∞ n i=0 i

| → 0 because by the Law of Large Numbers lim

=

= µ as n → ∞. The contribution of multiple edges is asymptotically zero similarly.
A PPENDIX B
P ROOF OF T HEOREM 1

To prove convergence and concentration inequalities for real-valued functions for random networks we use some classical
notions of probability such as martingale difference sequences. Rhee [38, Theorem 1] presents a concentration inequality for
martingale difference sequences. Here we use a slightly more general version of it. The proof presented by Rhee [38] is valid
by following the same line of reasoning.
Theorem 7. Let Xi , i = 1, 2, . . . , k be a martingale difference sequence. If max kXi k∞ ≤ M < ∞ and
1≤i≤k

k
P
i=1

E(Xi2 |Fi−1 ) ≤

a2 < ∞ then for all t ≥ 0
P(|

k
X

Xi | > t) ≤ 2 exp(−

i=1

a2 M t
ρ(
))
M 2 a2

where ρ(x) = (1 + x) log(1 + x) − x for x ≥ 0.
We prove the following stronger theorems:
Theorem 8. Assume f has the Lipschitz property and G = (V, E) is a random network in which V = {1, 2, . . . , n} and for
(n)

i, j ∈ V , the edge i → j exists independently with probability pij . If
lim sup
n→∞

then

f (G)−E(f (G))
n

n→∞
f (G)−E(f (G))
n

(7)

→P 0 as n → ∞. Furthermore, if
lim sup

then

n
1 X (n)
(n)
p (1 − pij ) = 0
n2 i,j=1 ij

n
log n X (n)
(n)
p (1 − pij ) = 0
n2 i,j=1 ij

(8)

→ 0 a.s. as n → ∞. When the average degree is finite (e.g. ER(λ) for λ < ∞) the rate of convergence

is exponential. In general given
n
1 X (n)
(n)
pij (1 − pij ) ≤ C < ∞
n≥1 n i,j=1

sup

(9)

we have:
P(

|f (G) − E(f (G))|

> ) ≤ 2 exp(−nCρ( ))
n
C

Proof: To have more convenient notation we enumerate all possible edges i → j from 1 to k where k = n2 for
directed ER and k =

n(n+1)
2

for undirected ER. Indeed, Zi , i = 1, 2, . . . , k are independent Bernoulli random variables

17

showing the existence of edges, i.e. if Zi = 1 the corresponding edge exists and if Zi = 0 the corresponding edge does not
exist. Let pi , i = 1, 2, . . . be edge existence probabilities, P(Zi = 1), F0 be the trivial sigma-field and for i = 1, . . . , k let
Fi = σ(Z1 , . . . , Zi ). Now define a martingale difference sequence as Xi = E(f (G)|Fi ) − E(f (G)|Fi−1 ), i = 1, . . . , k so
E(f (G)|Fk ) = f (G), E(f (G)|F0 ) = E(f (G)). Define:
Ui = E(f (G)|Z1 , . . . , Zi−1 , Zi = 1)
Vi = E(f (G)|Z1 , . . . , Zi−1 , Zi = 0)
Thus,
E(f (G)|Z1 , . . . , Zi−1 ) = pi Ui + (1 − pi )Vi


 (1 − pi )(Ui − Vi )
Zi = 1
Xi =

 −pi (Ui − Vi )
Zi = 0
E(Xi2 |Fi−1 ) = pi (1 − pi )(Ui − Vi )2
Since f has the Lipschitz property, |Ui − Vi | ≤ M (M = 1 for directed ER and M = 2 for undirected ER):
max kXi k∞ ≤ max max{pi , 1 − pi } ≤ 1

1≤i≤k
k
X

1≤i≤k

E(Xi2 |Fi−1 ) ≤

k
X

pi (1 − pi ) ≤ a2 < ∞

i=1

i=1

By Theorem 7 for all  > 0 we have:
P(
lim ρ(x)
2
x→0 x

=

1
2

|f (G) − E(f (G))|
n
> ) ≤ 2 exp(−a2 ρ( 2 ))
n
a

(10)

implies:
P(

now if (7) holds then

f (G)−E(f (G))
n

|f (G) − E(f (G))|
n2
> ) ≤ 2 exp(−2 2 )
n
2a

→P 0 as n → ∞. To show the a.s. convergence, note that (8) gives

∞
P
n=1

) < ∞ so by the Borel-Cantelli lemma

f (G)−E(f (G))
n

(G))|
P( |f (G)−E(f
>
n

→ 0 a.s. as n → ∞.

Finally using (9) we can let a2 = nC in (10) to obtain:
P(

|f (G) − E(f (G))|

> ) ≤ 2 exp(−nCρ( ))
n
C

Theorem 8 provides convergence and concentration inequality for ER random networks. A corollary of Theorem 8 is that
the obtained results are valid for undirected random networks of Chung-Lu type (see page 82 of Durrett [30]). In a Chung-Lu
random network the edge between i and j exists with probability

wi wj
n
P
wk
k=1

for the set of weights w1 , . . . , wn . Conditions (7),

18

(8), (9) for a Chung-Lu random network will be lim sup wnn = 0, lim sup wn nlog n = 0 and sup wn < ∞ respectively, where
n→∞

n→∞

wn is the average weight wn =

1
n

n
P

n≥1

wk .

k=1

Theorem 9. Assume f has the Lipschitz properrty and G = (V, E), |E| = kn is U F S. If
kn
=0
n2

(11)

kn log n
=0
n2

(12)

lim sup
n→∞

then

f (G)−E(f (G))
n

→P 0 as n → ∞. If furthermore,
lim sup
n→∞

then

f (G)−E(f (G))
n

→ 0 a.s. as n → ∞. The rate of convergence is exponential when the average degree is finite (e.g. U F S(λ)

for λ < ∞). Namely sup knn ≤ C < ∞ implies:
n≥1

P(

|f (G) − E(f (G))|
2
> ) ≤ 2 exp(−n )
n
C

(13)

Proof: Rhee [38, Theorem 4] shows
P(|f (G) − E(f (G))| > t) ≤ 2 exp(−
2

t2
)
kn

If (11) holds then letting t = n we have exp(− ktn ) → 0. If (12) holds then
Borel-Cantelli Lemma

f (G)−E(f (G))
n

∞
P
n=1

(G))|
P( |f (G)−E(f
> ) < ∞ so by the
n

→ 0 a.s. as n → ∞. To show (13) it suffices to let t = n.

Theorem 10. Let G = (V, E) be DD(pin , pout ) or DD(p) (in the recent case pin = pout = p). Assuming real-valued function
f has the Lipschitz property if
|E|
=0
n2

(14)

|E| log n
=0
n2

(15)

lim sup
n→∞

then

f (G)−E(f (G))
n

→P 0 as n → ∞. If in addition
lim sup
n→∞

then

f (G)−E(f (G))
n

→ 0 a.s.. as n → ∞. When the average degree is finite i.e.
|E|
≤C<∞
n≥1 n
sup

(16)

the rate of convergence is exponential:
P(

|f (G) − E(f (G))|

> ) ≤ 2 exp(−nCρ(
))
n
4C

Proof: To form an inequality like (10) let k be the number of half-edges before being paired (so k is the number of
directed edges - every undirected edge is two directed edges). Enumerate half-edges and for i = 1, 2, . . . , k let Zi be the
random variable indicating the vertex whose half-edge the half-edge i is paired to i.e. Zi = j, j ∈ {1, . . . , n} if half-edge i

19

is paired to a half-edge of vertex j. Let F0 be trivial sigma-field and for i = 1, . . . , k let Fi = σ(Z1 , . . . , Zi ). Now define a
martingale difference sequence as Xi = E(f (G)|Fi ) − E(f (G)|Fi−1 ), i = 1, . . . , k and Uij , Pij as :
Uij = E(f (G)|Z1 , . . . , Zi−1 , Zi = j)
Pij = P(Zi = j|Z1 , . . . , Zi−1 )
Hence Ui = E(f (G)|Z1 , . . . , Zi−1 ) =

n
P

Pij Uij and Xi = Uij − Ui whenever Zi = j. On the other hand,

j=1
n
X

E(Xi2 |Fi−1 ) =

Pij (Uij − Ui )2

j=1

Lipschitz property of f implies |Uij − Uil | ≤ M (M ≤ 4 for undirected case and M ≤ 2 for directed case). Hence for all
i = 1, . . . , k:
kXi k∞ ≤ max kUij − Ui k∞ ≤ max
1≤j≤n

k
X

1≤j≤n

E(Xi2 |Fi−1 ) ≤

n
k X
X

n
X

Pil kUij − Uil k∞ ≤ M < ∞

l=1

Pij M 2 ≤

i=1 j=1

i=1

k
X

M 2 ≤ kM 2 ≤ a2 < ∞

i=1

By Theorem 7 we have:
∀ ≥ 0 P(

|f (G) − E(f (G))|
a2 M n
> ) ≤ 2 exp(− 2 ρ( 2 ))
n
M
a

2

Now (14), (15), (16) give lim sup na 2 = 0, lim sup a
n→∞

n→∞

2

log n
n2

2

= 0 and sup an ≤ 16C < ∞ respectively.
n≥1

A PPENDIX C
P ROOF OF T HEOREM 4

Letting M (n) = n − |MG (G)| be the number of unmatched vertices M (n) =

n
P

Mi where

i=1

Mi =



 1

the vertex picked in i-th iteration is unmatched


 0

the vertex picked in i-th iteration is matched

Now note that according to the algorithm
n−i+1+

P(Mi = 1|M1 , . . . , Mi−1 ) = q
For example P(M (n) = 0) = P(M1 = 0, . . . , Mn = 0) =

n
Q

i−1
P

Mj

j=1

(1 − q n−i+1 ) = αn (q). We have

i=1

P(M (n) = k) =

X
|I|=k

P(Mi = 1{i∈I} , ∀ i = 1, . . . , n).

20

If I = {i1 , . . . , ik } then
P Mi = 1{i∈I} , ∀i = 1, . . . , n



=

(1 − q n ) . . . (1 − q n−i1 +1 )q n−i1 +1 (1 − q n−i1 ) . . . (1 − q n−ik +1 )q n−ik +1 . . . (1 − q k+1 )

=

k
αn (q) Y n−ij +1
q
αk (q) j=1

Thus:
P(M

(n)

αn (q) 1 k(k−1)
= k) =
q2
αk (q)

k
P

X

q

ij

j=1

1≤i1 <...<ik ≤n

But:
k
P

X

q

ij

=

j=1

1≤i1 <...<ik ≤n

n
X
ik =k

=

=

=

=

n
X

iX
k −1

q ik

q ik−1 . . .

q ik . . .

ik =k

i2 =2

n
X

iX
3 −1

q ik . . .

ik =k

i2 =2

n
X

iX
4 −1

q ik . . .

ik =k

i3 =3

n
X

iX
4 −1

q ik . . .

q i2 (q

1 − q i2 −1
)
1−q

q i2

q 1 αi2 −1 (q)
α1 (q) αi2 −2 (q)

q i3

i
q 1+2 h
(1 + q)(1 − q i3 −2 ) − q(1 − q 2i3 −5 )
α2 (q)

q i3

q 1+2 αi3 −1 (q)
α2 (q) αi3 −3 (q)

i3 =3

ik =k

q i1

i1 =1

ik−1 =k−1
iX
3 −1

iX
2 −1

1
αn (q)
= ... =
q 2 k(k+1)
αk (q)αn−k (q)

M (n)
n→∞ n

which establishes the result. Now to show lim

=

log(2−e−λ )
λ

for ER(λ), for large n let (1 − nλ )j = exp(− nλ j) to have:




1 − exp − nλ (n − k)
λ
P(M (n) = k + 1)
1 − q n−k 2k+1
q
=
=
2 exp − (2k + 1) .
(1 − q k+1 )2
n
P(M (n) = k)
1 − exp − nλ (k + 1)
Denote βk = exp(− nλ k) to obtain:

Therefore

P(M (n) =k+1)
P(M (n) =k)

βk2 (1 − e−λ βk−1 )
P(M (n) = k + 1)
=
.
λ
λ
P(M (n) = k)
e n − 2βk + e− n βk2
λ

λ

> 1 if and only if (e− n − 1)βk2 + (e−λ − 2)βk + e n < 0 i.e. the probability mass function is unimodal

and as n → ∞, P(M (n) = k + 1) > P(M (n) = k) if and only if βk−1 < 2 − e−λ which is equivalent to k <
letting k ∗ = arg max P(M (n) = k) we get P(|M (n) − k ∗ | > n) → 0 for all  > 0 as n → ∞ i.e.
0≤k≤n

M (n)
n

→P

log(2−e−λ )
n
λ
log(2−e
λ

−λ

)

so

. By

Theorem 8, a.s. convergence holds as well. To prove the asymptotic normality we will show
lim log

n→∞
k(t)−nµ
√
, k(0)
n
n→∞

where t = lim

= k ∗ ≈ nµ, µ =

P(M (n) = k(t))
t2
=− 2
(n)
2σ
P(M
= k(0))

log(2−e−λ )
, σ2
λ
n−k(t)

log P(M

(n)

= k(t)) =

X
j=1

=

1
4λ .

We have:

√
t
fj ( √ ) − λnµ2 − λt2 − 2λ nµt
n

(17)

21

where the functions fj : R → R, j = 1, 2, . . . are fj (x) = 2 log(1 − e−λ(µ+j/n)−λx ) − log(1 − e−λj/n ). Note that
e−λµ = (2 − e−λ )−1 .

(18)

But for aj = e−λ(µ+j/n) < 1 and some B < ∞
fj (0)

=

fj0 (0)

=

fj00 (0)

=

2 log(1 − e−λ(µ+j/n) ) − log(1 − e−λj/n )
2λaj
1 − aj
−2λ2 aj
(1 − aj )2

|fj000 (x)| <

B.
∗

2

3

t
Now writing fj ( √tn ) = fj (0)+fj0 (0) √tn +fj00 (0) 2n
+fj000 ( √t n ) 6nt√n for some t∗ ∈ [0, t] and using (18), because

1
n (n−k(t))

→

1 − µ definition of Riemann integral implies:
n−k(t)
1 X 0
f (0)
n j=1 j

1−µ
Z

→ 2λ

1
√
n n
Note that | n1

n−k(t)
P
j=1

fj0 (0)−2λµ| ≤

n−k(t)

X
j=1

(1−µ)2
n

→

−2λ

sup
µ≤x≤1

dx = 2λµ

2

1−µ
Z

e−λ(µ+x)
dx = −2λ
(1 − e−λ(µ+x) )2

0

∗

t
fj000 ( √ )
n

−1

0

n−k(t)

1 X 00
f (0)
n j=1 j

1
eλµ+λx

B
√ → 0.
n

<

∂
1
∂x eλx −1

and sup
µ≤x≤1

∂
1
∂x eλx −1

= sup
µ≤x≤1

λeλx
(eλx −1)2

< ∞ imply

√1
n

n−k(t)
P
j=1

fj0 (0)−

n−k(0)
P
√
2λµ n → 0. Now plugging all in (17) we get the desired result since log P(X = k(0)) =
fj (0) − λnµ2 .
j=1

A PPENDIX D
P ROOF OF L EMMA 2
To prove the Lipschitz property for maximum matching let G = (L, R, E), G0 = (L, R, E 0 ), E 0 = E ∪ {e}, |L| = |R| = n
and let M ⊂ E 0 be a maximum matching in G0 . If e ∈
/ M then M is a maximum matching in G. If e ∈ M then M − {e} is
a matching in G so the size of maximum matching is at least |M − {e}|. Thus |M ∗ (G0 )| − 1 ≤ |M ∗ (G)| ≤ |M ∗ (G0 )|.
For the Greedy algorithm, if n = 1 then clearly |MG (G0 )|, |MG (G)| are both either 0 or 1 so |MG (G0 )| − |MG (G)| ≤ 1.
Assume function |MG | has the Lipschitz property for all networks of vertex size n − 1 and define networks H, H 0 as the
networks G, G0 after the first iteration: H = G − {u, v}, H 0 = G0 − {u0 , v 0 }; u, u0 ∈ L; v, v 0 ∈ R so both H, H 0 have n − 1
vertices.
If u = u0 and v = v 0 then networks H, H 0 are exactly the same except potentially the new edge e which can be added to
H in order to get H 0 . Since H, H 0 both have n − 1 vertices, by the assumption |MG (H 0 ) − MG (H)| ≤ 1. On the other hand,
MG (G) = MG (H) ∪ {(u, v)}, MG (G0 ) = MG (H 0 ) ∪ {(u, v)} imply |MG (G)| = |MG (H)| + 1, |MG (G0 )| = |MG (H 0 )| + 1
i.e. |MG (G0 ) − MG (G)| ≤ 1.

22

If v 6= v 0 then the new edge e is connected to v 0 ∈ R, u0 ∈ L and degG (v 0 ) = 0, degG0 (v 0 ) = 1. Now there are two possible
cases:
1) vertex u0 ∈ L is not used in MG (G) i.e. there is not any vertex w ∈ R in MG (G) such that u0 is matched to w by
Greedy algorithm applied to G. Therefore iterations of the Greedy algorithm after the first iteration will not change once
the new edge e is added. In this case MG (G) = MG (H 0 ) and MG (G0 ) = MG (H 0 ) ∪ {(u0 , v 0 )}.
2) vertex u0 ∈ L is used in MG (G) i.e. there is a vertex w ∈ R such that u0 is matched to w by Greedy algorithm applied to G:
(u0 , w) ∈ MG (G) . Therefore the only iteration of the Greedy algorithm which will change once the new edge e is added
is the one that vertex w ∈ R is picked. In this case MG (G) = MG (H 0 ) ∪ {(u0 , w)} and MG (G0 ) = MG (H 0 ) ∪ {(u0 , v 0 )}.
In both cases we have |MG (G0 )| − |MG (G)| ≤ 1. So |MG | has the Lipschitz property. Note that there is no assumption
about the vertices v, v 0 picked in the first iteration of the Greedy algorithm. So this proof is valid assuming vertices v, v 0 are
of minimum degree, i.e. the proof works for |MKS | and |MOKS | as well.

A PPENDIX E
P ROOF OF T HEOREM 2
We prove the theorem in two steps. In Step 1, first we embed the dynamics of input and output degree sequences during the
algorithm in a continuous time Markov process for a random network with bounded degrees. Then, we find explicit expressions
for differential equations governing the dynamics of degree sequences for infinitely large networks. Then, we show that for a
finite random network, the dynamics of degree sequences can be approximated by the solution of the presented initial value
problem. Finally, we show that this solution spends zero time in the cases where there is no vertex of degree one so the number
of iterations of the algorithm there is no vertex of degree one on the right side of the random network is sublinear w.r.t. the
size of the network. In Step 2, we generalize the proof to the unbounded, but finite mean, degree sequences.
Step 1: Embedding in a continuous time Markov process. Assume in addition that the asymptotic empirical degree
distributions are bounded: pin (i) = pout (i) = 0 for i > N i.e. for every vertex v ∈ L ∪ R we have deg(v) ≤ N . First, we
embed the dynamics of the algorithm in a continuous time Markov process. To go to continuous time, define Gn (t) as the
n-vertex network at time t ∈ R where state changes Gn = Gn − {u, v} occur at Exp(n) interarrival times. More precisely, let
τ1 , τ2 , . . . be i.i.d Exp(n) random variables, i.e. the probability density function is ne−nt for t ≥ 0 so E(τi ) =

1
n.

The first

state change Gn = Gn − {u, v} occurs at time t = τ1 , the second one occurs at t = τ1 + τ2 and so forth. Now we construct a
Markov process on R2N which describes the performance of the algorithm. The transition kernel of the Markov process will
be described later. Define X (n) (t), Y (n) (t) ∈ RN as:
(n)

Xk (t) =
(n)

Yk (t) =

1
{v ∈ R : deg(v) = k in Gn (t)} ,
n
1
{v ∈ L : deg(v) = k in Gn (t)} ,
n

for k = 1, 2, . . . , N . In addition let m = m(X (n) (t)) be the minimum degree of vertices in R(t): m(X (n) (t)) = min{k :
(n)

Xk (t) 6= 0} so letting v1 = v, u1 = u whenever a state change occurs we have deg(v1 ) = m. Let (ui , v) ∈ E for

23

i = 1, . . . , m, K = deg(u1 ) and (u, vj ) ∈ E for j = 1, . . . , K. So for a network of size n we have the following conditional
degree distributions for vertices u1 , . . . , um , v2 , . . . , vK :
(n)

nkYk (t) − k
Pn (deg(ui ) = k|Ai−1 (t)) =
n

N
P
k=1

(n)

(n)

n

N
P
k=1

(n)
kXk (t)

1deg(uj )=k

j=1

kYk (t) −

nkXk (t) − k
Pn (deg(vi ) = k|Bi−1 (t)) =

i−1
P

i−1
P

,
deg(uj )

j=1

i−1
P

1deg(vj )=k

j=1

−

i−1
P

,
deg(vj )

j=1

where Ai (t) = (deg(u1 ), . . . , deg(ui ), Y (n) (t)), Bi (t) = (deg(v1 ), . . . , deg(vi ), X (n) (t)). Note that since interarrival times are
i.i.d exponential random variables, X (n) (t), Y (n) (t) are continuous time Markov processes.
Letting X̃ (n) , Ỹ (n) ∈ RN be the corresponding vectors after one state change for x, y ∈ RN define functions Fn , Gn :
R2N → RN as:
Fn (x, y) = nEn (X̃ (n) − X (n) |X (n) = x, Y (n) = y),
Gn (x, y) = nEn (Ỹ (n) − Y (n) |X (n) = x, Y (n) = y),
where En is expected value w.r.t Pn . Since the process is Markov, probability distribution of X̃ (n) , Ỹ (n) depends only on
X (n) , Y (n) .
(n)

Asymptotic initial value problem: Define P(deg(ui ) = k) =

kYk (t)
, P(deg(vi )
N
P
(n)
kYk (t)

(n)

= k) =

k=1

kXk (t)
.
N
P
(n)
kXk (t)

Note that Pn , P

k=1

can be defined for every x, y ∈ RN with non-negative components. Now, for arbitrary x, y, some algebra gives:

For C1 =

2N 2
, C2
N
P
kyk
k=1

=

2N 2
.
N
P
kxk

|Pn (deg(ui ) = k|Ai−1 (t)) − P(deg(ui ) = k)| ≤

C1
,
n

(19)

|Pn (deg(vi ) = k|Bi−1 (t)) − P(deg(vi ) = k)| ≤

C2
.
n

(20)

Define:

k=1

F(x, y) = nE(X̃ (n) − X (n) |X (n) = x, Y (n) = y),
G(x, y) = nE(Ỹ (n) − Y (n) |X (n) = x, Y (n) = y),
where E is expected value w.r.t P. Since
(n)

nX̃k

(n)

= nXk

+

K
X
[1deg(vj )=k+1 − 1deg(vj )=k ] − 1k=m ,

(21)

j=2

(n)
nỸk

=

(n)
nYk

m
X
+
[1deg(uj )=k+1 − 1deg(uj )=k ] − 1k=K ,
j=2

(22)

24

inequalities (19), (20) yield
kFn (x, y) − F(x, y)k1 ≤

4N 4 1
,
N
P
n
kxk

(23)

k=1

kGn (x, y) − G(x, y)k1 ≤

4N 4 1
,
N
P
n
kyk

(24)

k=1

and,
F(x, y) = (

kA2 yk1
1
− 1)
(SAx − Ax) − 1m(x) ,
kAyk1
kAxk1

G(x, y) = −

Ay
m(x) − 1
+
(SAy − Ay),
kAyk1
kAyk1

where A and S are moment matrix and shift matrix respectively, i.e., A, S ∈ RN ×N , Aij is i for i = j and 0 otherwise, and Sij
is 1 for i = j − 1 and 0 otherwise, m(x) = min{k : xk 6= 0} and 1m ∈ RN is the vector in which m-th component is 1 and all
N
N
P
P
(n)
(n)
others are 0. Note that kAX (n) (t)k1 = kAY (n) (t)k1 because for finite n always |E(t)| = n
kXk (t) = n
kYk (t).
k=1

k=1

Besides, transition kernel of the Markov process can be formulated by Pn according to (21), (22).
Approximating the dynamics of the degree sequences by the solution of asymptotic initial value problem: Now we
can use Kurtz’s Theorem [39]. Given functions F, G : R2N → RN and positive constant T , define x(t), y(t) : [0, T ] → RN as
the solution of the initial value problems

and let E = {z ∈ RN such that:  <

ẋ = F(x, y), xk (0) = pin (k), k = 1, . . . , N ,

(25)

ẏ = G(x, y), yk (0) = pout (k), k = 1, . . . , N ,

(26)

N
P

kzk ≤ N }. Suppose the following statements hold:

k=1

1) lim

sup kFn (z1 , z2 ) − F(z1 , z2 )k1 = 0.

2) lim

sup kGn (z1 , z2 ) − G(z1 , z2 )k1 = 0.

n→∞ z1 ,z2 ∈E

n→∞ z1 ,z2 ∈E

(n)

3) for all k = 1, . . . , N , lim Xk (0) = pin (k).
n→∞

(n)

4) for all k = 1, . . . , N , lim Yk (0) = pout (k).
n→∞

5) functions F, G are Lipschitz (in the classic sense).
Then


lim Pn ∃t ∈ [0, T ] : m(X (n) (t)) 6= m(x(t)) = 0.

(27)

n→∞

Letting T = T () = sup{t :

N
P
k=1

kxk (t) > ,

N
P

kyk (t) > } for some arbitrary  > 0, the first two conditions are satisfied by

k=1
(n)

(n)

(23), (24). By the definition of asymptotic empirical degree distributions lim Xk (0) = pin (k) and lim Yk (0) = pout (k).
n→∞

n→∞

On the other hand, the initial value problems (25), (26) have unique solutions since defining metric d on RN as d(x, y) =

25

kx − yk1 + 1m(x)6=m(y) , F, G are Lipschitz with respect to this metric i.e. there is a B < ∞ such that for all x, x0 , y, y 0 ∈ RN
d(F(x, y), F(x0 , y 0 )) < B(d(x, x0 ) + d(y, y 0 )),
d(G(x, y), G(x0 , y 0 )) < B(d(x, x0 ) + d(y, y 0 )).
Note that stopping time at T (), i.e. when n edges are remaining in the network to be removed by the algorithm, will not
cause any problem since continuing the algorithm from that point on cannot add more than  edges to the matching on a scale
relative to the number n of vertices.
Properties of the asymptotic initial value problems: The useful fact about the solutions of (25), (26) is that Lebesgue
measure of the set {0 < t < T : m(x(t)) > 1} is zero. Suppose it is not. So there are 0 < t1 < t2 such that x1 (t) = 0 for all
t ∈ [t1 , t2 ] so

dx1 (t)
dt

= 0 for all t ∈ (t1 , t2 ). But
dx1 (t)
kA2 yk1
1
= F1 (x, y) = (
− 1)
(2x2 (t) − x1 (t))
dt
kAyk1
kAxk1

implies x2 (t) = 0 for all t ∈ (t1 , t2 ) which means m(x(t)) > 2 for all t ∈ (t1 , t2 ). Repeating this argument for x2 now we
will get m(x(t)) > 3 and so on. Therefore, m(x(t)) > N which is impossible. Thus, the set {0 < t < T : m(x(t)) > 1} has
zero Lebesgue measure.
Sublinearity of the number of iterations of the algorithm with no degree one vertex: Let J (n) ⊂ {1, 2, . . . , n} be the
set of indices i of iterations of OKS such that after the i-th iteration the minimum degree on the right side of the network is
larger than one. Since the set {0 < t < T : m(x(t)) > 1} has zero Lebesgue measure by (27) Lebesgue measure of the set
{0 < t < T : m(X (n) (t)) > 1} goes to 0 as n grows. Because the Lebesgue measure of the set {0 < t < T : m(X (n) (t)) > 1}
P
P
P
1
is
τi+1 we have lim
τi+1 = 0 but by the Law of Large Numbers lim |J (n)
nτi+1 = E(nτ1 ) = 1. Therefore
|
i∈J (n)
(n)
lim |J |
n→∞ n

=

n→∞
i∈J (n)
P
|J (n) | 1
lim
(n) |
n→∞ n |J
i∈J (n)

n→∞

nτi+1 = lim

n→∞

P

i∈J (n)

τi+1 = 0 i.e. the number of iterations of OKS algorithm for which

i∈J (n)

there is no vertex of degree one on the right side of the network is sublinear w.r.t. the size of the network.
|J (n) |
n→∞ n

Sublinearity of difference between the output of OKS and maximum matching: Using lim

= 0 we prove that

the size of the matching provided by the OKS algorithm is away from maximum matching size by a sublinear factor. Starting
the algorithm, as long as the minimum degree on the right side of the network is one, OKS makes no mistake, i.e. the size of
the matching by OKS is the same as the size of maximum matching. When the minimum degree is m = m(X (n) (t)) > 1 it
is possible that OKS picks a vertex on the left side which is not the optimal choice. We make it optimal by manipulating the
network: if v ∈ R, u ∈ L, deg(v) = m are the chosen vertices in the iteration of the algorithm to be removed from the network,
MOKS = MOKS ∪ {(u, v)}, manipulate the network by removing all other m − 1 edges connected to v. Since |M ∗ | has the
Lipschitz property, removing these m − 1 edges will change the size of the maximum matching by at most m − 1. Since m is
the minimum degree and the average degree is bounded, m − 1 is bounded as well. On the other hand, the number of iterations
that OKS will face such cases is sublinear w.r.t. the size of the network, so the whole number of possible errors, or in other
words, the whole deviation from maximum matching made by OKS is sublinear, i.e. lim

n→∞

|MOKS (G)|
n

= lim

n→∞

|M ∗ (G)|
.
n

Step 2: Generalization to unbounded degree. Now to generalize the proof to cases where the asymptotic empirical degree

26

distributions are not bounded, we use the classical technique of truncation. For arbitrary  > 0, let N be large enough such
∞
∞
P
P
that
kpin (k) < 2 ,
kpout (k) < 2 . In random network G remove some edges in order to have no vertex of degree
i=N +1

k=N +1

larger than N to get random network H which has bounded asymptotic empirical degree distributions. By Step 1,
|M ∗ (H)|
|MOKS (H)|
= lim
.
n→∞
n→∞
n
n
lim

(28)

Because by Lemma 2 both functions |M ∗ |, |MOKS | have the Lipschitz property and asymptotically the number of edges
removed from G to get H is less than n:
|M ∗ (H)| − |M ∗ (G)|
< ,
n

(29)

|MOKS (H)| − |MOKS (G)|
< .
n

(30)

lim

n→∞

lim

n→∞

Now (28), (29), (30) imply the desired result. Further, when  → 0, N → ∞, so formally we can take N = ∞ and write the
functions F, G : R∞ → R∞ as

F(x, y)
G(x, y)

kA2 yk1
1
− 1)
(SAx − Ax) − 1m(x) ,
kAyk1
kAxk1
Ay
m(x) − 1
= −
+
(SAy − Ay),
kAyk1
kAyk1

=

(

for matrices A, S ∈ R∞×∞ provided kA2 x(0)k1 =

∞
P

k 2 pin (k) < ∞ or kA2 y(0)k1 =

k=1

∞
P

k 2 pout (k) < ∞.

k=1

A PPENDIX F
P ROOF OF T HEOREMS 5,6
As we saw in the proof of Theorem 2, The asymptotic performance of Greedy, OKS and KS algorithms can be described
by asymptotic empirical degree distributions which are solutions of some initial value problems. If we find functions F, G :
R∞ → R∞ for Greedy and KS we will have
(

kA2 yk1
1
x
− 1)
(SAx − Ax) −
,
kAyk1
kAxk1
kxk1

F(x, y)

=

G(x, y)

kAxk1
Ay
kxk1 − 1
= −
++
(SAy − Ay)
kAyk1
kAyk1

for Greedy and for KS
F(x, y)

G(x, y)

=





xm
kA2 yk1
1
ym
Ax
m−1
(
− 1)
(SAx − Ax) − 1m +
−
+
(SAx − Ax)
xm + ym
kAyk1
kAxk1
xm + ym
kAxk1
kAxk1

=





ym
kA2 xk1
1
xm
Ay
m−1
(
− 1)
(SAy − Ay) − 1m +
−
+
(SAy − Ay)
xm + ym
kAxk1
kAyk1
xm + ym
kAyk1
kAyk1

27

where m = min{m(x(t)), m(y(t))} is the minimum degree. Since for KS we have G(x, y) = F(y, x), when x(0) = y(0)
(i.e. pin = pout ) x(t) = y(t) and
ẋ = F(x) = (

kA2 xk1
SAx − Ax
Ax
1m
+ m − 2)
−
−
kAxk1
2kAxk1
2kAxk1
2

Thus for any degree distribution p the dynamics of KS is the same for both DD(p) and DD(p, p). Further, regarding the
results provided in Theorems 5, 6 the relative size of the output of the algorithm as well as the dynamics of the algorithm is the
same for all random networks ER(λ), U F S(λ), DD(p) and DD(p, p) where probability distribution p is Poisson(λ) because
|MG (G)|
n
n→∞

they all are sharing the asymptotic empirical degree distributions. So Theorem 4 implies lim

= 1−

log(2−e−λ )
.
λ

For

KS, all mentioned statements are proved for undirected ER(λ) by Karp and Sipser [22] so are valid for the desired class of
random networks.
A PPENDIX G
P ROOF OF T HEOREM 3
Here we assume in addition that kA2 x(0)k1 =

∞
P

k 2 pin (k) < ∞ and kA2 y(0)k1 =

k=1

∞
P

k 2 pout (k) < ∞. Generalization to

k=1

the case where above quantities are not bounded is straightforward similar to Step 2 in the proof of Theorem 2 and is omitted.
Because lim

n→∞

|M ∗ (G)|
n

= lim

n→∞

|MKS (G)|
n

it suffices to show U ∗ = lim 1 − |MKSn (G)| . To show the latter claim, we run KS
n→∞

algorithm and find the number of vertices left unmatched by the algorithm. Similar to what we did in the proof of Theorem
2 the asymptotic fraction of vertices left unmatched by KS is
|MKS (G)|
1 − lim
= pin (0) +
n→∞
n

ZT 


xm
kA2 yk1
(m − 1)ym x1 (t)
(
− 1) +
dt
xm + ym kAyk1
xm + ym kAxk1

0

where
T = sup{t :

∞
X

kxk (t) > 0,

k=1

∞
X

kyk (t) > 0}

k=1

ẋ = F(x, y), x(0) = pin
ẏ = F(y, x), y(0) = pout




kA2 yk1
1
ym
Ax
m−1
xm
(
− 1)
(SAx − Ax) − 1m +
−
+
(SAx − Ax)
F(x, y) =
xm + ym
kAyk1
kAxk1
xm + ym
kAxk1
kAxk1
and m = min{m(x(t)), m(y(t))} is the minimum degree. Since as we saw in the proof of Theorem 2 the set {t : m(x(t)) >
1, m(y(t)) > 1} is of zero Lebesgue measure without loss of generality in all integrations we can assume m = 1, especially
|MKS (G)|
1 − lim
= pin (0) +
n→∞
n

ZT

x1
kA2 yk1
x1 (t)
(
− 1)
dt
x1 + y1 kAyk1
kAxk1

0

Now define:

Zt
x0 (t) = pin (0) +
0

x1
kA2 y(s)k1
x1 (s)
(
− 1)
ds,
x1 + y1 kAy(s)k1
kAxk1

28

Zt
y0 (t) = pout (0) +

y1
kA2 x(s)k1
y1 (s)
(
− 1)
ds,
x1 + y1 kAx(s)k1
kAyk1

0

µ(t) =

∞
X

ixi (t) =

i=0

∞
X

iyi (t) = kAxk1 = kAyk1 ,

i=0

Φin (t, u) =

∞
X

xi (t)ui ,

i=0

Φout (t, u) =

∞
X

yi (t)ui ,

i=0

φin (t, u) =

∞
X
i=1

φout (t, u) =

∞
X
i=1

ixi (t) i−1
u ,
kAx(t)k1
iyi (t) i−1
u ,
kAy(t)k1

φin (t, w2 (t)) = w3 (t),
φin (t, 1 − w1 (t)) = 1 − w4 (t),
φout (t, w4 (t)) = w1 (t),
φout (t, 1 − w3 (t)) = 1 − w2 (t),
V (t) =

∞
X

xi (t) = kx(t)k1 ,

i=1

U (t) =

1
2

h

Φin (t, w2 (t)) + Φin (t, 1 − w1 (t)) + Φout (t, w4 (t)) + Φout (t, 1 − w3 (t)) − 2

i
+ µ(t) w3 (t)(1 − w2 (t)) + w1 (t)(1 − w4 (t))

Since x1 (T ) = x2 (T ) = . . . = 0, y1 (T ) = y2 (T ) = . . . = 0 we have V (T ) = 0, µ(T ) = 0. But V (0) = 1 − pin (0) and for
m=1
dkxk1
V̇ (t) =
dt



x1
kA2 yk1
x1
y1
=
−(
− 1)
−1 −
x1 + y1
kAyk1
kAxk1
x1 + y1
x1
kA2 yk1
x1
(
− 1)
−1
= −
x1 + y1 kAyk1
kAxk1
= −ẋ0 (t) − 1

i.e. −1 + pin (0) = V (T ) − V (0) = x0 (0) − x0 (T ) − T = pin (0) − x0 (T ) − T . Therefore Φin (T, u) = x0 (T ), Φout (T, u) =
y0 (T ), U (T ) = 1 − 2T and
1 − lim

n→∞

|MKS (G)|
= x0 (T ) = y0 (T ) = 1 − T
n

(31)

29

On the other hand, as long as m = 1:
dµ
µ̇(t) =
dt





y1
kA2 xk1
x1
kA2 yk1
−x1 − kAxk1 + x1
=
−
+
(
− 1)
−1
x1 + y1
kAxk1
x1 + y1
kAyk1
kAxk1
x1 kA2 yk1
y1 kA2 xk1
= −
−
x1 + y1 kAyk1
x1 + y1 kAxk1
x1 kA2 yk1 + y1 kA2 xk1
= −
,
(x1 + y1 )kAxk1

d
Φin (t, w2 (t))
dt

=
+
=
+

d
Φin (t, 1 − w1 (t))
dt

=
+
=
+

d
[µ(t)w3 (t)(1 − w2 (t))]
dt

i
x1 h kA2 yk1
(
− 1)φin (t, w2 (t))(1 − w2 (t)) − w2 (t)
x1 + y1 kAyk1

y1 
− w2 (t)φin (t, w2 (t)) + kAxk1 ẇ2 (t)φin (t, w2 (t))
x1 + y1


x1
kA2 yk1
(
− 1)w3 (t)(1 − w2 (t)) − w2 (t)
x1 + y1
kAyk1

y1 
− w2 (t)w3 (t) + kAxk1 ẇ2 (t)φin (t, w2 (t)),
x1 + y1

i
x1 h kA2 yk1
(
− 1)φin (t, 1 − w1 (t))w1 (t) − 1 + w1 (t)
x1 + y1 kAyk1

y1 
− 1 + w1 (t)φin (t, 1 − w1 (t)) − kAxk1 ẇ1 (t)φin (t, 1 − w1 (t))
x1 + y1


x1
kA2 yk1
(
− 1)w1 (t)(1 − w4 (t)) − 1 + w1 (t)
x1 + y1
kAyk1

y1 
− (1 − w1 (t))(1 − w4 (t)) − kAxk1 ẇ1 (t)φin (t, 1 − w1 (t)),
x1 + y1

= µ̇(t)w3 (t)(1 − w2 (t)) + µ(t)ẇ3 (t)(1 − w2 (t)) − µ(t)w3 (t)ẇ2 (t)




x1 kA2 yk1 + y1 kA2 xk1
=
−
w3 (t)(1 − w2 (t)) + kAxk1 ẇ3 (t)(1 − w2 (t)) − w3 (t)ẇ2 (t) .
(x1 + y1 )kAxk1

The above equations imply:
dU (t)
=
dt 

x1
kA2 yk1
y1
(
− 1)w3 (t)(1 − w2 (t)) − w2 (t) +
[−w2 (t)w3 (t)] + kAxk1 ẇ2 (t)φin (t, w2 (t))
x1 + y1
kAyk1
x1 + y1


x1
kA2 yk1
y1
(
− 1)w1 (t)(1 − w4 (t)) − 1 + w1 (t) +
[−(1 − w1 (t))(1 − w4 (t))] − kAxk1 ẇ1 (t)φin (t, 1 − w1 (t))
x1 + y1
kAyk1
x1 + y1


y1
kA2 xk1
x1
(
− 1)w1 (t)(1 − w4 (t)) − w4 (t) +
[−w4 (t)w1 (t)] + kAyk1 ẇ4 (t)φin (t, w4 (t))
x1 + y1
kAxk1
x1 + y1


y1
kA2 xk1
x1
(
− 1)w3 (t)(1 − w2 (t)) − 1 + w3 (t) +
[−(1 − w3 (t))(1 − w2 (t))] − kAyk1 ẇ3 (t)φin (t, 1 − w3 (t))
x1 + y1
kAxk1
x1 + y1
x1 kA2 yk1 + y1 kA2 xk1
(−
)w3 (t)(1 − w2 (t)) + kAxk1 [ẇ3 (t)(1 − w2 (t)) − w3 (t)ẇ2 (t)]
(x1 + y1 )kAxk1
x1 kA2 yk1 + y1 kA2 xk1
(−
)w1 (t)(1 − w4 (t)) + kAxk1 [ẇ1 (t)(1 − w4 (t)) − w1 (t)ẇ4 (t)]
(x1 + y1 )kAxk1

2

+
+
+
+
+

30

i.e.
d
2 U (t)
dt


x1
kA2 yk1
kA2 yk1
=
−
(w3 (t)(1 − w2 (t)) +w1 (t)(1 − w4 (t))) + (
− 1)w3 (t)(1 − w2 (t)) − w2 (t)
x1 + y1
kAyk1
kAyk1

kA2 yk1
+(
− 1)w1 (t)(1 − w4 (t)) − 1 + w1 (t) −w4 (t)w1 (t) − (1 − w3 (t))(1 − w2 (t))
kAyk1

y1
kA2 xk1
+
−
(w3 (t)(1 − w2 (t)) +w1 (t)(1 − w4 (t))) −w2 (t)w3 (t) − (1 − w1 (t))(1 − w4 (t))
x1 + y1
kAxk1

kA2 xk1
kA2 xk1
− 1)w1 (t)(1 − w4 (t)) − w4 (t) +(
− 1)w3 (t)(1 − w2 (t)) − 1 + w3 (t)
+(
kAxk1
kAxk1
+ kAxk1 [ẇ2 (t)w3 (t) − ẇ1 (t)(1 − w4 (t)) +ẇ4 (t)w1 (t) − ẇ3 (t)(1 − w2 (t))
+

ẇ3 (t)(1 − w2 (t)) − w3 (t)ẇ2 (t) +ẇ1 (t)(1 − w4 (t)) − w1 (t)ẇ4 (t)] .

Simplifying
2

d
U (t)
dt

=

+


x1
kA2 yk1
kA2 yk1
−
(w3 (t)(1 − w2 (t)) + w1 (t)(1 − w4 (t))) +
w3 (t)(1 − w2 (t)) − w3 (t)(1 − w2 (t))
x1 + y1
kAyk1
kAyk1

kA2 yk1
−w2 (t) +
w1 (t)(1 − w4 (t)) − w1 (t)(1 − w4 (t)) − 1 +w1 (t) − w4 (t)w1 (t) − (1 − w3 (t))(1 − w2 (t))
kAyk1

kA2 xk1
y1
−
(w3 (t)(1 − w2 (t)) +w1 (t)(1 − w4 (t))) − w2 (t)w3 (t) − (1 − w1 (t))(1 − w4 (t))
x1 + y1
kAxk1

kA2 xk1
kA2 xk1
+
w1 (t)(1 − w4 (t)) − w1 (t)(1 − w4 (t)) − w4 (t) +
w3 (t)(1 − w2 (t)) − w3 (t)(1 − w2 (t)) − 1 + w3 (t)
kAxk1
kAxk1

yields
2

d
x1
y1
U (t) =
[−2] +
[−2] = −2
dt
x1 + y1
x1 + y1

Again, since the set {t : m > 0} is of zero Lebesgue measure integrating both sides of

d
dt U (t)

= −1 we have:

1 − 2T = U (T ) = U (0) − T.
So U ∗ = U (0) = 1 − T which is the desired result by (31).

R EFERENCES
[1] C.-T. Lin, “Structural controllability,” Automatic Control, IEEE Transactions on, vol. 19, no. 3, pp. 201–208, 1974.
[2] I. Rajapakse, M. Groudine, and M. Mesbahi, “What can systems theory of networks offer to biology?” PLoS computational biology, vol. 8, no. 6, p.
e1002543, 2012.
[3] R. Srikant, The mathematics of Internet congestion control.

Springer Science & Business Media, 2004.

[4] E. Dinits, “Algorithm of solution to problem of maximum flow in network with power estimates,” Doklady Akademii Nauk SSSR, vol. 194, no. 4, p.
754, 1970.
[5] L. R. Ford and D. R. Fulkerson, “Maximal flow through a network,” Canadian journal of Mathematics, vol. 8, no. 3, pp. 399–404, 1956.
[6] A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum-flow problem,” Journal of the ACM (JACM), vol. 35, no. 4, pp. 921–940, 1988.
[7] T. B. Crabill, D. Gross, and M. J. Magazine, “A classified bibliography of research on optimal design and control of queues,” Operations Research,
vol. 25, no. 2, pp. 219–232, 1977.
[8] L. Tadj and G. Choudhury, “Optimal design and control of queues,” Top, vol. 13, no. 2, pp. 359–412, 2005.

31

[9] C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of optimal queuing network control,” Mathematics of Operations Research, vol. 24, no. 2, pp.
293–305, 1999.
[10] J. Nino-Mora, “Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach,” Mathematical programming,
vol. 93, no. 3, pp. 361–413, 2002.
[11] D. G. Luenberger, Introduction to dynamic systems.

John Wiley & Sons New York, 1979.

[12] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex networks,” Nature, vol. 473, no. 7346, pp. 167–173, 2011.
[13] I. Rajapakse, D. Scalzo, and M. Groudine, “Losing control: Cancer’s catastrophic transition,” Nucleus, vol. 2, no. 4, pp. 249–252, 2011.
[14] J.-M. Dion, C. Commault, and J. Van Der Woude, “Generic properties and control of linear structured systems: a survey,” Automatica, vol. 39, no. 7,
pp. 1125–1144, 2003.
[15] A. Gibbons, Algorithmic graph theory.

Cambridge University Press, 1985.

[16] B. Bollobás, “Random graphs, volume 73 of cambridge studies in advanced mathematics,” 2001.
[17] A. Frieze and P. Melsted, “Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables,” Random Structures &
Algorithms, vol. 41, no. 3, pp. 334–364, 2012.
[18] J. Aronson, A. Frieze, and B. G. Pittel, “Maximum matchings in sparse random graphs: Karp-Sipser revisited,” Random Structures and Algorithms,
vol. 12, no. 2, pp. 111–177, 1998.
[19] T. Tao and V. Vu, “Random matrices have simple spectrum,” arXiv preprint arXiv:1412.1438, 2014.
[20] T. Bohman and A. Frieze, “Karp-Sipser on random graphs with a fixed degree sequence,” Combinatorics, Probability and Computing, vol. 20, no. 05,
pp. 721–741, 2011.
[21] P. Balister and S. Gerke, “Controllability and matchings in random bipartite graphs,” Surveys in Combinatorics 2015, vol. 424, p. 119, 2015.
[22] R. M. Karp and M. Sipser, “Maximum matching in sparse random graphs,” in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science.
IEEE, 1981, pp. 364–375.
[23] A. Olshevsky, “Minimal controllability problems,” Control of Network Systems, IEEE Transactions on, vol. 1, no. 3, pp. 249–258, 2014.
[24] C. Commault, J.-M. Dion, and J. W. van der Woude, “Characterization of generic properties of linear structured systems for efficient computations,”
Kybernetika, vol. 38, no. 5, pp. 503–520, 2002.
[25] S. Assadi, S. Khanna, Y. Li, and V. M. Preciado, “Complexity of the minimum input selection problem for structural controllability,” IFAC-PapersOnLine,
vol. 48, no. 22, pp. 70–75, 2015.
[26] C. Commault and J.-M. Dion, “The single-input minimal controllability problem for structured systems,” Systems & Control Letters, vol. 80, pp. 50–55,
2015.
[27] S. Pequito, S. Kar et al., “A framework for structural input/output and control configuration selection in large-scale systems,” 2013.
[28] N. J. Cowan, E. J. Chastain, D. A. Vilhena, J. S. Freudenberg, and C. T. Bergstrom, “Nodal dynamics, not degree distributions, determine the structural
controllability of complex networks,” PloS one, vol. 7, no. 6, p. e38398, 2012.
[29] S. Micali and V. V. Vazirani, “An O(|V |0.5 |E|) algoithm for finding maximum matching in general graphs,” in Foundations of Computer Science, 1980.,
21st Annual Symposium on.

IEEE, 1980, pp. 17–27.

[30] R. Durrett, Random graph dynamics.

Cambridge university press Cambridge, 2007, vol. 200, no. 7.

[31] T. H. Cormen and C. Charles, “C. e, leiserson, and rl rivest, introduction to algorithms,” 1990.
[32] M. A. Van Duijn, E. P. Zeggelink, M. Huisman, F. N. Stokman, and F. W. Wasseur, “Evolution of sociology freshmen into a friendship network,” Journal
of Mathematical Sociology, vol. 27, no. 2-3, pp. 153–191, 2003.
[33] D. J. Watts and S. H. Strogatz, “Collective dynamics of small-worldnetworks,” nature, vol. 393, no. 6684, pp. 440–442, 1998.
[34] J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” ACM Transactions on Knowledge Discovery from
Data (TKDD), vol. 1, no. 1, p. 2, 2007.
[35] L. A. Adamic and N. Glance, “The political blogosphere and the 2004 us election: divided they blog,” in Proceedings of the 3rd international workshop
on Link discovery.

ACM, 2005, pp. 36–43.

[36] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: simple building blocks of complex networks,” Science,
vol. 298, no. 5594, pp. 824–827, 2002.
[37] J. Ruths and D. Ruths, “Control profiles of complex networks,” Science, vol. 343, no. 6177, pp. 1373–1376, 2014.
[38] W. T.Rhee, “A concentration inequality for maximum matching size in random graphs,” Optimization, vol. 21, no. 5, pp. 797–803, 1990.

32

[39] T. G. Kurtz, “Solutions of ordinary differential equations as limits of pure jump Markov processes,” Journal of applied Probability, vol. 7, no. 1, pp.
49–58, 1970.

