Algorithm Brainstorm

I have thought up several possible approaches to determine the conditional importance of a node.

First, several observations:

Let P(x, A, B) be the importance of x to the nodes A and B.

- P(x, A, B) should equal P(x, B, A)
- P(x, A, B) should be at least somewhat related to P(x), the importance of x to the entire graph (PageRank)
- P(x, A, B) should also be related to P(A, x, B), P(B, x, A), etc, since importance is not directed. Of course, importance can be defined as directed: for example, the Internet might be important for your work but you are not important to the workings of the Internet. However, the way I am defining importance is more relatedness, and relatedness is commutative.


Definitions:
let D(x, y) be the shortest distance between x and y, in number of edges traversed.

So, here are the possibilities:

#1: Adjusted shortest-path
P(x, A, B) = max(D(x, A) + D(x, B), D(A, x) + D(x, B), D(A, x) + D(B, x), D(B, x) + D(x, A))

Justification:
It follows from the fact that relatedness is commutative that the above distance calculations should be about the same. If they are not, then it might be because the links are spurious. For example, from Six Degrees of Wikipedia:

"Shortest path from Darth Vader to Internet
(view reverse path)
Darth Vader
Chinese language
Internet
2 clicks needed"

However, clearly "Chinese language" has nothing to do with either Internet or Darth Vader. Indeed, the reverse path is completely different:

"Shortest path from Internet to Darth Vader
(view reverse path)
Internet
Advertising
Spaceballs
Darth Vader
3 clicks needed"

If both the forward path and the reverse path is short for x, then it is more likely that it is important/related. We could take the average of the several distances but that would allow a single spurious link to affect the average. It is probably better to take the maximum.

#2: Matrix factorization methods

I do not have any concrete justification for believing that this will work, but a graph can be represented as a adjacency matrix and a very popular way to analyze matrices is by using matrix factorization methods such as Singular Value Decomposition (SVD), Latent Semantic Analysis (LSA), and Non-Negative Matrix Factorization (NMF).

Let G be the adjacency matrix representation of the Wikipedia graph. The rows of G are vertices and so are the columns. Using NMF we can decompose it into a vertex-group matrix M and a group-vertex matrix N such that G = M X N. The should reveal clusters of nodes that are interconnected to each other.

We then construct a query vector Q where Q is 0 is everywhere except at A and B where it is 1.
Example:
Nodes: A, B, C, D, E, F, G
Q = <1,>

We then translate this vertex vector Q into a group vector Q'. We then calculate the dot product between Q and every row in M. The vertex that corresponds with the row that had the highest dot product with Q is the most similar node.

More will be forth coming.