Aggregating nonnegative eigenvectors of the adjacency matrix as a measure of centrality for a directed graph

Eigenvector centrality is a popular measure that uses the principal eigenvector of the adjacency matrix to distinguish importance of nodes in a graph. To find the principal eigenvector, the power method iterating from a random initial vector is often adopted. In this article, we consider the adjacency matrix of a directed graph and choose suitable initial vectors according to strongly connected components of the graph instead so that nonnegative eigenvectors, including the principal one, can be found. Consequently, for aggregating nonnegative eigenvectors, we propose a weighted measure of centrality, called the aggregated-eigenvector centrality. Weighting each nonnegative eigenvector by the reachability of the associated strongly connected component, we can obtain a measure that follows a status hierarchy in a directed graph.     

Continuous-Time Independent Edge-Markovian Random Graph Process

In this paper, the continuous-time independent edge-Markovian random graph process model is constructed. The authors also define the interval isolated nodes of the random graph process, study the distribution sequence of the number of isolated nodes and the probability of having no isolated nodes when the initial distribution of the random graph process is stationary distribution, derive the lower limit of the probability in which two arbitrary nodes are connected and the random graph is also connected, and prove that the random graph is almost everywhere connected when the number of nodes is sufficiently large.     

An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters

A comparison technique for random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be invariant with respect to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive graph.     

Random walks on trees

The classical gambler's ruin problem, i.e., a random walk along a line may be viewed graph theoretically as a random walk along a path with the endpoints as absorbing states. This paper is an investigation of the natural generalization of this problem to that of a particle walking randomly on a tree with the endpoints as absorbing barriers. Expressions in terms of the graph structure are obtained from the probability of absorption at an endpoint e in a walk originating from a vertex v, as well as for the expected length of the walk.     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

具有联盟结构的position值

position值是图对策中著名的分支有效解, 该值充分体现了图的边在合作中的贡献, 因而也可作为网络中心性的一种测度方法。本文基于van den Brink等提出的具有联盟结构与图结构的合作对策, 将position值推广到具有联盟结构的图对策上, 提出了具有联盟结构的position值, 该值可以作为受优先联盟约束的网络中心性的一种测度方法。本文首先证明了具有联盟结构的position值可以由分割分支有效性和平衡边贡献性所唯一刻画。其次, 以跨国天然气管道网的收益分配为例, 对这个值与其他值做了比较分析。     

有向图上的随机游动

设G=(V,Г)是有向图,G上的随机游动X(G)定义如下:位于某个顶点上的一个粒子将以等概率转移到该顶点的所有后继顶点.令M(j,n)表示随机游动X(G)在前n步内访问顶点j的平均次数,用W(j)表示随机游动X(G)到达顶点j所需要的平均步效.我们对M(j,n)和W(j)的值进行了估计,证明了M(j,n)=O(n),并给出了W(j)的上界.     

Random walk centrality and a partition of Kemeny’s constant

We consider an accessibility index for the states of a discrete-time, ergodic, homogeneous Markov chain on a finite state space; this index is naturally associated with the random walk centrality introduced by Noh and Reiger (2004) for a random walk on a connected graph. We observe that the vector of accessibility indices provides a partition of Kemeny’s constant for the Markov chain. We provide three characterizations of this accessibility index: one in terms of the first return time to the state in question, and two in terms of the transition matrix associated with the Markov chain. Several bounds are provided on the accessibility index in terms of the eigenvalues of the transition matrix and the stationary vector, and the bounds are shown to be tight. The behaviour of the accessibility index under perturbation of the transition matrix is investigated, and examples exhibiting some counter-intuitive behaviour are presented. Finally, we characterize the situation in which the accessibility indices for all states coincide.     

Linear cover time is exponentially unlikely

We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small. We conjecture that the same holds for any simple graph.     

Hitting Times,Cover Cost,and the Wiener Index of a Tree

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are “easier to reach” by a random walk, but “more difficult to get out of.” We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self‐contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.     

拟顶点可迁图上简单随机游走的切割点

