# pagerank_for_edges_axiomatic_characterization__7c4408e5.pdf

Page Rank for Edges: Axiomatic Characterization

Natalia Kucharczuk, Tomasz W as, Oskar Skibski

Institute of Informatics, University of Warsaw, Poland nk406686@students.mimuw.edu.pl, t.was@mimuw.edu.pl, o.skibski@mimuw.edu.pl

Edge centrality measures are functions that evaluate the importance of edges in a network. They can be used to assess the role of a backlink for the popularity of a website as well as the importance of a flight in virus spreading. Various node centralities have been translated to apply for edges, including Edge Betweenness, Eigenedge (edge version of Eigenvector centrality), and Edge Page Rank. With this paper, we initiate the discussion on the axiomatic properties of edge centrality measures. We do it by proposing an axiomatic characterization of Edge Page Rank. Our characterization is the first characterization of any edge centrality measure in the literature.

Introduction Centrality measures that evaluate the importance of nodes and edges in a network constitute one of the fundamental tools of network analysis (Brandes and Erlebach 2005; Jackson 2005). In complex networks that describe the surrounding world, they enable us to indicate the most significant genes (Özgür et al. 2008), key terrorists (Krebs 2002) and important pages in the World Wide Web (Page et al. 1999). Historically, centrality analysis was developed in social networks literature. Hence, the vast majority of work concentrates on nodes which represent people in such networks. However, in many types of networks, edges represent entities that we want to assess. In particular, edge evaluation may indicate which backlink to our website is the most profitable in Search Engine Optimization (Ledford 2015) or which flight should be canceled in order to delay virus spreading (Marcelino and Kaiser 2012). Edge centralities have also been used to identify edges that connect different communities in clustering algorithms (Newman 2004). Various node centralities have been translated to apply for edges, including Edge Betweenness (Girvan and Newman 2002), Eigenedge (edge version of Eigenvector centrality) (Huang and Huang 2019), and Edge Page Rank (Chapela et al. 2015). However, other measures not related to any node concepts have also been proposed in the literature, such as Spanning Edge Betweenness defined as the fraction of spanning trees that contain a specific edge (Teixeira et al. 2013). Multiplicity of centrality measures constitute a problem of its own, as it is becoming harder to choose one measure for a

Copyright c 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

specific application. In result, more than often a measure to use is selected based on its intuitive understanding or popularity rather than its suitability and desirable features. That is why, in recent years, efforts at organizing the space of centrality measures intensified (Schoch and Brandes 2015; Bloch, Jackson, and Tebaldi 2016). The axiomatic approach is one of the most convenient methods for this goal as it highlights similarities and differences between various concepts. In this approach, simple and desirable properties are identified that capture specific features of centrality measures. Choosing a carefully designed set of axioms allows to create a unique characterization of the measure that is more intuitive and easier to relate to the considered application. To date, plenty of node centrality measures have been axiomatized (Boldi and Vigna 2014). Notably, much research focused on feedback centralities (Altman and Tennenholtz 2005; Dequiedt and Zenou 2014), although distancebased centralities (Garg 2009) and game-theoretic centralities (Skibski et al. 2019) have also received considerable attention. However, to the best of our knowledge, so far no paper has considered edge centrality measures. With this paper, we initiate the discussion on the axiomatic properties of edge centrality measures. We do it by proposing an axiomatic characterization of Edge Page Rank. Edge Page Rank, analogically to standard Page Rank, can be defined as the unique solution to the system of recursive equations that ties centralities of incident edges. Our characterization is the first characterization of any edge centrality. We base our work on a recent characterization of (node) Page Rank (W as and Skibski 2020) and ask: is it possible to adapt such a characterization of the node centrality for the edge centrality measure? We answer positively to this question. Specifically, we define six axioms that correspond to axioms proposed for Page Rank and show that Edge Page Rank is the only measure that satisfies all of them. The main technical challenge comes from the fact that edge centrality measures consider pairs of nodes, which adds a new dimension to the complexity of the problem. In result, analyzing edge centralities cannot be reduced to the analysis of node centralities. We discuss this on the example of line graph approach. Moreover, this means that also the expressive power of axioms can vary. For these reasons, our proof is essentially different from the proof for (node) Page Rank.

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

