{'fraction_non_alphanumeric': 0.044611916697506984, 'fraction_numerical': 0.008915654543619419, 'mean_word_length': 4.245103229221811, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Signature stability analysis for networks of coupled dynamical systems with Hermitian Jacobian

The central theme of complex systems research is understanding the emergent macroscopic properties of a system from the interplay of its microscopic constituents. Here, we ask what conditions a complex network of microscopic dynamical units has to meet to permit stationary macroscopic dynamics, such as stable equilibria or phase-locked states. We present an analytical approach which is based on a graphical notation that allows rewriting Jacobi's signature criterion in an interpretable form. The derived conditions pertain to topological structures on all scales, ranging from individual nodes to the interaction network as a whole. Our approach can be applied to many systems of symmetrically coupled units. For the purpose of illustration, we consider the example of synchronization, specifically the (heterogeneous) Kuramoto model and an adaptive variant. Moreover, we discuss how the graphical notation can be employed to study isospectrality in Hermitian matrices. The results complete and extend the previous analysis of Do et al. [Phys. Rev. Lett. 108, 194102 (2012)].

Characterizing the behavior of complex systems and discovering the critical boundaries in parameter space at which qualitative changes occur are of central interest in statistical physics. Many studies have demonstrated that, in specific models, this can be achieved by the instruments of nonlinear dynamics [1][2][3][4]. However, applying these tools to large heterogeneous systems, such as complex networks of dynamical units poses significant challenges [5][6][7][8]. In particular, there is no simple way to capture the structural aspects of such systems, which are known to crucially influence the emergent dynamics [9,10].
The interplay of dynamics and structure in networks has extensively been studied using the example of synchronization [9,11,12]. Systems of coupled phase oscillators, originally proposed by Kuramoto [13,14], have become a paradigmatic example. The exploration of such systems revealed that the synchronizability of a network depends on global topological measures such as the clustering coefficient, the diameter, and the degree or weight distribution [15][16][17][18][19][20][21], but also on local and mesoscale details [12,22,23]. This shows that a conceptual understanding of collective phenomena on dynamical networks can only be achieved if structural properties on all scales are taken into account.
In a recent paper, we proposed a nonlinear dynamics approach, which allows to study the dependence of dynamics on structure in networks of symmetrically coupled units [24,25]. We showed that Jacobi's signature criterion (JSC) can be used to determine necessary conditions an interaction network has to obey in order to support a given type of macroscopic behavior. These conditions pertain to subgraphs on all scales, from single nodes to * ly@mpipks-dresden.mpg.de the entire network. In this paper, we complete and extend the analysis of [24]. We present the full derivation of the proposed approach and discuss a number of new applications including an adaptive Kuramoto model, in which the topology of the coupling network coevolves with the local dynamics of the phase oscillators [26,27].

I. STABILITY IN NETWORKS OF PHASE-OSCILLATORS
The approach outlined below is applicable to all dynamical systems with Hermitian Jacobian matrices, and in particular to all networks of symmetrically-coupled one-dimensional dynamical units. However, for the sake of illustration, we first consider specifically the example of N coupled phase oscillatorṡ (1) Here, x i and ω i denote the phase and the intrinsic frequency of node i, and A ∈ R N ×N is the weight matrix of an undirected, weighted interaction network. Two oscillators i, j are thus connected if A ij = A ji = 0. Equation (1) represents the so-called Kuramoto model, that is today considered to be a paradigm for the study of synchronization phenomena in coupled discrete systems [14].
The model is therefore used as the natural benchmark for comparative evaluations of performances of methods and tools. It is known that the Kuramoto-model can exhibit phase-locked states, which correspond to steady states of the governing system of equations. The local stability of such states is determined by the spectrum of the Jacobian matrix J ∈ R N ×N defined by J ik = ∂ẋ i /∂x k . As J is symmetric, its spectrum is real. The state under consideration is asymptotically stable if all eigenvalues are ≤ 0.
Below, we analyze the spectrum of J by means of Jacobi's signature criterion (JSC). The JSC (also known as Sylvester criterion) states that a hermitian or symmetric matrix J with rank r = N − 1 has r negative eigenvalues if and only if all principal minors of order q ≤ r have the sign of (−1) q [25]. Here, the principal minor of order q is defined as D q := det (J ik ), i, k = s 1 , . . . , s q .
Stability analysis by means of JSC is well-known in control theory [28] and has been applied to problems of different fields. For instance, the JSC has been used in [29] to analyze advection-diffusion equations, and in [30] to determine stability boundaries in thermodynamic systems. Moreover, it has been applied to study the dynamics of offshore platforms [31] and social systems [32].
Two obstacles that are encountered in the application of the JSC to large networked systems are the growth of (a) the number of terms in each determinant, and (b) the number of determinants that have to be checked. Difficulty (a) can be overcome by means of a graphical notation, which allows to derive topological stability criteria. This notation is introduced in Sec. II. Difficulty (b) can be evaded by considering necessary rather than sufficient conditions for stability: While the sufficient condition for stability necessitates the evaluation of all principal minors, a necessary condition for stability is already obtained by demanding sgn (D q ) = (−1) q for some q.
The necessary stability condition that is found by considering a principal minor of given order q depends on the ordering of variables, i.e., the ordering of rows and columns in the Jacobian. By considering different orderings the number of conditions obtained for a given q can therefore be increased [32]. To distinguish minors that are based on different orderings of the variables, we define S = {s 1 , . . . , s q } as a set of |S| = q indices and D |S|,S as the determinant of the submatrix of J, which is spanned by the variables x s1 , . . . , x sq . Therewith, the conditions for stability read sgn D |S|,S = (−1) |S| , ∀S, |S| = 1, . . . , r. (2)

II. GRAPHICAL NOTATION
Below, we address difficulty (a) mentioned above, i.e., the combinatorial explosion of terms that are needed to write out the conditions for increasing |S|. In the common notation, more than 700 terms are necessary for expressing the minors of order 6. For circumventing this problem we employ a graphical notation that captures basic intuition and allows for expressing the minors in a concise way [24].
The graphical notation relies on a topological reading of the minors. We interpret the Jacobian J as the weight matrix of an undirected, weighted graph G. A Jacobian element J ij then corresponds to the weight of a link connecting nodes i and j. Moreover, we relate products of FIG. 1. Example for the graphical notation. Shown are the minors of the matrix (5) in algebraic, and graphical notation, and, for each term, the corresponding subgraph of a threenode graph G. Here, as well as in the next figures, filled symbols correspond to nodes ∈ S, open symbols to nodes / ∈ S.
the Jacobian elements to subgraphs of G spanned by the respective links. For instance J ij J jk is interpreted as path i − j − k. Similarly, J ij J jk J ki is interpreted as a closed path from i to j to k and back to i.
We can now express the minors of J as sums over subgraphs of G. The Leibniz formula for determinants [33] implies that (i) a minor D |S|,S is a sum over |S|! elementary products J i1j1 · . . . · J i |S| j |S| ; and that (ii) in each of these products every index s i ∈ S occurs exactly twice. In the topological reading this translates to the following statements: Because of property (i), each term of a minor D |S|,S corresponds to a subgraph with |S| links. Because of property (ii), these subgraphs can be decomposed in cycles of G: Every index s i ∈ S occurs either with multiplicity two on a diagonal element of J, or, with multiplicity one, on two off-diagonal elements of J. In the former case, the respective factor corresponds to a selfloop of G, i.e., to a cycle of length n = 1; in the latter case, there is a set of factors J ij , i = j, corresponding to a closed path of links, i.e., a cycle of length n > 1.
In summary, the index structure of every term of a minor D |S|,S can be expressed by a combination of symbols denoting cycles of G of a given length n. The idea is now to supplement the basis of symbols with a summation convention; This convention is designed such that all algebraic terms that are structurally identical and only differ by index permutations can be captured in one symbolic term, which drastically reduces the complexity of the expressions.
Below, we use the following definitions: The basis of symbols is given by ×, |, △, , , . . . denoting cycles of length n = 1, 2, 3, 4, 5, . . .. The summation convention stipulates that in a minor D |S|,S , every product of symbols denotes the sum over all non-equivalent possibilities to build the depicted subgraph with the nodes ∈ S (cf. Fig. 1). With these conventions the first 4 principal mi-nors can be written as More generally, where symbols with n > 2 appear with a factor of 2 that reflects the two possible orientations in which the corresponding subgraphs can be paced out. Symbols with an even (odd) number of links carry a negative (positive) sign related to the sign of the respective index permutation in the Leibniz formula for determinants [33].
An example for the graphical notation is presented in Fig. 1. The figure displays the three principal minors of the symmetric 3 × 3 matrix in algebraic, and graphical notation. Moreover, it displays for each term the corresponding subgraph of a three-node graph G.

III. ZERO ROW SUM
In many systems, including the standard Kuramoto model, fundamental conservation laws impose a zero-rowsum condition, such that J ii = − j =i J ij . Using this relation, we can remove all occurrences of elements J ii from the Jacobian and its minors [24]. In the topological reading, this substitution changes the graph G by replacing a self-loop at a node i by the negative sum over all links that connect to i.
The simplification of the minors due to the zero-rowsum condition can be understood using the example of the Eqs. (3). Replacing the self-loops, the first term of every minor D |S|,S , × |S| , is (−1) |S| times the sum over all subgraphs meeting the following conditions: (i) the subgraph contains exactly |S| links, and (ii) it can be drawn by starting each (undirected) link at a different node in S. By means of elementary combinatorics it can be verified that all other terms of D |S|,S cancel exactly those subgraphs in × |S| that contain cycles. This enables us to express the minors in another way: Defining Φ |S|,S = all acyclic subgraphs of G meeting (i) and (ii) (6) we can write We remark that for |S| = N − 1, Φ |S|,S is the sum over all spanning trees of G (cf. Eq. (6)). Thus, Kirchhoff's Theorem [34], which has previously been used for the analysis of dynamical systems [35,36], can be regarded as a special case of the more general Eq. (7).
The simplification of the minors due to the zero-rowsum condition as well as the relation between the D |S|,S and their topological equivalents Φ |S|,S can be illustrated by means of a simple example. Consider the symmetric zero-row-sum 6 × 6 matrix Here, (J ii ) abbreviates − j =i J ij . In Fig. 2, we calculate the minor D 4,S={1,...,4} in terms of the subgraphs of the corresponding graph G. The calculation illustrates the reasoning that lead to the Eqs. (6) and (7). On the one hand, the complete sequence of minors D |S|,S , |S| = 1, . . . , rank(J) can be calculated as . . , k}, and rank(J) = 5 due to the zerorow-sum condition.
On the other hand, we can use the definition (6) to construct the sequence Φ |S|,S , |S| = 1, . . . , rank(J), directly from the graph G (cf. Fig. 3). A comparison of both, the algebraic and the topological results, reproduces Eq. (7). We note that labeling the nodes in different order would have yielded different algebraic as well as topological expressions.

IV. TOPOLOGICAL STABILITY CONDITIONS
Let us shortly summarize what we obtained so far. The topological reading of determinants maps a Hermitian Jacobian J with zero row sum onto a graph G, whose weight matrix is given by the off-diagonal part of J. The minors of J can then be interpreted as sums over terms associated with subgraphs of G. Combining the Eqs. (2) and (7), the algebraic stability constraints on the minors of J translate into Φ |S|,S > 0, ∀S, |S| = 1, . . . , rank(J).
We emphasize that the graph G is not an abstract construction, but combines information about the physical interaction topology and the dynamical units. For example, if a graph G has disconnected components, there is a reordering of the variables x i , such that J is block diagonal. This implies that the spectra of different topological components of G decouple and can thus be treated independently.
From Eq. (9) we can immediately read off a weak sufficient condition for stability: Because Φ |S|,S is a sum over products of the J ij , a Jacobian with J ij ≥ 0 ∀i, j Let C be an unbranched segment of a cycle of G that consists of d links ci, i ∈ {1, . . . , d}. Let further wi denote the weight of ci, and cx denote the only link in C with negative weight wx. Then stability requires that |wx| < i∈I * wi all distinct products of (d − 2) factors w i , i ∈ I * (C1) , is a solution to Eq. (9) irrespective of the specific structure of G [37]. By contrast, if J ij < 0 for some i, j, then the existence of solutions of Eq. (9) is dependent on the topology.
The Φ-notation allows to investigate which combinations of negative J ij in a graph G lead to the violation of at least one of the Eqs. (9): The definition of Φ implies that any given Φ |S|,S can be represented as a function over a set of Φ |Si|,Si where the S i are subsets of S, and f depends on the choice of the S i . The key point is now that for showing that a given topological arrangement of negative J ij is incompatible with the stability conditions Eqs. (9), it suffices to show that there exists some Φ |S|,S and some expansion (10) thereof, for which there is no solution with all occurring Φ > 0. Let us emphasize that the sketched approach dispenses with the need to specifically calculated any Φ |S|,S , and hence with addressing the up to |S|! terms they subsume.
In [24], we employ the outlined approach to show that stability requires that every component of G has a spanning tree, whose links all have positive weights. A detailed mathematical proof of this result will be published in [25]. For the sake of completeness we present a sketch of a proof in Appendix A. The proof uses the Φ-notation to show that at least one of the necessary conditions must be violated when no spanning tree of positive connections exists. It thereby also provides an illustration of the direct application of the notation in a calculation.
In addition to the spanning tree criterion for stability, which pertains to a global property of G, Eq. (9) implies further restrictions, which pertain to mesoscale properties of G. Thus, the weights of all links that are not part of any cycle of G have to be positive. Moreover, at most one of the links that build an unbranched segment of a cycle of G may have a negative weight. Finally, the weight of a 'negative link' in an unbranched segment of a cycle of G is bounded below by a value that depends on the weights of the other links in the segment (cf. Fig 4).
Note that while the mesoscale criteria restricting the number and position of negative links can be subsumed under the global spanning tree criterion, the mesoscale criteria restricting the weights of possible negative links are inherently bound to the mesoscale. In particular, the latter can only be derived by considering Φ |S|,S with small and intermediate |S|. This highlights the benefits of the proposed approach: The JSC provide stability criteria on all scales |S|, which are made accessible by means of the graphical notation and symbolic calculus.
Applied to the Kuramoto model defined in Eq. (1), the spanning tree criterion for stability allows to deduce properties shared by all possible phase-locked states [24]. In a phase-locked state, J ij = A ij cos(x j −x i ), where x j − x i is the stationary phase difference between oscillator j and i. Given that all link weights A ij ≥ 0, stability of the phase-locked state thus requires that the coupling network has a spanning tree of oscillators obeying |x j − x i | < π/2.

