9
$\begingroup$

Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.

Two natural ways of doing it are:

  1. By the degrees.
  2. By the entries in a Perron eigenvector of the adjacency matrix.

These two methods coincide for regular graphs and for so-called harmonic graphs (defined as graphs in which the degree vector is an eigenvector) - which is all a tad trivial.

What is more interesting is that for many random graphs I've checked the two orderings coincide as well and I am able to show that they coincide for threshold graphs.

Have such graphs been studied?

I did find in the mathematical sociology literature some work on the question when the most central vertex w.r.t both rankings is the same but nothing for the whole vector.

(If such graphs haven't been named yet, I propose to call them tranquil, since tranquility is a lesser form of harmony).

P.S. Method 2 is essentially what Google does in its PageRank algorithm.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ A remark about PageRank: the PageRank vector with seed vector $s$ and jumping constant $\alpha \in (0,1)$ is the steady state for $v \mapsto \alpha v + (1-\alpha)AD^{-1}v$ where $A$ is the adjacency matrix and $D$ is the degree matrix. When $\alpha = 0$ the PageRank vector is the degree vector (it is the Perron eigenvector for the "random walk" matrix $A D^{-1}$. There is some literature on the question of how big $\alpha$ must be for the PageRank and degree vectors to give different orderings (depending on $s$) but I'm not sure this will help with your question. $\endgroup$
    – Paul Siegel
    Commented Sep 2, 2014 at 10:26

1 Answer 1

Reset to default
2
+100
$\begingroup$

I'm not sure how common this is. It may depend on how you are determining random graphs.

There may be ties so let me separate the issues of the equivalence relation "same rank" from those of the linear order among equivalence classes. In the case of ranking by degrees there will have to be at least one tie. In the case of the Perron ranking there might or might not be any ties. Vertices in the same orbit of the automorphism group will have the same rank in the Perron ranking (and equal degree). In the simplest graph with no automorphisms ( A seven vertex tree with leaves at distances $1,2,$ and $3$ from a central vertex) no two vertices get the same weight. It is true for this graph that the three lowest weights occur on the degree $1$ vertices and the highest weight on the unique degree $3$ vertex. Is this what you mean? Otherwise I'd expect "most" trees to fail.

Since vertices in the same orbit of the automorphism group will have the same rank in either system. If the automorphism group is degree transitive there is some chance that the two equivalence relations will be the same. This would partly explain threshold graphs. I say partly because I have not shown that the linear order on equivalence classes is according to degree. Perhaps this additional condition (which holds for threshold graphs) is enough: If there is a path $u,v,w$ with $v$ having lower degree than $u$ or $w$, then there is also an edge $u,w.$ That is just a guess, but I give an example below where this condition does not hold and the linear orders are not the same.

At the end I note a weaker condition than degree transitivity which suffices for same degree vertices to have equal Perron rank. It is useful for analyzing examples such as the following one:

Here is a rather symmetric graph where the linear order fails: Consider a graph with $26$ vertices belonging to classes $A,B,C,D$ of respective sizes $9,3,12,2$ and respective degrees $1,7,2,6.$ Each vertex in $B$ is connected to $3$ vertices from $A$ and $4$ from $C$ while each vertex in $D$ is connected to $6$ vertices from $C.$ Then the largest eigenvalue is roughly $3.38$ and a Perron eigenvector assigns weights of roughly $0.267,0.904,0.563,1$ to the classes. So the two degree $6$ vertices receive higher weight than the three degree $7$ vertices. In the similar example with degrees $1,5,2,4$ the vertices of degrees $4$ and $5$ both get equal weight.

Somewhat more general than degree transitivity is degree regularity: Suppose that the existing degrees are $d_1,d_2,\cdots,d_k$ and that there are $k^2$ integers $n_{ij}$ so that each vertex of degree $d_i$ has exactly $n_{ij}$ neighbors of degree $d_j$. Then the (right) Perron eigenvector of the $k \times k$ matrix with entries $n_{ij}$ lifts in an obvious way to the graph.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is degree regularity another way of saying that the degree partition is equitable? P.S. The remark about this explaining threshold graphs is very helpful - thanks! $\endgroup$
    – Felix Goldberg
    Commented Sep 2, 2014 at 11:11
  • $\begingroup$ As for the example in your 1st paragraph - yes, I consider this case to be ok (i.e. tranquil). Ties are fine. What renders a graph non-tranquil for me is the existence of two vertices $u,v$ such that $d_{u}>d_{v}$ and $Perron(u)<Perron(v)$. $\endgroup$
    – Felix Goldberg
    Commented Sep 2, 2014 at 11:12
  • $\begingroup$ Yes by degree regular I mean that the degree partition is equitable. The example I gave is essentially the same as a four vertex having a directed multigraph (equivalently: a directed graph with positive integer edge weights) whose incidence matrix has has above the diagonal $1,4,1$ and below $3,1,6$. It is easy to find the Perron Eigenvector of this small matrix and then to get a simple undirected graph one just replaces each node with indegree $a$ outdegree $b$ with a set of size a multiple of $\gcd(a,b).$ This approach would make it easy to investigate further. $\endgroup$
    – Aaron Meyerowitz
    Commented Sep 8, 2014 at 6:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .