# attachment_centrality_for_weighted_graphs__0ef57a72.pdf

Attachment Centrality for Weighted Graphs

Jadwiga Sosnowska, Oskar Skibski University of Warsaw, Poland {j.sosnowska,o.skibski}@mimuw.edu.pl

Measuring how central nodes are in terms of connecting a network has recently received increasing attention in the literature. While a few dedicated centrality measures have been proposed, Skibski et al. [2016] showed that the Attachment Centrality is the only one that satisfies certain natural axioms desirable for connectivity. Unfortunately, the Attachment Centrality is defined only for unweighted graphs which makes this measure ill-fitted for various applications. For instance, covert networks are typically weighted, where the weights carry additional intelligence available about criminals or terrorists and the links between them. To analyse such settings, in this paper we extend the Attachment Centrality to node-weighted and edgeweighted graphs. By an axiomatic analysis, we show that the Attachment Centrality is closely related to the Degree Centrality in weighted graphs.

1 Introduction

Centrality analysis belongs to fundamental research problems in network analysis. Its aim is to quantify the importance of nodes in a network according to some criteria that typically depend on the application at hand [Brandes and Erlebach, 2005]. For instance, in the transportation network we may look for nodes which are closest on average to all other nodes in the network [Tarkowski et al., 2016] or which are positioned on most shortest paths between nodes [Derrible, 2012]. One particular such criterion that has recently attracted a lot of attention in the literature is connectivity. Intuitively, this means that we are interested in nodes that are essential to keeping the network together. At a first glance, it may seem that we should simply look for nodes with the highest degree, i.e., the number of incident edges. However, a need for more advanced measures of connectivity has been advocated in a number of different areas, spanning from evaluation of the importance of genes in gene interaction networks [Moretti et al., 2010] and assessing the impact of failure in monetary flows networks [Belau, 2014] to social network analysis [Narayanam et al., 2014] and the analysis of covert networks [Lindelauf et al., 2013].

Most centrality measures dedicated to connectivity were constructed in various contexts of particular applications. Unfortunately, such results are difficult to generalize especially given that they were evaluated solely based on experiments with some real-life and synthetic networks. Only recently, Skibski et al. [2016] took a more general, axiomatic approach and showed that there exists a unique centrality measure that satisfies some natural axioms that may be considered desirable for connectivity. This new centrality, called Attachment Centrality, is defined for unweighted graphs, i.e., graphs whose nodes and edges have not been assigned any weights and each two nodes or two edges are equally important. This assumption, however, does not hold in many applications [Bagler, 2008; Nepusz et al., 2012; Palla et al., 2007]. One example is covert network analysis a setting that has recently attracted considerable attention in the literature. In these networks, weights of nodes and edges may carry additional intelligence available about criminals or terrorists and the links between them. For instance, weights of edges are used to represent frequency of interaction [Koschade, 2006] while weights of nodes to represent individual evaluations of terrorists, based on known skills and prior activities [Lindelauf et al., 2013]. Unfortunately, neither is the Attachment Centrality in its current form able to incorporate such data nor is it clear how this centrality can be adapted to do so. Specifically, the axiomatization of the Attachment Centrality relies on Normalization. This axiom states both the minimum and maximum bounds on the values of centrality and specifies the values for the center of a star and for the isolated nodes. However, in weighted graphs, centrality is unbounded and the value of the center of a star is far from obvious. In this paper, we propose the first extension of the Attachment Centrality to nodeand edge-weighted graphs. We begin by developing a new axiomatization of the Attachment Centrality for unweighted graphs. It is built upon two new axioms One-Edge Normalization and Additivity and two already proposed in the literature: Balanced Contributions [Myerson, 1980]; and Gain-loss [Skibski et al., 2016]. Next, we extend this axiomatization to node-weighted graphs, and finally to nodeand edge-weighted graphs and propose the corresponding formulas for the Attachment Centrality. As a reference, we build this axiomatization in a close relation to the Degree Centrality [Freeman, 1979].

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

2 Preliminaries

This section provides the necessary background and notation.

