Ранжирование вершин графа с использованием абсолютных потенциалов узлов электрической цепи

Vladimir V. Mazalov; Vitalia A. Khitraya

doi:10.21638/11701/spbu10.2023.209

Authors

Vladimir V. Mazalov Federal Research Center “Karelian Research Center of the Russian Academy of Sciences”, 11, Pushkinskaya uh, Petrozavodsk, Republic of Karelia, 185910, Russian Federation; Petrozavodsk State University, 33, pr. Lenina, Petrozavodsk, Republic of Karelia, 185910, Russian Federation
Vitalia A. Khitraya Federal Research Center “Karelian Research Center of the Russian Academy of Sciences”, 11, Pushkinskaya uh, Petrozavodsk, Republic of Karelia, 185910, Russian Federation; Petrozavodsk State University, 33, pr. Lenina, Petrozavodsk, Republic of Karelia, 185910, Russian Federation

DOI:

https://doi.org/10.21638/11701/spbu10.2023.209

Abstract

A method for ranking the vertices of a graph based on Kirchhoff’s laws for determining the potentials of an electrical network is proposed. The graph is represented as an electrical network, where the edge weights are interpreted as electrical conductivities. Next, the current is supplied to one of the vertices, and the absolute potentials of all vertices are determined by the Kirchhoff method. Based on the obtained potential values, the vertices are ranked. Then the current is sequentially applied to all vertices and the ranking is performed each time. For the final ranking, it is proposed to apply the ranking procedure based on the tournament matrix. The operation of the ranking algorithm is illustrated by numerical examples related to graphs of specific transport networks.

Keywords:

graph, centrality measure, ranking procedure, Kirchhoff’s circuit laws, transportation network, electrical circuit model

Downloads

Download data is not yet available.

References

Литература

Brandes U. Centrality measures based on current flow // STACS 2005. 22nd Annual Symposium on Theoretical Aspects of Computer Science. Stuttgart, Germany. February 24–26, 2005. Proceedings / eds by V. Diekert, B. Durand. Vol. 3404 of Lecture Notes in Computer Science. Stuttgart: Springer, 2005. P. 533-544. https://doi.org/10.1007/978-3-540-31856-9_44

Newman M. E. J. A measure of betweenness centrality based on random walks // Social Networks. 2005. Vol. 27. P. 39-54. http://dx.doi.org/10.1016/j.socnet.2004.11.009

Avrachenkov K., Litvak N., Medyanikov V., Sokol M. Alpha current flow betweenness centrality // Algorithms and Models for the Web Graph. 10th International Workshop, WAW 2013. Cambridge, MA, USA, December 14-15, 2013. Proceedings / eds by A. Bonato, M. Mitzenmacher, P. Pralat. Vol. 8305 of Lecture Notes in Computer Science. Cambridge: Springer, 2013. P. 106-117. https://doi.org/10.1007/978-3-319-03536-9_9

Avrachenkov K. E., Mazalov V. V., Tsynguev B. T. Beta current flow centrality for weighted networks // Computational Social Networks. 4th International Conference, CSoNet 2015. Beijing, China, August 4-6, 2015. Proceedings. Lecture Notes in Computer Science N 9197. 2015. P. 216-227. https://doi.org/10.1007/978-3-319-21786-4_19

Gomez D., Gonzalez-Aranguena E., Manuel C., Owen G., Pozo M., Tejada J. Centrality and power in social networks: a game theoretic approach // Math. Soc. Sci. 2003. Vol. 46. N 1. P. 27-54. https://doi.org/10.1016/S0165-4896(03)00028-3

Suna P., Parilina E. M., Gaob H. W. Two-stage network games modeling the Belt and Road Initiative // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2022. Т. 18. Вып. 1. С. 87-98. https://doi.org/10.21638/11701/spbu10.2022.107

Мазалов В. В., Хитрая В. А., Хитрый А. В. Методы теории кооперативных игр в задаче ранжирования текстов // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2022. Т. 18. Вып. 1. C. 63-78. https://doi.org/10.21638/11701/spbu10.2022.105

Kondratev A. A., Mazalov V. V. Ranking procedure with the Shapley value // Intelligent Information and Database Systems - 9th Asian Conference, ACIIDS 2017. Kanazawa, Japan, April 3-5, 2017. Proceedings. Pt II / eds by N. T. Nguyen, S. Tojo, L. M. Nguyen, B. Trawinski. Vol. 10192 of Lecture Notes in Computer Science. 2017. P. 691-700. https://doi.org/10.1007/978-3-319-54430-4_66

Алескеров Ф. Т., Хабина Е. Л., Шварц Д. А. Бинарные отношения, графы и коллективные решения. Примеры и задачи: учеб. пособие для вузов. М.: Изд-во Юрайт, 2023. 458 с.

Page L., Brin S., Motwani R., Winograd T. The pagerank citation ranking: Bringing order to the Web // Proceedings of the 7th International World Wide Web Conference. Brisbane, Australia. 1998. P. 161-172. https://citeseer.nj.nec.com/page98pagerank.html