Preliminaries In this paper, we consider directed multigraphs with node weights and possible self-loops. Since the emphasis of our work is on edges, not nodes, we need a model of a multigraph in which every edge is a separate entity. To this end, in our model each edge has its own label and an additional function specifies the start and the end of this edge. See Figure 1 for an illustration. In this way, we do not assume that all edges between the same pair of nodes are equally important which could lead to other undesirable (or unexpected) implications.1 Formally, we define a graph as a tuple G = (V, E, φ, b), where V is a set of nodes, E is a set of edges, φ : E V V is an incidence function mapping every edge to an ordered pair of nodes, and b : V R 0 is a node weight function. For an edge e E with φ(e) = (u, v), we denote the start u and the end v by φ1(e) and φ2(e), respectively. This edge is an outgoing edge for u and an incoming edge for v. For node v, the set of all incoming (outgoing) edges is denoted by E v (G) (E+ v (G)). The sizes of these sets are called in-degree and out-degree of node v, i.e., deg v (G) = |E v (G)| and deg+ v (G) = |E+ v (G)|. The set of all incident edges, both incoming and outgoing, is denoted by E v (G). Two nodes u and v are called out-twins if there exists a bijection ψ : E+ u (G) E+ v (G) such that φ2(e) = φ2(ψ(e)) for every e E+ u (G). A node v is a sink if it has no outgoing edges: E+ v (G) = . If it does not have incoming edges as well, i.e., E v (G) = , then it is an isolated node. If v has no incoming, but one outgoing edge, i.e., E v (G) = {e}, then this edge is called a source edge. If a source edge e is the only edge incident to its end, i.e., φ(e) = (v, u) and E u (G) = {e}, then we say it is an isolated edge. A path from u to v is a sequence of edges e1, . . . , ek such that φ1(e1) = u, φ2(ek) = v and φ2(ei) = φ1(ei+1) for every i {1, . . . , k 1}. If there exists a path from u to v, then v is called a successor of u. The set of all successors of u is denoted by Su(G). Consider an arbitrary function f : A X. We will use the following shorthand function notation. For a A and x X we denote by f[a x] the function obtained by replacing the value of a with x:

f[a x](c) = x if a = c, f(c) otherwise.

Also, for B A, we denote the function f restricted to B by f|B : B X. For a second function f : A X with A A = , we define function (f + f ) : A A X as follows: (f + f )(c) = f(c) for c A and (f + f )(c) = f (c) for c A . The sum of two disjoint graphs G = (V, E, φ, b) and G = (V , E , φ , b ) with V V = and E E = is defined as G + G = (V V , E E , φ + φ , b + b ).

1To give an example, if we consider unlabeled edges and know that changing the end of edge e5 from v2 to v1 in the graph from Figure 1 does not affect centrality of any edge, then we get that edges e4, e5, and e6 all have equal centralities.

Figure 1: An example graph G = (V, E, φ, b) with nodes v1, . . . , v4 and edges e1, . . . , e8. The incident function, φ, specifies the start and the end of each edge, e.g., φ(e5) = φ(e6) = (v3, v2). We assume uniform node weights, i.e., b(vi) = 1 for every vi V .

When graph G = (V, E, φ, b) is known from the context, we will simply write e : (u, v) E by which we understand e E s.t. φ(e) = (u, v) . Also, to denote small graphs we will write: G = ({v1, . . . , vn}, {e1 : c1, . . . , em : cm}, [b1, . . . , bn]) which means G = ({v1, . . . , vn}, {e1, . . . , em}, φ, b) such that φ(ei) = ci for every i {1, . . . , m} and b(vj) = bj for every j = {1, . . . , n}. For a graph G = (V, E, φ, b) and nodes u, v V , a graph obtained from redirecting node u into node v is denoted by Ru v(G) and defined as follows: Ru v(G) = (V \ {u}, E \ E+ u (G), φ , b ), where b = (b[v b(u) + b(v)])|V \{u} and φ (e) = (w, v) if φ(e) = (w, u) and φ (e) = φ(e) otherwise.

Edge Page Rank An (edge) centrality measure F is a function that assesses the importance of an edge e in a graph G; this value is denoted by Fe(G) and is non-negative. Edge Page Rank (Chapela et al. 2015) is defined as a unique centrality measure that for every graph G = (V, E, φ, b) and edge e:(u, v) E satisfies recursive equation

PRa e(G) = 1 deg+ u (G)

e E u (G) PRa e (G) + b(u)

(1) where constant a [0, 1) is a decay factor, i.e., a parameter of Edge Page Rank. Equivalently, we can define Edge Page Rank using random walks on a graph. To this end, imagine a surfer that travels throughout a graph in a schematic manner. She starts her walk from a random node (with the probability that the surfer starts in a node proportional to the weight of this node). Then, in each step, she makes two choices: first, she chooses one of the outgoing edges of a node she currently occupies, uniformly at random, and follows it to the next node; second, she decides whether she wants to continue the walk (with probability a) or end it (with probability 1 a). If the surfer ever arrives at a sink, she ends her walk automatically. Now, in such a walk, Page Rank of an edge is the expected number of times the surfer traversed this edge, multiplied by the sum of node weights in the graph. We note that

this model is a slight variation on a standard random walk model used for interpretation of Page Rank. The only difference between our model and the model presented in (W as and Skibski 2020) is the order of the decisions made by the surfer: there, she first decides whether she continues the walk and only if so, she chooses an outgoing edge. In result, the expected number of traverses over an edge is multiplied by a in comparison to our model. Additionally, the definition of Edge Page Rank can be also based on its relation with (node) Page Rank. Specifically, for every graph, G = (V, E, φ, b), and edge, e : (u, v) E, it holds that