Graph theory: A (undirected) graph is a tuple, (V, E, ω, ρ), where V is the set of nodes, E is the set of edges, and ω, ρ are weight functions (see below). Given V , the set of all possible graphs is denoted by GV . For G = (V, E, ω, ρ) and E E we use shorthand notations G + E (and G E ) to denote the graph obtained by adding E to E (removing E from E). An edge {v, u} E is said to be incident to nodes v and u, and u is said to be a neighbour of v. For node v V , the set of its neighbours is denoted by NG(v) and the set of its (incident) edges is denoted by ΓG(v). Formally: NG(v) = {u V : {v, u} E} and ΓG(v) = {{v, u} E : u V }. If a node, v, has no neighbours, i.e., NG(v) = ΓG(v) = , we say that v is isolated. If a node has exactly one neighbour, we call it a leaf. A path, p = (v1, . . . , vk), is a sequence of nodes in which there exists an edge between every two consecutive nodes, i.e., {vi, vi+1} E, i {1, . . . , k 1}. Nodes v, u V are said to be connected if there exists a path between them. A graph G is connected if every two nodes in it are connected. For any subset of nodes, S V , the subgraph with nodes in S and all edges that both ends belong to subset S is called the subgraph induced by S. Formally, G[S] = (S, E[S], ω, ρ) and E[S] = {{v, u} E : v, u S}. For a disconnected graph, G, we denote by K(G) the partition of V into disjoint sets of nodes, called connected components, that each induces a maximal connected subgraph in G. Finally, we denote by Kv(G) the connected component containing v in G. A forest is a graph without cycles, i.e., a graph such that there exists at most one path between every two nodes. A connected forest is called a tree. A star is a tree in which there exists a node, v, called the center of a star, that is connected by an edge with every other node: E = {{v, u}: u V \{v}}.

Graph weights: Function ω : V R+ is a node-weight function that assigns to every node in V its weight. Function ρ : E R+ is an edge-weight function that assigns to every edge in E its weight. A function that assigns 1 to every argument is denoted by 1. A graph is unweighted if ω = 1 and ρ = 1. Otherwise, if ω = 1 and ρ = 1, then graph is called a node-weighted graph. If ω = 1 and ρ = 1, a graph is called a nodeand edge-weighted graph. For a function, f : X R+, x X, and α R+ we write f α x to denote the function obtained by changing the value of x in f to α: f α x (x) = α and f α x (y) = f(y) for every y X \ {x}. Moreover, we use f x to denote the function obtained by removing argument x from the domain of f.

Cooperative games: A (cooperative) game is a pair (V, f), where V is the set of players and f : 2V R is the characteristic function. The characteristic function assigns to each subset of players, called a coalition, a real number, called the value of a coalition, where f( ) = 0. Typically, we will refer to the game simply by its characteristic function f. A value of a game, ϕ : (2V R) RV , is a function that assigns a payoff to each player v V . This payoff can be interpreted as the player s importance in the game. One of the most important such values was proposed by Shapley [1953b]. The

Shapley value of player v in game f, denoted by SVv(f), is defined as:

SVv(f) = 1 |V |!

f(Sπ v ) f(Sπ v \ {v}) ,

where Ω(V ) is the set of all permutations of V , i.e., bijections π : V {1, . . . , |V |}, and Sπ v = {u V : π(u) π(v)} is the set of players at the position of v or earlier in π. Importantly, the Shapley value satisfies Additivity (ϕ(f)+ϕ(f ) = ϕ(f + f )) and Efficiency (P v V ϕv(f) = f(V )). Myerson [1977] extended the Shapley value to the model in which the cooperation of players is restricted by a communication graph. The Myerson value for player v in game f, denoted by MVv(f, G), is defined as the Shapley value of the restricted game f/G: MVv(f, G) = SVv(f/G), where f/G(S) = P C K(G[S]) f(C) for every S V . Myerson proved that the Myerson value is the only value that satisfies Component Efficiency and Fairness. The former axiom states that for every connected component C the sum of values of nodes in C equals f(C). The later one requires that addition of an edge equally affects the two nodes connected by it. Later on, Myerson [1980] proposed Balanced Contributions (see Section 3) and proved that it implies Fairness.

Centrality measures: A centrality measure, F : GV RV , is a function that assigns to every node a number reflecting its importance. Thus, it plays the same role as a value of a game. The one of the most well-known centrality measures is the Degree Centrality. For an unweighted graph, the Degree Centrality rates every node taking into consideration only a number of its neighbours, i.e.: Dv(V, E, 1, 1) = |NG(v)|. For a weighted graph, the Degree Centrality extends to: WDv(V, E, ω, ρ) = P u NG(v) ρ({v, u}) ω(u). (1)

This definition follows [Opsahl et al., 2010; Heitzig et al., 2010]. We will refer to this centrality measure as the Weighted Degree Centrality. Skibski et al. [2016] proposed the Attachment Centrality as a dedicated measure of connectivity. Definition 1. The Attachment Centrality for an unweighted graph G = (V, E, 1, 1) is defined as follows: Av(G)=SVv(f G) where f G(S) = 2(|S| |K(G[S])|) for every S V . Alternatively, Av(G) = MV (f , G) for f (S) = 2(|S| 1) for every S V . Skibski et al. proved that Attachment Centrality is the unique centrality that satisfies Myerson s Fairness, Normalization, Locality, and Gain-loss. Normalization states that Fv(G) [0, |V | 1] and Fv(G) = 0, when v is isolated in G, and Fv(G) = |V | 1, when G is a star, the center of which is v. Locality states that the centrality of a node depends solely on the connected component the node belongs to (i.e., removing other components does not affect the centrality of a node). Gain-loss will be described later. Our goal in this paper is to extend Attachment Centrality to node-weighted and edge-weighted graphs. To this end, we first propose a new axiomatization of Attachment Centrality for unweighted graphs. Upon this result we will later on build an axiomatization of Attachment Centrality for weighted graphs.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

