On decay centrality in graphs

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

Abstract

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.

References

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

>

Published
2018-08-01
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
Section
Articles