证明了体积增长不低于5次多项式的拟顶点可迁图上的简单随机游走几乎处处有无穷多个切割时,从而有无穷多个切割点.该结论在所论情形下肯定了Benjamini,Gurel-Gurevich和Schramm在文[2011,Cutpoints and resistance of random walk paths,Ann.Probab.,39(3):1122-1136]中提出的猜想:顶点可迁图上暂留简单随机游走几乎处处有无穷多个切割点.     

一类随机图的演化

定义一随机图过程:如果图Gt-1不是完全图时,图Gt分别以概率p和q加一个点和一条有向边;如果图Gt-1是完全图时,则以概率1加一个点．研究图Gt顶点和边的概率分布以及当顶点数固定时,边数的期望界值估计．     

Hamiltonicity of random graphs produced by 2‐processes

Suppose that a random graph begins with n isolated vertices and evolves by edges being added at random, conditional upon all vertex degrees being at most 2. The final graph is usually 2‐regular, but is not uniformly distributed. Some properties of this final graph are already known, but the asymptotic probability of being a Hamilton cycle was not known. We answer this question along with some related questions about cycles arising in the process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Lower bounds for transition probabilities on graphs

The paper presents two results. The first one provides separate conditions for the upper and lower estimates of the distribution of the time of exit from balls of a random walk on a weighted graph. The main result of the paper is that the lower estimate follows from the elliptic Harnack inequality. The second result is an off-diagonal lower bound for the transition probability of the random walk.     

Information flow in graphs

A formula is obtained for the global flow of information in a discrete Markov system which is defined on a locally finite graph. It is shown that the information flow is related to a random walk on the lattice of finite subgraphs of the graph.     

Asymptotic normality in random graphs with given vertex degrees

We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph.     

A random walk on a circular path

This short note introduces an interesting random walk on a circular path with cards of numbers. By using high school probability theory, it is proved that under some assumptions on the number of cards, the probability that a walker will return to a fixed position will tend to one as the length of the circular path tends to infinity.     

Persistence of centrality in random growing trees

We investigate properties of node centrality in random growing tree models. We focus on a measure of centrality that computes the maximum subtree size of the tree rooted at each node, with the most central node being the tree centroid. For random trees grown according to a preferential attachment model, a uniform attachment model, or a diffusion processes over a regular tree, we prove that a single node persists as the tree centroid after a finite number of steps, with probability 1. Furthermore, this persistence property generalizes to the top K ≥ 1 nodes with respect to the same centrality measure. We also establish necessary and sufficient conditions for the size of an initial seed graph required to ensure persistence of a particular node with probability , as a function of ϵ: In the case of preferential and uniform attachment models, we derive bounds for the size of an initial hub constructed around the special node. In the case of a diffusion process over a regular tree, we derive bounds for the radius of an initial ball centered around the special node. Our necessary and sufficient conditions match up to constant factors for preferential attachment and diffusion tree models.     

The survival of branching annihilating random walk

Summary Branching annihilating random walk is an interacting particle system on . As time evolves, particles execute random walks and branch, and disappear when they meet other particles. It is shown here that starting from a finite number of particles, the system will survive with positive probability if the random walk rate is low enough relative to the branching rate, but will die out with probability one if the random walk rate is high. Since the branching annihilating random walk is non-attractive, standard techniques usually employed for interacting particle systems are not applicable. Instead, a modification of a contour argument by Gray and Griffeath is used.     

Hitting times for random walks on subdivision and triangulation graphs

Let G be a connected graph. The subdivision graph of G, denoted by S(G), is the graph obtained from G by inserting a new vertex into every edge of G. The triangulation graph of G, denoted by R(G), is the graph obtained from G by adding, for each edge uv, a new vertex whose neighbours are u and v. In this paper, we first provide complete information for the eigenvalues and eigenvectors of the probability transition matrix of a random walk on S(G) (res. R(G)) in terms of those of G. Then we give an explicit formula for the expected hitting time between any two vertices of S(G) (res. R(G)) in terms of those of G. Finally, as applications, we show that, the relations between the resistance distances, the number of spanning trees and the multiplicative degree-Kirchhoff index of S(G) (res. R(G)) and G can all be deduced from our results directly.