A novel centrality method for weighted networks based on the Kirchhoff polynomial

• A new centrality measurement is introduced for weighted networks.
• It evaluates the importance of a vertex from very different structural aspects with other existing centrality methods.
• When it applies on several benchmark social networks, expected and even better results are obtained.
• The new centrality score is easily calculated, either by the Kirchhoff Polynomial or by the Laplacian eigenvalues.

The measuring of centralities, which determines the importance of vertices in a network, has been one of the key issues in network analysis. Comparing with various measures developed for unweighted networks, little work has been done yet for weighted networks. In this paper, a new centrality measurement, called spanning tree centrality (STC for short), is introduced for weighted networks. The STC score of a vertex v in G is defined as the number of spanning trees with the vertex v as a cut vertex. We show that STC scores can be calculated by the Kirchhoff polynomial of G. In order to verify the validity of STC, we apply it on several benchmark social networks and all get satisfied and even better results. Furthermore, to verify the pairwise positive correlations between STC and other existing methods, Kendall’s rank correlation coefficients are calculated. The advantage of STC is further shown by the parameter of “network centralization”, which is used to measure the extent that a whole network has a centralized structure under a certain centrality method.