V. GENERAL SYSTEMS OF COUPLED UNITS
The derivation of stability criteria by graphical interpretation of the JSC is applicable to all systems with Hermitian Jacobian matrix. Further, the simplification leading up to the spanning tree criterion is possible, whenever the Jacobian has zero row sums. This condition is satisfied for instance by all systems of the forṁ (11) where the A ij are the weights of a symmetric interaction network and the O ij odd functions. We emphasize that the approach remains applicable in heterogeneous networks containing different link strengths A ij , coupling functions O ij or intrinsic parameters C i .
The class of systems to which the present results are directly applicable include general networks of phase oscillators as well as other models such as continuous-time variants of the Deffuant model of opinion formation [40] or a class of ecological metapopulation models [41].
Although the specific criteria derived above are contingent on the zero-row-sum condition, it can be expected that the general approach proposed here is also applicable to situations where this condition is violated, such as in the model of cooperation among interacting agents studied in [32]. A simple extension of Eq. (11) which violates the zero-row-sum condition is found by replacing C i by a function of x i , which allows dynamical retuning of the intrinsic frequency, e.g. for modeling homeostatic feedback in neural networks. For illustrating the application of the proposed method to models, in which the zero-row-sum condition is violated in some rows, we consider another model inspired by neuroscience in the subsequent section.

