12 CHAPTER 2. BACKGROUND AND TRADITIONAL APPROACHES
we require positive centrality values, we can apply the Perron-Frobenius Theo-
rem
1
to further determine that the vector of centrality values e is given by the
eigenvector corresponding to the largest eigenvalue of A [Newman, 2016].
One view of eigenvector centrality is that it ranks the likelihood that a node
is visited on a random walk of infinite length on the graph. This view can be
illustrated by considering the use of power iteration to obtain the eigenvector
centrality values. That is, since λ is the leading eigenvector of A, we can
compute e using power iteration via
2
e
(t+1)
= Ae
(t)
. (2.4)
If we start off this power iteration with the vector e
(0)
= (1, 1, ..., 1)
>
, then we
can see that after the first iteration e
(1)
will contain the degrees of all the nodes.
In general, at iteration t ≥ 1, e
(t)
will contain the number of length-t paths
arriving at each node. Thus, by iterating this process indefinitely we obtain a
score that is proportional to the number of times a node is visited on paths of
infinite length. This connection between node importance, random walks, and
the spectrum of the graph adjacency matrix will return often throughout the
ensuing sections and chapters of this book.
Returning to our example of the Florentine marriage network, if we compute
the eigenvector centrality values on this graph, we again see that the Medici
family is the most influential, with a normalized value of 0.43 compared to the
next-highest value of 0.36. There are, of course, other measures of centrality that
we could use to characterize the nodes in this graph—some of which are even
more discerning with respect to the Medici family’s influence. These include
betweeness centrality—which measures how often a node lies on the shortest
path between two other nodes—as well as closeness centrality—which measures
the average shortest path length between a node and all other nodes. These
measures and many more are reviewed in detail by Newman [2018].
The clustering coefficient
Measures of importance, such as degree and centrality, are clearly useful for dis-
tinguishing the prominent Medici family from the rest of the Florentine marriage
network. But what about features that are useful for distinguishing between the
other nodes in the graph? For example, the Peruzzi and Guadagni nodes in the
graph have very similar degree (3 v.s. 4) and similar eigenvector centralities
(0.28 v.s. 0.29). However, looking at the graph in Figure 2.1, there is a clear
difference between these two families. Whereas the the Peruzzi family is in the
midst of a relatively tight-knit cluster of families, the Guadagni family occurs
in a more “star-like” role.
1
The Perron-Frobenius Theorem is a fundamental result in linear algebra, proved inde-
pendently by Oskar Perron and Georg Frobenius [Meyer, 2000]. The full theorem has many
implications, but for our purposes the key assertion in the theorem is that any irreducible
square matrix has a unique largest real eigenvalue, which is the only eigenvalue whose corre-
sponding eigenvector can be chosen to have strictly positive components.
2
Note that we have ignored the normalization in the power iteration computation for
simplicity, as this does not change the main result.
我的内容管理
展开
