How directed is a directed network? — TEI-tagged view

R. S. MacKaypersName, S. JohnsonpersName, B. SansompersName (2020date). “How directed is a directed network?.” Royal Society Open Sciencetitle·j.

Object of study — trophic levelsterm·mth and trophic coherenceterm·mth of directed networksterm·dom, redefined so they can be computed on any directed networkterm·key

Research question — to what extent the edges of a directed networkterm·key line up in an overall direction, and where each nodeterm·dom sits within that flow

Contribution — improved definitions of trophic levelterm·mth and coherence that need no basal nodesterm·key and are linked to normalityterm·mth, cycles and spectral radiusterm·key

Full text — tagged

The reference list is not part of the text we hold for this paper. Our copy was extracted from the publisher's page and the bibliography did not survive that extraction, so the article below ends before its references. Nothing has been removed by us.

How directed is a directed networkterm·key?

Abstract The trophic levelsterm·mth of nodesterm·dom in directed networksterm·dom can reveal their functional properties. Moreover, the trophic coherenceterm·mth of a network, defined in terms of trophic levelsterm·mth, is related to properties such as cycle structure, stability and percolation. The standard definition of trophic levelsterm·mth, however, borrowed from ecology, suffers from drawbacks such as requiring basal nodesterm·key, which limit its applicability. Here we propose simple improved definitions of trophic levelsterm·mth and coherence that can be computed on any directed networkterm·key. We demonstrate how the method can identify nodeterm·dom function in examples including ecosystems, supply chain networks, gene expression and global language networks. We also explore how trophic levelsterm·mth and coherence relate to other topological properties, such as non-normality and cycle structure, and show that our method reveals the extent to which the edges in a directed networkterm·key are aligned in a global direction.

Introduction Many complex systems have an underlying network, whose nodesterm·dom represent units of the system and whose edges indicate connections between the units [ 1 ]. In some contexts, the connections are symmetric, but in many they are directed, for example, indicating flows from one unit to another or which units affect which other units [ 2 ]. A classic example is a food webterm·key, in which the nodesterm·dom represent species and there is a directed edge from each species to those which eat it.

In a directed networkterm·key, the ecological concept of ‘trophic levelterm·mth’ [ 3 ] allows one to assign a height to each nodeterm·dom in such a way that on average the height goes up by one along each edge. The trophic levelsterm·mth can help to associate function to nodesterm·dom, for example, plant, herbivore, carnivore in a food webterm·key. The concept was reinvented in economics [ 4 ], where it is called ‘upstreamnessterm·mth’, though [ 5 ] trace it back to Leontief and the ‘output multiplier’. It is also an ingredient in the construction of SinkRank, a measure of contribution to systemic risk [ 6 ].

The standard deviation of the distribution of height differences along edges gives a measure of the extent to which the directed edges fail to line up, called the ‘trophic incoherenceterm·mth’ [ 7 ]. The trophic incoherenceterm·mth is an indicator of network structure that has been related to stability, percolation, cycles, normalityterm·mth and various other system properties [ 8 – 12 ].

The standard definitions of trophic levelterm·mth and incoherenceterm·mth are limited in various ways, however. In particular, they require the network to have a basal nodeterm·key (a nodeterm·dom with no incoming edges), they give too much emphasis to basal nodesterm·key if there is more than one, they do not give a stable way to determine levels and incoherenceterm·mth for a piece of a network, and they do not give a natural notion of maximal incoherenceterm·mth. Furthermore, in some contexts, like production networks indicating the flows of goods and services between firms or sectors, the reverse flow plays an equivalent role, representing the financial payments, but the standard concept of trophic levelterm·mth does not treat these symmetrically.

In this paper, we present improved 1 definitions of trophic levelterm·mth and incoherenceterm·mth that overcome these limitations. We illustrate their application in a variety of domains. We show that the new levels continue to be a useful indicator of function in the network and that the new incoherenceterm·mth measure continues to be related to stability, cycles and normalityterm·mth. We compare the new notions with the old for cases that have basal nodesterm·key; and we show the robustness of our new trophic levelsterm·mth to truncation of a network. Mathematical proofs are given in appendices.

The improved notions of trophic levelterm·mth and incoherenceterm·mth We consider directed networksterm·dom (also known as directed graphs or digraphsterm·dom) with set N of nodesterm·dom (also known as verticesterm·dom) and set E of directed edges (also known as links or ties). We suppose that there is at most one edge from a nodeterm·dom m to a nodeterm·dom n , and denote the edge by mn . There can also be an edge from n to m . Each edge carries a weight w mn > 0. This can represent the strength of the edge, for example the amount of flow along it or a quantification of influence of one nodeterm·dom on another. We write w mn = 0 if there is no edge from m to n and we assemble the w mn into a matrix W . The edge weights could be set to 1, as is common in the literature, and the array W is then called the adjacency matrix A of the network, but the ability to represent the strength of the edge is a useful extension. If there were multiple edges from m to n , then we would amalgamate them into a single edge by adding the weights. Self-edges mm (also called loops) are permitted.

For each nodeterm·dom n , we define its in-weight and out-weight by 2.1 w n in = ∑ m ∈ N w m n and w n out = ∑ m ∈ N w n m . Alternative terminology could be in- and out-strength, extending [ 13 ], who called the out-weight of a nodeterm·dom its strength . We define the (total) weight of the nodeterm·dom n by 2.2 u n = w n in + w n out , and the imbalance for nodeterm·dom n by 2.3 v n = w n in − w n out , the latter representing the difference between the flow into and out of the nodeterm·dom. We make vectors u and v from the u n and v n . The (weighted) graph-Laplacian operator Λ on vectors h is defined by 2.4 ( Λ h ) m = u m h m − ∑ n ∈ N ( w m n + w n m ) h n , or in matrix form (where superscript T denotes transpose), 2.5 Λ = diag ( u ) − W − W T .

Then our improved notion of trophic levelterm·mth is the solution h of the linear system of equations 2.6 Λ h = v , modulo shifts to be characterized in the next paragraph. Note that although the operator Λ is symmetric, asymmetry of the network appears in the imbalance vector v . Comparisons with previous notions will be made in § 4 .

Equations ( 2.6 ) always have a solution (see appendix A.1) but it is non-unique, because one can add an arbitrary constant in each connected component of the network. A connected component (more correctly called ‘weakly connected component’) of a network is a maximal subset S ⊂ N such that it is possible to get from any m ∈ S to any n ∈ S by a path of edges ignoring their directions. Thus to solve Λ h = v , one can replace the equation for one nodeterm·dom m S in each connected component S by an equation h m S = c S for arbitrary constants c S , for example 0. Then there is a unique solution for h , which can be found by any linear algebra package. Afterwards one can add an arbitrary constant to the levels in each component S if desired, for example to make the lowest one be 0 or to make the average level (with respect to the weights u n , for example) in S be 0.

Our improved notion of trophic incoherenceterm·mth is 2.7 F 0 = ∑ m n w m n ( h n − h m − 1 ) 2 ∑ m n w m n , using the levels h determined above; it is independent of the choice of shifts on connected components. This has the nice features that F 0 = 0 if and only if all the level differences z mn = h n − h m are 1, F 0 = 1 if and only if all the level differences are 0, and otherwise F 0 is strictly between 0 and 1 (see appendix A.2 for a proof). We say a network is maximally coherent if it has F 0 = 0, maximally incoherent if it has F 0 = 1. We define the trophic coherenceterm·mth to be 1 − F 0 . In appendix A.3 we prove the trophic coherenceterm·mth can be expressed alternatively as the weighted mean difference z ¯ in trophic levelsterm·mth between nodesterm·dom along the edges of the network.

The motivation for our new definitions is to seek levels h n , n ∈ N , that minimize the trophic confusion 2.8 F ( h ) = ∑ m n w m n ( h n − h m − 1 ) 2 ∑ m n w m n , where the target level difference for each edge mn is set to 1. A vector h of levels minimizes F if and only if Λ h = v (see appendix A.2). The resulting minimum value of F is the incoherenceterm·mth F 0 .

The coherence 1 − F 0 represents the extent to which levels can be assigned to make the level difference along each edge be the target difference of 1. So we can alternatively call 1 − F 0 the ‘directionality’ or ‘directedness’ of the network, hence the title of our paper.

For an electrical interpretation of ( 2.6 ), see appendix A.4.

Illustrations To illustrate the new notions of trophic levelterm·mth and incoherenceterm·mth, we begin with the classic context of food websterm·key. Here the nodesterm·dom represent species and there is a directed edge from a species to each species that eats it. Figure 1 shows the Ythan estuary food webterm·key [ 14 ] with height in the layout corresponding to our new notion of trophic levelterm·mth. The networks are spread out in the horizontal dimension by a force-based algorithm (details and refinements will be presented in a future publication). The network is fairly strongly layered; this is borne out by a small value of trophic incoherenceterm·mth F 0 = 0.08. Figure 1. Ythan estuary food webterm·key with height corresponding to our new trophic levelsterm·mth which reveal a strongly layered structure. Edges represent prey → predator relations and edge weights are all taken to be 1 as the data do not specify the relative importances of relationships.

We move now to an example from economics where the ‘upstreamnessterm·mth’/‘downstreamness’ of firms , sectors and economies in production chains is of wide relevance and interest [ 5 , 15 , 16 ]. Figure 2 shows the inter-industrial flows of goods and services in the USA and Saudi economies in 2015 (data taken from OECD IO tables). Here the nodesterm·dom represent economic sectors and weighted edges represent the dollar value of supply → purchase transactions between them (the full IO table had 35 sectors, but nodesterm·dom with lower weight ( 2.2 ) were removed to allow presentation of a labelled network). This is an interesting application because there are no basal nodesterm·key (indeed the networks are completely connected, as is usual for IO relations, with every sector both supplying and buying from every other sector), so the old notions of trophic levelterm·mth and incoherenceterm·mth cannot be applied. Figure 2. Network of inter-industrial flows of goods and services in the USA ( a ) and Saudi ( b ) economies in 2015. Nodesterm·dom represent a subset of economic sectors (accounting for largest share of inter-industry flows as captured by weight ( 2.2 )) and weighted edges represent the dollar value of supply → purchase transactions between them. Edge widths reflect the value of flows, and nodeterm·dom size reflects nodeterm·dom weight ( 2.2 ).

