Navigating networks by using homophily and degree. Simsek, Jensen. PNAS 2008.

Deals with decentralized communication in networks where short paths exist between nearly all nodes

Approach outperforms competitors, is based on two measures commonly used to summarize local information

Homophily is the tendency of similar nodes to be connected

The algorithm simply passes the message to the node that has the highest likelihood of being connected to the goal (algorithm is called expected-value navigation)

This algorithm generalizes earlier approaches

Goal is to minimize length of path of message

Each node knows what neighbors it is connected to as well as their feature information and degree

Uses probability estimates of distances, but its not clear why these distributions are needed if the algorithm is deterministic (not sure yet).

Seems like the operation tries to send to a node that has the highest probability of a distance of 1 from the goal, as opposed to a minimal weighted distance, as apparently homophily implies that a high probability of distance 1 means also a high probability of other small distances

Need to read on what guarantees related to homophily are

Seems like as defined, a node s has similarity to node t of q_{st}. For all edges leaving from s, the probability that each edge goes to t is also q_{st}. This means that distances have to be normalized over each node. The probability of s connecting directly to t then is just a binomial distribution

Does not revisit nodes (assigns them 0 probability), if all visited, traversal at random

I can’t believe nobody did this already?

Compares to pure similarity, pure degree (this approach does both) as well as random. In synthetic and real-world networks. Surprise this works best.

For medium homophilly, it does fairly well relative to global planning, but for low homophily the distance metric isnt so useful, and for high homophily means there are few short paths

Also did an example with paper citations where keywords were distance metric, cute

Uses a Poisson approximation of the binomial? (its been awhile since OR, forgot about this)