Pavel Chebotarev

dblp:94/3624 · also Pavel Yu. Chebotarev · DBLP profile ↗
← Back
7ranked-venue papers
6as first author
2since 2021 · last 2025
0000-0001-8232-847XORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 5 · 4 first-author · 1 since 2021Human-computer interaction and ubiquitous computing · 1 · 1 first-author · 1 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author
YearPublicationVenuePosition
2025 How to Choose the Most Appropriate Centrality Measure? A Decision-Tree Approach
abstract
Centrality metrics play a crucial role in network analysis, while the choice of specific measures significantly influences the accuracy of conclusions as each measure represents a unique concept of node importance. Among over 400 proposed indices, selecting the most suitable ones for specific applications remains a challenge. Existing approaches—model-based, data-driven, and axiomatic—have limitations, requiring association with models, training datasets, or restrictive axioms for each specific application. To address this, we introduce the culling method, which relies on the expert concept of centrality behavior on simple graphs. The culling method involves forming a set of candidate measures, generating a list of as small graphs as possible needed to distinguish the measures from each other, constructing a decision-tree survey, and identifying the measure consistent with the expert’s concept. We apply this approach to a diverse set of 40 centralities, including novel kernel-based indices, and combine it with the axiomatic approach. Remarkably, only 13 small 1-trees are sufficient to separate all 40 measures, even for pairs of closely related ones. By adopting simple ordinal axioms like Self-consistency or Bridge axiom, the set of measures can be drastically reduced making the culling survey short. Applying the culling method provides insightful findings on some centrality indices, such as PageRank, Bridging, and dissimilarity-based Eigencentrality measures, among others. The proposed approach offers a cost-effective solution in terms of labor and time, complementing existing methods for measure selection, and providing deeper insights into the underlying mechanisms of centrality measures.
Pavel Chebotarev, Dmitry A. Gubanov
IEEE Trans. Syst. Man Cybern. Syst.1
2023 The power of small coalitions under two-tier majority on regular graphs
Pavel Chebotarev, David Peleg
Discret. Appl. Math.1
2017 Kernels on Graphs as Proximity Measures
Konstantin Avrachenkov, Pavel Chebotarev, Dmytro Rubanov
WAW2
2012 The walk distances in graphs
Pavel Chebotarev
Discret. Appl. Math.1
2011 A class of graph-geodetic distances generalizing the shortest-path and the resistance distances
Pavel Chebotarev
Discret. Appl. Math.1
2010 Comments on "Consensus and cooperation in networked multi-agent systems"
abstract
The objective of this note is to give several comments regarding consensus and cooperation in networked multi-agent systems, and to mention some closely related results published in 2000 and 2001. This paper focuses on the graph theoretic results underlying the analysis of consensus in multiagent systems. As stated in the Introduction, "Graph Laplacians and their spectral properties are important graph related matrices that play a crucial role in convergence analysis of consensus and alignment algorithms." In particular, the stability properties of the distributed consensus algorithms for networked multiagent systems are completely determined by the location of the Laplacian eigenvalues of the network.
Pavel Chebotarev
Proc. IEEE1
2008 Spanning forests and the golden ratio
Pavel Chebotarev
Discret. Appl. Math.1