PRa e(G) = PRa u(G)/ deg+ u (G),

where PRa u(G) is Page Rank of node u in graph G. This relation is true for multigraphs, which we consider in this paper. If, instead, we considered graphs with edge weights, ω : E R>0, then the relation would be

PRa e(G) = ω(e) P

e E+ u ω(e ) PRa u(G).

Finally, Edge Page Rank can be also defined as a (node) Page Rank of the corresponding line graph. We will discuss this in details later in the text.

Example 1. An example application for Edge Page Rank is to create a ranking of the hyperlinks pointing toward a webpage in the order of their importance for the Internet traffic (Criado et al. 2018). Often, the obtained ranking does not coincide with the Page Rank ranking of the webpages they are coming from. To see why, let us consider Edge Page Rank of incoming edges of node v4 in graph G from Figure 1. Each of them comes from a different node: e2 from v1, e3 from v2, and e7 from v3. Among these nodes, the greatest Page Rank has v3, followed by v1, and then v2. However, e3 is the only outgoing edge of node v2, whereas both v3 and v1 have multiple outgoing edges. In result, Edge Page Rank of edge e3 is greater than that of e2 and e7, making it the most important incoming edge of v4. Page Rank values of nodes and edges considered in this example for a = 0.9 are presented in the following table:

node v PR0.9 v (G, b) v1 7.09 v2 6.80 v3 12.89

edge e φ(e) PR0.9 e (G, b) e2 (v1, v4) 3.55 e3 (v2, v4) 6.80 e7 (v3, v4) 3.22

In this section, we propose our axioms that are based on the axioms for (node) Page Rank introduced in (W as and Skibski 2020). While some of our axioms are straightforward adaptations of the original axioms, some required significant modifications in order to work for an edge centrality. What is important, is that these six adapted axioms now uniquely characterize Edge Page Rank (what we prove in Theorem 1).

The axioms are as follows: Node Deletion: For every graph G = (V, E, φ, b) and isolated node u V it holds that

Fe(V \ {u}, E, φ, b|V \{u}) = Fe(G)

for every e E. Edge Deletion: For every graph G = (V, E, φ, b) and edge e :(u, v) E it holds that

Fe(V, E \ {e }, φ|E\{e }, b) = Fe(G)

for every e:(w, w ) E such that w Su(G) {u}. Edge Multiplication: For every graph G = (V, E, φ, b) and edge e :(u, v) E such that E+ u (G) E v (G) let E = E \ E+ u (G) {e }. Then, it holds that

Fe(V, E , φ|E , b) = deg+ u (G) Fe (G) if e = e , Fe(G) otherwise,

for every e E . Edge Swap: For every graph G = (V, E, φ, b) and edges e1:(u1, v1), e2:(u2, v2) E such that Fe1(G) = Fe2(G) it holds that

Fe(V, E, φ[e1 (u1, v2), e2 (u2, v1)], b) = Fe(G)

for every e E. Node Redirect: For every graph G = (V, E, φ, b) and out-twins u, w V with the bijection ψ it holds that

Fe(Ru w(G)) = Fe(G) + Fψ(e)(G) if e E+ w(G), Fe(G) otherwise,

for every e E \ E+ u (G). Baseline: For every graph G = (V, E, φ, b) and isolated edge e:(u, v) E it holds that Fe(G) = b(u). These six axiom uniquely characterize Edge Page Rank. Theorem 1. Edge centrality measure F satisfies Node Deletion, Edge Deletion, Edge Multiplication, Edge Swap, Node Redirect, and Baseline, if and only if, it is Edge Page Rank. Our first two axioms describe when the centrality of an edge is not affected by a removal of an element of a graph, a node or an edge. More in detail, Node Deletion states that removing an isolated node does not affect the centrality of any edge. In turn, Edge Deletion says that removing an edge does not affect the centralities of edges that cannot be reached from the start of the removed edge. Both axioms capture the intuition that the importance of an edge should not be affected by the parts of a network from which it is disconnected. They are direct adaptations of the axioms proposed in (W as and Skibski 2020), only there, the axioms state that the centralities of respective nodes are not affected. The next axiom, Edge Multiplication, has been more significantly modified. The original Edge Multiplication is focused on a node it states that creating additional copies of all outgoing edges of a node does not affect the centralities of any node in a graph. Here, we modify the axiom so that it focuses on an edge instead. We say that if an edge is the only outgoing edge of a node, then creating k 1 additional

copies of this edge, divides its centrality by k and does not affect the centrality of other edges. For the sake of notational convenience, in the formulation of the axiom we consider removing these additional copies of an edge, but the meaning is equivalent. Intuitively, the axiom means that for a centrality measure the absolute number of edges is not important.