Unlike the Ythan food webterm·key, we see that these IO networks are rather incoherent, meaning their trophic incoherencesterm·mth are not small ( F 0 = 0.63 and F 0 = 0.46, respectively). Nevertheless, the new levels reveal an overall direction between sectors of flow in intermediate production: some sectors are key suppliers of intermediate inputs (for the USA, financial, real estate and other business service sectors; for Saudi Arabia, energy extraction and finance) while other sectors are key users of inputs from other sectors (e.g. healthcare and construction). Some sectors, however, are both users and suppliers of products (e.g. wholesale, transport and storage).

Figure 3 provides a more systematic and detailed analysis, presenting box-plots of the level of different sectors (using full 35 sector IO tables) for 57 countries (2015 data). Levels for each economy have been normalized to make the mean level 0 (weighted by u n ). While the size of different sectors varies across economies, there is considerable consistency of sector levels, which reveal the architecture of value chains in the production process: we see an overall direction of flow from energy extraction and finance sectors; through other primary materials; then manufacturing industries; followed by sectors that supply final demand more directly, such as food makers, entertainment and services; ending with education, public administration and defence sectors (that are overwhelmingly users more than suppliers of intermediate inputs). Figure 3. These boxplots present the distribution of the new trophic levelsterm·mth for each of 35 different economic sectors (ISIC Rev. 4) as obtained from the national 2015 input–output (IO) networks of 57 different economies (including OECD, and G20 economies). Sectors are sorted by their median trophic levelterm·mth (across all 57 IO networks). Red crosses indicate outliers.

There may be links to explore between sector levels and their role in economic performance—it is interesting to note, for example, that construction—which is known to lead the wider business cycle in many economies [ 17 , 18 ]—appears as a key user of inputs from other industries (implying strong backward-linkages). Meanwhile variation in the level of some sectors across different economies may also reveal interesting differences in production structure (e.g. finance occupies the same minimum position as energy extraction in China, but comes higher in the value chain for many other economies).

In biology, regulatory networks are sets of macromolecules that interact to control the level of expression of various genes in a given genome [ Nature subjects: Regulatory networks ]. Studies on regulatory networks have identified the existence of directed structures and have linked node-levels to node-properties, function [ 19 – 21 ] and the importance of regulators [ 22 ]. Assigning levels in networks with cycles, however, has presented a methodological challenge for this literature, which our improved levels overcome. Figure 4 shows an example transcription regulatory network (the yeast Saccharomyces cerevisiae [ 20 ]) plotted first with a force-directed method (left), then according to the new levels (right). The new levels reveal a striking layered structure. There are basal (red), intermediate (yellow) and top (blue) nodesterm·dom, but intermediate nodesterm·dom do not form a distinct layer and the relevance of variation in their levels might be explored. Figure 4. These two charts plot the same yeast transcription regulatory network (linking transcription factors and target genes) first with a standard force directed layout (left); then with nodeterm·dom heights corresponding to new trophic levelsterm·mth h to reveal the network’s flow-based hierarchy. Red nodesterm·dom represent transcription factors, blue nodesterm·dom denote regulated genes, and those with both functions are coloured in yellow.

Levels derived from influence networks will also be useful in social network settings (hierarchy and stratification are important concepts in sociology) and have been studied in e.g. online social networks [ 23 , 24 ].

Figure 5 shows the trophic analysis of a network of book translations [ 25 ] based on a collection of more than 2.2 million book translations compiled by UNESCO’s Index Translationum project [ 26 ]. Edge weights correspond to the number of books translated between source and target languages. While it is unlikely that individual books flow along paths in this network (given books are presumably translated from their original source language) its structure may be important in the flow of knowledge and ideas [ 25 ]. Figure 5. Global book translation network [ 25 ]. Edges and edge weights represent the number of books translated from source into target language. Upward arrows are plotted green and downward arrows red. Nodeterm·dom size is proportional to weight ( 2.2 ).

The role of eigenvector centrality in the influence of different languages within this network was studied in [ 25 ]. Our trophic analysis reveals that this network is strongly directional ( F 0 = 0.51), implying knowledge and ideas are not exchanged equally but flow in particular directions. It also reveals interesting information on the role of different languages within this directional flow: at the bottom appear languages that are only source languages—unsurprisingly these include many ‘dead languages’ (Ancient Greek, Middle French and English, Sanskrit, etc.). At the top appear languages from which nobody translates (these include minority and other languages that are small by number of speakers such as Faroese, Sami and Mongolian). In the middle, we find languages that are both target and source languages. The role of English is striking: while translated into and out of, English is more important as a source language (it has a lower trophic levelterm·mth than any other major language) and there are large flows from English into French, German, Spanish and Japanese. In this dataset only English is translated into Chinese which is in turn only a source language for minority languages in China (such as Hani and Zhuang). Russian is rather isolated in the global language network but forms an interesting community of bi-directional links with languages in its region.

