Open networks from within: input or output betweenness centrality of nodes in directed networks

Abstract

New betweenness centralities of nodes in a directed network are proposed based on the idea that nodes in a network are processes rather than things. They are called input and output betweenness centralities. They measure importance of nodes as input and output for gluing arcs together as interface between processes, respectively. We demonstrate their use and discuss their meaning by calculating them in two toy directed networks and one real-world network. We also compare them with the existing centrality measures that reflect asymmetry of links in directed networks: out- and in-degrees and Hub and Authority scores. We found that input and output betweenness centralities behave differently from these measures in some nodes. It is suggested that they can effectively identify nodes that are less important in terms of existing measures but are noteworthy from the viewpoint that nodes are processes.

Introduction

Categorical network theory is a general framework to study open networks, namely, networks with explicit input and output nodes such as electrical circuits (Baez and Fong 2015), signal flow diagrams (Baez and Erbele 2015; Bonchi et al. 2014) and chemical reaction networks (Baez and Pollard 2017). It thinks of networks as processes in contrast to network science where networks are thought of as things (Baez 2014). Indeed, the main challenges in network science are analysis and modeling of network structure found in nature and society (Newman 2010; Estrada 2012; Barabási 2016). On the other hand, the primary interest of categorical network theory is the behavior of open networks determined by the relation between inputs and outputs that is revealed by black-boxing the internal structure of networks (Baez and Fong 2015). The divide into networks as things and networks as processes is a natural consequence of the category theoretic perspective. As we explain in next section, a category has two-level structure: objects representing things and morphisms representing processes between things. In categorical network theory, networks are regarded as morphisms. The aim of this study is to bridge these two different approaches to networks and get a new insight into structure of networks. Our approach is based on a reformulation of our previous work (Haruna 2013b) that has been developed independently of categorical network theory. However, we reinterpret our previous work as an internalization of the idea of categorical network theory into networks themselves and as a result we find new betweenness centralities that are obscure so far.

Identifying important nodes or links from a specific perspective is a basic task when analyzing networks found in social and natural sciences. A variety of centrality measures has been proposed to quantify importance of nodes or links (Borgatti and Everett 2006). In this paper, we focus on betweenness centrality among them since it seems to be the most natural one in our context. There are many variants of betweenness centrality such as the original one based on shortest paths (Anthonisse 1971; Freeman 1977) and those based on network flows (Freeman et al. 1991), random walks (Newman 2005) and percolation (Piraveenan et al. 2013). We will be faced with a path notion called lateral path different from the usual directed path in directed networks in the following attempt to internalize the idea of categorical network theory into networks themselves. Here, we only focus on the simplest betweenness centrality based on shortest lateral paths because extensions to other variants seem to be non-trivial and are out of the scope of this paper. We propose input (resp. output) betweenness centrality of nodes in a directed network quantifying importance of nodes as input (resp. output) from the viewpoint that nodes are processes.

This paper is organized as follows. In the second section, we explain how the idea of categorical network theory can be internalized into networks themselves and derive input or output betweenness centrality from the viewpoint that nodes are processes. In the third section, we calculate them in two toy directed networks and a real-world network. In the final section, conclusions are given.

Input or output betweenness centrality

In this section, we first explain the main idea of categorical network theory and then proceed to the way we internalize it into directed networks themselves. There are several approaches based on different techniques such as cospans (Fong 2015), props (Bonchi et al. 2014; Baez et al. 2017) and operads (Spivak 2013). Here, we follow the one based on cospans (Fong 2015). Finally, input or output betweenness centrality is introduced.

Idea of categorical network theory

In categorical network theory, networks are regarded as processes, namely, a certain kind of action with input and output. This can be formalized in category theory. Here, we do not intend to go into the technical details. However, a few terminologies cannot be avoided to explain it without ambiguity. So, first we explain them.

