PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes

Giulia Menichetti, Luca Dall'Asta, Ginestra Bianconi

arXiv:1405.4365v3cond-mat.stat-mechcond-mat.dis-nnphysics.soc-ph

TL;DR

This paper examines how low in-degree and out-degree nodes relate to the number of driver nodes needed for structural controllability. Using the maximum-matching framework, it finds that networks with minimum in-degree and out-degree above 2 have a vanishing driver-node fraction in the thermodynamic limit, and proposes adding links to low-degree nodes to improve controllability.

  • Problem

    The paper investigates how network structure, particularly the fraction of low in-degree and out-degree nodes, relates to the number of driver nodes required for controllability.

    Source: p. 1

  • Method

    It maps structural controllability to maximum matching and uses the cavity method to study matchings on directed random graphs.

    Source: pp. 1–2

  • Results

    nD→0 when P(1)=P(2)=0 for power-law networks with any γ>1; for networks with minimum in-degree and out-degree greater than 2, nD=0 in the thermodynamic limit.

    Source: p. 3

  • Takeaways & Limitations

    The proposed strategy improves structural controllability by adding links to low-degree nodes, reducing the density of nodes with in-degree and out-degree below 3.

    Source: pp. 1, 4

    The degree-distribution example uses a power-law tail Ck−γ for k∈[3,K], alongside specified probabilities for degrees 1 and 2.

    Source: p. 3

Abstract

from arXiv · show

The problem of controllability of the dynamical state of a network is central in network theory and has wide applications ranging from network medicine to financial markets. The driver nodes of the network are the nodes that can bring the network to the desired dynamical state if an external signal is applied to them. Using the framework of structural controllability, here we show that the density of nodes with in-degree and out-degree equal to $0$, $1$ and $2$ determines the number of driver nodes of random networks. Moreover we show that networks with minimum in-degree and out-degree greater than 2, are always fully controllable by an infinitesimal fraction of driver nodes, regardless on the other properties of the degree distribution. Finally, based on these results, we propose an algorithm to improve the controllability of networks.

1. The maximum matching problem

The maximum-matching problem is represented with binary variables on directed links, subject to constraints that limit matched links at each node. Its energy is used to characterize optimal matchings in the zero-temperature limit.

1. The maximum matching problem

  • Directed maximum matching uses binary link variables: 1 marks a matched edge and 0 an unmatched edge.The variables are chosen subject to matching constraints.Source: §1 · p. 5
  • Each node can have at most one matched incoming link and one matched outgoing link.These are the matching constraints on the directed graph.Source: §1 · p. 5
  • The distribution is examined as β→∞ to characterize optimal, maximum-sized matchings; the energy is related to the number of unmatched nodes, ND.The passage identifies ND as the number of unmatched nodes and gives the energy as the objective quantity.Source: §1 · p. 5

2. The BP equations

For locally tree-like networks, the paper uses Belief Propagation messages to represent the matching distribution and derive equations in cavity fields. The Bethe approximation expresses network and link marginals through those messages.

2. The BP equations

  • On locally tree-like networks, BP solves the distribution P({sij}) using messages exchanged between nearby nodes.The messages distinguish the direction along a link from the opposite direction.Source: §2 · p. 5
  • Messages along and against each link are parametrized by cavity fields hi→j and ˆhi→j.The fields provide an equivalent representation of the two message types.Source: §2 · p. 5
  • In cavity-field form, the BP message relations reduce to equations first derived for this problem.The equations are given in the cited work.Source: §2 · p. 5
  • In the Bethe approximation, network and link marginals are computed from cavity messages or their equivalent fields.The passage identifies the node and link marginals as the distributions being computed.Source: §2 · pp. 5–6

3. Free energy and energy of the problem

The paper obtains the matching problem's free energy through the Gibbs free energy of the constrained distribution. In the Bethe approximation, fixed-point BP solutions yield that distribution and the associated energy.