Comparison with previous notions The established concept of trophic levelterm·mth [ 3 ] requires the network to have at least one basal nodeterm·key, i.e. a nodeterm·dom with no incoming edges. Then the height x b (to use Levine’s symbol) was set to a common value of 0 for all basal nodesterm·key b , though nowadays it is more common to set it to 1. The heights x n of the other nodesterm·dom in connected components with basal nodesterm·key were determined by solving 4.1 x n = 1 + ∑ m x m w m n w n in , for all non-basal n , where each sum is over the nodesterm·dom m having edges to n . Levine normalized the weights w mn coming into each nodeterm·dom n so that w n in = 1 , which makes no change to ( 4.1 ). In matrix form, the equation for the heights (with the convention x n = 1 for basal nodesterm·key) can be written as 4.2 L x = v ~ , where 4.3 v ~ n = w n in if non-zero , else 1 , and 4.4 ( L x ) n = v ~ n x n − ∑ m x m w m n . The same concept was introduced in economics by Antràs et al. [ 4 ], but fixing top nodesterm·dom (those with no outgoing edges) to a common height. It is equivalent to Levine’s after reversing all the edges.

Then [ 7 ] defined the trophic incoherenceterm·mth of the network to be the standard deviation of the height differences z mn = x n − x m over edges. They took edge weights all 1, but a natural generalization is to weight the height differences by the edge weights. The edge-weighted mean difference of Levine’s heights is precisely 1 [ 3 ], so JohnsonpersName et al. ’s [ 7 ] definition of trophic incoherenceterm·mth q becomes 4.5 q = ∑ m n w m n ( x n − x m − 1 ) 2 ∑ m n w m n . Indeed, Levine defined ‘trophic specialization’ of a nodeterm·dom m as 4.6 σ m 2 = ∑ n w m n ( x n − x m − 1 ) 2 ∑ n w m n . So q 2 is the average of σ m 2 weighted by w m out .

Our equation for trophic heights can be seen as a symmetrized version of Levine’s, without the fix for basal nodesterm·key. Thus, our definition does not need any basal nodesterm·key and does not force them all to the same level if there is more than one basal nodeterm·key.

Our definition of trophic incoherenceterm·mth is the same as q 2 but using our new heights instead of Levine’s. It represents, in roughly the same way, the failure of the height differences to all be 1. A distinction to bear in mind, however, is that for our new levels, the edge-weighted mean height-difference 4.7 z ¯ = ∑ m n w m n ( h n − h m ) ∑ m n w m n , is not necessarily 1. In fact, we prove in appendix A.3 that z ¯ = 1 − F 0 . So F 0 is not in general the (edge-weighted) variance of the height differences. To obtain the variance σ 2 of the height differences, one has to subtract ( z ¯ − 1 ) 2 from F 0 . Thus there is a case for considering alternative measures of incoherenceterm·mth to F 0 , such as the ratio η = σ / z ¯ , which evaluates to 4.8 η = F 0 1 − F 0 , and is the appropriate replacement for q . In the other direction, the analogue of F 0 is q 2 /(1 + q 2 ).

While we acknowledge there may be some applications where fixing all basal (or top) nodesterm·dom to the same level may be most appropriate, we believe that in many cases it will be more natural to allow the height of basal nodesterm·key to be determined according to their integration into the overall flow hierarchy of the network. If we take, for example, figure 6 as representing a simple stylized sequential production process where intermediate inputs are transformed over six stages, it seems to us that this process is better described by levels according to our notion—which returns integer levels identifying the discrete stages of the process and which stage each nodeterm·dom belongs to—than it is by standard levels. It seems natural to consider nodeterm·dom 10 to be more upstream than nodeterm·dom 1 or 2 (although they are all ‘basal’), and this may be important in the context of e.g. sector specific shocks. Figure 6. This figure shows a comparison between our levels versus standard levels calculated for a toy example of a sequential process with six stages.

Of course the flow hierarchy of most real processes will be a more complex web of intermediate flows. Figure 7 shows some comparisons of trophic levelsterm·mth determined by the two methods for two different empirical supply networksterm·key. In these networks, the nodesterm·dom represent firms and each directed edge represents a significant supplier → buyer relationship. 2 We see that the requirement of the standard approach to put all basal nodesterm·key at a common level makes what we consider to be an artificial distortion of the levels—especially in the left-hand case. Figure 7. Supply networksterm·key around two firms (indicated by the larger black dot), plotted with the new (top) and old (bottom) notions of trophic levelterm·mth. The horizontal positions are determined to spread out the nodesterm·dom while attempting to make most of the edges near vertical, but the same horizontal positions are used in both the upper and lower pictures. Supply chain data compiled from Bloomberg L.P.

As an alternative comparison, in figure 8 we plot (for the same two supply networksterm·key as figure 7 ) the old levels against the new levels. Figure 8. New levels against old levels for the same two supply networksterm·key as in figure 7 .

