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


  1. Deals with decentralized communication in networks where short paths exist between nearly all nodes
  2. Approach outperforms competitors, is based on two measures commonly used to summarize local information
  3. Homophily is the tendency of similar nodes to be connected
  4. 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)
    1. This algorithm generalizes earlier approaches
  5. Goal is to minimize length of path of message
  6. Each node knows what neighbors it is connected to as well as their feature information and degree
  7. Uses probability estimates of distances, but its not clear why these distributions are needed if the algorithm is deterministic (not sure yet).
  8. 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
    1. Need to read on what guarantees related to homophily are
  9. 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 is also q_{st}.  This means that distances have to be normalized over each node.  The probability of s connecting directly to then is just a binomial distribution
  10. Does not revisit nodes (assigns them 0 probability), if all visited, traversal at random
  11. I can’t believe nobody did this already?
  12. Compares to pure similarity, pure degree (this approach does both) as well as random.  In synthetic and real-world networks.  Surprise this works best.
  13. 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
  14. Also did an example with paper citations where keywords were distance metric, cute
  15. Uses a Poisson approximation of the binomial? (its been awhile since OR, forgot about this)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: