On decay centrality in graphs
DOI:
https://doi.org/10.7146/math.scand.a-106210Abstract
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
