Status and Prestige

In the last handout, we saw how to compute the most popular centrality measures. Freeman’s “big three” have strong graph-theoretic foundation and do a good job of formalizing and quantifying the idea that a node is central if it is “well-placed” in the network, where being well-placed resolves into either being able to reach others (directly as with degree or indirectly as with closeness) or being able to intermediate between others (as with betweenness).

Networks as Prisms

There is, however, another strong and well-motivated intuition as to what it means to be “well-placed” in a network. Here the ties in the network are seen less as “pipes” that transmit stuff and more like “prisms” that reflect on you (Podolny 2001).

One way to think about this second version of well-placedness is that what is transmitted through the network is the network itself, or more accurately, the importance, status, and prestige of the people you are connected to, preferably flowing from them (high status people) to you.

Under this interpretation, actors get status and prestige in the network from being connected to prestigious and high status others. Those others, in turn, get their status from being connected to high status others, and so ad infinitum.

One way of quantifying this idea goes like this. If \(\mathbf{x}\) is a vector containing the desired status scores, then the status of actor \(i\) should be equal to:

\[ x_i = \sum_{j} a_{ij}x_j \tag{1}\]

Where \(a_{ij} = 1\) if \(i\) is adjacent to \(j\) in the network. Note that this formula just sums up the status scores of all the others each actor is connected to.

In matrix notation, if \(\mathbf{x}\) is a column vector of status scores then:

\[ \mathbf{x} = A\mathbf{x} \]

Because \(\mathbf{x}\) is an \(n \times n\) matrix and \(\mathbf{x}\) is \(n \times 1\) column vector, the multiplication \(A\mathbf{x}\) will return another column vector of dimensions \(n \times 1\), in this case \(\mathbf{x}\) itself!

Note the problem that this formulation poses: \(\mathbf{x}\) appears on both sides of the equation, which means that in order to know the status of any one node we would need to know the status of the others, but calculating the status of the others depends on knowing the status of the focal node, and so on. There’s a chicken and the egg problem here.

Now, there is an obvious (to the math majors) mathematical solution to this problem, because there’s a class of solvable (under some mild conditions imposed on the matrix \(\mathbf{A}\)) linear algebra problems that take the form:

\[ \lambda\mathbf{x} = A\mathbf{x} \]

Where \(\lambda\) is just a plain old number (a scalar). Once again conditional of the aforementioned mild conditions being met, we can iteratively search for a value \(\lambda\), fix it, then fill up the \(\mathbf{x}\) vector with another set of values, fix those, search for a new \(\lambda\), and continue until we have values of \(\lambda\) and \(\mathbf{x}\) that make the above equality true.

When we do that successfully, we say that the value of \(\lambda\) we hit upon is an eigenvalue of the matrix \(\mathbf{A}\) and the values of the vector \(\mathbf{x}\) we came up with are an eigenvector of the same matrix (technically in the above equation a right eigenvector).

Eigenvalues and eigenvectors, like Don Quixote and Sancho Panza, come in pairs, because you need a unique combination of both to solve the equation. Typically, a given matrix (like an adjacency matrix) will have multiple \(\lambda/\mathbf{x}\) pairs that will solve the equation. Together the whole set \(\lambda/\mathbf{x}\) pairs that make the equation true are the eigenvalues and eigenvectors of the matrix.

Eigenvalues, Eigenvectors, Oh My!

Note that all of this obscure talk about eigenvalues and eigenvectors is just matrix math stuff. It has nothing to do with networks and social structure.

In contrast, because the big three centrality measures have a direct foundation in graph theory, and graph theory is an isomorphic model of social structures (points map to actor and lines map to relations) the “math” we do with graph theory is directly meaningful as a model of networks (the counts of the number of edges incident to a node is the count of other actors they someone is directly connected to).

Eigenvalues and eigenvectors are not a model of social structure in the way graph theory is (their first scientific application was in Chemistry and Physics). They are just a mechanical math fix to a circular equation problem.

This is why it’s a mistake to introduce network measures of status and prestige by jumping directly to the machinery of linear algebra (or worse talk about the idea of eigenvector centrality which means nothing to most people).

