Axioms for Centrality

Abstract

Given a social network, which of its nodes are more central? This question has been asked many times in sociology, psychology, and computer science, and a whole plethora of centrality measures (a.k.a. centrality indices, or rankings) were proposed to account for the importance of the nodes of a network. In this study, we try to provide a mathematically sound survey of the most important classic centrality measures known from the literature and propose an axiomatic approach to establish whether they are actually doing what they have been designed to do. Our axioms suggest some simple, basic properties that a centrality measure should exhibit.

Surprisingly, only a new simple measure based on distances, harmonic centrality, turns out to satisfy all axioms; essentially, harmonic centrality is a correction to Bavelas’s classic closeness centrality [Bavelas 50] designed to take unreachable nodes into account in a natural way.

As a sanity check, we examine in turn each measure under the lens of information retrieval, leveraging state-of-the-art knowledge in the discipline to measure the effectiveness of the various indices in locating webpages that are relevant to a query. Although there are some examples of such comparisons in the literature, here, for the first time, we also take into consideration centrality measures based on distances, such as closeness, in an information-retrieval setting. The results closely match the data we gathered using our axiomatic approach.

Our results suggest that centrality measures based on distances, which in recent years have been neglected in information retrieval in favor of spectral centrality measures, do provide high-quality signals; moreover, harmonic centrality pops up as an excellent general-purpose centrality index for arbitrary directed graphs.

Notes

Here and in the following, by “distance” we mean the length of a shortest path between two nodes.

The reader might find this definition a bit vague, and some variants are often spotted in the literature: this is a general well-known problem, also highlighted recently, for example, in [Li et al. 05].

The notion can also be generalized to a weighted summation of node contributions multiplied by some discount functions applied to their distance to a given node [Cohen and Kaplan 07].

Dominant eigenvectors were rediscovered as a generic way of computing centralities on graphs by [Bonacich 72].

To be precise, Kleinberg’s algorithm works in two phases; in the first phase, one selects a subgraph of the starting web graph based on the pages that match the given query; in the second phase, the centrality score is computed on the subgraph. Because in this paper we are looking at HITS simply as a centrality index, we will simply apply it to the graph under examination.

Most centrality measures proposed in the literature were actually described only for undirected, connected graphs. Because the study of web graphs and online social networks has posed the problem of extending centrality concepts to networks that are directed, and possibly not strongly connected, in the rest of this study we consider measures depending on the incoming arcs of a node (e.g., incoming paths, left dominant eigenvectors, distances from all nodes to a fixed node). If necessary, these measures can be called “negative,” opposed to the “positive” versions obtained by considering outgoing paths, or (equivalently) by transposing the graph.

We remark that Yannick Rochat, in a talk at Application of Social Network Analysys (ASNA 2009) observed that in an undirected graph with several disconnected components, the inverse of the harmonic mean of distances offers a better notion of centrality than closeness, because it weights less those elements that belong to smaller components. Tore Opsahl made the same observation in a March 2010 blog posting. Raj Kumar Pan and Jari Saramäki deviated from the classical definition of closeness in [Pan and Saramäki 11], using, in practice, harmonic centrality, with the motivation of better handling disconnected nodes (albeit with no reference to the harmonic mean). Edith Cohen and Haim Kaplan defined in [Cohen and Kaplan 07] the notion of a spatially decaying aggregate, of which harmonic centrality is a particular instance.

We must note that the original definition of Katz’s index is 1A∑^∞_{i = 0}βⁱAⁱ = 1/β∑_{i = 0}^∞β^{i + 1}A^{i + 1} = (1/β)∑^∞_{i = 0}βⁱAⁱ − 1/β. This additional multiplication by A is somewhat common in the literature, even for PageRank; clearly, it alters the order induced by the scores only when there is a nonuniform preference vector. Our discussion can be easily adapted for this version.

The reader should be aware, however, that the literature about the actual effectiveness of PageRank in information retrieval is rather scarce, and comprises mainly negative results such as those found in [Najork et al. 07a] and [Craswell et al. 03].

A few years before, [Bonacich 91] had introduced the same method for computing the centrality of individuals and groups related by a rectangular incidence matrix. Kleinberg’s approach is slightly more general, as it does not assume that the two scores are assigned to different types of entities.

As discussed in [Farahat et al. 06], the dominant eigenvector may not be unique; equivalently, the limit of the recursive definition given above may depend on the way the authority and hub scores are initialized. Here, we consider the result of the iterative process starting with .

This property, which appears to be little known, is proved in Proposition 2 of the original paper [Lempel and Moran 01].

The authors claim to formalize PageRank [Page et al. 98], but they do not consider the damping factor (equivalently, they are setting α = 1), so they are actually formalizing Seeley’s venerable index [Seeley 49].

A graph is vertex-transitive if for every nodes x and y there is an automorphism exchanging x and y.

The graph is of course disconnected. It is a common theme of this work that centrality measures should work also on graphs that are not strongly connected, for the very simple reason that we meet this kind of graphs in the real world, the web being a common example.

[Lempel and Moran 01] while designing their own centrality measure observe that “the size of the community should be considered when evaluating the quality of the top pages in that community”.

This paper contributed so much to the popularization of Bavelas’s closeness centrality that the latter is often called “Sabidussi’s centrality” in the literature.

There are actually two notions of radiality, which correspond to our notions of “positive” and “negative” centralities.

It should be noted, however, that this is true only for the values of the parameter β that still make sense after the addition.

It is interesting to note that it is actually the only centrality satisfying the size axiom—in fact, one needs a cycle of ≈e^k nodes to beat a k-clique.

We note that since D_{k, p} is strongly connected, closeness and Lin’s centrality differ just by a multiplicative constant.

It is actually now possible to approximate them efficiently [Boldi and Vigna 13].

Note that the β-measure originally defined by van den Brink and Gilles in [van den Brink and Gilles 94] is the positive version, that is, the negative β-measure can be obtained by applying the β-measure defined in [van den Brink and Gilles 94] to the transposed graph.