VI. ADAPTIVE KURAMOTO MODEL
We now apply the proposed approach to an example of an adaptive network, i.e., a system in which the topology of the network coevolves with the dynamics of oscillators [26,42,43]. In the context of the Kuramoto model, adaptive coupling has recently attracted keen interest as it allowed to show that the emergence of synchronous motion can be intimately related to a selection mechanism of specific network topologies [44], and to the identification of complex hierarchical structures in the graph connectivity [26,27]. We consider a system of N phase oscillators that evolve according to Eq. (1), while the coupling strength A ij evolves according to The first term in Eq. (12) states that the more similar the phases of two nodes the stronger reinforced is their connection, the second term guarantees convergence. In a stationary, phase-locked state state A ij = cos(x j −x i )/b and all oscillators oscillate with a common frequency Ω = where o ij := 1 b cos 2 (x j − x i ), m i := − j =i o ij , s ji := sin(x j − x i ) and we have chosen N = 3 for illustration. The marked partitioning separates two blocks on the diagonal. The upper one is a diagonal submatrix of size L × L, L := N (N − 1)/2, the lower one is a N × N symmetric submatrix with zero row sum, which we denote as j.
Let us start our analysis by focusing on the upper left block of J. In the chosen ordering of variables, the first L minors D |S|,S satisfy the stability condition Eq. (2) iff b > 0. Concerning the minors of order |S| > L, the following conventions prove advantageous: Below, we consider sets S that contain all variables A ij and n of the variables x i . For every such set, we define S ′ as the subset of S that only contains the n variables x i . Moreover, we definej as the matrix that is obtained from j if all o ij are substituted by cos(2(x j −x i )). Finally, we defineD n,S ′ as the determinant of the submatrix ofj, which is spanned by the variables ∈ S ′ .
We find that Asj is symmetric and has a zero row sum, its minors, D n,S , can be rewritten using Eq. (7) whereΦ n,S ′ refers to subgraphs of the graphG defined by the off-diagonal entries ofj. Stability requires that sgn (D L+n,S ) = sgn (−1) L+n . As the necessary stability condition b > 0 implies b L−n > 0, it follows that in a stable system Φ n,S ′ > 0, ∀S, n = 1, . . . , rank(j).
Comparison with Eq. (9) reveals that a necessary condition for stability is that every component of the graphG has a positive spanning tree. Revisiting the definitions of graphG, we find that the weight of a link ij ofG is given by cos(2(x j − x i )). Hence, every component ofG has a positive spanning tree iff every component of the adaptive coupling network has a spanning tree of oscillators obeying |x j − x i | < π/4. The restriction on the stationary phase-differences in a stable, phase-locked state are thus more strict in the adaptive than in the non-adaptive case.

