Red arrows indicate the edges that constitute a maximum matching set. Green arrows indicate the external control input. (a) Dilation and inaccessibility problems are independent of one another. (a left) Example of dilation: an input at n₃ could reach every node, but branching causes dilation. (a right) Example of inaccessibility: an input from n₄ could not reach any other node however, there is no dilation. (b) Maximum flow, shown at (b right), is adapted to extract maximum matching set of a simple example (b left). The network is represented as a bipartite graph so that maximum flow from a global source node s to global target node t identifies a maximum matching set. Note that nodes s and t are not part of the original network.

(a) Effect of four different pruning strategies on a small-world network. The green, blue, red and cyan represent the effect of out-pruning (out), ordered-MM pruning (ord), random pruning (rnd), and resilient pruning(rev), respectively. Each of the curves shows the mean of 50 different realizations bounded by a gray region, representing the corresponding standard deviation. For most of them, the gray region is very small narrow to be visible. (b–l) Same as in panel (a) but for different types artificial, social and biological networks. The name of the network is mentioned on the respective panel. (a–c) Watts-Strogatz spectrum of directed networks with respective randomising probabilities of 0.02, 0.1 and 1, hence small-world (S-W), intermediate (W-S) and Erdos-Renyi (E-R) random networks. The panels (a–f), refer to artificial networks of size 250 and connection density of nearly 5%. (g-i) Social networks from Google+, Facebook and Airport connections. (j–l) BNNs: large-scale connectivity of the macaque brain, the meso-scale connectome of the mouse brain and the complete neuronal connectivity of C. elegans. The color descriptions of all curves is shown in panel (f) as green, blue, red and cyan - it represents the effect of out-pruning (out), ordered-MM pruning (ord), random pruning (rnd), and resilient pruning(rev), respectively.

(a) Effect of the conditioned pruning strategies on the control node count in macroscopic connectivity of macaque brain. The white circles show five different network structures (spanning digraph) which could either be achieved through a specific pruning process (when the white circle lies on the four traces) or arbitrarily (when the white circle lies on the four traces). (b–f) The effect of pruning process on the original macaque brain network without affecting the chosen spanning digraph marked by the white circles. Note that, by preserving a specific spanning digraph, each pruning strategy results in same (R_C eq. ), unlike the in panel (a) where we did not care to preserve any specific spanning digraph.

The overall damage indices of the four pruning strategies ordered-MM, out-, random and resilient pruning strategies (ord., out., rand., res.) are shown for synthetic (three scale-free (a) and three Watts-Strogatz models (b)) and real networks (three biological neuronal networks (c) and seven social and related networks (d)).

The cardinality curve plots the cardinalities of MM sets against their indices of extraction, from earliest to latest order. It enables to compare the performance of ordered-MM pruning with that of the other pruning strategies. The steeper the curve, the higher the performance of ordered-MM pruning. (a) Cardinality curve of the three scale-free. (b) Same as in (a) for the biological networks. (c) Cardinality curve of random networks with different size and fixed connection probability (ρ = 5%). Zero slope implies zero effect of ordered-MM pruning on nCN, as in SW (small-world) and random (E-R). (d) Cardinality curve of a random network (N = 250) for different connection probabilities (ρ). (e, left) Six basic network types. Convex refers to a network whose adjacency matrix is a lower triangular matrix. Divergent also refers to a lower triangular adjacency matrix, but with some columns set to zero (i.e. some nodes have zero out-degree). (e, right) Cardinality curves of six basic network types. The gray region covers the density of the full network without self connections – it helps to compare the connection density of the other networks from the area bounded under their cardinality curves. The cardinality curve reveals also important network features such as the degree heterogeneity by its steepness, the connection density by the area under it, the existence of hubs by its horizontal length, and the existence of long paths or cycles by its height.