A better approach is to see if we can motivate the use of measures like the ones above using the simple model of the distribution of status and prestige we started with earlier. We will see that we can, and that doing that leads us back to solutions that are the mathematical equivalent of all the eigenvector stuff.

Distributing Centrality to Others

Let’s start with the simplest model of how people can get their status from the status of others in a network. It is the simplest because it is based on degree.

Imagine everyone has the same “quantum” of status to begin with (this can be stored in a vector containing the same number of length equals to number of actors in the network). Then, at each step, people “send” the same amount of status to all their alters in the network. At the end of each step, we compute people’s status scores using Equation 1. We stop doing this after the status scores of people stop changing across each iteration.

Let us see a real-life example at work.

We will use a data set collected by David Krackhardt on the friendships of 21 managers in a high tech company in the West coast (see the description here). The data are reported as directed ties (\(i\) nominates \(j\) as a friend) but we will constrain ties to be undirected:

   library(networkdata)
   library(igraph)
   g <- as.undirected(ht_friends, mode = "collapse")

This is what the network looks like:

We extract the adjacency matrix corresponding to this network:

   A <- as.matrix(as_adjacency_matrix(g))

And here’s a simple custom function using a while loop that exemplifies the process of status distribution through the network we talked about earlier:

   status1 <- function(A) {
      n <- nrow(A) #number of actors
      x <- rep(1, n) #initial status vector set to all ones
      w <- 1 
      k <- 0 #initializing counter
      while (w > 0.0001) {
          o.x <- x #old status scores
          x <- A %*% x #new scores a function of old scores and adjacency matrix
          x <- x/norm(x, type = "E") #normalizing new status scores
          w <- abs(sum(abs(x) - abs(o.x))) #diff. between new and old scores
          k <- k + 1 #incrementing while counter
      }
   return(as.vector(x))
   }