Our next axiom is Edge Swap. Here, again, the axiom is quite different from the one introduced for (node) Page Rank. In its original wording, Edge Swap considers swapping the ends of outgoing edges of two nodes with equal out-degrees and equal centralities. Thus, this condition could not be included in our axiom since the centrality of a node is not defined. To solve this issue, we require only that the swapped edges have equal centrality. In this way, we obtain a simpler axiom: if two edges have equal centralities, swapping their ends does not affect the centrality of any edge. It captures the key property of feedback centralities: that your importance depends only on the importance of your incoming edges.

Intuitively, our next axiom, Node Redirect, says that two nodes that are identical (with regards to outgoing edges) can be redirected to each other without affecting the centralities in a network. It entails the same intuition as Node Redirect in (W as and Skibski 2020), but the construction is a little more subtle. The original axiom considered redirecting a node into its out-twin and stated that this operation sums up the centralities of the out-twins and does not affect the centralities of other nodes. Here, we say that since there is a one-to-one correspondence between the outgoing edges of out-twins, their redirection should sum up the centralities of corresponding edges. Also, the centralities of other edges in a graph should not be affected.

Finally, the original Baseline axiom stated that centrality of an isolated node is equal to its weight. The intuition behind it was that an isolated node is not influenced by the topology of a graph, so its centrality should be equal to its base importance that is reflected in its weight. Hence, in our version of Baseline we consider an isolated edge and say that its centrality is equal to the weight of its start.

We conclude this section with an example that shows how our axiomatization can be used to decide whether Edge Page Rank should be used in a particular application.

Example 2. Consider a network of flight connections between airports, in which an edge from airport A to airport B represents a single flight from A to B. We can think about the importance of each connection on the global virus spread, as considered by Marcelino and Kaiser (2012). Imagine that there is an airport, A, from which there are flights to only one other airport, B. In such a case, Edge Multiplication implies that the change in the number of flights from A to B does not affect the importance of any edge. However, additional flights from A to B increase the chance of virus spread from A to B, which in turn makes it more probable that flights outgoing from B would spread the virus. Therefore, Edge Multiplication is not an adequate axiom in such a setting. This implies that since Edge Page Rank satisfies Edge Multiplication, it should not be used in this application.

Proof of Uniqueness In this section, we sketch the proof of our main result that Edge Page Rank is uniquely characterized by our axioms (Theorem 1). The full proof can be found in the extended version of the paper.2 We begin by noting that Edge Page Rank indeed satisfies all six axioms. Lemma 2. Edge Page Rank satisfies Node Deletion, Edge Deletion, Edge Multiplication, Edge Swap, Node Redirect, and Baseline. We skip the proof of Lemma 2 and instead focus on proving that an arbitrary centrality measure F satisfying our axioms is indeed Edge Page Rank. To this end, we adopt the following structure of the proof:

First, we prove simple properties of F (Proposition 3). Specifically, we show that the centrality of an edge depends only on its connected component (Locality), does not depend on weights of sinks (Sink Weight), and if the edge is a source edge, then it is equal to the weight of its start (Source Edge). Then, we analyze simple graphs in which all edges are incident to one node, v. We begin with graphs in which v has one incoming edge (from u) and one outgoing edge (to w). First, we show that there exists a constant a F such that the centrality of the outgoing edge of v equals a F times b(u) plus b(v) (Lemma 4). Then, we prove that a F [0, 1) (Lemma 5). Furthermore, we consider graphs in which node v has k outgoing and zero (Lemma 6) or one (Lemma 7) incoming edges. Finally, we prove that for arbitrary graph, F is equal to Edge Page Rank with the decay factor a F (Lemma 8).

We note that there are significant differences between our proof and the proof of unique characterization of (node) Page Rank introduced in (W as and Skibski 2020). More in detail, the main axis of the proof for (node) Page Rank is the induction on the number of cycles in a graph. Here, we follow a different path and prove that centrality F satisfying all our axioms satisfies also Page Rank recursive equation (Equation (1)). Since this equation uniquely defines Page Rank, this implies that F is indeed Page Rank. In effect, the proof obtained in this paper is notable simpler. We begin with a proposition that captures simple properties of an edge centrality measure implied by our axioms. Proposition 3. If edge centrality measure F satisfies Node Deletion, Edge Deletion, Node Redirect, and Baseline, then for every graph G = (V, E, φ, b) and e E it holds that (a) (Locality) Fe(G) = Fe(G + G ) for every G disjoint with G, (b) (Sink Weight) Fe(G) = Fe(V, E, φ, b[w 0]) for every sink w V , (c) (Source Edge) Fe(G) = b(u) if e:(u, v) E is a source edge

2https://arxiv.org/pdf/2112.04339.pdf

Figure 2: An illustration to the proof of Lemma 4.

Proof (Sketch). Node Deletion and Edge Deletion imply (a). (b) follows from (a) and Node Redirect. Finally, Edge Deletion and Baseline yield (c).

In the following lemma, we introduce constant a F that, as we will prove later on, is decay factor of the Edge Page Rank to which F is equal to.