3 Unweighted Graphs In this section, we propose a new axiomatization of the Attachment Centrality that does not rely on Normalization. Our new axiomatization involves Balanced Contributions by Myerson [1980], Gain-loss by Skibski et al. [2016] and two new axioms Additivity and One-Edge Normalization. We follow the idea of Skibski et al. and build an axiomatization in a close relation to the Degree Centrality. In fact, all above axioms except Gain-loss are satisfied by the Degree Centrality, and we prove that adding Star-Max and Monotonicity leads to an axiomatization of the Degree Centrality. We begin by introducing two new axioms. Firstly, we replace Normalization with much simpler axiom, called One-Edge Normalization. More in detail, One-Edge Normalization states that if there is only one edge in the graph, then both adjacent nodes have centralities equal to one.

One-Edge Normalization: For every v, u V , Fv(V, {{v, u}}, 1, 1) = 1.

Our second axiom, Additivity, states that the centrality of a node that connects disjoint parts of the graph is simply the sum of its centralities computed for each part separately.

Additivity: For every unweighted graph G=(V, E, 1, 1), node v V and sets S, T V such that S T = {v}, Fv(V,E[S],1,1)+Fv(V,E[T],1,1)=Fv(V,E[S] E[T],1,1).

The third axiom, Balanced Contributions [Myerson, 1980], states that removing edges of v affects the centrality of u in the same way as removing edges of u affects the centrality of v.

Balanced Contributions: For every unweighted graph G = (V, E, 1, 1) and every two nodes v, u V , Fv(G) Fv(G ΓG(u)) = Fu(G) Fu(G ΓG(v)).

Finally, we present Gain-loss, first proposed by Skibski et al. [2016]. It states that the sum of centralities of a graph does not change when we add or remove edges, as far as the set of connected components stays the same.1

Gain-loss: For every unweighted graph G=(V, E, 1, 1) and v, u C K(G), P w V Fw(G) = P w V Fw(G + {{v, u}}).

We will use Gain-loss to axiomatize the Attachment Centrality. For comparison, let us also axiomatize the Degree Centrality. Here, we will use Monotonicity and Star-Max. Monotonicity was proposed by Skibski et al. and states that adding an edge does not decrease the centrality of any node.

Monotonicity: For every unweighted graph G = (V, E, 1, 1) and v, u, w V , Fv(G) Fv(G + {{u, w}}). The last axiom, Star-Max, inspired by Normalization, states only that a centrality of a node is maximized when it is the center of a star, but it does not specify a value.

1This is a slight modification of the original axiom that considers only adding edges to a connected graph, while we consider adding edges inside a connected component of possibly disconnected graph.

Star-Max: For every unweighted graph G = (V, E, 1, 1) and v V , Fv(G) Fv(V, {{v, u} : u V }, 1, 1).

In the following theorem, we show that Balanced Contributions, Additivity, and One-Edge Normalization imply that the centrality of a node in a tree equals its number of neighbours. In particular, the centrality of an isolated node is 0. Theorem 1. Let G = (V, E, 1, 1) be an unweighted graph and v V . If a centrality measure, F, satisfies Balanced Contributions, Additivity, and One-Edge Normalization and Kv(G) is a tree, then Fv(G) = |NG(v)|. The proof is analogous to the proof of Theorem 4 for weighted graphs, so we omit details. We are now ready to state the main theorems of this section that characterize the Degree and Attachment Centralities in unweighted graphs. Theorem 2. If a centrality measure, F, satisfies Balanced Contributions, Additivity, One-Edge Normalization, Star Max and Monotonicity, then for every unweighted graph G = (V, E, 1, 1) and v V it is equal to the Degree Centrality: Fv(G) = Dv(G).

Sketch of Proof. The proof is based on induction on the number of edges. From Monotonicity and Theorem 1 it can be shown that Fv(G) Dv(G). To prove that Fv(G) Dv(G) we use graph G where V \ {v} forms a clique and prove that Fv(G ) = Dv(G ) using the inductive assumption. Due to space constraints we omit details.

Theorem 3. If a centrality measure, F, satisfies Balanced Contributions, Additivity, One-Edge Normalization and Gain-loss, then for every unweighted graph G = (V, E, 1, 1) and v V it is equal to the Attachment Centrality: Fv(G) = Av(G).

Proof. Let G = (V, E, 1, 1) be an unweighted graph. Fix v V . First, we will show that a centrality of node v does not depend on edges from other connected components in graph G. From Additivity we get Fv(V, E, 1, 1) = Fv(V, E[Kv(G)], 1, 1) + Fv(V, E[V \ Kv(G)], 1, 1). Node v in the later graph is isolated and from Theorem 1 its centrality equals 0. Thus, we get Fv(V, E, 1, 1) = Fv(V, E[Kv(G)], 1, 1). Let us compute the sum of centralities of nodes in component Kv(G). To this end, let G = (V, E , 1, 1) be a graph obtained from G by removing edges in the component of v so that Kv(G ) is a tree. From Theorem 1, we know that for every u Kv(G) we have Fu(G ) = |NG (u)|. Summing over all nodes u Kv(G) and using Gain-loss we get that X