Lines 1-5 initialize various quantities, most importantly the initial status vector for each node to just a series of ones:

   rep(1, nrow(A))

 [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Then lines 6-12 implement a little loop of how status is distributed through the network, with the most important piece of code being line 8 where the current status scores for each node are just the sum of the status scores of its neighbors computed one iteration earlier. The program stops when the difference between the old and the new scores is negligible (\(\delta < 0.0001\)) as checked in line 10.

Note the normalization step on line 9, which is necessary to prevent the sum of status scores from getting bigger and bigger indefinitely (in mathese, this is referred to as the sum “diverging”). In base R, the type = "E" normalization implements the euclidean vector norm (also sometimes confusingly called the Frobenieus norm), by which we divide each value of the status scores by after each update.¹

And here’s the resulting (row) vector of status scores for each node:

   s <- status1(A)
   s <- s/max(s) #normalizing by maximum
   round(s, 3)

 [1] 0.619 0.635 0.446 0.489 0.629 0.430 0.205 0.380 0.444 0.468 0.814 0.549
[13] 0.162 0.401 0.613 0.360 1.000 0.247 0.680 0.360 0.392

What if I told you that this vector is the same as that given by the leading (first) eigenvector of the adjacency matrix?

   s <- abs(eigen(A)$vector[, 1])#computing the first eigenvector
   s <- s/max(s) #normalizing by maximum
   round(s, 3)

 [1] 0.619 0.635 0.446 0.489 0.629 0.430 0.205 0.380 0.444 0.468 0.814 0.549
[13] 0.162 0.401 0.613 0.360 1.000 0.247 0.680 0.360 0.392

Which is of course what is computed by the eigen_centrality function in igraph:

   round(eigen_centrality(g)$vector, 3) #igraph automatically normalizes the scores

 [1] 0.619 0.635 0.446 0.489 0.629 0.430 0.205 0.380 0.444 0.468 0.814 0.549
[13] 0.162 0.401 0.613 0.360 1.000 0.247 0.680 0.360 0.392

So, the “eigenvector centralities” are just the limit scores produced by the status distribution process implemented in the status1 function!

When treated as a structural index of connectivity in a graph (aka a centrality measure) the eigenvector status scores induce an ordering of the nodes which we may be interested in looking at:

   nodes <- 1:vcount(g)
   eig.cent <- round(status1(A), 3)
   eig.dat <- data.frame(Nodes = nodes, Eigen.Cent = eig.cent, Deg.Cent = degree(g))
   eig.dat <- eig.dat[order(eig.dat$Eigen.Cent, decreasing = TRUE), ]
   library(kableExtra)
   kbl(eig.dat[1:10, ], 
       format = "html", align = "c", row.names = FALSE,
       caption = "Top Ten Eigenvector Scores.") %>%    kable_styling(bootstrap_options = c("hover", "condensed", "responsive"))

Top Ten Eigenvector Scores.
Nodes	Eigen.Cent	Deg.Cent
17	0.413	18
11	0.336	14
19	0.281	10
2	0.262	10
5	0.260	10
1	0.256	9
15	0.253	9
12	0.227	8
4	0.202	7
10	0.193	8

Most other measures of status in networks are constructed using similar principles. What changes is the model of how status is distributed in the system. That’s why scary and non-intuitive stuff about eigenvectors or whatever is misleading.

Other measures are designed such that they either change the quantum of status that is distributed through the network by making it dependent on some node characteristic (like degree) or differentiate between different routes of distribution in directed graphs, by for instance, differentiating status derived from outgoing links from that derived from incoming links.

Let’s see some examples of these alternative cases.

Bonacich Prestige

In a classic paper, Philip Bonacich (1972) noted the above connection between different ways people conceptualized status and prestige in networks and the leading eigenvector of the adjacency matrix. He then noted that we can extend similar ideas to the directed case.

Here, people get status from receiving nominations from high status others (i.e., those who receive a lot of nominations), whose partners also get status from receiving a lot of nominations from high status others, and so forth.

This means that in a directed system of relations, status distribution operates primarily via the in-degree of each node, so that if \(\mathbf{A}\) is the asymmetric adjacency matrix corresponding to the directed graph, then if we play our status game on the transpose of this matrix \(\mathbf{A}^T\) we will get the scores we seek (Fouss, Saerens, and Shimbo 2016, 204).

Recall that in transposing the matrix of a directed graph, we change it from being a from/to matrix (nodes in the rows send ties to nodes in the columns) to a to/from matrix: Nodes in the rows receive ties from nodes in the columns. So we want to play our status game in this matrix, because we want to rank nodes according to their receipt of ties from high-status others.

Let’s see a real-life example, this time using the directed version of the Krackhardt friendship nomination network among the high-tech managers:

   g <- ht_friends
   A <- as.matrix(as_adjacency_matrix(g))
   s <- status1(t(A))
   s <- s/max(s)
   round(s, 3)

 [1] 0.922 1.000 0.379 0.639 0.396 0.190 0.240 0.531 0.411 0.117 0.413 0.769
[13] 0.082 0.428 0.368 0.449 0.592 0.440 0.425 0.225 0.583

Which are the same scores we would have gotten using the eigen_centrality function in igraph with the argument directed set to TRUE:

   round(eigen_centrality(g, directed = TRUE)$vector, 3)

 [1] 0.922 1.000 0.379 0.639 0.396 0.190 0.240 0.531 0.411 0.117 0.413 0.769
[13] 0.082 0.428 0.368 0.450 0.592 0.440 0.425 0.225 0.583

And, like before, we can treat these scores as centrality measures and rank the nodes in the graph according to them.

Here are the top ten nodes:

Top Ten Eigenvector Scores for a Directed Graph.
Nodes	Eigen.Cent	In.Deg.Cent
2	1.000	10
1	0.922	8
12	0.769	8
4	0.639	5
17	0.592	6
21	0.583	5
8	0.531	5
16	0.449	4
18	0.440	4
14	0.428	5

While the top in-degree centrality node (2) also gets the top Eigenvector Centrality scores, we see many cases of nodes with equal in-degree centrality that get substantively different Eigenvector scores. So who you are connected matters in addition to how many incoming connections you have.

A Degree-Dependent Model of Status (AKA PageRank)

Note that the model of status distribution implied by the Bonacich’s Eigenvector Centrality just reviewed implies that each node distributes the same amount of status independently of the number of connection it has; status just replicates indefinitely. Thus, a node with a 100 friends has 100 status units to distribute to each of them and a node with a 10 friends has 10 units.

This is why the eigenvector idea rewards nodes who are connected to popular others more. Even though everyone begins with a single unit of status, well-connected nodes by degree end up having more of it to distribute.

But what if status dissipated proportionately to the number of connections one had? For instance, if someone has 100 friends and they only had so much time or energy, they would only have a fraction of status to distribute to others than a person with 10 friends.

In that case, the node with a hundred friends would only have 1/100 of status unites to distribute to each of their connections while the node with 10 friends would have 1/10 units. Under this formulation, being connected to discerning others, that is people who only connect to a few, is better than being connected to others who connect to everyone else indiscriminately.

How would we implement this model? First, let’s create a variation of the undirected friendship nomination adjacency matrix called the \(\mathbf{P}\) matrix:

   g <- as.undirected(ht_friends, mode = "collapse")
   A <- as.matrix(as_adjacency_matrix(g))
   P <- A/rowSums(A)

So this is the original adjacency matrix, with each entry \(a_{ij}\) divided by the sum of the corresponding row, which, as you may recall, is equivalent to the degree of node \(i\).

Here are the first 10 rows and columns of the new matrix:

   round(P[1:10, 1:10], 2)

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,] 0.00 0.11 0.00 0.11 0.00 0.00 0.00 0.11 0.00  0.00
 [2,] 0.10 0.00 0.00 0.10 0.10 0.10 0.00 0.00 0.00  0.00
 [3,] 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00  0.17
 [4,] 0.14 0.14 0.00 0.00 0.00 0.00 0.00 0.14 0.00  0.00
 [5,] 0.00 0.10 0.00 0.00 0.00 0.00 0.00 0.00 0.10  0.10
 [6,] 0.00 0.14 0.00 0.00 0.00 0.00 0.14 0.00 0.14  0.00
 [7,] 0.00 0.00 0.00 0.00 0.00 0.33 0.00 0.00 0.00  0.00
 [8,] 0.20 0.00 0.00 0.20 0.00 0.00 0.00 0.00 0.00  0.20
 [9,] 0.00 0.00 0.00 0.00 0.17 0.17 0.00 0.00 0.00  0.17