3. Free energy and energy of the problem

  • The Gibbs free energy is evaluated for P({sij}) subject to the matching constraints ψ({sij}).The distribution is expressed as P({sij}) = e−βEψ({sij})/Z.Source: §3 · p. 6
  • In the Bethe approximation, the fixed-point BP distribution minimizes Gibbs free energy and gives βFGibbs = −ln Z.The passage states that the distribution is computed using the Bethe approximation and fixed-point BP equations.Source: §3 · p. 6
  • Substituting the preceding expressions yields the matching problem's free energy, from which its energy is obtained.The passage describes these successive derivations without supplying the expressions themselves.Source: §3 · p. 6

4. The β →∞limit

In the β→∞ limit, the energy describes a maximum matching and the cavity-field equations become zero-temperature BP, or Max-Sum, equations. The paper also specifies boundary fields and a criterion for selecting among coexisting solutions.

4. The β →∞limit

  • In the β→∞ limit, the energy expression is for a maximum matching.This is the zero-temperature limit of the matching problem.Source: §4 · p. 6
  • The cavity fields satisfy zero-temperature Belief Propagation equations, also called Max-Sum equations.The equations apply to each directed link.Source: §4 · p. 6
  • A node with one outgoing link has hi→j = 1; one with one incoming link has ˆhi→j = 1.These are the stated degree-one boundary assignments.Source: §4 · p. 6
  • When multiple solutions coexist, dynamically stable solutions of minimum energy are the correct maximum-matching solutions.In the infinite-size limit, the fields have support either on {−1, 1} or on {−1, 0, 1}.Source: §4 · p. 6

Appendix B: BP/MS Equations in an ensemble of random networks with given degree distribution

In the zero-temperature limit, the field distributions reduce to mixtures of three delta functions, and the MS equations describe their probabilities. The energy, and thus the driver-node fraction, can be expressed using those probabilities; selecting among solutions requires probability, stability, and minimum-energy checks.

Appendix B: BP/MS Equations in an ensemble of random networks with given degree distribution

  • At β → ∞, the field distributions are represented as mixtures of three delta functions.The weights for each set of fields are normalized to sum to one.Source: Appendix B · p. 7
  • The MS equations are written in terms of the probabilities {w} and {ŵ}, with the third weight in each set fixed by normalization.Specifically, w3 = 1 − w1 − w2 and ŵ3 = 1 − ŵ1 − ŵ2.Source: Appendix B · p. 7
  • The energy can be expressed using the field-distribution weights, and the driver-node fraction is nD = E/(2N).Thus the weights determine the fraction through the energy density.Source: Appendix B · p. 7
  • When the MS equations have multiple solutions, the selected solution must be a probability distribution, stable under small perturbations, and have the lowest energy among qualifying solutions.The lowest-energy criterion applies when more than one solution satisfies the first two conditions.Source: Appendix B · p. 7

1. Stability condition

The appendix assesses replica-symmetric solutions for stability against perturbations to cavity-field distributions and discrete changes that propagate through the network. For the zero-energy solution with no degree-one nodes, the stability criteria imply the main-text condition; when in- and out-degree distributions match, several stable solutions can have the same zero energy density.

1. Stability condition

  • Replica symmetry assumes common cavity-field distributions; relaxing it allows distributions over those distributions and exposes two distinct instability types.One instability is dynamical, while the other is bug proliferation.Source: §1 · pp. 7–8
  • Dynamical instability is tested by requiring every eigenvalue of the 6 × 6 Jacobian for the MS equations to have modulus below one.It corresponds to cavity-field distributions failing to concentrate around discrete values and the solution being unreachable from finite temperature.Source: §1 · pp. 7–8
  • Bug proliferation tracks discrete cavity-field changes transmitted when a node’s incoming field changes after one of its parent nodes changes.The transition probabilities are averaged over degree distributions, accounting for the changed node’s other messages.Source: §1 · p. 8
  • The zero-energy solution w1 = w2 = ŵ1 = ŵ2 = 0, with P_in(1) = P_out(1) = 0, yields the stability condition stated in Eq. (6) of the main text.The appendix derives this condition from the stability criteria for the solution.Source: §1 · p. 8
  • When P_in(k) = P_out(k), multiple stable solutions can occur under the same conditions and all have energy density E/N = 0.The zero-energy solution w1 = w2 = ŵ1 = ŵ2 = 0 is among these solutions.Source: §1 · p. 9