In general, a category consists of objects and morphisms between objects. It is subject to a few axioms but we leave the details such as the rigorous definition of categories and their basic properties to introductory textbooks (Awodey 2010; Spivak 2014). Objects represent things of interest and a morphism between two objects represents an allowed process from one to the other. For example, in the category of sets, objects are sets and morphisms are maps. A map f from a set A to another set B (we write f:A→B) specifies an element of B to which each element of A is transformed. As the map f has its domain A and codomain B, each morphism in a category has its domain and codomain. The domain and codomain of a morphism can be seen as input and output to the process represented by the morphism, respectively. We denote a morphism m with domain D and codomain E in a category by m:D→E as in the case of maps. As two maps f:A→B and g:B→C can be composed and yield a new map g∘f:A→C, two morphisms m:D→E and n:E→F can be composed. The obtained morphism is denoted by n∘m:D→F.

Now, let us consider directed networks. We denote a directed network by G=(N,A,s,t) where N is the set of nodes, A is the set of arcs and s and t are maps from A to N sending each arc to its source and target nodes, respectively. Directed networks form a category $\mathcal {D}$. Its objects are directed networks and morphisms are homomorphisms of directed networks, namely, “maps” preserving the structure of directed networks: A morphism m:G₁=(N₁,A₁,s₁,t₁)→G₂=(N₂,A₂,s₂,t₂) is a pair of maps (m_N:N₁→N₂, m_A:A₁→A₂) such that m_N∘s₁=s₂∘m_A and m_N∘t₁=t₂∘m_A.

In the category of directed networks $\mathcal {D}$, directed networks are objects and thus they are regarded as things, not processes. However, we can build a category whose morphisms are directed networks with input and output as follows. Let us call a pair of morphisms (i:I→G, o:J→G) in $\mathcal {D}$ a cospan from I to J. In Fig. 1a, an example is shown. If we have another cospan (i^′:J→H, o^′:K→H) from J to K (Fig. 1b), we can glue them via o:J→G and i^′:J→H (Fig. 1c). As a result, we obtain a new cospan $(\tilde {i}:I \to H \circ G, \ \tilde {o'}: K \to H \circ G)$ from I to K (Fig. 1d), where $\tilde {i}$ and $\tilde {o'}$ are homomorphisms to H∘G that are induced automatically from i and o^′, respectively. Thus, we can compose cospans. It is known that we can form a category $\text {Cospan}(\mathcal {D})$ whose objects are objects of $\mathcal {D}$, namely, directed networks and morphisms are cospans (precisely, we should take isomorphism classes of cospans (Borceux 1994)). This fact itself is not used in the following, we have remarked it for completeness. Thus, a directed network G together with its input i:I→G and output o:J→G can be regarded as a process within the category $\text {Cospan}(\mathcal {D})$. This is one of the main ideas of categorical network theory. Note that here we only consider network topology. To include weights or dynamics on networks requires extra machineries (Fong 2015).

Fig. 1

An example of composition (c, d) of cospans (a, b) in the category of directed networks $\mathcal {D}$. See the main text for details

Internalization

In the previous subsection, we explain how a directed network together with its input and output can be seen as a process. In this subsection, we internalize this idea into networks themselves. The content of this subsection is a recapitulation of our previous work (Haruna 2013b) from the viewpoint of categorical network theory.

Our motivation is as follows. In real-world networks, nodes are not just points. They often have internal processes. In particular, this is obvious for some biological networks. For example, let us consider food webs. We will analyze one in next section. In a food web, nodes are biological taxa. They are living processes. Links represent prey-predator relations. From the physical viewpoint, they are passages of organic materials. However, if we think of nodes as processes, then links can be interpreted as interface between living processes. Thus, the idea that networks are processes should be internalized to each node in a given network. In the following, we explain how this idea can be formalized.

We would like to represent nodes as processes in the sense of categorical network theory. One of the simplest and natural way is to represent a node in a directed network by the cospan (i:I→G, o:J→G) (Fig. 2a): G consists of two distinct nodes {a, b} and an arc f from a to b. I and J are networks with a single node and no arcs. Maps i and o send the single nodes to a and b, respectively. Now let us consider two nodes in the network connected by an arc (Fig. 2b). We replace the source and target nodes of the arc by the two copies of the cospan (i:I→G, o:J→G). The arc is interface between these two processes. This can be manifested by identifying the output of the cospan for the source node with the input of the one for the target node. Then, we can compose these two cospans and obtain a new cospan shown in the bottom of Fig. 2b. By forgetting the input and the output of the obtained cospan, we can see that the network at the left top in Fig. 2b is transformed to the one at the apex of the cospan at the bottom in Fig. 2b. Indeed, this procedure can be extended to the whole network and gives rise to a network transformation L described as follows (Haruna 2013b): Let G=(N,A,s,t) be a directed network. L(G)=(N^′,A^′,s^′,t^′) is a directed network such that N^′=N×{0,1}/∼, A^′=N and maps s^′, t^′:A^′→N^′ are defined by s^′(x)=[(x,0)] and t^′(x)=[(x,1)]. Here, ∼ is an equivalence relation on the set N×{0,1} generated by the relation R: We define (x,1)R(y,0) when there is f∈A such that s(f)=x and t(f)=y. [(x,i)] is the equivalence class containing (x,i) for i=0,1. In other words, nodes in G become arcs in L(G) and they are glued up together along the relation induced by arcs in G. (x,0) and (x,1) correspond to the input and the output of the cospan in Fig. 2a, respectively. An example is shown in Fig. 4.

Fig. 2

a A cospan representing nodes as processes. b What happens when two nodes as processes are linked by an arc

What is the precise relationship between the composition of cospans and L(G)? Both are examples of colimits (MacLane 1998). Colimits are a categorical construction to form an object by gluing parts together. The composition of cospans is a special type of colimits called pushouts (MacLane 1998). On the other hand, L(G) is a more general colimit depending on the “shape” of G (Haruna 2013b).

The idea that arcs are interface between nodes as processes can be formalized as a map φ:A→N^′ defined by φ(f)=[(s(f),1)] or equivalently, φ(f)=[(t(f),0)]. In Fig. 4, arcs f, g and h in G are mapped to a single node in L(G). In general, φ(f)=φ(g) holds for f,g∈A if and only if f and g are connected by a lateral path (Fig. 3). A lateral path between two arcs f and g in a directed network is a sequence of arcs such that the first and last arcs are f and g, respectively, and successive arcs in the sequence have a common target node or source node alternately. Note that lateral paths are not defined between nodes but arcs in this paper. Lateral paths between nodes have been considered in the literature (Crofts et al. 2010) to reveal the bipartite community structure of directed networks. The map φ has a characterization in terms of a category theoretic universality (Haruna 2013b): It is the “minimum” map materializing the idea that arcs are interface between nodes as processes. We also note that the directed network transformation L is a kind of dual transformation to the operation of taking the line-graph: the line graph R(G) of a directed network G=(N,A,s,t) is a directed network such that the set of nodes is A and arcs are directed paths of length 2 in G. In category theoretic terms, both L and R can be made into functors from $\mathcal {D}$ to itself and L is left adjoint to R (Pultr 1979; Haruna and Gunji 2007).

Fig. 3

Lateral paths are defined between two arcs, not between two nodes. A lateral path between two arcs f and g is a sequence of arcs between them such that successive arcs have a common target node or source node alternately

Fig. 4

A directed network G is transformed to another directed network L(G). Associated map φ from the set of arcs of G to the set of nodes in L(G) is also shown

Definition of input or output betweenness centrality

Let us consider a directed network G shown on the left-hand side in Fig. 4. In G, a is the input to f and c is the output from f in the sense of cospan (isolate f and its source a and target c from G and consider the cospan like Fig. 2a). The same holds for g and h. From the result of the previous subsection, we can regard a, b, c and d as processes and f,g and h as interface between them by applying L to G and considering the map φ. By the map φ, f, g and h are sent to the same node at the center of L(G). From this viewpoint, we can say that a and b are input to the set {f,g,h} and c and d are output from {f,g,h} (Fig. 4). A natural question is, how important are they as input or output? Since f, g and h are related by lateral paths, one could use lateral paths to measure importance of nodes in G with respect to cohesiveness among f, g and h. One way is to introduce analogues of betweenness centrality (Anthonisse 1971; Freeman 1977). Namely, if a node is the source (resp. target) of arcs in many shortest lateral paths, then it would be important as input (resp. output) for retaining cohesiveness of arcs mapped to the same node in L(G). To quantify importance of nodes as input (resp. output) in this sense, first we calculate the betweenness centrality of arcs with respect to lateral paths and then project them to their source (resp. target) nodes.

Let G=(N,A,s,t) be a directed network. The lateral betweenness centrality (LBC) of an arc f∈A is (Haruna 2013b)

$$ \text{LBC}_{f} = C \sum_{g,h \in A, \ l_{gh}>0} \frac{l_{gh}^{f}}{l_{gh}}, $$

(1)

where l_gh is the number of shortest lateral paths between g and h, $l_{gh}^{f}$ is the number of shortest lateral paths between g and h that pass through f and $C=\sum _{g,h \in A, l_{gh}>0} (d_{gh}+1)$ is the normalization constant such that $\sum _{f \in A}\text {LBC}_{f}=1$. d_gh denotes the length of shortest lateral paths between g and h. The length of a lateral path is the number of nodes that are passed through between g and h. In particular, d_gg=0. $\sum _{f \in A}\text {LBC}_{f}=1$ follows from the equality $\sum _{f \in A} l_{gh}^{f}=l_{gh}(d_{gh}+1)$ for g,h∈A such that l_gh>0. Indeed, both sides of the equality are two different ways to count the number of arcs on shortest paths from g to h with repetition. Note that in the summation in Eq. (1), g,h are an ordered pair. Thus, the same shortest lateral path is counted twice if g≠h: one is from g to h and the other is from h to g.

The input betweenness centrality (IBC) of a node x∈N is defined by summing all LBC_fs such that the source of f is x:

$$ \text{IBC}_{x} = \sum_{s(f)=x} \text{LBC}_{f}. $$

(2)

The output betweenness centrality (OBC) of x is defined similarly:

$$ \text{OBC}_{x} = \sum_{t(f)=x} \text{LBC}_{f}. $$

(3)

Note that we do not directly focus on the structure of L(G) to define LBC, IBC and OBC. Lateral paths induce an equivalence relation on the set of arcs in G to form the nodes in L(G). These measures evaluate contribution of each arc or node for gluing arcs along lateral paths and yielding nodes in L(G). Since lateral paths are derived from the map φ representing arcs as interface between nodes as processes, we suggest that IBC (resp. OBC) can be used to identify natural input (resp. output) nodes of a given directed network from the viewpoint that nodes are processes.

The LBCs of all the arcs can be calculated by slightly modifying the Brandes-Newman algorithm (Brandes 2001; Newman 2001): For each arc f, we construct the shortest path tree with respect to lateral paths and run the algorithm to calculate the contribution to LBC of shortest lateral paths starting from all the arcs and ending at f. The time complexity to calculate LBC_f for all the arcs f in G is O(|A|²) or O(|N|²) for sparse networks. The same holds for the calculation of IBCs or OBCs of all the nodes.

Examples and an application

In this section, we calculate IBC and OBC of two toy networks and one real-world network. We compare them with existing centrality measures reflecting asymmetry of links. The aim of this section is not a thorough analysis of a specific network but demonstration of their use.

Toy examples

First, let us calculate IBC and OBC of nodes in a small network for an illustration (Fig. 5a). Since l_ij=1 for all i,j∈{f,g,h}, d_ff=d_gg=d_hh=0, d_fg=d_gf=d_gh=d_hg=1 and d_fh=d_hf=2, we have C=3(0+1)+4(1+1)+2(2+1)=17. Since $l_{ff}^{f}=l_{fg}^{f}=l_{gf}^{f}=l_{fh}^{f}=l_{hf}^{f}=1$, LBC_f=5/17. Similarly, we find LBC_g=7/17 and LBC_g=5/17. Thus, we have IBC₁=LBC_f=5/17, IBC₂=LBC_g+LBC_h=12/17 and IBC₃=IBC₄=0. Similarly, OBC₁=OBC₂=0, OBC₃=LBC_f+LBC_g=12/17 and OBC₄=LBC_h=5/17.

Fig. 5

a, b Toy networks. See the main text for details

Next, let us consider a larger but still a small network consisting of 10 nodes and 12 arcs (Fig. 5b). Here, thickness of arcs is proportional to LBC, size of red nodes IBC and size of blue node OBC. OBC of node i for 1≤i≤5 and IBC of node j for 6≤j≤10 are 0. Let us call a set of arcs forming dense lateral connections lateral community of arcs (LCA). In Fig. 5b, we could identify two such communities by visual inspection: the set of arcs from nodes 1,2,3 to 6,7 and the set of arcs from nodes 4,5 to 8,9,10. From this example, it is suggested that nodes bridging LCAs from input and output sides of them have high IBC and OBC, respectively. This can be expected from the definitions of IBC and OBC since shortest lateral paths between two LCAs must pass through an arc bridging them as in the case of the classical betweenness centrality. The values of IBC and OBC of all the nodes are shown in Table 1 together with out-degree, in-degree, Hub score and Authority score for comparison. Recall that the out-degree of a node in a directed network is the number of outgoing arcs from the node and the in-degree of a node is the number of incoming arcs to the node. Authority and Hub scores were originally proposed as a method to find authoritative pages about a specific topic on the WWW together with hubs collecting such authoritative pages (Kleinberg 1999). The idea is that a page with a high Hub score has many links toward pages with a high authority score on one hand, a page with a high Authority score receives many links from pages with a high Hub score on the other hand. In this paper, we apply the HITS algorithm (Kleinberg 1999; Newman 2010) to calculate Authority and Hub scores of all the nodes in a given network.

Table 1 Centrality measures for the toy network in Fig. 5b

From Table 1, one can see that there is no monotone relation between IBC and Hub score or between OBC and Authority score. For example, OBC of node 8 is the highest OBC but its Authority score is not. Nodes 1 and 2 have the lowest IBC but their Hub scores are the second highest. This example quantitatively suggests that IBC and OBC measure importance of nodes that cannot be captured by Hub and Authority scores.

Florida Bay food web

In this subsection, we consider a food web of Florida Bay (Ulanowicz et al. 1998). It consists of 121 nodes and 1767 arcs. To focus on the prey-predator relation, we excluded the two detrital nodes and the node representing roots from the original data (Ulanowicz 2002) from the analysis. In Fig. 6a and b, IBC and OBC are plotted against out-degree and in-degree, respectively. One can find overall positive correlation. However, we can identify several nodes with significantly high IBC or OBC values by the following procedure: First, we prepared 1000 randomized networks with degree-preservation as a null model. Second, we calculated the p−value of b where b denotes IBC or OBC of a given node. It was calculated from its z−score if the distribution of b in the null model can be approximated by a normal distribution. We tested this by the Kolmogorov-Smirnov test. If the p−value of the KS test is greater than 0.10, then we adopted the normal approximation. Otherwise, the p−value of b is simply the proportion of the degree-preserving randomization trials in which b exceeds the value in the real-world network. Third, we applied the Benjamini-Hochberg-Yekutieli procedure for arbitrary dependency at level 0.05 for the multiple comparisons correction (Benjamini and Yekutieli 2001). This means that we keep the false discovery rate less than 0.05.

Fig. 6

Input betweenness centrality (IBC) a and Output betweenness centrality (OBC) b of each node in a food web of Florida bay are plotted against its out-degree and in-degree, respectively. The blue triangles are the average value over 1000 randomized networks with degree-preservation. The error bars represent the standard deviation. The red squares represent nodes whose IBC or OBC are judged to be significantly higher than those of the corresponding nodes in degree-preserving random networks by the procedure describe in the main text. The green points are the other non-significant nodes

In Fig. 7, IBC and OBC are plotted against Hub and Authority scores, respectively. We again found positive correlations. However, there are several nodes that are deviated from the line of the best linear fittings. They mostly overlap with those judged to be significant in Fig. 6.

Fig. 7

IBC a and OBC b of each node in the same food web as in Fig. 6 are plotted against Hub score and Authority score, respectively. The red squares represent nodes whose IBC or OBC are judged to be significantly high in Fig. 6. The green points are the other non-significant nodes. Dotted lines are the best linear fits. The coefficients of determination are indicated

The nodes that are judged to have significantly high IBC and OBC are listed in Tables 2 and 3, respectively. One noticing point is that 6 out of 7 phytoplankton taxa whose out-degree is relatively low appear in Table 2, but the other taxa of primary producers such as seagrasses that are important in the carbon cycle (Ulanowicz et al. 1998) do not have significantly high IBC. Another point is that Table 3 consists of mostly invertebrates and fishes that occupy intermediate level of the food chain. The taxa at the top of the food chain such as mammals, and some of reptiles and birds, namely, nodes with zero out-degree, do not have significantly high OBC. The table of centrality measures of all the nodes in the food web is available as an Additional file 1.

Table 2 Nodes with significantly high IBC in the Florida Bay food web. The values of out-degree and Hub score are also shown

Table 3 Nodes with significantly high OBC in the Florida Bay food web. The values of in-degree and Authority score are also shown

How can we interpret these results? In our previous work, we found that robustness of the largest connected components with respect to lateral paths for ten food webs is higher than that for randomized ones (Haruna 2013a). We suggested that the non-random structures of real-world food webs contribute to their robustness. Since nodes that have significantly high IBC or OBC are expected to lie at boundaries between LCAs that are destroyed by degree-preserving randomization, they could play a key role to enhance robustness of food webs as a collection of living processes joined via prey-predator interactions. In particular, we here identified phytoplankton as such nodes as input in the Florida Bay food web. This is unexpected in the literature (Ulanowicz et al. 1998) and cannot be derived by using out-degree or Hub score. Thus, IBC (resp. OBC) can be used as an exploratory tool to find important nodes as input (resp. output) that are overlooked by the conventional measures.

Conclusions

In this paper, we bridged two existing approaches to networks, categorical network theory and network science. The former regards networks as processes, on the other hand, the latter does networks as things. We internalized the idea that networks are processes into networks themselves: Nodes are processes rather than things. Based on the category theoretic representation of this viewpoint, we proposed betweenness centralities of nodes as input and output called IBC and OBC, respectively. We discussed their meaning through toy directed networks and demonstrated their use in real-world directed networks by calculating them for a food web. We also compared them with existing centrality measures that reflect asymmetry of links in directed networks. We found that IBC and OBC take quite different values from out- and in-degrees or Hub and Authority scores for some nodes.

In this paper, IBC and OBC are defined based on shortest lateral paths between arcs. Thus, contributions to betweenness from the other lateral paths are ignored. Their contributions can be included by considering random walks along lateral paths (Newman 2005), which is left as future work. Another future direction is an analytic study of the behavior of IBC and OBC in random networks generated by the configuration model as has been investigated in the case of the classical betweenness centrality (He et al. 2009; Guo et al. 2010). Finally, we only consider unweighted directed networks in this paper. Proposing a natural way to define analogues of IBC and OBC in weighted directed networks seems to be a non-trivial task. We hope that further development of the idea presented in this paper will open a new perspective in network science.