In graph theory, eigenvector centrality is a common measure to find the relative centrality of nodes in a graph or network. In the algorithm I notice that the node centrality are nothing but the eigenvector along the largest eigenvalue. And since the graph adjacent matrix is always positive, the largest eigenvector is also positive. Mathematically it is as following,
$$Av = \lambda v$$
where $A$ is adjacent matrix, $v$ is the eigenvector and $\lambda$ is eigenvalue.
So basically for the largest value of $\lambda$, we analyse $v$ for node centrality.
In a given scenario, I want to compare two weighted-directed graphs with same nodes but different edges. So my first idea was to compare the the eigenvector centrality of same nodes in two graphs to find how they differ. I can possibly do it for in-edges and out-edges separately to find the difference based on in-centrality and out-centrality for each node and then make a comparison. However, I am a bit confused in using it for comparison since an eigenvector is a unit vector. The eigenvector makes sense for comparing the intra-graph nodes where we see all nodes with respect to each other. On the other hand, for comparing nodes in two graphs, it becomes tricky as I am comparing the components of two different unit vectors, where each unit vector may possibly relate to a different eigenvalue.
So my question is, what would be the consequences if instead of using $v$, I use $\lambda v$ for make a cross-graph node comparison?
In my opinion, as $\lambda$ is a scaling factor to the unit eigenvectors, the scaled-eigenvectors, i.e. $\lambda v$, would remove the normalization (or change the unit eigenvectors to a scaled version), and so makes is suitable for comparison. (Or may be I am too naive to think like this)
Any suggestion, lead or reference to the literature is highly appreciated.
Thanks a lot in advance.
PS. I am dealing with smaller graphs with total nodes less than 30.
Best Answer
You have this backwards.
If $\boldsymbol x$ is an eigenvector of the greatest eigenvalue in one graph, and $\boldsymbol y$ is an eigenvector of the greatest eigenvalue in the other graph, and we normalize them to have $\|\boldsymbol x\| = \|\boldsymbol y\| = 1$, then it's valid to compare their entries. The condition $\|\boldsymbol x\| =1$ (with respect to any norm you like, as long as it's the same for both vectors) ensures that the "total amount of centrality" is fixed, which puts $x_v$ on a fixed scale. Essentially, $x_v$ measures the influence of vertex $v$ as a fraction of the total influence of all vertices.
It's meaningful to compare these: if $x_v > y_v$, then $v$ is more influential in the first graph than in the second.
On the other hand, if $\lambda$ is the eigenvalue of $\boldsymbol x$ in one graph, and $\lambda'$ is the eigenvalue of $\boldsymbol y$ in the other graph, then comparing $\lambda\boldsymbol x$ to $\lambda' \boldsymbol y$ is an unfair comparison. Maybe $\lambda$ is much smaller than $\lambda'$. In that case, comparing $\lambda \boldsymbol x$ to $\lambda'\boldsymbol y$ will tell you that even the most central vertex of the first graph is less central than it is in the second graph.
For example, you might be comparing a webpage's ranking at two different points in time. (For simplicity, let's say that all webpages exist at both times.) Suppose that the internet has gotten more connected overall; then $\lambda$ will increase over time. Comparing $x_v$ to $y_v$ will tell you if a webpage $v$ has gotten more or less influential. Comparing $\lambda \boldsymbol x$ to $\lambda' \boldsymbol y$ might just end up telling you that all webpages have gotten more influential, which would be nonsense.
Or maybe it wouldn't be. Depending on your application, you might care about different things from your eigenvalue measure. But in this case, you should start first by thinking about what those things are. What properties do you want from your cross-graph comparisons?
Here's an interesting example. Compare the following graphs:
Let $v$ be the vertex of degree $9$ in both graphs. If we normalize $\boldsymbol x$ by its $2$-norm and compare, then $v$ is more central in $K_{1,9}$. But if we scale by $\lambda$ first, then $v$ is more central in $K_{10}$. Which of these is reasonable?