Seeley's index

In graph theory, Seeley's index (also called Seeley index or simplified PageRank) is a measure of the influence of a node in a directed network. It is a form of eigenvector centrality in which each node splits its score equally among the nodes it points to, so that the score of a node is the sum of the scores of the nodes pointing to it, each divided by its out-degree. Equivalently, once normalized, Seeley's index is the stationary distribution of the random walk on the network. It was introduced in 1949 by the sociologist John R. Seeley to measure the popularity of the children of a group, given who liked whom.

PageRank is a damped version of Seeley's index, and tends to it as its damping factor tends to one.

Using the adjacency matrix to find Seeley's index

For a given directed graph ${\displaystyle G=(V,E)}$, let ${\displaystyle A=(a_{x,y})}$ be its adjacency matrix, that is, ${\displaystyle a_{x,y}=1}$ if there is an arc from ${\displaystyle x}$ to ${\displaystyle y}$, and ${\displaystyle a_{x,y}=0}$ otherwise, and assume that every vertex has at least one outgoing arc, so that its out-degree ${\displaystyle d^{+}(x)=\sum _{y\in V}a_{x,y}}$ is positive. The Seeley's index ${\displaystyle s_{x}}$ of a vertex ${\displaystyle x}$ satisfies

${\displaystyle s_{x}=\sum _{y\in V}{\frac {a_{y,x}}{d^{+}(y)}}s_{y},}$

that is, the score of ${\displaystyle x}$ is the sum of the scores of the vertices ${\displaystyle y}$ with an arc to ${\displaystyle x}$, each divided by the out-degree of ${\displaystyle y}$. Seeley noted that indices obtained by simply counting the choices received by an individual do not take into account that being liked by someone who is in turn liked a lot matters more: an index of importance should be defined recursively, so that the score of an individual is the weighted sum of the scores of those who endorse that individual.

Let ${\displaystyle P}$ be the matrix obtained by dividing each row of ${\displaystyle A}$ by its sum, that is, ${\displaystyle P=D^{-1}A}$, where ${\displaystyle D}$ is the diagonal matrix of the out-degrees. Then, the definition can be written as

${\displaystyle {\boldsymbol {s}}^{T}P={\boldsymbol {s}}^{T}.}$

The matrix ${\displaystyle P}$ is a stochastic matrix, as each of its rows sums to one: thus, 1 is an eigenvalue of ${\displaystyle P}$, and the equation above has nonzero solutions. By the Perron–Frobenius theorem, 1 is also the spectral radius of ${\displaystyle P}$, so Seeley's index is a dominant left eigenvector, and there are solutions with nonnegative entries; if the graph is strongly connected, the solution is unique up to a multiplicative constant, and positive. Seeley expressed the definition as a system of linear equations, solved by Cramer's rule.

Normalized so that its entries sum to one, Seeley's index is the stationary distribution of the Markov chain with transition matrix ${\displaystyle P}$, that is, of the random walk that at each step follows an arc chosen uniformly at random among those leaving the current vertex. It can be computed by power iteration from any distribution: the iterates may oscillate forever if the graph is periodic, but their averages (Cesàro means) converge to Seeley's index.

Relation to other centralities

Seeley's index and eigenvector centrality differ in the normalization of the rows of the adjacency matrix: in eigenvector centrality the whole score of a node contributes to the score of each of its successors, whereas in Seeley's index a node splits its score equally among its successors. The same difference separates Katz centrality from PageRank, which are damped versions of eigenvector centrality and of Seeley's index, respectively:

PageRank with damping factor ${\displaystyle \alpha }$ and preference vector ${\displaystyle {\boldsymbol {v}}}$ (a distribution) is

${\displaystyle {\boldsymbol {p}}_{\alpha }^{T}=(1-\alpha )\,{\boldsymbol {v}}^{T}\sum _{k\geq 0}\alpha ^{k}P^{k}=(1-\alpha )\,{\boldsymbol {v}}^{T}\left(I-\alpha P\right)^{-1}.}$

As ${\displaystyle \alpha \to 1}$, ${\displaystyle {\boldsymbol {p}}_{\alpha }^{T}}$ tends to ${\displaystyle {\boldsymbol {v}}^{T}}$ multiplied by the eigenprojection of ${\displaystyle P}$ associated with the eigenvalue 1, which, for a stochastic matrix, is the Cesàro limit of the powers of ${\displaystyle P}$:

${\displaystyle \lim _{\alpha \to 1}{\boldsymbol {p}}_{\alpha }^{T}={\boldsymbol {v}}^{T}\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=0}^{n-1}P^{k}.}$

Thus, the limit of PageRank is a Seeley's index: the limit distribution, in average, of the random walk started from ${\displaystyle {\boldsymbol {v}}}$. The preference vector, which is the distribution from which the damped walk restarts, becomes the starting distribution of the undamped one; it determines the limit only if the graph has more than one terminal strongly connected component, as otherwise Seeley's index is unique.

On undirected graphs, whose edges can be followed in both directions, Seeley's index is proportional to the degree, as the stationary distribution of the random walk on an undirected graph assigns to each vertex its degree divided by twice the number of edges. On graphs that are not strongly connected, every stationary distribution of the random walk is zero outside the terminal strongly connected components, that is, the components that no arc leaves: only nodes in these components can have a nonzero Seeley's index, and when there are several such components the index is not unique.

Axiomatic characterization

Altman and Tennenholtz gave a set of axioms characterizing the ranking (that is, the ordering of the nodes) induced by Seeley's index on strongly connected graphs; they call the measure PageRank, but their definition has no damping factor.

Applications

• Sociometry: Seeley introduced the index to measure the popularity of the children of a group, given who liked whom.
• World Wide Web: in the technical report introducing PageRank, Page, Brin, Motwani, and Winograd rediscover Seeley's index, with no reference to Seeley, as a "slightly simplified version of PageRank" of the graph of web pages and hyperlinks, whence the name simplified PageRank; they then add a "source of rank" to deal with groups of pages that accumulate rank without passing it on.
• Opinion dynamics: in the DeGroot model, agents repeatedly replace their opinions with weighted averages of the opinions of their neighbors; when the neighbors of each agent have equal weights, the influence of an agent on the final consensus is its Seeley's index, which on undirected networks is proportional to its degree.
• Sports: the logistic regression/Markov chain model ranks college basketball teams by the stationary distribution of a random walk on the teams in which, from a team, one of its games is chosen uniformly at random, and the walk moves to the winner or to the loser of the game with probabilities estimated by logistic regression.
• Ecology: to measure the importance of species for coextinctions in food webs, Allesina and Pascual use a dominant eigenvector in which each link carries an equal fraction of the importance of a species, after adding a root node, linked to all primary producers and from all species, to make the web strongly connected. They explicitly reject damping, as "nutrients cannot randomly 'jump' among links in the food web".

See also

• Centrality
• Eigenvector centrality
• Katz centrality
• PageRank

References

This article needs additional or more specific categories. Please help out by adding categories to it so that it can be listed with similar articles. (October 2026)