Pavel Chebotarev

Pavel Chebotarev, Rafig Agaev

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.

Rafig Agaev, Pavel Chebotarev

The paper studies the problem of achieving consensus in multi-agent systems in the case where the dependency digraph $Γ$ has no spanning in-tree. We consider the regularization protocol that amounts to the addition of a dummy agent (hub) uniformly connected to the agents. The presence of such a hub guarantees the achievement of an asymptotic consensus. For the "evaporation" of the dummy agent, the strength of its influences on the other agents vanishes, which leads to the concept of latent consensus. We obtain a closed-form expression for the consensus when the connections of the hub are symmetric, in this case, the impact of the hub upon the consensus remains fixed. On the other hand, if the hub is essentially influenced by the agents, whereas its influence on them tends to zero, then the consensus is expressed by the scalar product of the vector of column means of the Laplacian eigenprojection of $Γ$ and the initial state vector of the system. Another protocol, which assumes the presence of vanishingly weak uniform background links between the agents, leads to the same latent consensus.

Rafig Agaev, Pavel Chebotarev

We show that any discrete opinion pooling procedure with positive weights can be asymptotically approximated by DeGroot's procedure whose communication digraph is a Hamiltonian cycle with loops. In this cycle, the weight of each arc (which is not a loop) is inversely proportional to the influence of the agent the arc leads to.

Sergei Parsegov, Pavel Chebotarev

The paper addresses the problem of consensus seeking among second-order linear agents interconnected in a specific ring topology. Unlike the existing results in the field dealing with one-directional digraphs arising in various cyclic pursuit algorithms or two-directional graphs, we focus on the case where some arcs in a two-directional ring graph are dropped in a regular fashion. The derived condition for achieving consensus turns out to be independent of the number of agents in a network.

Pavel Chebotarev, Rafig Agaev

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.

Rafig Agaev, Pavel Chebotarev

In this paper, we propose several consensus protocols of the first and second order for networked multi-agent systems and provide explicit representations for their asymptotic states. These representations involve the eigenprojection of the Laplacian matrix of the dependency digraph. In particular, we study regularization models for the problem of coordination when the dependency digraph does not contain a converging tree. In such models of the first kind, the system is supplemented by a dummy agent, a "hub" that uniformly, but very weakly influences the agents and, in turn, depends on them. In the models of the second kind, we assume the presence of very weak background links between the agents. Besides that, we present a description of the asymptotics of the classical second-order consensus protocol.

Vladimir Ivashkin, Pavel Chebotarev

Graph measures that express closeness or distance between nodes can be employed for graph nodes clustering using metric clustering algorithms. There are numerous measures applicable to this task, and which one performs better is an open question. We study the performance of 25 graph measures on generated graphs with different parameters. While usually measure comparisons are limited to general measure ranking on a particular dataset, we aim to explore the performance of various measures depending on graph features. Using an LFR graph generator, we create a dataset of 11780 graphs covering the whole LFR parameter space. For each graph, we assess the quality of clustering with k-means algorithm for each considered measure. Based on this, we determine the best measure for each area of the parameter space. We find that the parameter space consists of distinct zones where one particular measure is the best. We analyze the geometry of the resulting zones and describe it with simple criteria. Given particular graph parameters, this allows us to recommend a particular measure to use for clustering.

Rinat Aynulin, Pavel Chebotarev

Proximity measures on graphs have a variety of applications in network analysis, including community detection. Previously they have been mainly studied in the context of networks without attributes. If node attributes are taken into account, however, this can provide more insight into the network structure. In this paper, we extend the definition of some well-studied proximity measures to attributed networks. To account for attributes, several attribute similarity measures are used. Finally, the obtained proximity measures are applied to detect the community structure in some real-world networks using the spectral clustering algorithm.

Pavel Chebotarev, Dmitry Gubanov

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, Yana Tsodikova, Anton Loginov et al.

In this paper, we study the efficiency of egoistic and altruistic strategies within the model of social dynamics determined by voting in a stochastic environment (the ViSE model) using two criteria: maximizing the average capital increment and minimizing the number of bankrupt participants. The proposals are generated stochastically; three families of the corresponding distributions are considered: normal distributions, symmetrized Pareto distributions, and Student's $t$-distributions. It is found that the "pit of losses" paradox described earlier does not occur in the case of heavy-tailed distributions. The egoistic strategy better protects agents from extinction in aggressive environments than the altruistic ones, however, the efficiency of altruism is higher in more favorable environments. A comparison of altruistic strategies with each other shows that in aggressive environments, everyone should be supported to minimize extinction, while under more favorable conditions, it is more efficient to support the weakest participants. Studying the dynamics of participants' capitals we identify situations where the two considered criteria contradict each other. At the next stage of the study, combined voting strategies and societies involving participants with selfish and altruistic strategies will be explored.

Vladimir Ivashkin, Pavel Chebotarev

We consider a number of graph kernels and proximity measures including commute time kernel, regularized Laplacian kernel, heat kernel, exponential diffusion kernel (also called "communicability"), etc., and the corresponding distances as applied to clustering nodes in random graphs and several well-known datasets. The model of generating random graphs involves edge probabilities for the pairs of nodes that belong to the same class or different predefined classes of nodes. It turns out that in most cases, logarithmic measures (i.e., measures resulting after taking logarithm of the proximities) perform better while distinguishing underlying classes than the "plain" measures. A comparison in terms of reject curves of inter-class and intra-class distances confirms this conclusion. A similar conclusion can be made for several well-known datasets. A possible origin of this effect is that most kernels have a multiplicative nature, while the nature of distances used in cluster algorithms is an additive one (cf. the triangle inequality). The logarithmic transformation is a tool to transform the first nature to the second one. Moreover, some distances corresponding to the logarithmic measures possess a meaningful cutpoint additivity property. In our experiments, the leader is usually the logarithmic Communicability measure. However, we indicate some more complicated cases in which other measures, typically, Communicability and plain Walk, can be the winners.

Konstantin Avrachenkov, Pavel Chebotarev, Alexey Mishenin

We study a semi-supervised learning method based on the similarity graph and RegularizedLaplacian. We give convenient optimization formulation of the Regularized Laplacian method and establishits various properties. In particular, we show that the kernel of the methodcan be interpreted in terms of discrete and continuous time random walks and possesses several importantproperties of proximity measures. Both optimization and linear algebra methods can be used for efficientcomputation of the classification functions. We demonstrate on numerical examples that theRegularized Laplacian method is competitive with respect to the other state of the art semi-supervisedlearning methods.

Rafig Agaev, Pavel Chebotarev

For the case where the dependency digraph has no spanning in-tree, we characterize the region of convergence of the basic continuous-time distributed consensus algorithm and show that consensus can be achieved by employing the method of orthogonal projection, which has been proposed for the discrete-time coordination problem.

Pavel Chebotarev, Rafig Agaev

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.

Pavel Chebotarev

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.