[10,] 0.00 0.00 0.12 0.00 0.12 0.00 0.00 0.12 0.12  0.00

Note that the entries are now numbers between zero and one and the matrix is asymmetric that is \(p_{ij}\) is not necessarily equal to \(p_{ji}\). In fact \(p_{ij}\) will only be equal to \(p_{ji}\) when \(k_i = k_j\) (nodes have the same degree).

Moreover the rows of \(\mathbf{P}\) sum to one:

   rowSums(P)

 [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Which means that the \(\mathbf{P}\) matrix is row stochastic. That is the “outdegree” of each node in the matrix is forced to sum to a fixed number (which means that it is a useless quantity). However, the indegree is not:

   round(colSums(P), 2)

 [1] 1.11 1.34 0.63 0.86 1.56 1.06 0.37 0.51 0.61 1.21 2.33 0.92 0.17 0.87 1.08
[16] 0.53 2.73 0.54 1.21 0.60 0.77

Which means that inequalities in the system will be tied to the indegree of each node in the \(\mathbf{P}\) matrix, which is given by either the column sums of the matrix (as we just saw) or the row sums of the transpose of the same matrix:

   round(rowSums(t(P)), 2)

 [1] 1.11 1.34 0.63 0.86 1.56 1.06 0.37 0.51 0.61 1.21 2.33 0.92 0.17 0.87 1.08
[16] 0.53 2.73 0.54 1.21 0.60 0.77

This will come in handy in a second.

The \(\mathbf{P}\) matrix has many interpretations, but here it just quantifies the idea that the amount of centrality each node can distribute is proportional to their degree, and that the larger the degree, the less there is to distribute (the smaller each cell \(p_{ij}\) will be). Meanwhile, it is clear that nodes that are pointed to by many other nodes who themselves don’t point to many others have a large indegree in \(\mathbf{P}\).

Now we can just adapt the the model of status distribution we used for eigenvector centrality but this time using the \(\mathbf{P}\) rather than the \(\mathbf{A}\) matrix. Note that because we are interested in the status that comes into each node we use the transpose of \(\mathbf{P}\) rather than \(\mathbf{P}\).

So at each step the status of a node is equivalent to the sum of the status scores of their in-neighbors, with more discerning in-neighbors passing along more status than less discerning ones:

   s2 <- round(status1(t(P)), 3)
   s2 <- s2/max(s2)
   round(s2, 3)

 [1] 0.500 0.555 0.333 0.388 0.555 0.388 0.167 0.278 0.333 0.445 0.778 0.445
[13] 0.110 0.333 0.500 0.278 1.000 0.222 0.555 0.278 0.333

What if I told you that these numbers are the same as the leading eigenvector of \(\mathbf{P}^T\)?

   s2 <- abs(eigen(t(P))$vector[, 1])
   s2 <- s2/max(s2)
   round(s2, 3)

 [1] 0.500 0.556 0.333 0.389 0.556 0.389 0.167 0.278 0.333 0.444 0.778 0.444
[13] 0.111 0.333 0.500 0.278 1.000 0.222 0.556 0.278 0.333

And, of course, the (normalized) scores produced by this approach are identical to those computed by the page_rank function in igraph:

   pr <- page_rank(g, damping = 1, algo = "arpack")$vector
   round(pr/max(pr), 3)

 [1] 0.500 0.556 0.333 0.389 0.556 0.389 0.167 0.278 0.333 0.444 0.778 0.444
[13] 0.111 0.333 0.500 0.278 1.000 0.222 0.556 0.278 0.333

So the distributional model of status is the same one implemented in the PageRank algorithm!

PageRank of course was designed to deal with directed graphs (like the World Wide Web). So let’s load up the version of the Krackhardt’s Managers data that contains the advice network which is an unambiguously directed relation.

   g <- ht_advice

We then compute the \(\mathbf{P}\) matrix:

   A <- as.matrix(as_adjacency_matrix(g))
   P <- A/rowSums(A)
   round(P[1:10, 1:10], 2)

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,] 0.00 0.17 0.00 0.17 0.00 0.00 0.00 0.17 0.00  0.00
 [2,] 0.00 0.00 0.00 0.00 0.00 0.33 0.33 0.00 0.00  0.00
 [3,] 0.07 0.07 0.00 0.07 0.00 0.07 0.07 0.07 0.07  0.07
 [4,] 0.08 0.08 0.00 0.00 0.00 0.08 0.00 0.08 0.00  0.08
 [5,] 0.07 0.07 0.00 0.00 0.00 0.07 0.07 0.07 0.00  0.07
 [6,] 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00  0.00
 [7,] 0.00 0.12 0.00 0.00 0.00 0.12 0.00 0.00 0.00  0.00
 [8,] 0.00 0.12 0.00 0.12 0.00 0.12 0.12 0.00 0.00  0.12
 [9,] 0.08 0.08 0.00 0.00 0.00 0.08 0.08 0.08 0.00  0.08