u Kv(G) Fu(G) = X

u Kv(G) Fu(G ) = 2 (|Kv(G)| 1). (2)

Finally, from [Skibski et al., 2017, Lemma 5] we get that there exists a unique centrality that satisfies Fairness and has specific sum of centralities for every component. Since Balanced Contributions implies Fairness, from Equation (2) we get that there exists at most one centrality that satisfies axioms from the statement of Theorem 3. It is easy to check that the Attachment Centrality satisfies these axioms, so Fv(G) = Av(G), which concludes the proof of Theorem 3.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

4 Node-Weighted Graphs

In this section, we extend the Attachment Centrality to nodeweighted graphs. Following the analysis from Section 3, our starting point is the analysis of axioms in weighted trees.

Example 1. Consider a node-weighted graph with one edge {v, u}: G = (V, {{v, u}}, ω, 1). For this graph we have:

WDv(G) = ω(u) and WDu(G) = ω(v).

Clearly, One-Edge Normalization is not satisfied for weighted graphs. Moreover, Balanced Contributions needs to be revisited. Observe that the profit from adding edge {v, u} is higher for a node with a lower weight. Thus, in case of the Weighted Degree Centrality, the profit is inversely proportional to the weight of a node.

This example leads to the generalization of One-Edge Normalization and Balanced Contributions.

Weighted One-Edge Normalization: For every v, u V ,

Fv(V, {{v, u}}, ω, 1) = ω(u).

Let us introduce Inverse Weighted Balanced Contributions. This is a new axiom which states that for every two nodes v, u V , removing edges of v affects the centrality of u multiplied by its weight in the same way as removing edges of u affects the centrality of v multiplied by its weight.

Inverse Weighted Balanced Contributions: For every node-weighted G = (V, E, ω, 1) and every v, u V ,

Fv(G) Fv(G ΓG(u))

ω(u) =Fu(G) Fu(G ΓG(v))

The name of Inverse Weighted Balanced Contributions comes from the fact that the weight of a node v is inversely correlated with the change in its centrality. Finally, Additivity, Star-Max, and Monotonicity naturally translate to node-weighted graphs by replacing 1 with an arbitrary ω function in the graph definition. Due to space constraints we omit details. Now, Inverse Weighted Balanced Contributions, Additivity and Weighted One-Edge Normalization uniquely characterize the centrality for trees.

Theorem 4. Let G = (V, E, ω, 1) be a node-weighted graph and v V . If a centrality measure, F, satisfies Inverse Weighted Balanced Contributions, Additivity, and Weighted One-Edge Normalization and Kv(G) is a tree, then Fv(G) = P u NG(v) ω(u).

Proof. Assume F satisfies Inverse Weighted Balanced Contributions, Additivity and Weighted One-Edge Normalization and fix a node-weighted graph G = (V, E, ω, 1) and v V . We divide the proof in three parts:

(a) if NG(v) = (v is isolated), then Fv(G) = 0;

(b) if NG(v) = {u} (v is a leaf), then Fv(G) = ω(u);

(c) if |NG(v)| = k and |K(G ΓG(v))| |K(G)| = k, then Fv(G) = P u NG(v) ω(u).

(a) Since ΓG(v) = , from Inverse Weighted Balanced Contributions we get: (Fv(G) Fv(G ΓG(u)))/ω(u) = 0

for every u V . It means that the centrality of v does not depend on edges between other nodes; thus, it is the same as in graph with no edges: Fv(G) = Fv(V, , ω, 1). From Additivity, we have that Fv(V, , ω, 1) = Fv(V, , ω, 1) + Fv(V, , ω, 1)=0 for every node v, which implies Fv(G)=0. (b) Since v is a leaf, ΓG(v) = {{v, u}}. From Additivity Fu(G) Fu(G ΓG(v)) = Fu(V, ΓG(v), ω, 1). In graph G ΓG(u) node v is isolated; thus, from (a): Fv(G ΓG(u)) = 0. Combining these facts with Equation (3) and Weighted One-Edge Normalization, we get: Fv(G)/ω(u) = Fu(V, ΓG(v), ω, 1)/ω(v) = 1. (c) Assume NG(v) = {u1, u2, . . . , uk}. The set of edges in the component of v can be divided into the following k sets: E1, E2, . . . , Ek, such that {v, ui} Ei, and S Ei S Ej = {v} for every i, j {1, . . . , k}, i = j. From Additivity: Fv(G) = P 1 i k Fv(V, Ei, ω, 1)+Fv(G (E1 . . . Ek)). In each graph (V, Ei, ω, 1) node v is a leaf and in graph G (E1 . . . Ek) node v is isolated. Thus, from (a) and (b) we get that Fv(G) = P u NG(v) ω(u).

Building upon this result, we get an axiomatization of the Weighted Degree Centrality (for node-weighted graphs). Theorem 5. If a centrality measure, F, satisfies Inverse Weighted Balanced Contributions, Additivity, Weighted One Edge Normalization, Star-Max, Monotonicity, then for every node-weighted graph G = (V, E, ω, 1) and v V it is equal to the Weighted Degree Centrality: Fv(G) = WDv(G). The proof, based on Theorem 4, uses the similar reasoning as the proof of Theorem 2. Let us focus on the Attachment Centrality and examine Gain-loss for weighted graphs in the following example. Example 2. Let V = {v, u, w} and consider two graphs: G1 = (V, {{v, u}, {v, w}}, ω, 1) and G2 = (V, {{v, u}, {u, w}}, ω, 1). For these graphs we have: P v V WDv(G1) = 2 ω(v) + ω(u) + ω(w), P v V WDv(G2) = ω(v) + 2 ω(u) + ω(w).

Thus, P v V WDv(G1) = P v V WDv(G2) if ω(v) = ω(u). In result, we know that there exists no measure such that Fv(G) = WDv(G) if G is a tree and satisfies Gain-loss for node-weighted graphs, i.e., such that adding edges to a connected component does not affect the sum of centralities. To cope with this problem we ask the question: how the weight of a node contributes to the sum of centralities? In the case of the Weighted Degree Centrality, as we saw in Example 2, the more central the node is, the bigger impact its weight has on the sum of centralities. In fact, we observe that the impact of the weight of a node is exactly proportional to its centrality. We formalize this notion in the following axiom, called Node-Weight Impact.

Node-Weight Impact: For every G = (V, E, ω, 1), every v V and every α R, X

u V Fu(G)=Fv(V, E,1,1) α+ X

u V Fu(V, E, ωω(v) α v ,1).

To introduce the Weighted Attachment Centrality we use the Weighted Shapley Value, originally proposed by [Shapley,

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

1953a] and studied by [Kalai and Samet, 1987]. For a game, f, and vector of weights, ω : V R+, the Weighted Shapley Value is defined as follows:

WSV ω v (f)= X

w Sπ u ω(w)

f(Sπ v ) f(Sπ v \{v}) .

The Weighted Shapley Value rewards elements with higher weights. However, as shown in Example 1, in our case we need an inverse notion. That is why, we will use Weighted Shapley Value, but with the inverse weight function 1

ω defined as follows: 1

ω(v) = 1 ω(v).

Definition 2. The Weighted Attachment Centrality for a node-weighted graph G = (V, E, ω, 1) is defined as follows:

WAv(G) = WSV

1 ω v (f A G),

where f A G(S) = P v S Av(S, E[S], 1, 1) ω(v). Haeringer [1999] proposed the Weighted Myerson value, calculated as the Weighted Shapley value for restricted game f/G. The Attachment Centrality for node-weighted graphs can be considered as the Weighted Myerson value for inverse weight vector 1

ω and game f A G. In the following lemma, we prove that the Weighted Attachment Centrality is equal to the Attachment Centrality for unweighted graphs. Lemma 6. For every unweighted graph G = (V, E, 1, 1), WAv(G) = Av(G).

Proof. From Definition 2: f A G(S) = P v S Av(S,E[S],1,1). From Definition 1: P v S Av(S,E[S],1,1) = f G(S). Thus, f A G=f G. Moreover, WSV 1 v (f)=SVv(f) for every f and we get that WAv(G)=WSV 1 v (f A G)=SVv(f G)=Av(G).

In the main theorem of this section Theorem 7 we prove that by adding Node-Weight Impact to axioms from Theorem 3 we get a characterization of the Weighted Attachment Centrality. Note that we use Gain-loss for unweighted graphs, since it is undesirable for node-weighted graphs (see Example 2). Theorem 7. If a centrality measure, F, satisfies Inverse Weighted Balanced Contributions, Additivity, Weighted One Edge Normalization, Gain-loss for unweighted graphs and Node-Weight Impact, then for every node-weighted graph G = (V, E, ω, 1) and v V it is equal to the Weighted Attachment Centrality: Fv(G) = WAv(G).

Proof. Since Inverse Weighted Balanced Contributions, Additivity and Weighted One-Edge Normalization imply Balanced Contributions, Additivity and One-Edge Normalization when ω = 1, from Theorem 3 we have that Fv(G) = Av(G) for every unweighted graph G. Let F, F be two centralities that satisfy Inverse Weighted Balanced Contributions, Node Weight Impact, and Additivity and assume Fv(G) = F v(G) for every unweighted graph G = (V, E, 1, 1). To prove uniqueness, it remains to show that Fv(G) = F v(G) for every node-weighted graph G = (V, E, ω, 1). Fix graph G=(V, E, ω, 1) and u V . From Node-Weight Impact we get: P v V Fv(G) = (ω(u) 1)Fv(V, E, 1, 1) +