If one reverses all the edges, then with our new definition one obtains the reflection of the trophic levelsterm·mth, up to an overall shift depending on the convention used to fix the zero of the levels. The trophic incoherenceterm·mth is unchanged. For example, for a supply networkterm·key, instead of the flows of goods and services one could consider the flows of payment, which are more or less the reverses of the flows of goods and services.

By contrast, the old notion of trophic levelterm·mth is usually not symmetric with respect to change of direction of all the edges. Figure 9 shows the trophic levelsterm·mth of firms in our two example supply networksterm·key obtained according to the old notion, (i) when edges are directed from supplier to buyer (showing the direction of material and service flows), and (ii) under the reverse interpretation (showing the direction of payment flows from buyers to sellers). It is apparent that with the old notion there is a big change in levels, the relevance of which is unclear. Unless there is a good reason to favour basal nodesterm·key, we propose that our symmetric notion is advantageous. Figure 9. The same two supply networksterm·key as in figures 7 and 8 with nodesterm·dom organized according to trophic levelsterm·mth obtained using the old notion for (i) the original networks (vertical axis) and (ii) the same networks but with interpretation of edges reversed (horizontal axis).

There have been some other approaches to rectifying the limitations of the original notion of trophic levelterm·mth. Dominguez et al. [ 8 ] obtain a ‘basal set’ of nodesterm·dom and eliminate all edges within that set. Moutsinas et al. [ 27 ] define levels using a pseudo-inverse of L . These solutions allow application to networks without basal nodesterm·key but they do not possess a natural notion of maximal incoherenceterm·mth nor symmetry with respect to reversal of edge directions (though in some contexts one might not want symmetry).

Trophic incoherenceterm·mth is related to the number of directed cycles in a network [ 10 ], and hence to measures of acyclicity. For example, one can find the smallest number of edges to delete to obtain an acyclic graph [ 28 ], although this method has some defects [ 29 ]. The smallest number is called the ‘agonyterm·mth’ of the network. Our trophic analysis provides a useful upper bound for agonyterm·mth, given by the number of edges with negative height difference, and could be used as a convenient heuristic for its exact computation. However, agonyterm·mth and incoherenceterm·mth are different concepts, since acyclic networks can differ in incoherenceterm·mth [ 7 ]. Related papers are [ 30 ] on reordering a matrix to make it as triangular as possible, and [ 31 ] quantifying directedness by the fraction of edges not in any cycle.

A precursor of our notion of trophic levelsterm·mth was given by [ 32 ], with the same minimization principle (extended to arbitrary height differences as we do in § 7 ), but they chose a different quantification of directedness, namely the ratio of the difference in levels of the highest and lowest nodesterm·dom to the diameter of the network, which is more sensitive to extremes and in our opinion less correlated with the other network properties we have considered. The same minimization principle was proposed again by De Bacco et al . [ 33 ], but without a quantification of directedness. The recent papers [ 34 , 35 ] derive essentially the same notions of levels and coherence as us, by decomposing flows on a network into the sum of a potential part and a circulating part. This is a very nice approach, though it requires specifying conductivities for each edge as well as the flow on it, instead of specifying a weight and a target height difference for each edge. The analysis has strong connections with ours, in particular the minimization principle to determine the potential and an electrical interpretation. The connections are described in appendix A.14.

Next, we comment on the large literature on hierarchical methods for directed networksterm·dom. Although the term ‘hierarchy’ is often used just to describe a nodeterm·dom as being above or below another (cf. our use of ‘flow hierarchy’), it generally has more connotations that we are not addressing here. In particular, in an ideal hierarchy the graph of immediate superiority relations is often assumed to have a unique maximal nodeterm·dom and to form a pyramid, and the question posed is how far a network deviates from this structure. The question overlaps with the one we address, but is different. A full survey of the literature will have to wait for a future publication, but we highlight the book [ 36 ] and the following references. Corominas-Murtra et al . [ 37 ] propose three measures of hierarchy: treeness, feed-forwardness and orderability. Ravasz et al . [ 38 ] consider containment hierarchy. Ruths & Ruths [ 39 ] consider control of directed networksterm·dom. Czègel & Palla [ 40 ] introduce a method to distinguish between a directed acyclic graph and ones with maximal directedness, something which our method also does. Mones et al . [ 41 ] introduce a global reaching centrality measure. Maktoubian et al . [ 42 ] propose how to take signed edge-weights into account.

There are many other concepts of importance for nodesterm·dom in a network, e.g. PageRank, HITS and Katz centrality (for a survey, see [ 43 ]). To the best of our knowledge, however, these are all very different from trophic levelsterm·mth.

Robustness of local computation If we determine trophic levelsterm·mth on a piece of a network by truncating the network at some distance from a chosen nodeterm·dom, measured for example by the number of edges in either direction, how robust are the resulting levels to the truncation? This is an important question in practice, because it might be infeasible to obtain or analyse the whole of a large network, yet it can be useful to determine relative levels on a piece of the network.

First we take care of the arbitrariness of the zero of trophic levelsterm·mth. The simplest way to do that is to take the chosen nodeterm·dom to be always at height zero.