Lemma 4. If edge centrality measure F satisfies Node Deletion, Edge Deletion, Node Redirect, and Baseline, then there exists a constant, a F R, such that for every graph G=({u, v, w}, {e1:(u, v), e2:(v, w)}, [x, y, 0]) it holds that

Fe1(G) = x and Fe2(G) = a F x + y.

Proof (Sketch). First equation follows directly from Source Edge (Proposition 3c). Thus, we will focus on proving that Fe2(G) = a F x+y. First, assume y = 0 and consider graph G = ({u , v , w },{e 1:(u , v ), e 2:(v , w )},[x , 0, 0]) such that u , v , w {u, v, w} (see Figure 2). By Locality (Proposition 3a), we know that in G + G the centrality of all edges is the same as in G or G . In graph G + G , we sequentially redirect nodes w , v , u into w, v, u respectively, to obtain graph G = ({u,v,w},{e1:(u, v), e2:(v, w)},[x + x , 0, 0]), which is exactly G, but with different weight of node u. Since each time we redirected a node into its out-twin, from Node Redirect, we get that Fe2(G ) = Fe2(G) + Fe 2(G ). From this and the arbitrariness of the choice of nodes and edges, we conclude that there is a function, f : R 0 R 0, such that Fe2(G) = f(x) and that f is additive. Since it is also non-negative, we get f(x) = a F x (Cauchy 1821). Now, if y is not necessarily 0, then we consider graph G =({u,v,v ,w},{e1:(u,v), e2:(v,w), e3:(v ,w)},[x, 0, y, 0]) (see Figure 2). Node v is not a successor of v , hence from Edge Deletion, Node Deletion, and the first part of the proof, we get that Fe2(G ) = a F x. Also, Fe3(G ) = y from Source Edge (Proposition 3c). Thus, since redirecting v into v in G results in G, Node Redirect yields the thesis.

Additionally, we can show the bounds for constant a F (the proof is omitted due to space constraints).

Lemma 5. If edge centrality measure F satisfies Node Deletion, Edge Deletion, Edge Swap, Node Redirect, and Baseline, then a F [0, 1).

In Lemmas 6 and 7 we consider graphs in which v has multiple outgoing edges. First, we assume that it does not have any incoming edge.

Lemma 6. If edge centrality measure F satisfies Node Deletion, Edge Deletion, Edge Multiplication, Node Redirect, and Baseline, then for every k N and graph G =

Figure 3: An illustration to the proof of Lemma 6 for k = 3.

({v, w1, . . . , wk},{e1:(v, w1), . . . , ek:(v, wk)},[x, 0, . . . , 0]), it holds that

Fei(G) = x/k for every i {1, . . . , k}.

Proof. Let us fix arbitrary i {1, . . . , k}. Since nodes w1, . . . , wk are all sinks, they are also out-twins. Hence, from Node Redirect, we know that sequentially redirecting nodes w2, . . . , wk into node w1 preserves the centrality of edges e1, . . . , ek. Therefore, in the obtained graph, G = ({v, w1},{e1:(v, w1), . . . , ek:(v, w1)},[x, 0]), we have Fei(G) = Fei(G ). See Figure 3 for an illustration. Next, consider graph Gi = ({v, w1},{ei :(v, w1)},[x, 0]). Observe that Gi can be obtained from G by removing all edges but ei. Thus, from Edge Multiplication, we get Fei(G ) = Fei(Gi)/k. On the other hand, from Baseline, Fei(Gi) = x. Combining all equations, we obtain that Fei(G) = Fei(G ) = Fei(Gi)/k = x/k.

Now, we assume that v has exactly one incoming edge and multiple outgoing edges.

Lemma 7. If edge centrality measure F satisfies Node Deletion, Edge Deletion, Edge Multiplication, Node Redirect, and Baseline, then for every k N and graph

G = ({u, v, w1, . . . wk}, {e:(u, v), e1 :(v, w1), . . . , ek :(v, wk)}, [x, y, 0, . . . , 0]),

it holds that Fe(G) = x and Fei(G) = (a F x + y)/k for every i {1, . . . , k}.

Proof (Sketch). The proof is analogous to the proof of Lemma 6 with only two differences: first, in every graph node v has one incoming edge from u; second, the final equation for graphs Gi is of the form Fei(Gi) = a F x + y, which is implied by Lemma 4.

We are now ready for the final lemma of this section.

Lemma 8. If edge centrality measure F satisfies Node Deletion, Edge Deletion, Edge Multiplication, Edge Swap, Node Redirect, and Baseline, then F is Edge Page Rank.

Proof (Sketch). We will prove that F satisfies Edge Page Rank recursive equation (Equation (1)) with decay factor a F for every graph G = (V, E, φ, b) and edge e : (v, w) E. Since this equation uniquely define Edge Page Rank, it will imply that F is indeed Edge Page Rank. First assume that v does not have incoming edges. Then, removing all edges not incident with v and nodes that become isolated in doing so, we obtain a graph from