P v V Fv(V, E, ω1 u, 1). Using the same argument for graph (V, E, ω1 u, 1) and sequentially for all other nodes we get: P v V Fv(G) = P v V Fv(V, E, 1, 1) ω(v). Thus, we get that P v V Fv(G) = P v V F v(G). Moreover, from Additivity we get Fv(V, , ω, 1) = 0 = F v(V, , ω, 1). From [Skibski et al., 2017, Lemma 13] we know that there exists a unique centrality that satisfies Balanced Contributions and the sum of centralities in every graph as well as values in empty graph (V, ) are specified. Using the same reasoning for weighted graphs and weighted version of Balanced Contributions we get that F = F . It remains to prove that the Weighted Attachment Centrality satisfies all axioms. We consider them one by one: Weighted One-Edge Normalization: Consider graph G = (V, {{v, u}}, ω, 1). From Definition 2 f A G(S) = ω(v) + ω(u) if v, u S, and f A G(S) = 0, otherwise. Thus, it is a unanimity game and from [Kalai and Samet, 1987] we get that WAv(G) = WSV

1 ω v (f A G) = 1 ω(v)/( 1 ω(v) + 1 ω(u)) (ω(v) + ω(u)) = ω(u). Gain-loss for unweighted graphs: Immediate from Lemma 6 and [Skibski et al., 2016]. Node-Weight Impact: From Definition 2 and the definition of Weighted Shapley value we get that P v V WAv(G) = f A G(V ) = P v V Av(V, E, 1, 1) ω(v) for every graph G = (V, E, ω, 1). This implies Node-Weight Impact. Additivity: Fix graph G = (V, E, ω, 1), two sets S, T V and v V , such that S T = {v}. From the analysis of cut-vertices in [Skibski et al., 2016, Theorem 4] and the fact that the Attachment Centrality of an isolated node is zero, we get that Au(V, E[S], 1, 1) + Au(V, E[T], 1, 1) = Au(V, E[S] E[T], 1, 1) for every u V . This combined with Definition 2 implies that for every U V : f A (V,E[S],ω,1)(U) + f A (V,E[T ],ω,1)(U) = f A (V,E[S] E[T ],ω,1)(U). Since the Weighted Shapley value is additive we get AVu(V, E[S], ω, 1) + AVu(V, E[T], ω, 1) = AVu(V, E[S] E[T], ω, 1) for every u V (including u = v). Inverse Weighted Balanced Contributions: Consider graph G = (V, E, ω, 1). Fix node v V and subset S V such that v S. Consider graph G = G ΓG(v). Since v is isolated in G we have Av(G [S]) = 0 and Au(G [S]) = Au(G [S \ {v}]) = Au(G[S \ {v}]) for every u V \ {v}. Combined with Definition 2 we get f A G ΓG(v)(S) = f A G(S \ {v}). (4) From the formula of the Weighted Shapley value it is visible that for arbitrary game g, node u V and game g defined as follows: g (S) = g(S) g(S \ {u}) we have WSV ω u (g) = WSV ω u (g ). Applying this observation and Equation (4) to left-hand side of the Inverse Weighted Balanced Contributions condition we get ω(u) (AVu(G) AVu(G ΓG(v))) = ω(u)

1 ω u (f A G f A G ΓG(v) f A G ΓG(u)+f A G (ΓG(v) ΓG(u))). In this formula, game is symmetric for v and u, thus payoffs of nodes v and u are proportional to their weights. This concludes the proof of Theorem 7.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

5 Nodeand Edge-Weighted Graphs So far, we considered only weights of nodes. In this section, we show how weights of edges can be incorporated in the Weighted Attachment Centrality. Again, we begin with an example that helps us understand how weights of edges affect importance of nodes. Example 3. Let G = (V, {e}, ω, ρ) be a graph with one edge e = {v, u} and consider weight ρ of edge e. First, assume ρ(e) (0, 1). In such case, weight can be interpreted as the probability that a given edge exists. Thus, with probability ρ(e) edge exists (G = (V, {e}, ω, 1)), and with probability (1 ρ(e)) edge does not exist (G = (V, , ω, 1)). This interpretation is consistent with the Weighted Degree Centrality:

WDv(V, {e}, ω, ρ) = ρ(e) WDv(V, {e}, ω, 1) + (1 ρ(e)) WDv(V, , ω, 1) = ρ(e) ω(u).

Now, assume ρ(e) = k for some k N. This graph can be interpreted as the multigraph with the set of edges E = {e, e, . . . , e}, |E| = k. By treating each edge separately the Weighted Degree Centrality equals: WDv(V, {e}, ω, ρ) = ρ(e) ω(u). While both interpretations are based on different insights, they both characterize the same property: the profit from the edge is proportional to its weight. Our analysis from Example 3 leads to the following axiom:

Edge-Weight Proportionality: Let G = (V, E, ω, ρ) be a graph. For every v V , e E and α, β R+,

α (Fv(V, E, ω, ρβ e ) Fv(V, E \ {e}, ω, ρ e)) = β (Fv(V, E, ω, ρα e ) Fv(V, E \ {e}, ω, ρ e)).

In the following theorem we show that if centrality satisfies Edge-Weight Proportionality, then it is uniquely defined by specifying values on graphs without edge-weights, i.e., formally, where weight of each edge equals 1. Theorem 8. If a centrality measure, F, satisfies Edge-Weight Proportionality, then for every graph (V, E, ω, ρ):

Fv(V, E, ω, ρ) =

e E\M (1 ρ(e)) Fv(V, M, ω, 1)

Sketch of Proof. For graph G = (V, E, ω, ρ), let us denote by E1 E the subset of edges with weight 1: E1 = {e E : ρ(e) = 1}. We will prove Equation (5) by induction on the size of set E \ E1, i.e., the number of edges in a graph with the weight different than 1. If |E \ E1| = 0, then ρ = 1 and Equation (5) trivially holds. Assume Equation (5) is satisfied for every graph G = (V, E, ω, ρ) such that |E \ E1| < k for k > 0. Now, consider G = (V, E, ω, ρ) such that |E \ E1| = k. From Edge-Weight Proportionality for an arbitrary edge e E \ E1, α = 1 and β = ρ(e ) we get Fv(V, E, ω, ρ) = ρ(e ) Fv(V, E, ω, ρ1 e ) + (1 ρ(e )) Fv(V, E \{e }, ω, ρ e ). Using inductive assumption we get Equation (5), which concludes the proof of Theorem 8.

Now, we are ready to define the Weighted Attachment Centrality for nodeand edge-weighted graphs.

Definition 3. The Weighted Attachment Centrality for graph G = (V, E, ω, ρ) is defined as follows:

WAv(G) = WSV

1 ω v (f P G ), where f P G =P M E Q e M ρ(e) Q e E\M(1 ρ(e))f A (V,M,ω,1).

For a graph G = (V, E, 1, ρ) with unweighted nodes, the Weighted Attachment Centrality is equal to the Probabilistic Myerson value, defined by Calvo et al. [1999] with characteristic function f G. Based on Theorem 8, we get the following two axiomatizations of the Weighted Degree Centrality and the Weighted Attachment Centrality. Theorem 9. There is a unique centrality measure that satisfies Inverse Weighted Balanced Contributions, Weighted One Edge Normalization, Additivity, Star-Max, Monotonicity, and Edge-Weight Proportionality; this measure is the Weighted Degree Centrality.

Proof. From Theorem 5 and 8 it is enough to show that the Weighted Degree Centrality satisfies Edge-Weight Proportionality. This is straightforward from Equation (1).

Theorem 10. There is a unique centrality measure that satisfies Inverse Weighted Balanced Contributions, Weighted One Edge Normalization, Additivity, Gain-loss for unweighted graphs, Node-Weight Impact and Edge-Weight Proportionality; this measure is the Weighted Attachment Centrality.

Proof. Immediate from Theorems 7 and 8.

6 Related Work Amer and Gim enez [2004] proposed the first measure of connectivity by computing semi-value of a game that assigns 1 if coalition is connected, and 0 otherwise. This solution works only for unweighted graphs. Lindelauf et al. [2013] expanded this concept to weighted graphs by using an arbitrary function if coalition is connected. The authors proposed several definitions of function f, but only for specific terrorist networks. Michalak et al. [2013] analysed the computational properties of these measures and proposed using the Myerson value instead of the Shapley value for connectivity games. Skibski et al. [2014] improved those algorithms and introduced a class of measures. However, no specific measures were proposed. Above concepts were only tested empirically and no axiomatic analysis was offered.

7 Conclusions In this paper, we proposed Weighted Attachment Centrality an extension of the Attachment Centrality to nodeand edgeweighted graphs and provided its axiomatization. In future work, we are keen to study the computational properties of the Weighted Attachment Centrality and to extend the Attachment Centrality to directed graphs.

Acknowledgments Jadwiga Sosnowska and Oskar Skibski were supported by the Foundation for Polish Science within the Homing programme (Project title: Centrality Measures: from Theory to Applications ).

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

[Amer and Gim enez, 2004] Rafael Amer and Jos e Miguel Gim enez. A connectivity game for graphs. Mathematical Methods of Operations Research, 60(3):453 470, 2004.

[Bagler, 2008] Ganesh Bagler. Analysis of the airport network of india as a complex weighted network. Physica A: Statistical Mechanics and its Applications, 387(12):2972 2980, 2008.

[Belau, 2014] Julia Belau. Consequences of connection failure - centrality and the importance for cohesion. In Public Choice Society, 2014.

[Brandes and Erlebach, 2005] Ulrik Brandes and Thomas Erlebach. Network analysis: Methodological foundations. Springer-Verlag, 2005.

[Calvo et al., 1999] Emilio Calvo, Javier Lasaga, and Anne van den Nouweland. Values of games with probabilistic graphs. Mathematical Social Sciences, 37(1):79 95, 1999.

[Derrible, 2012] S. Derrible. Network centrality of metro systems. PLo S ONE, 7(7), 2012.

[Freeman, 1979] Linton C. Freeman. Centrality in social networks: Conceptual clarification. Social Networks, 1(3):215 239, 1979.

[Haeringer, 1999] Guillaume Haeringer. Weighted Myerson value. International Game Theory Review, 1(02):187 192, 1999.

[Heitzig et al., 2010] Jobst Heitzig, Norbert Marwan, Yong Zou, Jonathan F Donges, and J urgen Kurths. Consistently weighted measures for complex network topologies. Europ. Phys. J. B, 85:1 16, 2010.

[Kalai and Samet, 1987] Ehud Kalai and Dov Samet. On weighted Shapley values. International Journal of Game Theory, 16(3):205 222, 1987.

[Koschade, 2006] Stuart Koschade. A social network analysis of Jemaah Islamiyah: The applications to counterterrorism and intelligence. Studies in Conflict & Terrorism, 29(6):559 575, 2006.

[Lindelauf et al., 2013] Roy Lindelauf, Herbert Hamers, and Bart Husslage. Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al Qaeda. European Journal of Operational Research, 229(1):230 238, 2013.

[Michalak et al., 2013] Tomasz P. Michalak, Talal Rahwan, Piotr L. Szczepa nski, Oskar Skibski, Ramasuri Narayanam, Michael Wooldridge, and Nicholas R. Jennings. Computational analysis of connectivity games with applications to the investigation of terrorist networks. In Proceedings of 23rd International Joint Conference on Artificial Intelligence (IJCAI), pages 293 301, 2013.

[Moretti et al., 2010] Stefano Moretti, Vito Fragnelli, Fioravante Patrone, and Stefano Bonassi. Using coalitional games on biological networks to measure centrality and power of genes. Bioinformatics, 26(21):2721 2730, 2010.

[Myerson, 1977] Roger B. Myerson. Graphs and cooperation in games. Mathematical Methods of Operations Research, 2(3):225 229, 1977. [Myerson, 1980] Roger B. Myerson. Conference structures and fair allocation rules. International Journal of Game Theory, 9:169 82, 1980. [Narayanam et al., 2014] Ramasuri Narayanam, Oskar Skibski, Hemank Lamba, and Tomasz P. Michalak. A Shapley value-based approach to determine gatekeepers in social networks with applications. In Proceedings of 21st European Conference on Artificial Intelligence (ECAI), pages 651 656, 2014. [Nepusz et al., 2012] Tam as Nepusz, Haiyuan Yu, and Alberto Paccanaro. Detecting overlapping protein complexes in protein-protein interaction networks. Nature methods, 9(5):471 472, 2012. [Opsahl et al., 2010] Tore Opsahl, Filip Agneessens, and John Skvoretz. Node centrality in weighted networks: Generalizing degree and shortest paths. Social networks, 32(3):245 251, 2010. [Palla et al., 2007] Gergely Palla, Albert-L aszl o Barab asi, and Tam as Vicsek. Quantifying social group evolution. Nature, 446(7136):664 667, 2007. [Shapley, 1953a] Lloyd S Shapley. Additive and nonadditive set functions. Princeton University, 1953. [Shapley, 1953b] Lloyd S. Shapley. A value for n-person games. In H.W. Kuhn and A.W. Tucker, editors, Contributions to the Theory of Games, volume II, volume II, pages 307 317. Princeton University Press, 1953. [Skibski et al., 2014] Oskar Skibski, Tomasz P. Michalak, Talal Rahwan, and Michael Wooldridge. Algorithms for the Shapley and Myerson values in graph-restricted games. In Proceedings of 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 197 204, 2014. [Skibski et al., 2016] Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, and Makoto Yokoo. Attachment centrality: An axiomatic approach to connectivity in networks. In Proceedings of 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 168 176, 2016. [Skibski et al., 2017] Oskar Skibski, Tomasz P. Michalak, and Talal Rahwan. Axiomatic characterization of gametheoretic network centralities. In Proceedings of 31st AAAI Conference on Artificial Intelligence (AAAI), pages 698 705, 2017. [Tarkowski et al., 2016] Mateusz K Tarkowski, Piotr Szczepa nski, Talal Rahwan, Tomasz P. Michalak, and Michael Wooldridge. Closeness centrality for networks with overlapping community structure. In Proceedings of 30th AAAI Conference on Artificial Intelligence (AAAI), pages 622 629, 2016.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)