A Measure of Betweeness Centrality Based on Random Walks. Newman. Social Networks 2005.


Notes based on a version on arxiv, so may not be identical to the journal version

  1. Betweeness as a measure of centrality is normally calculated as the ratio of shortest paths that go through a node
  2. Here they use a similar measure but don’t only consider shortest paths (although they give more weight to them)
  3. Measure here is based on random walks
  4. Closeness is defined as the mean shortest-path distance from a given node to all other nodes
  5. Betweeness, on the other hand, is the measure of how often a node lies on a path between other pairs of nodes
  6. If you consider only shortest paths, some strange behavior can arise in pathologic networks.  Also, in the real world, it is likely that not all actions/paths are optimal (such as the letter chains in Milgrams experiments)
    1. Therefore, value in considering paths of different lenghts, but weighing shorter paths more strongly
  7. Another proposal is based on max-flow  <I don’t know much about network flow> O(m^2 n) <but whats m and n?>
  8. But using flow can be just as problematic as shortest paths <ok, everything can be problematic but saying other things has problems doesn’t mean whats proposed here doesn’t>
  9. Here, random walk betweeness is considered <I would definitely says this is more problematic than the other ones>
  10. This is O((m+n)n^2)
  11. Mention something called Bonachich’s power centrality which is a discounted measure of centrality
  12. <Ok, think I got the point – if I need to come back to this paper I can.>
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: