Geodesic
Graph vertices ranking using absolute potentials of electric circuit nodes
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 19 (2023) no. 2, pp. 233-250 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{VSPUI_2023_19_2_a8,
     author = {V. V. Mazalov and V. A. Khitraya},
     title = {Graph vertices ranking using absolute potentials of electric circuit nodes},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {233--250},
     year = {2023},
     volume = {19},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2023_19_2_a8/}
}
TY  - JOUR
AU  - V. V. Mazalov
AU  - V. A. Khitraya
TI  - Graph vertices ranking using absolute potentials of electric circuit nodes
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2023
SP  - 233
EP  - 250
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2023_19_2_a8/
LA  - ru
ID  - VSPUI_2023_19_2_a8
ER  - 
%0 Journal Article
%A V. V. Mazalov
%A V. A. Khitraya
%T Graph vertices ranking using absolute potentials of electric circuit nodes
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2023
%P 233-250
%V 19
%N 2
%U http://geodesic.mathdoc.fr/item/VSPUI_2023_19_2_a8/
%G ru
%F VSPUI_2023_19_2_a8
V. V. Mazalov; V. A. Khitraya. Graph vertices ranking using absolute potentials of electric circuit nodes. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 19 (2023) no. 2, pp. 233-250. http://geodesic.mathdoc.fr/item/VSPUI_2023_19_2_a8/

[1] Brandes U., “Centrality measures based on current flow”, 22$^{\rm nd}$ Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005, Proceedings (Stuttgart, Germany, February 24-26, 2005), Lecture Notes in Computer Science, 3404, eds. V. Diekert, B. Durand, Springer, Stuttgart, 2005, 533–544 | DOI | MR | Zbl

[2] Newman M. E. J., “A measure of betweenness centrality based on random walks”, Social Networks, 27 (2005), 39–54 | DOI

[3] Avrachenkov K., Litvak N., Medyanikov V., Sokol M., “Alpha current flow betweenness centrality”, Algorithms and Models for the Web Graph, 10$^{\rm th}$ International Workshop, WAW 2013, Proceedings (Cambridge, MA, USA, December 14–15, 2013), Lecture Notes in Computer Science, 8305, eds. A. Bonato, M. Mitzenmacher, P. Pralat, Springer, Cambridge, 2013, 106–117 | DOI | MR | Zbl

[4] Avrachenkov K. E., Mazalov V. V., Tsynguev B. T., “Beta current flow centrality for weighted networks”, Computational Social Networks, 4$^{\rm th}$ International Conference, CSoNet 2015, Proceedings (Beijing, China, August 4–6, 2015), Lecture Notes in Computer Science, 9197, 2015, 216–227 | DOI

[5] Gómez D., González-Arangüena E., Manuel C., Owen G., Pozo M., Tejada J., “Centrality and power in social networks: a game theoretic approach”, Math. Soc. Sci., 46:1 (2003), 27–54 | DOI | MR | Zbl

[6] 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, 18:1 (2022), 87–98 | DOI | MR

[7] Mazalov V. V., Khitraya V. A., Khitryi A. V., “Cooperative game theory methods for text ranking]”, Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 18:1 (2022), 63–78 (In Russian) | DOI | MR

[8] Kondratev A. A., Mazalov V. V., “Ranking procedure with the Shapley value”, Intelligent Information and Database Systems — 9$^{\rm th}$ Asian Conference, ACIIDS 2017, Proceedings (Kanazawa, Japan, April 3–5, 2017), v. II, Lecture Notes in Computer Science, 10192, eds. N. T. Nguyen, S. Tojo, L. M. Nguyen, B. Trawinski, 2017, 691–700 | DOI

[9] Aleskerov F. T., Habina E. L., Shvarc D. A., Binary relations, graphs and collective solutions. Examples and tasks, Textbook for universities, Uright Press, M., 2023, 458 pp. (In Russian)

[10] Page L., Brin S., Motwani R., Winograd T., “The pagerank citation ranking: Bringing order to the Web”, Proceedings of the 7$^{\rm th}$ International World Wide Web Conference (Brisbane, Australia, 1998), 161–172 https://citeseer.nj.nec.com/page98pagerank.html | MR

[11] 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, 15 (2022), 18–31 | DOI | MR

[12] Mazalov V. V., Khitraya V. A., “A modified Myerson value for determining the centrality of graph vertices”, Automation and Remote Control, 82:1 (2021), 145–159 | DOI | MR | Zbl

[13] 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, 362 (2006), 941–945 | DOI