Home > discussions, what i've been doing, What Matt Says > Seminar/Presentation 29 Nov 2010

Seminar/Presentation 29 Nov 2010

November 29th, 2010 Leave a comment Go to comments

Presentation summary:

Routing in Human Interaction Networks

The goal of this seminar is to get some ideas from the participants, about the feasibility, and possible directions for this research.

We believe that by detecting the underlying patterns of human interaction involving movement and contacts between individuals, we can design a delay tolerant mechanism for passing messages between actors in the system (for example using mobile phones) that does not rely on fixed infrastructure. A system such as this should exhibit low cost (hop count, update overhead, delivery latency) and high efficiency (delivery ratio).

We believe that we can drive a routing policy by calculating and sharing metrics and meta-data at node level; from the contacts they make and the places they visit, without the need for a centralised system. In particular we are interested in using location to drive the messaging scheme.

We will show recent, related results of Persistence Based Routing vs existing schemes, some initial results from our simple schemes, and will ask for suggestions regarding the direction of our research into Location Based Routing.

Present: Pádraig Cunningham, Davide Cellai, Derek Green, Conrad Lee, Fergal Reid, Neil Hurley

Presented some background, and ideas about routing in human interaction networks (Slides – 1.2MB), someone noted tha Delivery Ratio and Latency are directly linked, with the suggested that the requirement for high delivery ratio and low latency, may not be intuitive in some situations. e.g. when someone who will cause a high latency, may be the only one to get the message across.

The presentation seemed to go well, however some parts I might not have delivered properly, meaning that I seemed to be skimming over a few bits.

Some suggestions were made:

  • Consider the use of some sort of altered vector clocks, which keep a history, and can be shared with other nodes
  • Partition the graph in the Reality Mining data, to identify the communities, then test the algorithms for only those communities
  • Strong consensus to start using periodic patterns for predicting routes
  • Neil suggested that I try to generate a dataset that does work well for LBR
  • Ferhgal suggested what we had talked about before: finding out at what places, messages get sent

Reference to chase up:

  1. PNAS 2005/2006 – LIBEN-NOWELL – ?GeoRouting in social networks?
  2. SneakerNet
  3. Talk to Martin Harrigan – who is using Vector Clocks in some clever way

There may have been other things I don’t remember – feel free to comment with additions!

  1. Davide
    December 6th, 2010 at 12:24 | #1

    Fergal also mentioned to me that the problem was reminding him of the so-called A* search algorithm. As far as I understand it, this is a search algorithm for finding the shortest path according to some notion of cost. It is based on a heuristic distance which constitutes the lower bond of path effectiveness.
    The advantage of the A* algorithm is that it can always find a minimal cost path (if it exists), and it’s optimal in the sense that it doesn’t visit more nodes than any other algorithm of the same class.
    http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?&arnumber=4082128&abstractAccess=no&userType=inst
    http://portal.acm.org/citation.cfm?id=1056779
    Fergal said that this could give us insights into the problem, perhaps helping us in finding something similar in the case of dynamic networks.

  1. No trackbacks yet.