Figure 4: The scheme of the proof of Lemma 8 for an example graph, G, with m = 2.

Lemma 6 except possibly non-zero weights of sinks. Hence, from Edge Deletion, Node Deletion, Sink Weight (Proposition 3b), and Lemma 6, we get Fe(G) = b(v)/ deg+ v (G), which is Equation (1) for edge e in graph G. Thus, let us assume that v has m > 0 incoming edges, i.e., E v (G) = {e1, . . . , em}. We denote their centralities by xi = Fei(G) for every i {1, . . . , m}. In what follows, through several operations we transform graph G into graph from Lemma 7 such that the centrality of e is unchanged. To this end, for every i {1, . . . , m}, we add to G a simple one-edge graph Gi = ({ui, vi}, {e i : (ui, vi)}, [xi, 0]) (see Figure 4). In the obtained sum of graphs, for every i {1, . . . , m}, edges ei and e i have equal centralities (from Locality (Proposition 3a) and Baseline). Thus, if we exchange their ends, then by Edge Swap we won t affect the centrality of any edge. Exchanging ends sequentially for all such pairs, we obtain graph G in which incoming edges of v, i.e., E v (G ) = {e 1, . . . , e m}, are all source edges. Now, observe that in graph G , nodes u1, . . . , um are outtwins (each has one outgoing edge to v). Thus, from Node Redirect we can sequentially redirect nodes u2, . . . , um into u1 without affecting the centrality of e. Let us denote resulting graph by G . Observe that the weight of node u1 in graph G is equal to Pm i=1 xi. Also, node v has one incoming edge, e 1, that is a source edge. Removing all edges not incident with v and nodes that become isolated in doing so, we obtain graph from Lemma 7 but with possibly non-zero weights of sinks. Thus, from Edge Deletion, Node Deletion, Sink Weight (Proposition 3b), and Lemma 7 we get that

Fe(G ) = 1 deg+ v (G )

i=1 xi + b(v)

Since Pm i=1 xi = P

ei E v (G) Fei(G), Fe(G ) = Fe(G), and deg+ v (G ) = deg+ v (G), Equation (1) holds.

Comparison with Other Edge Centralities

In this section, we provide an overview of edge centrality measures from the literature and analyze which of our axioms they satisfy. Some of these measures are defined only for a specific class of graphs, e.g., strongly connected graphs. In such case, we consider our axioms restricted to this class, i.e., we add an additional constraint that in all graphs considered in the axiom the centrality is well defined. Eigenedge (Huang and Huang 2019) assumes that the centrality of an edge is proportional to the sum of the central-

ities of the edges incoming to its start. Formally, it is defined as a measure that for every strongly connected graph G = (V, E, φ, b) and edge e:(u, v) E satisfies

Eige(G) = 1

e E u (G) Eige (G),

where λ is the largest eigenvalue of the adjacency matrix of G. Usually, a normalization condition is added to make the solution unique, e.g., that the sum of all centralities is equal to 1. With this condition, Eigenedge is well defined for all strongly connected graphs and satisfies all our axioms restricted to this class except for Edge Multiplication. Edge Katz centrality can be derived from (node) Katz centrality (Katz 1953) in the same way as Eigenedge is derived from Eigenvector centrality (Bonacich 1972), and Edge Page Rank from (node) Page Rank. It works similarly to Eigenedge, but to every edge we add a base centrality equal to the weight of its start. Formally, for a decay factor a R 0 it is defined as a unique measure that for every graph G = (V, E, φ, b) with λ < 1/a and edge e:(u, v) E satisfies

Ka e (G) = a X

e E u (G) Ka e (G) + b(u).

Katz centrality satisfies all our axioms restricted to the class of graphs with λ < 1/a except for Edge Multiplication. In the same way, Edge Seeley index can be derived from (node) Seeley index (Seeley 1949) (known also as Katz Prestige or simplified Page Rank). It can be seen as a borderline case of Page Rank, when we increase decay factor a to 1 (W as and Skibski 2021). Formally, it is defined as the measure that for every strongly connected graph G = (V, E, φ, b) and edge e:(u, v) E satisfies

SIe(G) = 1 deg+ u (G)

e E u (G) SIe (G).

Like for Eigenedge, to obtain uniqueness, we add a normalization condition that the sum of centralities is equal to 1. Then, Seeley index satisfies all of our axioms restricted to the class of strongly connected graphs (since axioms are restricted, this does not contradict Theorem 1). Edge Betweenness (Girvan and Newman 2002) measures how often an edge is on a shortest path between two nodes. For graph G = (V, E, φ, b) and edge e E it is defined as

s,t V,s =t,t Ss(G)