Ermolin N. A., Khitraya V. A., Khitryi A. V., Mazalov V. V., Nikitina N. N. Modeling of the city’s transport network using game-theoretic methods on the example of Petrozavodsk // Contributions to Game Theory and Management. 2022. Vol. 15. P. 18-31.

Mazalov V. V., Khitraya V. A. A modified Myerson value for determining the centrality of graph vertices // Automation and Remote Control. 2021. Vol. 82. Iss. 1. P. 145-159.

Stroeymeyt N., Grasse A. V., Crespi A., Mersch D. P., Cremer S., Keller L. Social network plasticity decreases disease transmission in a eusocial insect // Science. 2006. Vol. 362. P. 941-945.

References

Brandes U. Centrality measures based on current flow. STACS 2005. 22nd Annual Symposium on Theoretical Aspects of Computer Science. Stuttgart, Germany, February 24-26, 2005. Proceedings. Eds by V. Diekert, B. Durand. Vol. 3404 of Lecture Notes in Computer Science. Stuttgart, Springer Publ., 2005, pp. 533-544. https://doi.org/10.1007/978-3-540-31856-9_44

Newman M. E. J. A measure of betweenness centrality based on random walks. Social Networks, 2005, vol. 27, pp. 39-54. http://dx.doi.org/10.1016/j.socnet.2004.11.009

Avrachenkov K., Litvak N., Medyanikov V., Sokol M. Alpha current flow betweenness centrality. Algorithms and Models for the Web Graph. 10th International Workshop, WAW 2013. Cambridge, MA, USA, December 14-15, 2013. Proceedings. Eds. by A. Bonato, M. Mitzenmacher, P. Pralat. Vol. 8305 of Lecture Notes in Computer Science. Cambridge, Springer Publ., 2013, pp. 106-117. https://doi.org/10.1007/978-3-319-03536-9_9

Avrachenkov K. E., Mazalov V. V., Tsynguev B. T. Beta current flow centrality for weighted networks. Computational Social Networks. 4th International Conference, CSoNet 2015. Beijing, China, August 4-6, 2015. Proceedings. Lecture Notes in Computer Science, 2015, no. 9197, pp. 216-227. https://doi.org/10.1007/978-3-319-21786-4_19

Gomez D., Gonzalez-Aranguena E., Manuel C., Owen G., Pozo M., Tejada J. Centrality and power in social networks: a game theoretic approach. Math. Soc. Sci., 2003, vol. 46, no. 1, pp. 27-54. https://doi.org/10.1016/S0165-4896(03)00028-3

Suna P., Parilina E. M., Gaob H. W. Two-stage network games modeling the Belt and Road Initiative. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2022, vol. 18, iss. 1, pp. 87-98. https://doi.org/10.21638/11701/spbu10.2022.107

Mazalov V. V., Khitraya V. A., Khitryi A. V. Metody teorii kooperativnykh igr v zadache ranzhirovaniia tekstov [Cooperative game theory methods for text ranking]. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2022, vol. 18, iss. 1, pp. 63-78. https://doi.org/10.21638/11701/spbu10.2022.105 (In Russian)

Kondratev A. A., Mazalov V. V. Ranking procedure with the Shapley value. Intelligent Information and Database Systems - 9th Asian Conference, ACIIDS 2017. Kanazawa, Japan, April 3-5, 2017. Proceedings. Pt II. Eds by N. T. Nguyen, S. Tojo, L. M. Nguyen, B. Trawinski. Vol. 10192 of Lecture Notes in Computer Science, 2017, pp. 691–700. https://doi.org/10.1007/978-3-319-54430-4_66

Aleskerov F. T., Habina E. L., Shvarc D. A. Binarnye otnosheniia, grafy i kollektivnye resheniia. Primery i zadachi. Uchebnoe posobie dlia vuzov [ Binary relations, graphs and collective solutions. Examples and tasks. Textbook for universities ]. Moscow, Uright Press, 2023, 458 p. (In Russian)

Page L., Brin S., Motwani R., Winograd T. The pagerank citation ranking: Bringing order to the Web. Proceedings of the 7th International World Wide Web Conference. Brisbane, Australia, 1998, pp. 161-172. https://citeseer.nj.nec.com/page98pagerank.html

Ermolin N. A., Khitraya V. A., Khitryi A. V., Mazalov V. V., Nikitina N. N. Modeling of the city’s transport network using game-theoretic methods on the example of Petrozavodsk. Contributions to Game Theory and Management, 2022, vol. 15, pp. 18-31.

Mazalov V. V., Khitraya V. A. A modified Myerson value for determining the centrality of graph vertices. Automation and Remote Control, 2021, vol. 82, iss. 1, pp. 145-159.

Stroeymeyt N., Grasse A. V., Crespi A., Mersch D. P., Cremer S., Keller L. Social network plasticity decreases disease transmission in a eusocial insect. Science, 2006, vol. 362, pp. 941-945.