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

作者：Qi Xingqin; Fuller Edgar; Luo Rong; Zhang Cun quan^*

来源：Pattern Recognition Letters, 2015, 58: 51-60.

DOI：10.1016/j.patrec.2015.02.007

• Centrality method
• Spanning tree
• Weighted network
• Matrix tree theorem
• Kirchhoff polynomial

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.

• 出版日期2015-6-1
• 单位山东大学