[10,] 0.07 0.07 0.07 0.07 0.07 0.00 0.00 0.07 0.00  0.00

Remember how we said earlier that there are multiple ways of thinking about \(\mathbf{P}\)? Another way of thinking about the \(\mathbf{P}\) matrix is as characterizing the behavior of a random walker in the directed graph. At any time point \(t\) the walker (a piece of information, a virus, or status itself) sits on a node and the with probability \(p_{ij}\) it jumps to one of that node’s out-neighbors. The probabilities are stored in the matrix \(\mathbf{P}\).

One issue that arises is that there could be nodes with no out-neighbors (so-called sink nodes) or like node 6 above, who has just one out-neighbor, in which case the probability is 1.0 that if the random walker is at node 6 it will go to node 21.

To avoid this issue the original designers of the PageRank algorithm (Brin and Page 1998) added a “fudge” factor: That is, with probability \(\alpha\) the random walker should hop from node to node following the directed links in the graph. But once in a while with probability \(1-\alpha\) the walker should decide to “teleport” (with uniform probability) to any node in the graph whether it is an out-neighbor of the current node or not.

How do we do that? Well we need to “fix” the \(\mathbf{P}\) matrix to allow for such behavior. So instead of \(\mathbf{P}\) we estimate our distributive status model on the matrix \(\mathbf{G}\) (yes, for Google):

\[ \mathbf{G} = \alpha \mathbf{P} + (1 - \alpha) \mathbf{E} \]

Where \(\mathbf{E}\) is a matrix of the same dimensions as \(\mathbf{P}\) but containing \(1/n\) in every cell indicating that every node has an equal chance of being “teleported” to.

So fixing \(\alpha = 0.85\) our \(\mathbf{G}\) matrix would be:

   n <- vcount(g)
   E <- matrix(1/n, n, n)
   G <- (0.85 * P) + (0.15 * E)

And then we just play our status distribution game on the transpose of \(\mathbf{G}\):

   s3 <- round(status1(t(G)), 3)
   round(s3/max(s3), 3)

 [1] 0.302 0.573 0.165 0.282 0.100 0.437 0.635 0.255 0.092 0.180 0.237 0.242
[13] 0.087 0.268 0.097 0.170 0.258 0.440 0.087 0.200 1.000

Which is the same answer you would get from the igraph function page_rank by setting the “damping” parameter to 0.85:

   pr <- page_rank(g, damping = 0.85, algo = "arpack")$vector
   round(pr/max(pr), 3)

 [1] 0.302 0.573 0.165 0.281 0.100 0.437 0.635 0.256 0.091 0.180 0.237 0.242
[13] 0.086 0.269 0.097 0.169 0.258 0.440 0.086 0.200 1.000

Hubs and Authorities

Recall from previous discussions that everything doubles (sometimes quadruples like degree correlations) in directed graphs. The same goes for status as reflected in a distributive model through the network.

Consider two ways of showing your status in a system governed by directed relations (like advice). You can be highly sought after by others (be an “authority”), or you can be discerning in who you seek advice from, preferably seeking out people who are also sought after (e.g., be a “hub” pointing to high-quality others).

These two forms of status are mutually defining. The top authorities are those who are sought after by the top hubs, and the top hubs are the ones who seek the top authorities!

So this leads to a doubling of Equation 1:

\[ x^h_i = \sum_j a_{ij} x^a_j \]

\[ x^a_i = \sum_i a_{ij} x^h_i \]

Which says that the hub score \(x^h\) of a node is the sum of the authority scores \(x^a\) of the nodes they point to (sum over \(j\); the outdegree), and the authority score of a node is the sum of the hub scores of the nodes that point to it (sum over \(i\); the indegree).

So we need to make our status game a bit more complicated (but not too much) to account for this duality:

   status2 <- function(A) {
     n <- nrow(A)
     a <- rep(1, n)  #initializing authority scores
     diff.a <- 1 #initializing diff.
     while (diff.a >= 0.0001) {
         o.a <- a #old authority scores
         h <- A %*% o.a #new hub scores a function of previous authority scores of their out-neighbors
         h <- h/norm(h, type = "E")
         a <- t(A) %*% h #new authority scores a function of current hub scores of their in-neighbors
         a <- a/norm(a, type = "E")
         diff.a <- abs(sum(abs(o.a) - abs(a))) #diff. between old and new authority scores
         }
   return(list(h = as.vector(h), a = as.vector(a)))
   }

Everything is like our previous status1 function except now we are keeping track of two mutually defining scores a and h. As you may have guessed this is just an implementation of the “HITS” algorithm developed by Kleinberg (1999).²

The results for the Krackhardt advice network are:

   round(status2(A)$a/max(status2(A)$a), 3)

 [1] 0.782 1.000 0.356 0.496 0.330 0.644 0.684 0.711 0.290 0.615 0.769 0.498
[13] 0.323 0.677 0.267 0.570 0.645 0.871 0.323 0.589 0.776

   round(status2(A)$h/max(status2(A)$h), 3)

 [1] 0.370 0.176 0.841 0.709 0.835 0.065 0.492 0.490 0.773 0.672 0.206 0.122
[13] 0.331 0.279 1.000 0.274 0.313 0.800 0.581 0.687 0.600

Which are equivalent to using the igraph functions authority_score and hub_score:

   round(authority_score(g, scale = TRUE)$vector, 3)

 [1] 0.782 1.000 0.356 0.496 0.330 0.644 0.684 0.711 0.290 0.615 0.769 0.498
[13] 0.323 0.677 0.267 0.570 0.645 0.871 0.323 0.589 0.776

   round(hub_score(g, scale = TRUE)$vector, 3)

 [1] 0.370 0.176 0.841 0.709 0.835 0.065 0.492 0.490 0.773 0.672 0.206 0.122
[13] 0.331 0.279 1.000 0.274 0.313 0.800 0.581 0.687 0.600

Recall that both the eigenvector and PageRank status scores computed via the network status distribution game routine ended up being equivalent to the eigenvectors of a network proximity matrix (the adjacency matrix \(\mathbf{A}\) and the probability matrix \(\mathbf{P}\) respectively). It would be surprising if the same wasn’t true of the hub and authority status scores.

Let’s find out which ones!

Consider the matrices:

\[ \mathbf{M} = \mathbf{A}\mathbf{A}^T \]

\[ \mathbf{N} = \mathbf{A}^T\mathbf{A} \]

Let’s see what they look like in the Krackhardt manager’s network:

   M = A %*% t(A)
   N = t(A) %*% A
   M[1:10, 1:10]

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]    6    1    5    5    5    1    3    4    5     5
 [2,]    1    3    3    2    3    1    2    3    3     0
 [3,]    5    3   15   11   12    1    8    8   12     8
 [4,]    5    2   11   12   11    1    7    6   11     8
 [5,]    5    3   12   11   15    1    7    7   12    10
 [6,]    1    1    1    1    1    1    1    1    1     0
 [7,]    3    2    8    7    7    1    8    5    8     4
 [8,]    4    3    8    6    7    1    5    8    7     4
 [9,]    5    3   12   11   12    1    8    7   13     7
[10,]    5    0    8    8   10    0    4    4    7    14

   N[1:10, 1:10]

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]   13   13    4    5    5    6    8    8    4     8
 [2,]   13   18    5    8    5    9   11   10    4     9
 [3,]    4    5    5    4    4    2    4    4    2     3
 [4,]    5    8    4    8    3    4    6    6    3     4
 [5,]    5    5    4    3    5    1    3    3    3     3
 [6,]    6    9    2    4    1   10    7    7    2     6
 [7,]    8   11    4    6    3    7   13    6    3     7
 [8,]    8   10    4    6    3    7    6   10    3     6
 [9,]    4    4    2    3    3    2    3    3    4     3
[10,]    8    9    3    4    3    6    7    6    3     9

What’s in these matrices? Well let’s look at \(\mathbf{M}\). The diagonals will look familiar because they happen to be the outdegree of each node:

   degree(g, mode = "out")[1:10]

 [1]  6  3 15 12 15  1  8  8 13 14

You may have guessed that the diagonals of matrix \(\mathbf{N}\) contain the indegrees:

   degree(g, mode = "in")[1:10]

 [1] 13 18  5  8  5 10 13 10  4  9

Which means that the off-diagonals cells of each matrix \(m_{ij}\) and \(n_{ij}\), contain the common out-neighbors and common in-neighbors shared by nodes \(i\) and \(j\) in the graph, respectively.

As you may already be suspecting, the hub and authorities scores are the leading eigenvectors of the \(\mathbf{M}\) and \(\mathbf{N}\) matrices (Kleinberg 1999):

   h <- eigen(M)$vector[,1] * -1
   a <- eigen(N)$vector[,1] * -1
   round(h/max(h), 3)

 [1] 0.370 0.176 0.841 0.709 0.835 0.065 0.492 0.490 0.773 0.672 0.206 0.122
[13] 0.331 0.279 1.000 0.274 0.313 0.800 0.581 0.687 0.600

   round(a/max(a), 3)

 [1] 0.782 1.000 0.356 0.496 0.330 0.644 0.684 0.711 0.290 0.615 0.769 0.498
[13] 0.323 0.677 0.267 0.570 0.645 0.871 0.323 0.589 0.776

Once again demonstrating the equivalence between eigenvectors of proximity matrices in networks and our prismatic status distribution game!

A Final Ranking of Prestige Scores

Like before, we can treat the Eigenvector, PageRank, Hub, and Authority Scores as “centralities” defined over nodes in the graph. In that case we might be interested in how different nodes in Krackhardt’s High Tech Managers network stack up according to the different status criteria:

Top Prestige Scores Ordered by Indegree.
Node.ID	Eig.Cent	PageRank	Hub.Score	Auth.Score	Indegree
2	1.000	0.573	0.176	1.000	18
18	0.780	0.440	0.800	0.871	15
21	0.920	1.000	0.600	0.776	15
1	0.594	0.302	0.370	0.782	13
7	0.767	0.635	0.492	0.684	13
11	0.556	0.237	0.206	0.769	11
6	0.620	0.437	0.065	0.644	10
8	0.555	0.256	0.490	0.711	10
14	0.512	0.269	0.279	0.677	10
10	0.410	0.180	0.672	0.615	9
17	0.482	0.258	0.313	0.645	9
4	0.517	0.281	0.709	0.496	8
16	0.407	0.169	0.274	0.570	8
20	0.432	0.200	0.687	0.589	8
12	0.405	0.242	0.122	0.498	7
3	0.306	0.165	0.841	0.356	5
5	0.219	0.100	0.835	0.330	5
9	0.182	0.091	0.773	0.290	4
13	0.197	0.086	0.331	0.323	4
15	0.220	0.097	1.000	0.267	4
19	0.197	0.086	0.581	0.323	4

Top Prestige Scores Ordered by Outdegree
Node.ID	Eig.Cent	PageRank	Hub.Score	Auth.Score	Outdegree
15	0.220	0.097	1.000	0.267	20
18	0.780	0.440	0.800	0.871	17
3	0.306	0.165	0.841	0.356	15
5	0.219	0.100	0.835	0.330	15
10	0.410	0.180	0.672	0.615	14
9	0.182	0.091	0.773	0.290	13
4	0.517	0.281	0.709	0.496	12
20	0.432	0.200	0.687	0.589	12
19	0.197	0.086	0.581	0.323	11
21	0.920	1.000	0.600	0.776	11
7	0.767	0.635	0.492	0.684	8
8	0.555	0.256	0.490	0.711	8
1	0.594	0.302	0.370	0.782	6
13	0.197	0.086	0.331	0.323	6
17	0.482	0.258	0.313	0.645	5
14	0.512	0.269	0.279	0.677	4
16	0.407	0.169	0.274	0.570	4
2	1.000	0.573	0.176	1.000	3
11	0.556	0.237	0.206	0.769	3
12	0.405	0.242	0.122	0.498	2
6	0.620	0.437	0.065	0.644	1

References

Bonacich, Phillip. 1972. “Factoring and Weighting Approaches to Status Scores and Clique Identification.” Journal of Mathematical Sociology 2 (1): 113–20.

Brin, Sergey, and Lawrence Page. 1998. “The Anatomy of a Large-Scale Hypertextual Web Search Engine.” Computer Networks and ISDN Systems 30 (1-7): 107–17.

Fouss, François, Marco Saerens, and Masashi Shimbo. 2016. Algorithms and Models for Network Data and Link Analysis. Cambridge University Press.

Kleinberg, Jon M. 1999. “Authoritative Sources in a Hyperlinked Environment.” Journal of the ACM (JACM) 46 (5): 604–32.

Podolny, Joel M. 2001. “Networks as the Pipes and Prisms of the Market.” American Journal of Sociology 107 (1): 33–60.

Footnotes

For a vector of numbers \(\mathbf{x}\) the euclidean vector norm \(||\mathbf{x}||_2\) is given by: \(\sqrt{\sum x^2}\).↩︎
HITS is an acronym for the unfortunate and impossible to remember name “Hypertext Induced Topic Selection” reflecting the origins the approach is web-based information science.↩︎