VII. APPLICABILITY OF THE GRAPHICAL NOTATION TO ISOSPECTRALITY PROBLEMS
In addition to stability analysis, the graphical notation introduced here allows for instance exploring the isospectrality of Hermitian or symmetric matrices [38,39], which differ with respect to the signs of some off-diagonal entries. To see this consider a Hermitian matrix A ∈ C n×n . Its characteristic polynomial χ can be calculated as Considering the structure of the graph G associated to A − λI allows to determine which symbols contribute to χ. One can then determine which changes of sign of offdiagonal entries leave all contributing symbols and thus the characteristic polynomial and the spectrum invariant.
For instance, if the graph G is a tree, then the only symbols that contribute to the characteristic polynomial χ are the symbols × and |. Thus, χ is a polynomial of factors (A ii − λ) (corresponding to symbols ×), and factors A ij A ji (corresponding to symbols |). Due to the hermiticity of A, A ij A ji = |A ij | 2 . It follows that χ, and therewith the spectrum, is invariant under any operation that changes the sign of a pair of off-diagonal entries Along the same line, we can infer isospectrality relations for matrices A, whose corresponding graphs G are composed only of tree-like subgraphs and isolated cycles. For such matrices, the spectrum is invariant under symmetry preserving sign changes of • an arbitrary number of off-diagonal entries that do not belong to cyclic subgraphs of G.
• an even number of off-diagonal entries that belong to the same cyclic subgraph of G.