where δs,t is the number of shortest paths from s to t and δs,t(e) is the number of such paths passing through e. Edge Betweenness satisfies only Node Deletion. Information centrality (Fortunato, Latora, and Marchiori 2004) is defined as the relative loss in the network efficiency that results from removing an edge. Formally, for every graph G = (V, E, φ, b) and edge e E we have

Ie(G)= Eff(G) Eff(V, E \ {e}, φ|E\{e}, b) /Eff(G),

where Eff(G) = P v,w V,v =w 1/distv,w(G). It is well defined for strongly connected graphs and satisfies Node Deletion, Edge Deletion, and Baseline restricted to this class. GTOM (Generalized Topological Overlap Matrix) (Yip and Horvath 2007) of an edge measures how many common direct successors have its start and its end. Formally, for G = (V, E, φ, b) and edge e:(u, v) E it is defined as

GTOMe(G) = |{w:(u,w), (v,w) E}| + 1 min |{w:(u,w) E}|, |{w:(v,w) E}| .

It satisfies only Node Deletion. We do not consider Spanning Edge Betweenness (Teixeira et al. 2013) as it is defined only on undirected graphs.

Using Line Graphs in Axiomatization Many edge centrality measures, including Edge Page Rank, can be equivalently defined as node centralities in line graphs. In this section, we analyze whether this fact can be used in creating axiomatization of an edge centrality based on the axiomatization of a node centrality. For a graph G, the line graph L(G) is a graph that represents adjacencies between edges of G. Specifically, nodes of the line graph are edges of G and edges of the line graph connect nodes that represent edges incident in G. Formally, for graph G = (V, E, φ, b), its line graph is defined as

L(G) = (E, {(ei, ej) : φ2(ei) = φ1(ej)}, b ),

with b (e) = b(u)/ deg+ u (G) for every e : (u, v) E. See Figure 5 for an illustration. Chapela et al. (2015) proved that Edge Page Rank is equivalent to Page Rank of the corresponding line graph: PRa e(L(G)) = PRa e(G) for every graph G and edge e. This result suggests that an axiomatization can be obtained by using node centrality axioms on line graphs. Observe that most axioms proposed for (node) Page Rank are so-called invariance axioms: they specify graph operations that do not change centralities of nodes. For example, Edge Swap states that the ends of edges from equally important nodes with equal out-degrees can be swapped. Can we just use these axioms to uniquely characterize (node) Page Rank on line graphs which corresponds to Edge Page Rank? As it turns out, it is not possible. The first reason is the fact that line graphs are not closed under some of the invariance operations. To see that, consider graph G from Figure 5. Since graph L(G) is symmetrical, by Edge Swap, we can swap the ends of edges (e2, e6) and (e3, e7). However, we can prove that the graph obtained in this way is no longer a line graph of any graph. Assume that it is the line graph of

e1 e2 e3 e4

e5 e6 e7 e8

e1 e2 e3 e4

e5 e6 e7 e8

Figure 5: Graph G (on the left-hand side) and its line-graph L(G) (on the right-hand side). Dashed edges represent the effect of the edge swap operation.

some G = (V , E , φ , b ). Since after edge swap, e1 and e3 have edges to e6, it means that φ 2(e1) = φ 1(e6) = φ 2(e3). Similarly, we get that φ 2(e3) = φ 1(e8) = φ 2(e4). Thus, we get φ 2(e1) = φ 2(e4). However, this implies that in the line graph there are edges (e4, e6) and (e1, e8), none of which is present in our graph a contradiction. Finally, we note that not every edge centrality can be defined as a node centrality of a line graph. To see that, observe that merging starts of edges e1 and e4 in graph G from Figure 5 does not affect the line graph. However, for some edge centralities, e.g., Edge Betweenness, centrality of e4 changes after such merge. That is why analyzing edge centralities cannot be reduced to the analysis of node centralities in line graphs.

Related Work

Axiomatic characterizations have been proposed for many node centrality measures (Garg 2009; Skibski et al. 2019), including both simplified Page Rank (Altman and Tennenholtz 2005; Palacios-Huerta and Volij 2004), and Page Rank in its general form (W as and Skibski 2020). However, to the best of our knowledge, there are no axiomatic characterizations of edge centrality measures in the literature to date. Several papers studied properties of Edge Page Rank. Chapela et al. (2015) proved that Page Rank of an edge is equal to Page Rank of the corresponding node in the line graph. Kim, Son, and Jeong (2010) showed how Edge Page Rank (under the name Link Rank) can be used in community detection. A similar, but different, edge metric derived from Page Rank was used by Chung and Zhao (2010) in their graph sparsification algorithm.

Conclusions

In this paper, we proposed the first axiomatic characterization of an edge centrality measure in the literature. Specifically, we proved that Edge Page Rank is a unique centrality measure that satisfies six axioms: Node Deletion, Edge Deletion, Edge Multiplication, Edge Swap, Node Redirect, and Baseline. Our paper initiates the research on axiomatic properties of edge centrality measures, many of which deserve their own characterizations. An extension of our work into another direction would be to axiomatically analyze node similarity measures, e.g., Sim Rank.

