BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Pavel Chebotarev

Pavel Chebotarev contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete Mathematicsmath.MGmath.OCMultiagent SystemsNetworking and Internet Architecturemath.RASystems and ControlSocial and Information NetworksComputer Visionmath.NAmath.PR

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
13works
0followers
12topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2013arXiv

Matrices of forests, analysis of networks, and ranking problems

The matrices of spanning rooted forests are studied as a tool for analysing the structure of networks and measuring their properties. The problems of revealing the basic bicomponents, measuring vertex proximity, and ranking from preference relations / sports competitions are considered. It is shown that the vertex accessibility measure based on spanning forests has a number of desirable properties. An interpretation for the stochastic matrix of out-forests in terms of information dissemination is given.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The forest consensus theorem

We show that the limiting state vector in the differential model of consensus seeking with an arbitrary communication digraph is obtained by multiplying the eigenprojection of the Laplacian matrix of the model by the vector of initial states. Furthermore, the eigenprojection coincides with the stochastic matrix of maximum out-forests of the weighted communication digraph. These statements make the forests consensus theorem. A similar result for DeGroot's iterative pooling model requires the Cesaro (time-average) limit in the general case. The forests consensus theorem is useful for the analysis of consensus protocols.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Simple expressions for the long walk distance

The walk distances in graphs are defined as the result of appropriate transformations of the $\sum_{k=0}^\infty(tA)^k$ proximity measures, where $A$ is the weighted adjacency matrix of a connected weighted graph and $t$ is a sufficiently small positive parameter. The walk distances are graph-geodetic, moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter $t$ approaches its limiting values. In this paper, simple expressions for the long walk distance are obtained. They involve the generalized inverse, minors, and inverses of submatrices of the symmetric irreducible singular M-matrix ${\cal L}=ρI-A,$ where $ρ$ is the Perron root of $A.$

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Walk Distances in Graphs

The walk distances in graphs are defined as the result of appropriate transformations of the $\sum_{k=0}^\infty(tA)^k$ proximity measures, where $A$ is the weighted adjacency matrix of a graph and $t$ is a sufficiently small positive parameter. The walk distances are graph-geodetic; moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter $t$ approaches its limiting values. We also show that the logarithmic forest distances which are known to generalize the resistance distance and the shortest path distance are a subclass of walk distances. On the other hand, the long walk distance is equal to the resistance distance in a transformed graph.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Class of Graph-Geodetic Distances Generalizing the Shortest-Path and the Resistance Distances

A new class of distances for graph vertices is proposed. This class contains parametric families of distances which reduce to the shortest-path, weighted shortest-path, and the resistance distances at the limiting values of the family parameters. The main property of the class is that all distances it comprises are graph-geodetic: $d(i,j)+d(j,k)=d(i,k)$ if and only if every path from $i$ to $k$ passes through $j$. The construction of the class is based on the matrix forest theorem and the transition inequality.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Addendum to the paper "On determining the eigenprojection and components of a matrix" [arXiv:math/0508197]

The purpose of this note is to correct an inaccuracy in the paper: R.P. Agaev and P.Yu. Chebotarev, "On Determining the Eigenprojection and Components of a Matrix," Autom. Remote Control, 2002, vol. 63, pp. 1537-1545 [arXiv:math/0508197], and to present one of its results (namely, closed formulas for the eigenprojections and components of a matrix) in a simplified form.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Forest Metrics for Graph Vertices

We propose a new graph metric and study its properties. In contrast to the standard distance in connected graphs, it takes into account all paths between vertices. Formally, it is defined as d(i,j)=q_{ii}+q_{jj}-q_{ij}-q_{ji}, where q_{ij} is the (i,j)-entry of the {\em relative forest accessibility matrix} Q(ε)=(I+εL)^{-1}, L is the Laplacian matrix of the (weighted) (multi)graph, and εis a positive parameter. By the matrix-forest theorem, the (i,j)-entry of the relative forest accessibility matrix of a graph provides the specific number of spanning rooted forests such that i and j belong to the same tree rooted at i. Extremely simple formulas express the modification of the proposed distance under the basic graph transformations. We give a topological interpretation of d(i,j) in terms of the probability of unsuccessful linking i and j in a model of random links. The properties of this metric are compared with those of some other graph metrics. An application of this metric is related to clustering procedures such as "centered partition." In another procedure, the relative forest accessibility and the corresponding distance serve to choose the centers of the clusters and to assign a cluster to each non-central vertex. The notion of cumulative weight of connections between two vertices is proposed. The reasoning involves a reciprocity principle for weighted multigraphs. Connections between the resistance distance and the forest distance are established.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The graph bottleneck identity

