On decay centrality in graphs


  • Jana Coroničová Hurajová
  • Silvia Gago
  • Tomáš Madaras




The decay centrality of a vertex $v$ in a graph $G$ with respect to a parameter $\delta \in (0,1)$ is a polynomial in δ such that for fixed $k$ the coefficient of $\delta ^k$ is equal to the number of vertices of $G$ at distance $k$ from $v$. This invariant (introduced independently by Jackson and Wolinsky in 1996 and Dangalchev in 2011) is considered as a replacement for the closeness centrality for graphs, however its unstability was pointed out by Yang and Zhuhadar in 2011. We explore mathematical properties of decay centrality depending on the choice of parameter δ and the stability of vertex ranking based on this centrality index.


Bloom, G. S., Kennedy, J. W., and Quintas, L. V., Some problems concerning distance and path degree sequences, in “Graph theory (Łagów, 1981)'', Lecture Notes in Math., vol. 1018, Springer, Berlin, 1983, pp. 179--190. https://doi.org/10.1007/BFb0071628

Brandes, U. and Erlebach, T., Network analysis: methodological foundations, vol. 3418, Springer Science & Business Media, 2005. https://doi.org/10.1007/b106453

Dangalchev, C., Residual closeness and generalized closeness, Internat. J. Found. Comput. Sci. 22 (2011), no. 8, 1939–1948. https://doi.org/10.1142/S0129054111009136

Diestel, R., Graph theory, fourth ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. https://doi.org/10.1007/978-3-642-14279-6

Imrich, W. and Klavžar, S., Product graphs: Structure and recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.

Jackson, M. O., Social and economic networks, Princeton University Press, Princeton, NJ, 2008.

Jackson, M. O. and Wolinsky, A., A strategic model of social and economic networks, J. Econom. Theory 71 (1996), no. 1, 44–74. https://doi.org/10.1006/jeth.1996.0108

Knor, M. and Madaras, T., On farness- and reciprocally-selfcentric antisymmetric graphs, in “Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing”, vol. 171, 2004, pp. 173--178.

Latora, V. and Marchiori, M., Efficient behavior of small-world networks, Physical review letters 87 (2001), no. 19, 198701. https://doi.org/10.1103/PhysRevLett.87.198701

Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., and Dawson, S. M., The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology 54 (2003), no. 4, 396–405. https://doi.org/10.1007/s00265-003-0651-y

Padgett, J. F. and Ansell, C. K., Robust action and the rise of the Medici, 1400-1434, American Journal of Sociology 98 (1993), no. 6, 1259–1319. https://doi.org/10.1086/230190

Phelps, K. T., Latin square graphs and their automorphism groups, Ars Combin. 7 (1979), 273–299.

Yang, R. and Zhuhadar, L., Extensions of closeness centrality?, in “Proceedings of the 49th Annual Southeast Regional Conference”, ACM, 2011, pp. 304--305. https://doi.org/10.1145/2016039.2016119

Zachary, W. W., An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33 (1977), no. 4, 452–473. https://doi.org/10.1086/jar.33.4.3629752



How to Cite

Coroničová Hurajová, J., Gago, S., & Madaras, T. (2018). On decay centrality in graphs. MATHEMATICA SCANDINAVICA, 123(1), 39–50. https://doi.org/10.7146/math.scand.a-106210