Home > discussions, What i've been reading > Paper reading with Davide 26 Feb 2010

Paper reading with Davide 26 Feb 2010

February 26th, 2010 Leave a comment Go to comments

Spent a few hours going over the following paper with Davide:

Kossinets, G., Kleinberg, J., & Watts, D. (2008). The structure of information pathways in a social communication network. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining – KDD ’08 (p. 435). New York, New York, USA: ACM Press. doi: 10.1145/1401890.1401945.

This was a very useful session, as it meant that we were forced to really understand the paper.

The authors present analysis of email datasets usin using vector clocks as a framework. They argue that the issues of out-of-date information and indirect paths are central to the understanding of the patterns of systemic communicatoion.

They explore Granovetter’s theory of weak ties, which basically says that long range connections can give better information than close connections.

This paper lead me to think that vector clocks would be a great way to discover the state of an unknown network from the point of view of each node. E.g. if a node exchanges vector clocks with other nodes it meets (perhaps with some probability, and time restriction) it could quicky build up in internal state of the following:

  • the number of nodes in its connected network
  • hops to other nodes (?? maybe ?? – )
  • the range of other nodes (i.e. the amount information update a node gives about other nodes) – which can be used as a routing metric
  • membership clustering using the ball of radius (i.e. the nodes it is up to date with to some value Τ days, which could be based on periodicity)
  • periodic degree of a node can also be used (using T as the period)  as a routing metric

Each node must have a unique identity (perhaps based on BT Mac address), even Open World nodes that are not members of the closed world can be counted when it comes to degree calculations, but only as a ramp up, as only closed world nodes (i.e. others using this algorithm) will be of interest when sending messages.

  1. No comments yet.
  1. No trackbacks yet.