  Katz centrality (and its limiting case, eigenvector centrality) is a
frequently used tool to measure the importance of a node in a network, and to
rank the nodes accordingly. One reason for its popularity is that Katz
centrality can be computed very efficiently when the network is sparse, i.e.,
having only $O(n)$ edges between its $n$ nodes. While sparsity is common in
practice, in some applications one faces the opposite situation of a very dense
network, where only $O(n)$ potential edges are missing with respect to a
complete graph. We explain why and how, even for very dense networks, it is
possible to efficiently compute the ranking stemming from Katz centrality for
unweighted graphs, possibly directed and possibly with loops, by working on the
complement graph. Our approach also provides an interpretation, regardless of
sparsity, of "Katz centrality with negative parameter" as usual Katz centrality
on the complement graph. For weighted graphs, we provide instead an
approximation method that is based on removing sufficiently many edges from the
network (or from its complement), and we give sufficient conditions for this
approximation to provide the correct ranking. We include numerical experiments
to illustrate the advantages of the proposed approach.