Acknowledgments Natalia Kucharczuk was supported by the Ministry of Science and Higher Education project Szkola Orlow, project number 500-D110-06-0465160. This work was also supported by the Polish National Science Center grant 2018/31/B/ST6/03201.

References Altman, A.; and Tennenholtz, M. 2005. Ranking systems: the Page Rank axioms. In Proceedings of the 6th ACM Conference on Electronic Commerce (ACM-EC), 1 8. Bloch, F.; Jackson, M. O.; and Tebaldi, P. 2016. Centrality Measures in Networks. ar Xiv preprint ar Xiv:1608.05845. Boldi, P.; and Vigna, S. 2014. Axioms for centrality. Internet Mathematics, 10(3-4): 222 262. Bonacich, P. 1972. Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology, 2(1): 113 120. Brandes, U.; and Erlebach, T. 2005. Network analysis: Methodological foundations. Springer-Verlag. ISBN 3540249796. Cauchy, A. L. B. 1821. Cours d analyse de l École Royale Polytechnique: Analyse algébrique. Pte. 1. Imprimerie royale. Chapela, V.; Criado, R.; Moral, S.; and Romance, M. 2015. Intentional risk management through complex networks analysis. Springer. Chung, F.; and Zhao, W. 2010. A sharp Page Rank algorithm with applications to edge ranking and graph sparsification. In International Workshop on Algorithms and Models for the Web-Graph, 2 14. Springer.

Criado, R.; Moral, S.; Pérez, Á.; and Romance, M. 2018. On the edgesâ A Z Page Rank and line graphs. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28(7): 075503. Dequiedt, V.; and Zenou, Y. 2014. Local and consistent centrality measures in networks. CEPR Discussion Paper No. DP10031. Fortunato, S.; Latora, V.; and Marchiori, M. 2004. Method to find community structures based on information centrality. Physical Review E, 70(5): 056104. Garg, M. 2009. Axiomatic foundations of centrality in networks. Available at SSRN 1372441. Girvan, M.; and Newman, M. E. 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12): 7821 7826. Huang, X.; and Huang, W. 2019. Eigenedge: A measure of edge centrality for big graph exploration. Journal of Computer Languages, 55: 100925. Jackson, M. O. 2005. A survey of network formation models: stability and efficiency. In Group Formation in Economics: Networks, Clubs, and Coalitions, 11 49. Cambridge University Press: Cambridge, MA, USA. Katz, L. 1953. A new status index derived from sociometric analysis. Psychometrika, 18(1): 39 43.

Kim, Y.; Son, S.-W.; and Jeong, H. 2010. Finding communities in directed networks. Physical Review E, 81(1): 016103. Krebs, V. E. 2002. Mapping networks of terrorist cells. Connections, 24: 43 52. Ledford, J. L. 2015. Search engine optimization bible, volume 584. John Wiley & Sons. Marcelino, J.; and Kaiser, M. 2012. Critical paths in a metapopulation model of H1N1: efficiently delaying influenza spreading through flight cancellation. PLo S Currents, 4. Newman, M. E. 2004. Detecting community structure in networks. The European physical journal B, 38(2): 321 330. Özgür, A.; Vu, T.; Erkan, G.; and Radev, D. R. 2008. Identifying gene-disease associations using centrality on a literature mined gene-interaction network. Bioinformatics, 24(13): i277 i285. Page, L.; Brin, S.; Motwani, R.; and Winograd, T. 1999. The Page Rank citation ranking: bringing order to the web. Technical report, Stanford Info Lab. Palacios-Huerta, I.; and Volij, O. 2004. The measurement of intellectual influence. Econometrica, 72(3): 963 977. Schoch, D.; and Brandes, U. 2015. Stars, neighborhood inclusion, and network centrality. In SIAM Workshop on Network Science. Seeley, J. R. 1949. The net of reciprocal influence. a problem in treating sociometric data. Canadian Journal of Experimental Psychology, 3: 234. Skibski, O.; Rahwan, T.; Michalak, T. P.; and Yokoo, M. 2019. Attachment centrality: Measure for connectivity in networks. Artificial Intelligence, 274: 151 179. Teixeira, A. S.; Monteiro, P. T.; Carriço, J. A.; Ramirez, M.; and Francisco, A. P. 2013. Spanning edge betweenness. In Workshop on mining and learning with graphs, volume 24, 27 31. W as, T.; and Skibski, O. 2020. Axiomatic Characterization of Page Rank. ar Xiv preprint ar Xiv:2010.08487. W as, T.; and Skibski, O. 2021. An Axiom System for Feedback Centralities. In Zhou, Z.-H., ed., Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 443 449. International Joint Conferences on Artificial Intelligence Organization. Yip, A. M.; and Horvath, S. 2007. Gene network interconnectedness and the generalized topological overlap measure. BMC bioinformatics, 8(1): 1 14.