Next, we refine the question because the trophic levelsterm·mth near the boundary of the piece of the network may change significantly with the truncation. We ask how much the trophic levelsterm·mth change on a connected subset of the network containing the chosen nodeterm·dom, which we will call zone 1, given a buffer zone 2 chosen so that there are no direct edges in either direction between zone 1 and the outside, called zone 3. We choose the buffer zone so that in addition the union of zones 1 and 2 is connected (the only way this cannot be satisfied is if zone 2 contains nodesterm·dom which are not connected to zone 1 by a path in zone 2, in which case one can just throw them out).

Figure 10 shows the outcome of a test, taking zone 1 to be the set of suppliers and buyers of General Motors (GM) 2 hops from GM, and computing the effects on the trophic levelsterm·mth in zone 1 of truncation of the network at 3, 4 and 5 hops, respectively (i.e. allowing a zone 2 buffer), compared to truncating at 7 hops. One can see that the trophic levelsterm·mth on zone 1 stabilize quite rapidly. Figure 10. Plot of the new trophic levelsterm·mth of buyers and suppliers in a 2-hop neighbourhood of General Motors calculated on networks constructed by sampling neighbourhoods of increasing size (3,4 and 5 hops) (horizontal axes), versus the levels of the same set of nodesterm·dom calculated on a larger 7-hop neighbourhood (vertical axes). Supply chain information compiled from Bloomberg L.P.

In appendix A.5, we give some theoretical analysis to support the general conclusion that the levels on zone 1 are robust to changes on zone 3.

Connections to other network properties A large part of the interest of the original notion of trophic coherenceterm·mth was its relation to network properties such as the stability of equilibria of Lotka–Volterra dynamics on the network [ 7 ], the dynamics of spreading processes [ 11 ], prevalence of cycles [ 10 ], other motifs [ 12 ], intervality [ 8 ] and normalityterm·mth [ 9 ]. We show here that the new notion of trophic coherenceterm·mth has similar connections, even stronger, and it enlarges the scope of application because it does not require basal nodesterm·key. We examine three of the properties.

Normalityterm·mth A directed networkterm·key is said to be normal [ 44 ] if its weight matrix W commutes with its transpose W T , 6.1 W W T = W T W . Note that W T represents the same weighted network but with all the edges reversed. Empirical directed networksterm·dom are often highly non-normal [ 45 ], so the use of the word ‘normal’ is somewhat unfortunate in this context.

For the unweighted case of an adjacency matrix A , normalityterm·mth implies that the imbalance vector v is 0. This is because ( A T A ) mn is the number of sources in common to nodesterm·dom m and n , and ( AA T ) mn is the number of targets in common. In particular, ( A T A ) n n = w n in and ( A A T ) n n = w n out , so A T A = AA T implies that w in = w out and v = 0.

When v = 0 we say a network is balanced . In appendix A.6, we prove that a network is balanced if and only if its trophic incoherenceterm·mth F 0 = 1. So, from the previous paragraph, normal unweighted networks are maximally incoherent.

Another special case of normalityterm·mth is symmetric networks W = W T . If W is symmetric then the imbalance vector v = 0. So symmetry implies maximal incoherenceterm·mth.

The concept of normalityterm·mth is broader than either of these, however, and maximal incoherenceterm·mth is not equivalent to normalityterm·mth. There are non-normal networks with v = 0 and hence maximal incoherenceterm·mth, e.g. 6.2 W = [ 1 1 0 0 0 1 1 0 0 ] .

Nevertheless, the extent to which a network is normal seems to be positively correlated with its trophic incoherenceterm·mth F 0 . The degree of normalityterm·mth of a network can be quantified by 6.3 ν = ∑ j | λ j | 2 ∥ W ∥ F 2 , where ∥ W ∥ F = ∑ m n | w m n | 2 is called the Frobenius norm of W , and λ j ∈ C are the eigenvalues of W (with multiplicity). Some of the literature uses ∥ W ∥ F 2 − ∑ j | λ j | 2 as a quantifier of non-normality, but we consider it simpler to use the normalityterm·mth ν (as in the real elliptic Ginibre ensemble [ 46 ]). The normalityterm·mth ν of W lies in the interval [0, 1], with ν = 1 if and only if W is normal [ 44 ]. If W is maximally coherent ( F 0 = 0) then all its eigenvalues are 0 (appendix A.7), so ν = 0 and it is maximally non-normal. But one can have ν = 0 without F 0 = 0, for example, the feed-forward motif ( figure 11 ) with 6.4 W = [ 0 1 1 0 0 1 0 0 0 ] , for which h = [−2/3 0 2/3] T and F 0 = 1/9. Figure 11. Four simple motifs illustrating relationship between incoherenceterm·mth and normalityterm·mth: for the unweighted case of an adjacency matrix A , normalityterm·mth ( ν = 1) implies the imbalance vector v = 0, thus F 0 = 1. This is illustrated by the feed-back loop (top left). However, maximal incoherenceterm·mth is not equivalent to normalityterm·mth—motif 3 (bottom left) demonstrates one can have F 0 = 1 without ν = 1 (here motif 3 ( 6.2 ) is non-normal ( ν = 0.88)). If W is maximally coherent ( F 0 = 0) then all its eigenvalues are 0, so ν = 0 and it is maximally non-normal. This is illustrated by the chain (top right). However, one can have ν = 0 without F 0 = 0. This is demonstrated by the feed-forward motif (bottom right), which has ν = 0 but F 0 = 0.11.

