TY - JOUR

T1 - Diversity of Structural Controllability of Complex Networks with Given Degree Sequence

AU - Ghasemi, Abdorasoul

AU - Posfai, Marton

AU - D'Souza, Raissa M.

N1 - Publisher Copyright:
© 2013 IEEE.

PY - 2020/10/1

Y1 - 2020/10/1

N2 - We investigate to what extent the degree sequence of a directed network constrains the number of driver nodes. We develop a pair of algorithms that take a directed degree sequence as input and aim to output a network with the maximum or minimum number of driver nodes. We find an upper bound for the maximum and a lower bound for the minimum, and show that the algorithms achieve these bounds for all real and model networks, with few exceptions characterized by tiny system size and heterogeneous degree distributions. Applying these algorithms to a broad range of real networks, we show the gap between the upper and lower bounds can vary dramatically across different degree sequences. Thus, we introduce the notion of structural control complexity to capture how much more difficult it is to control a specific network beyond what is required given its degree sequence, suggesting additional structure is present. Using model networks, we numerically and analytically investigate how typical features of the degree distribution affect the range of required driver nodes. We find that the minimum is determined by the number of sources or sinks, while the maximum is strongly affected by the presence of hubs.

AB - We investigate to what extent the degree sequence of a directed network constrains the number of driver nodes. We develop a pair of algorithms that take a directed degree sequence as input and aim to output a network with the maximum or minimum number of driver nodes. We find an upper bound for the maximum and a lower bound for the minimum, and show that the algorithms achieve these bounds for all real and model networks, with few exceptions characterized by tiny system size and heterogeneous degree distributions. Applying these algorithms to a broad range of real networks, we show the gap between the upper and lower bounds can vary dramatically across different degree sequences. Thus, we introduce the notion of structural control complexity to capture how much more difficult it is to control a specific network beyond what is required given its degree sequence, suggesting additional structure is present. Using model networks, we numerically and analytically investigate how typical features of the degree distribution affect the range of required driver nodes. We find that the minimum is determined by the number of sources or sinks, while the maximum is strongly affected by the presence of hubs.

KW - Complex networks

KW - driver nodes.

KW - structural controllability

UR - http://www.scopus.com/inward/record.url?scp=85081297771&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2020.2977672

DO - 10.1109/TNSE.2020.2977672

M3 - Article

AN - SCOPUS:85081297771

SN - 2327-4697

VL - 7

SP - 2667

EP - 2679

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

IS - 4

M1 - 9020105

ER -