Centrality scores

The simplest of centrality scores is the degree of a vertex. In a directed network such as a citation network, there are two degrees, the in-degree and the out-degree. It is reasonable, for instance, to imagine that important or influential vertices in a citation network will receive many citations and therefore have high in-degree. A more sophisticated version of the same idea is eigenvector centrality, in which, rather than merely counting the number of citations a vertex gets, we award a higher score when the citing vertices are themselves influential.

The simplest way to do this is to define the centrality to be proportional to the sum of the centralities of the citing vertices, which makes the centralities proportional to the elements of the leading eigenvector of the adjacency matrix. Unfortunately, this method does not work for acyclic directed networks, such as citation networks, for which all such centralities turn out to be zero.

An interesting variant of eigenvector centrality has been proposed by Kleinberg that works well for acyclic networks. In this variant each vertex has two centralities, known as the authority score and the hub score, the first derived from the incoming links and the second from the outgoing links. In this view a “hub” is a vertex that points to many important authorities — a review paper in a scientific citation network, for instance — while an authority is a vertex pointed to by many important hubs — such as an important or authoritative research article on a particular subject. In the simplest version of the method the authority score ${x_{i}}$ of vertex $i$ is simply proportional to the sum of the hub scores yj of the vertices citing it:

for some constant λ, while the hub score is proportional to the sum of the authority scores of the vertices it cites:

In matrix form, these equations can be written

Or, eliminating either x or y,

Thus x and y are eigenvectors of the symmetric matrices AA^T and A^TA (also known as the cocitation and bibliographic coupling matrices respectively). In Kleinberg’s formulation of the problem one focuses on the leading eigenvector of each of the matrices, although in principle there could be useful information to be gleaned from other eigenvectors too.