VIII. CONCLUSIONS
In the present paper we presented a general approach for the analysis of symmetrically coupled systems and a specific simplification for systems, in which the Jacobian matrix J additionally has a zero row sum.
Using a graphical interpretation of Jacobi's signature criterion we showed that for all non-trivial eigenvalues of J to be negative, the graph G, whose adjacency matrix is given by the off-diagonal part of J, has to obey necessary topological conditions. Thus, G must have a spanning tree of links with positive weights, which restricts the number and position of potential negative entries in the Jacobian matrix. Moreover, the absolute value of potential negative link weights is bounded above by a topology depended relation.
We used the approach for deriving necessary conditions for local asymptotic stability of stationary and phaselocked states in networks of phase oscillators. Our results provide an analytical angle that is complementary to statistical analysis of network synchronizability. Where statistical approaches reveal global features impinging on the propensity to synchronize, our approach can pinpoint specific defects precluding synchronization. We note that such defects can occur on all scales, corresponding to the violation of the signature criterion in subgraphs of different size. This highlights synchronization of phase oscillators as a simple but intriguing example in which instabilities can arise from local, global or mesoscale structures. In the future, the approach proposed here may provide a basis for further investigation of these instabilities.
A limitation of the present approach is that the Jacobian matrix of the state under consideration has to be available in some form. However, this limitation is inherent to all forms of linear stability and bifurcation analysis and several strategies have been developed for mitigating it. These include for instance the equationfree approach [45], where the desired information on the Jacobian is generated on-demand from simulations or experiments, and generalized modeling [46], which reveals a parameterized presentation of the Jacobian for very general classes of systems. Even if these specific techniques are not applied, researchers are often aware of the structure of the Jacobian in the system under consideration, which can be sufficient for gaining some fundamental insights by the proposed approach.
It is apparent that applying the stability analysis proposed here may require overcoming specific problems. In particular, the requirements of symmetry and zero row sum may necessitate extending the basic scheme or focusing on specific cases, as we did in the adaptive network example. However, if these problems can be overcome, the approach can reveal hard analytical conditions that all stable steady states must meet. Further, it can identify topological structures (on all scales) that prevent the existence of such states and pinpoint them in networks. Because this type of information is complementary to insights revealed by common statistical approaches, it potentially of high value for the analysis of the system.

Appendix A: Spanning Tree Criterion for stability
To prove the spanning tree criterion for stability consider that in a network without a positive spanning tree it must be possible to partition the nodes into two nonempty sets I 1 , I 2 such that The idea is now to evaluate the stability conditions (9) for different S ⊆ I 1 thereby exploiting that all links leading out of I 1 have negative weights. For this purpose,it is convenient to define E * as the set of links connecting I 1 and I 2 , and X = {x 1 , . . . , x m } as the subset of nodes ∈ I 1 incident to at least one link from E * ('boundary vertices'). Further, we define σ i as the sum over all elements of E * incident to x i , and, for any subset Y of X, σ Y := m∈Y σ m . Finally, for any subset Y of X, we define τ Y as the sum over all forests of G that (i) span I 1 , and (ii) consist of |Y | trees each of which contains exactly one element from Y .
With the above definitions we can write where B and C are disjoint subsets of X and Φ I1\C := Φ q,I1\C . The rather abstract equation is illustrated in Fig. 5 by means of an example. Equation (A2) can be read as an expansion of Φ I1\C in contributions from E * . This expansion has the advantage that the sign of one of the two factors in each term is known: sgn (σ B ) = (−1) |B| . The signs of the factors τ B∪C , however, are still indeterminate. Nevertheless, we can show that Eq. (A2) is incompatible with the stability condition (9) by considering a linear combination of Φ I1\C : which is a contradiction. Therefore the existence of a spanning tree of positive elements is a necessary condition for stability.

Appendix B: Lower bound on the negative link weights
Consider a path of d − 1 degree-two nodes v i , i ∈ {1, . . . , d − 1}, that are part of at least one cycle of G. Together with the d egdes c i that are incident to at least one of the nodes v i , the path constitutes an unbranched segment C of a cycle of G (cf. Fig. 3).
According to the spanning tree criterion, C can have at most one link with negative weight. Below, we consider the case where C has exactly one such link, and show that Eq. (9) imposes an upper bound on the absolute value of the negative link weight.
We use the following conventions: Let the nodes be labeled such that the indices i occur in an increasing order if C is paced out. And let the links be labeled such that v i is incident to c i and c i+1 (cf. Fig. 2S). Further, let w i denote the weight of c i . And lastly, let c x denote the only link in C with negative weight w x . Below, we show that stability requires that |w x | < all wi, i ∈ I * all distinct products of (d − 2) factors wi, i ∈ I * , (B1) where I * = {1, . . . , d} \ x.
More generally, every element Φ Si of the sequence Φ S1 , . . . , Φ S d−1 modifies the upper bound on −w x as per −w x < all wi, i ∈ S * i all distinct products of (|Si| − 1) factors wi, i ∈ S * i , (B2) where S * i = (S i \ x) ∪ (max(S i ) + 1). The right hand side of Eq. (B2) is monotonously decreasing with increasing |S i |. We can thus conclude that C can have at most one link with negative weight, whose absolute value |w x | is bounded above by Eq. (B1).