Centralities in classical graphs and relations between them
https://doi.org/10.22405/2226-8383-2025-26-2-218-231
Abstract
In the paper relations between average clustering coefficient and global clustering coefficient, closeness, betweenness and stress centralities were proved for simple graphs. Also the theorem about the realtion between average clustering coefficient and radiality is clarified and these
centralities are calculated for 3 classical series of graphs.
About the Author
Mikhail Alekseevich Tuzhilin
Lomonosov Moscow State University
Russian Federation
Russian Federation
candidate of physical and mathematical sciences
References
1. Bonacich, P., 1972, “Factoring and weighting approaches to status scores and clique identification”, Journal of Mathematical Sociology, vol. 2, no. 1, pp. 113–120.
2. Borgatti, S.P., Everett, M.G., 2006, “A graph-theoretic perspective on centrality”, Social Networks, vol. 28, no. 4, pp. 466–484.
3. Kiss, C., Bichler, M., 2008, “Identification of influencers - measuring influence in customer networks”, Decision Support Systems, vol. 46, no. 1, pp. 233–253.
4. Lee, S.H.M., Cotte, J., Noseworthy, T.J., 2010, “The role of network centrality in the flow of consumer influence”, Journal of Consumer Psychology, vol. 20, no. 1, pp. 66–77.
5. You, J., Gomes-Selman, J.M., Ying, R., Leskovec, J., 2021, “Identity-aware graph neural networks”, Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 12, pp. 10737–10745.
6. Yuan, M.M., Guo, X., Wu, L., Zhang, Y.A., Xiao, N., Ning, D., Zhou, J., 2021, “Climate warming enhances microbial network complexity and stability”, Nature Climate Change, vol. 11, no. 4, pp. 343–348.
7. Watts, D.J., Strogatz, S.H., 1998, “Collective dynamics of ’small-world’ networks”, Nature, vol. 393, no. 6684, pp. 440–442.
8. Luce, R.D., Perry, A.D., 1949, “A method of matrix analysis of group structure”, Psychometrika, vol. 14, no. 2, pp. 95–116.
9. Estrada, E., 2016, “When local and global clustering of networks diverge”, Linear Algebra and its Applications, vol. 488, pp. 249–263.
10. Harary, F., 1994, Graph Theory, Reading, MA: Addison-Wesley, p. 46.
11. Pemmaraju, S., Skiena, S., 2003, “Cycles, Stars, and Wheels”, in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica, Cambridge: Cambridge University Press, pp. 248–249.
12. Tutte, W.T., 2005, Graph Theory, Cambridge: Cambridge University Press.
13. Dolev, D., Leighton, F.T., Trickey, H., 1983, “Planar embedding of planar graphs”, Advances in Computing Research, vol. 2, pp. 147–161.
14. Frati, F., Patrignani, M., 2008, “A note on minimum-area straight-line drawings of planar graphs”, in Graph Drawing: 15th International Symposium, Berlin: Springer, pp. 339–344.
15. Tuzhilin, M.A., 2024, “Relations between average clustering coefficient and other centralities in graphs”, Moscow University Mathematics Bulletin, in press.
Review
For citations:
Tuzhilin M.A. Centralities in classical graphs and relations between them. Chebyshevskii Sbornik. 2025;26(2):218-231. (In Russ.) https://doi.org/10.22405/2226-8383-2025-26-2-218-231
Views:
10
Email this article 