A matrix $S=(s_{ij})\in{\mathbb R}^{n\times n}$ is said to determine a \emph{transitional measure} for a digraph $G$ on $n$ vertices if for all $i,j,k\in\{1,\...,n\},$ the \emph{transition inequality} $s_{ij} s_{jk}\le s_{ik} s_{jj}$ holds and reduces to the equality (called the \emph{graph bottleneck identity}) if and only if every path in $G$ from $i$ to $k$ contains $j$. We show that every positive transitional measure produces a distance by means of a logarithmic transformation. Moreover, the resulting distance $d(\cdot,\cdot)$ is \emph{graph-geodetic}, that is, $d(i,j)+d(j,k)=d(i,k)$ holds if and only if every path in $G$ connecting $i$ and $k$ contains $j$. Five types of matrices that determine transitional measures for a digraph are considered, namely, the matrices of path weights, connection reliabilities, route weights, and the weights of in-forests and out-forests. The results obtained have undirected counterparts. In [P. Chebotarev, A class of graph-geodetic distances generalizing the shortest-path and the resistance distances, Discrete Appl. Math., URL http://dx.doi.org/10.1016/j.dam.2010.11.017] the present approach is used to fill the gap between the shortest path distance and the resistance distance.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Comments on "Consensus and Cooperation in Networked Multi-Agent Systems"

This note corrects a pretty serious mistake and some inaccuracies in "Consensus and cooperation in networked multi-agent systems" by R. Olfati-Saber, J.A. Fax, and R.M. Murray, published in Vol. 95 of the Proceedings of the IEEE (2007, No. 1, P. 215-233). It also mentions several stronger results applicable to the class of problems under consideration and addresses the issue of priority whose interpretation in the above-mentioned paper is not exact.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Analytical Expression of the Expected Values of Capital at Voting in the Stochastic Environment

In the simplest version of the model of group decision making in the stochastic environment, the participants are segregated into egoists and a group of collectivists. A "proposal of the environment" is a stochastically generated vector of algebraic increments of participants' capitals. The social dynamics is determined by the sequence of proposals accepted by a majority voting (with a threshold) of the participants. In this paper, we obtain analytical expressions for the expected values of capitals for all the participants, including collectivists and egoists. In addition, distinctions between some principles of group voting are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Spanning Forests and the Golden Ratio

For a graph G, let f_{ij} be the number of spanning rooted forests in which vertex j belongs to a tree rooted at i. In this paper, we show that for a path, the f_{ij}'s can be expressed as the products of Fibonacci numbers; for a cycle, they are products of Fibonacci and Lucas numbers. The {\em doubly stochastic graph matrix} is the matrix F=(f_{ij})/f, where f is the total number of spanning rooted forests of G and n is the number of vertices in G. F provides a proximity measure for graph vertices. By the matrix forest theorem, F^{-1}=I+L, where L is the Laplacian matrix of G. We show that for the paths and the so-called T-caterpillars, some diagonal entries of F (which provides a measure of the self-connectivity of vertices) converge to ϕ^{-1} or to 1-ϕ^{-1}, where ϕis the golden ratio, as the number of vertices goes to infinity. Thereby, in the asymptotic, the corresponding vertices can be metaphorically considered as "golden introverts" and "golden extroverts," respectively. This metaphor is reinforced by a Markov chain interpretation of the doubly stochastic graph matrix, according to which F equals the overall transition matrix of a random walk with a random number of steps on G.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Preference fusion when the number of alternatives exceeds two: indirect scoring procedures

We consider the problem of aggregation of incomplete preferences represented by arbitrary binary relations or incomplete paired comparison matrices. For a number of indirect scoring procedures we examine whether or not they satisfy the axiom of self-consistent monotonicity. The class of {\em win-loss combining scoring procedures} is introduced which contains a majority of known scoring procedures. Two main results are established. According to the first one, every win-loss combining scoring procedure breaks self-consistent monotonicity. The second result provides a sufficient condition of satisfying self-consistent monotonicity.

0 citations0 reviewsNo code linkedOpen access