Figure 12 shows normalityterm·mth against trophic incoherenceterm·mth for some real networks. We see that normalityterm·mth increases with F 0 , but not linearly. In appendix A.10, we present heuristic arguments in favour of a relationship between them of the form ν ≈ exp(1 − 1/ F 0 ). This is consistent with a relationship between normalityterm·mth and the old notion of trophic coherenceterm·mth [ 9 ]. Figure 12. Normalityterm·mth ν against trophic incoherenceterm·mth F 0 for some networks. The curve corresponds to the coherence-ensemble expectation ν ¯ = exp ⁡ ( 1 − 1 / F 0 ) .

Stability Next we discuss how dynamical processes on networks are affected by their trophic coherenceterm·mth.

A simple dynamical model for contagion on a weighted network in discrete time is 6.5 x n ′ = ∑ m x m w m n r , where x n ≥ 0 represents the amount of infection at nodeterm·dom n at some time, x ′ n the amount at the subsequent time, and r > 0 is a scaling factor. We wish to know whether the total infection ∥ x ∥ 1 = ∑ n x n on the network will grow or decay. In vector–matrix form, the solution after time t ∈ Z + is 6.6 x ( t ) = x ( 0 ) W t r t . The answer (see appendix A.8) is that if ρ < r then ‖ x ( t )‖ 1 → 0 as t → ∞, whereas if ρ > r and condition K holds ( x n > 0 for some nodeterm·dom n in or leading to a ‘key’ communicating class), then ‖ x ( t )‖ 1 → ∞, where the spectral radiusterm·key ρ of W is the largest absolute value of the eigenvalues of W . Actually, because W has all entries non-negative, it has a real positive eigenvalue of maximum modulus, so that is ρ . Indeed, under condition K , 6.7 t − 1 log ⁡ ∥ x ( t ) ∥ 1 → log ( ρ r ) as t → ∞ .

We have already mentioned that a maximally coherent network has all its eigenvalues 0, so F 0 = 0 implies ρ = 0. This suggests that ρ , scaled by a suitable measure of the strength of W , might correlate positively with F 0 . The strength of W can be measured by any norm, for example the 2-norm ‖ W ‖ 2 . This can be defined in various ways, of which perhaps the simplest is that ∥ W ∥ 2 2 is the largest eigenvalue of W T W (which is necessarily real and non-negative and is equal to that for WW T ). For any operator-norm, ρ ≤ ‖ W ‖. Thus ρ /‖ W ‖ is contained in [0, 1], like F 0 . An advantage of the particular choice of the 2-norm is that ρ = ‖ W ‖ 2 if W is normal. So we define the scaled spectral radiusterm·key 6.8 ρ s = ρ ∥ W ∥ 2 . Then we deduce from the subsection on normalityterm·mth various cases with simultaneously F 0 = 1 and ρ s = 1.

Thus we look at how F 0 correlates with the scaled spectral radiusterm·key ρ s in figure 13 . In appendix A.11, we give heuristic arguments in favour of a relation 6.9 ρ s ≈ exp ( 1 2 ( 1 − 1 F 0 ) ) . Figure 13. Scaled spectral radiusterm·key ρ /‖ W ‖ 2 against trophic incoherenceterm·mth F 0 for some networks. The curve corresponds to the coherence-ensemble prediction of ρ s = exp ⁡ ( ( 1 − 1 / F 0 ) / 2 ) .

We can also consider a simple dynamical model for contagion in continuous time, 6.10 x ˙ n = ∑ m x m w m n − r x n , with r a recovery rate (without immunity). The solution can be written in vector-matrix form as 6.11 x ( t ) = x ( 0 ) e ( W − r I ) t . Again one can ask whether the total infection ‖ x ( t )‖ 1 grows or decays. This is now a question of the maximal real part of the eigenvalues of W , but because W is non-negative, the maximal real part of eigenvalues is actually ρ . So the answer is growth for ρ > r , decay for ρ < r . So again it is interesting to link ρ with F 0 and relation ( 6.9 ) will be useful.

Some other dynamics on networks are discussed in appendix A.9.

Cycles By a cycle in a directed networkterm·key, we mean a closed walk in it. A walk is any sequence ( e j ) j = 1 J of edges such that for 1 ≤ j < J the head of e j is the tail of e j +1 . It is closed if the head of e J is the tail of e 1 . In contrast to much of the graph-theory literature, we allow a cycle to have repeated edges and repeated nodesterm·dom, but we prefer to use the shorter and more familiar word ‘cycle’ than ‘closed walk’. In particular, we allow a cycle to be a periodic repetition of a shorter cycle. The weight w γ of a cycle γ is the product of the weights along its edges.