Appendix C: Number of driver nodes

The BP equations are expected to give the correct driver-node density for large random networks, but predicting zero density does not guarantee zero drivers in a finite network. In simulations, exact matching found zero driver nodes sufficiently far from the stability boundary.

Appendix C: Number of driver nodes

  • BP is expected to give the correct driver-node density in the large-network limit, but zero predicted density does not guarantee zero driver nodes in finite networks.The distinction is between nD = 0 and the exact count ND = 0.Source: Appendix C · p. 9
  • Hopcroft–Karp simulations of finite networks found ND = 0 when the networks were sufficiently far from the stability-condition boundary.The simulations examined networks in the region where BP predicts nD = 0.Source: Appendix C · p. 9
  • Figure 5 reports histograms of exact driver-node counts for network realizations at points where BP predicts nD = 0.The histograms correspond to the Hopcroft–Karp simulations described in the appendix.Source: Appendix C · p. 9

Appendix D: Improving the controllability of scale-free networks

The appendix examines link additions to low-degree nodes as a way to improve controllability in scale-free networks. For the γ = 3 example with minimum in- and out-degree 2, the fraction of added links required for full controllability falls to 13%.

Appendix D: Improving the controllability of scale-free networks

  • 13% of added links achieves full controllability for the γ = 3 power-law network with minimum in- and out-degree 2.The comparison keeps the initial average degree the same as the γ = 2.3 example, for which the recipe was more demanding.Source: Appendix D · p. 9
  • Figure 5 shows histograms of exact driver-node counts across 50 realizations as P(2) varies, with P(1) = 0 and γ = 2.3.The caption reports consistency with ND = 0 sufficiently far from the stability condition P(2) = 0.181947.Source: Figure 5 · p. 9
  • Figure 6 plots the driver-node fraction nD(∆L)/nD(0) against the fraction of links added to low-degree nodes.Panel B plots average clustering coefficient and average distance against that added-link fraction for a γ = 3 power-law network.Source: Figure 6 · p. 9

Appendix E: Poisson networks

This appendix extends the low-degree analysis to Poisson networks, focusing on the case P(1)=0. Its phase diagram shows how the driver-node density varies with λ and P(2), including a stable region with no driver nodes.

Appendix E: Poisson networks

  • The appendix extends its analysis of low-degree nodes in uncorrelated random graphs with power-law degree distributions to Poisson networks.Source: Appendix E · p. 9
  • For P(1)=0, the appendix examines stability of the solution {w1,w2,w3}={0,0,1}.The accompanying passage identifies this as the solution whose stability condition is considered.Source: Appendix E · p. 10
  • The phase diagram maps nD over λ and P(2): the stable dark-grey region has nD=0, while outside it the lowest stable MS solution gives the required driver density.The figure concerns networks with P(1)=0 and a degree distribution given by Eq. (E1).Source: Appendix E · p. 10, Figure 7 · p. 10

Appendix F: Improving the controllability of Poisson networks

The proposed link-addition strategy also improves controllability in Poisson networks. In the reported example, a link fraction of order 5% achieves full controllability, and the authors state that the approach applies to any degree distribution.

Appendix F: Improving the controllability of Poisson networks

  • The authors state that the link-addition approach applies to networks with any degree distribution, beyond the scale-free and Poisson examples discussed.Source: Appendix F · p. 10
  • Efficiency is plotted instead of average distance because the network is not fully connected, especially at the beginning.Source: Appendix F · p. 10
  • A link fraction of order 5% yields full controllability in the tested Poisson network with average degree c=4.The plotted example starts with a Poisson network whose in- and out-degree distributions are equal.Source: Figure 8 · p. 10, Appendix F · p. 10
  • Links are added first to nodes with both degrees 0, then 1, then 2; the figure tracks driver-node fraction, clustering, and efficiency as links are added.Source: Figure 8 · p. 10
Loading 1405.4365v3…