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

Владимир Викторович Мазалов; Виталия Андреевна Хитрая

doi:10.21638/11701/spbu10.2023.209

Авторы

Владимир Викторович Мазалов Федеральный исследовательский центр «Карельский научный центр Российской академии наук», Российская Федерация, 185910, Петрозаводск, ул. Пушкинская, 11; Петрозаводский государственный университет, Российская Федерация, 185910, Петрозаводск, пр. Ленина, 33
Виталия Андреевна Хитрая Федеральный исследовательский центр «Карельский научный центр Российской академии наук», Российская Федерация, 185910, Петрозаводск, ул. Пушкинская, 11; Петрозаводский государственный университет, Российская Федерация, 185910, Петрозаводск, пр. Ленина, 33

DOI:

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

Аннотация

Предлагается метод ранжирования вершин графа на основе законов Кирхгофа для определения потенциалов электрической сети. Граф представляется в виде электрической сети, где веса ребер интерпретируются как электрические проводимости. Затем ток последовательно подается во все вершины и каждый раз определяются ранги вершин в соответствии с их потенциалами. Для окончательного ранжирования предлагается применять методы теории голосования на основе турнирной матрицы. Работа алгоритма ранжирования проиллюстрирована на численных примерах, связанных с графами конкретных транспортных сетей и графами взаимодействий муравьиной колонии.

Ключевые слова:

граф, меры центральности, ранжирование, законы Кирхгофа, транспортный граф, модель электрической цепи

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

Литература

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.