A maximally coherent network ( F 0 = 0) has no cycles, because it has height difference +1 for every edge, whereas along a cycle the net change in height has to be zero. There are acyclic graphs with F 0 > 0, however, for example the feed-forward motif ( 6.4 ).

A maximally incoherent network ( F 0 = 1) must have cycles. This is because it is balanced and so some of the flow that leaves a nodeterm·dom must eventually come back to it (see appendix A.12). In fact, we deduce that every edge is in at least one cycle.

So these results suggest some relation between trophic incoherenceterm·mth F 0 and a quantifier of cyclicity.

The total weight of cycles of length p is given by the trace of the p th power of W : tr W p , because ( W p ) m n = ∑ j w n 0 n 1 … w n p − 1 n p and the trace of a matrix is the sum of its diagonal entries. Note that this counts each cyclic permutation of a cycle as a different cycle. One might expect it to behave asymptotically exponentially as p → ∞, but for example if k points in a circle are each connected to just their clockwise neighbour by an edge of weight x , then tr W p = k x p when p is a multiple of k , 0 otherwise. The tidy way to study the sequence tr W p is to form the zeta function 6.12 ζ ( z ) = exp ⁡ ∑ p = 1 ∞ z p p tr W p , for complex z close enough to 0 (some authors define ζ ( z ) to be the reciprocal of this). Then a notion of the cyclicity of W is the reciprocal of the radius of convergence of the power series. This is just lim sup p → ∞ ( tr W p ) 1 / p . Using log ⁡ det = tr log , the zeta function can equivalently be written as det ( I − z W ) − 1 . The reciprocal of its radius of convergence is the spectral radiusterm·key ρ . So actually, the appropriate measure of cyclicity is ρ relative to some measure of the size of W . We take again ‖ W ‖ 2 for the latter. Thus, cyclicity ρ /‖ W ‖ 2 = ρ s is related to F 0 exactly as is the stability of our simple contagion processes. In particular it is 1 for any normal network.

In appendix A.13, we relate ζ to the prime cycles, those which are not repetitions of a shorter cycle, and furthermore to the elementary cycles, those which do not repeat a nodeterm·dom.

Extension to arbitrary target height differences So far, we have taken all the target height differences equal, but there are contexts in which this might not be appropriate. Instead of trying to fit the height differences along each edge to 1, it might be preferable to fit them to more general target height differences τ mn . For example, if two nodesterm·dom m , n are subunits of a single company with m supplying n it might be reasonable to assign a value τ mn less than 1. Or if there is a feed-forward motif that one does not want to contribute to circularity, then one could assign target height difference 1 / 2 to the edges for the indirect route and 1 to the direct edge.

The extension of our method to this setting is straightforward. Minimize F ( h ) = ∑ m n w m n ( h n − h m − τ m n ) 2 ∑ m n w m n τ m n 2 , over h . This is equivalent to solving Λ h = v with now v n = ∑ m ( w m n τ m n − w n m τ n m ) . If we set F 0 to be the minimizing value of F and z mn = ( h n − h m )/ τ mn and weight the z mn by w m n τ m n 2 , then we obtain all the same properties as before: 0 ≤ F 0 ≤ 1, z ¯ = 1 − F 0 , etc.

One context in which it is natural to use the data to set the target height differences is quantitative pairwise comparison, for example, use of goal differences in a football league to infer relative strengths of teams. Then it is natural to make each game carry equal weight and the outcome of our extended method is trophic levelsterm·mth representing the relative strengths of the teams [ 47 ].

Discussion In many domains of science, one is faced with a directed networkterm·key and wishes to determine (i) to what extent the edges line up in an overall direction, and (ii) the relative position of individual nodesterm·dom within any directional flow on the network.

The old concept of ‘trophic levelterm·mth’ from ecology, and its more recent analogue ‘upstreamnessterm·mth’ in economics, provided an answer to the question of the relative positions of individual nodesterm·dom; however, these previous notions required (respectively) basal or top nodesterm·dom; they give too much emphasis to basal/top nodesterm·dom if there is more than one; and they do not give a stable way to determine levels and incoherenceterm·mth for a piece of a network.

The notion of ‘trophic coherenceterm·mth’ introduced in [ 7 ], based on the old notion of trophic levelsterm·mth, provides a way to quantify the extent to which edges align in an overall direction and was shown to be connected with network properties such as cycles and spectral radiusterm·key, but it lacks a natural notion of maximal incoherenceterm·mth.

In this paper, we have introduced improved notions of trophic levelterm·mth and trophic coherenceterm·mth, which do not require basal or top nodesterm·dom; are as easy to compute as the old notions; and are connected in the same way with network properties such as normalityterm·mth, cycles and spectral radiusterm·key. Furthermore, they remove the problem of bias from basal nodesterm·key, make incoherenceterm·mth have a natural range from perfect coherence to maximal incoherenceterm·mth, and make it possible to compute them locally in a network without having to compute them for the whole network.

We expect this to be a valuable tool in domains from ecology, gene expression, neuroscience and biochemistry to economics, finance, social science and humanities.

Supplementary Material