|
This article is cited in 4 scientific papers (total in 4 papers)
Computer science
Graph vertices ranking using absolute potentials of electric circuit nodes
V. V. Mazalov, V. A. Khitraya Federal Research Center “Karelian Research Center of the Russian Academy of Sciences’’, 11, Pushkinskaya ul., Petrozavodsk, Republic of Karelia, 185910, Russian Federation Petrozavodsk State University, 33, pr. Lenina, Petrozavodsk, Republic of Karelia, 185910, Russian Federation
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.
Received: March 4, 2023 Accepted: April 25, 2023
Citation:
V. V. Mazalov, V. A. Khitraya, “Graph vertices ranking using absolute potentials of electric circuit nodes”, Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr., 19:2 (2023), 233–250
Linking options:
https://www.mathnet.ru/eng/vspui580 https://www.mathnet.ru/eng/vspui/v19/i2/p233
|
Statistics & downloads: |
Abstract page: | 49 | Full-text PDF : | 15 | References: | 23 |
|