Archive

Archive for the ‘General Meetings’ Category

Temporal Networks

May 31st, 2012 2 comments

Pádraig and  I discussed Time Respecting Paths  in the datasets we have based on the paper – Temporal Networks[1].

We want to detect the shortest/quickest paths between pairs of nodes, which respect the the temporal paths, so that we can derive a betweeness centrality measure.

The existing implementation we have, based on the BubbleRAP paper, floods the network, and calculates the betweeness centrality using the number of times a node is used in ANY path  – the BubbleRAP implementation uses only the SHORTEST paths. So there is some discrepancy here. The BubbeRAP paper reads as follows:

To calculate the individual centrality value for each node, we take an numerical approach. First we carry out a large number of emulations of unlimited flooding with different uniformly distributed traffic patterns created using the HaggleSim emulator, which can replay the collected mobility traces and emulate different forwarding strategies for every contact event. Then we count the number of times a node acts as a relay for other nodes on all the shortest delay deliveries. Here the shortest delay delivery refers to the case when the same message is delivered to the destination through different paths, and we only count the de- livery with the shortest delay. We call this number the betweenness centrality of this node in this temporal graph. Of course, we can normalise it to the highest value found. Here we use unlimited flooding since it can explore the largest range of delivery alternatives with the shortest delay. This definition captures the spirit of the Freeman centrality[2]

 

The Freeman centrality paper, which I only skimmed, doesn’t appear to refer to temporal graphs directly –  further inspection may yield a better understanding 🙂

There is a question over what observation period we should use, and how to decide which is really the ‘shortest path’  when paths may start/end at different times. In the Bubble RAP paper, they seem to have chosen the path with the least latency, but not considering the start time of the path. In the temporal networks paper [1], the authors talk about a Saw-tooth pattern which governs latency (as regular connections create a latency lag between connections), and mention a method to normalise over this pattern – but not really for the Betweeness Centrality measure.

e.g. If we start at time 0, and measure the time it takes to get to the destination node, that is fine. however, what if there is an intermediate time, 4, where, if we measure the path from there, we find a new shortest path – in Bubble RAP, this is taken as the shortest path, but is this correct?

I will implement the Time Respecting, shortest path (latency) betweeness centrality, (and maybe the shortest path – hops), as per BubbleRAP, and I will also investigate the normalised version as per the Temporal Networks paper.

[1]Holme P, Saramäki J. Temporal Networks. 2011:1-28. Available at: http://arxiv.org/abs/1108.1780. Accessed May 15, 2012..

[2]Freeman L. A set of measures of centrality based on betweenness. Sociometry. 1977. Available at: http://www.jstor.org/stable/10.2307/3033543. Accessed May 31, 2012.

Meeting with KM, SB and DC about Social Sensing data 7th July 2010

July 7th, 2010 No comments

Met with Kevin McCarthy, Steven Bourke and Davide Cellai about what the Social Sensing study data could be used for. We are all interested in movement patterns and prediction, and decided that we should work together.

The data itself is currently stored in a MongoDB, which is a document storage database, and is apparently very easy to query. The data itself is stored in approximately 200GB of seperate files. Kevin assured us that we would be able to access this data.

Steven suggested a number of sources of similar (location) data:

  • GeoLife, by Microsoft Research.
  • SimpleGeo
  • SpotRank by Skyhook

He also described how he collected location data from Gowalla, for ~2000 users in Dublin. His masters thesis was about DTN with sensors, and so his interests are in line with mine and DC’s.

We agreed to meet next week to brainstorm some ideas worthy of collaboration.

Quick meeting with Paddy 6th May 2010

May 6th, 2010 No comments

Met with paddy in his office and discussed updates so far.

Paddy wants to see something tangible by next week’s update – i.e. a worked example of how vector clocks will work in terms of location.

Also emphasised that I should not get sidetracked! (of course!)

Suggested storing temporal  information (parallel vector clocks?) – e.g. a from to, so that we can say things like does this time overlap this one, is it contained withing etc. etc.

Also thought about how to define location – the bounding of the location  gives an experimentation thing – change the grid size – whats the computation impact of the size of the grid – and what the relevance e.g. too big and it makes realistic.

Construct vector stamps – 5 separate path across these locations, two or three allow drop messages – run through and pick various vector clocks at various times, and show them. Then start generalising them.

From this we can draw general things about e.g.: decisions made, what information is stored, what we put in vector clocks, what operators we need.

Then run a simulation and see if generalisation works. Then we can see if some things fall down, and come back and change things.

Should stick with ideas about location, not proximity yet.

Using this it is then possible to write this concisely.

Actions:

  • Generate a worked example/scenario
    • show examples of vector clocks at times
    • show the movements over time
  • Don’t get sidetracked!

Meeting with Paddy 9 March 2010

March 9th, 2010 No comments

Met with Paddy to discuss funding and an idea of direction in PhD

Paddy said that if his EU grants get signed off, he will garauntee me another 1 year of funding from September, the only requirements will be a chunk of work which results in a ~30 page document – something to do with autonomous software patching.

Also spoke to him about the idea of Vector clocks and how we can use them for opportunisic networking – he wondered whether we could derive some utility for locations, perhaps based on duration spent at a location, number of nodes in that location etc. etc.

He said that perhaps a good paper would be on techniques for analysing locations for use with opportunistic networking.

Paddy said that he wants me to aim to submit to CfP on Social Based Routing in Mobile and Delay Tolerent Nets the deadline is in June, and split the time up until then into 6 week chunks, and for the first chunk, tell him what I will be doing – i.e. what problems I am solving, and for the whole time, what my goals are.

Also spoke about my idea for using the Dublin Bus network for research and profit – he mentioned a guy in trinity who has access to a load of transport data and also suggested I dig out an email address of someone important at Dublin bus, and send them a formal email about gettin information about the bus, and CC him (so it looks official).

He also mentioned the TextUS service based at DCU, (runs the Aircoach SMS payment service, and the SMS parking scheme) who we could collaborate with to provide a TFL type service for dublin.

Presentation 10th Feb 2010

February 11th, 2010 No comments

Gave presentation to Paddy, Davide, Neil Cowzer and Fergal Reid (clique) about my quick and dirty analysis of the dataset that I have collected allready.

Slides

General concensus was that there was not really enough users, and so there were some suggestions about other datasets that might be found -persuade a mobile phone company to give data about user movements. Mine flickr/twitter for geo-tagged photo’s/tweets, and try to determine groups of people based on similar locations.

Also suggested that the GMA is good for visualising data, not greatly interesting, PH is interesting as is SPD. BD is something that is useful as an application to gather data, but would need a very large engineering effort.

Paddy suggested that if we could make the data collection process very easy, then we could throw it out to the student population to start collecting data. Fergal said that in J2ME it would be very difficult, but by sticking to C++ it might work (for Nokia phones).

Also talked about getting ground truth for data, Fergal Suggested collecting accellorometer data too (so if someone asked – how did you verify GPS trace, one can say that we correlated it with the accelorometer data). I also suggested tagging locations.

Determined the following actions:

  • Look for access to datasets with good location – 1 week
    • WaveLAN Dataset
    • HeaNET – chase paddy – Eduroam
    • Mine location data from Flickr
  • Look at applying analysis to these datasets – specifically
    • Periodicity Hunting
    • Spatial Dependance on the Degree
  • See if we can construct overlay over these networks
    • e.g. drop nodes
      • Popular locations
      • popular people
      • Other?
      • Vector clocks might be the way to do it
  • Read up about Vector Clocks as suggested in the paper by Klineberg, Watts and ???? at  KDDOA
  • Speak to Graham about whether I can easily integrate this data into his code, if so – do it, otherwise think about implementing it seperately(robustly!)

Also planned to meet Paddy again next week to go over these things, and try to hammer out a better plan. Then meet with these people again in three weeks to show where I have go to.

Davide also talked about churn in proximity patterns – might be worth thinking about what this means (example was then a person regularly sees other people, and after a while, one of those people drops off the radar – what does this mean)

Paddy said that in his mind, the long goal is to be able to forward plan using the knowledge of data that has passed (prediction).

Discussion with Paddy and Davide 2nd Feb 2010

February 2nd, 2010 No comments

Met with Paddy and Davide and discussed what we have been doing.

  • Actions from last meeting:
  • Said that I had been collecting data which seems to have good location information.
  • Had spoken with prag etc. but not really very useful
  • Davide has come up with some great questions for analysis of data
  • The only thing I hadn’t done was arrange a presentation for findings so far.

Paddy was happy with the progress so far, and after we discussed a number of things, we came to the following action points:

  1. Do a quick and dirty analysis of data
    1. Mobility analysis
    2. Periodicity
    3. Buddys
    4. Spatial degree
    5. Situation detection e.g. what does periodiciy mean?
  2. This is so that we can ask:
    • Do we have the data we need already?
    • What are the limitations of the data?
    • Are there other questions we need to ask?
  3. Plan a presentation for next wednesday morning (more of a brainstorm) to develop the ideas further, and really try to hammer down the larger plan

Paddy also suggested that we think about putting a paper into ubicomp (deadline 13th March) about our analysis of this data, but put a spin on it, e.g. what does periodicity mean? Can we predict events based on this? – Can we infer some useful context, based simply on the structure of the data, without the need for advanced techniques ( – i call this Urban Guerilla Sensing).

We suggested that we might be able to do two applications based on one of buddy finding analysis part (see mobile_agents and PhD the Story) the first, Paddy dubbed F3 (Facebook Friend Finder) where we encourage people to collect data for us, in return for detecting the presence of other facebook users, and suggesting friends based on frequency of co-location. The second was a similar application, but for regular visitors to research seminars.

I mentioned my vision on the next three points of reference, the first being a paper about the collection and analysis of this dataset, the second being another work which tied this into an simulator for the dataset, which synthesises this data in to a generic set, which can be used to test MANETs etc. The final thing (I didn’t get this far) being the final writeup of my PhD which brings all of these ideas together.

Paddy likes this, and suggested the idea of Pattern Language (used to desrcribe patterns in software engineering) which had recently been applied to Ubicomp environments to describe patterns in situations, Paddy thought that this might be particularly relevent to this, and that he would like to see some language of description emerge from our analysis. This sounds like a great idea. 🙂

Finally, Paddy spoke anbo

Meeting with Davide 14 Dec 2009

December 14th, 2009 No comments

Had a meeting with Davide to discuss current research,

we talked about what I had discussed with Paddy, and Davide seemed to think this is effectively the same as the E-DTN position paper, and that we should pursue these ideas further.

We decided that in lieu of getting access to largert datasets, we should look at the ones we have allready.  I suggested that we use the Tom dataset that was collected over a week or so when Tom used the N95 I programmed – as a start this might help us to see what the data looks like. He suggested the following tasks:

  • Contact Eiko Yoneki to see if she has some datasets that we could use
    • UPDATE: She didn’t have any datasets and she is eager to get some herself…
  • Look at Grahams simulator, understand it, and extend it to include the ability for location data to be incorporated
  • Generate two graphs from the Tom data (which he called the TomStalker dataset):
    • Latitude vs Longitude vs Number devices seen (3d)
    • Frequency of device spotting vs time
  • Look into taking a statistics course at ucd, to learn the techniques of statisical analysis
  • Include him in correspondance about this

Meeting with Prag 9 Dec 2009

December 10th, 2009 No comments

Had a brief meeting with Prag Sharma, who described to me the sort of things that the clique group were doing.

I explained to him that I was interested in ways of analysing social networks in terms of movement patterns. He mentioned a few datasets that clique has some access to: Conrad and Fergul have access handset data from 6 million Nodes from a telephone network – IDIRO, but he did not know what the data included. Another dataset was NORON data, which is to do with financial fraud and included banking transaction data.

He suggested that a good person to talk to was Derek Green, who he thought was doing  similar work.

We saw Derek in is cube, and it seems he is looking more at social clustering, but we thought there might be some interesting overlap, so I will send him my position paper, and he will send me his recent presentation.

Prag suggested I check out the clique website.

Meeting – Basadaeir paper for IJHCR

September 7th, 2009 No comments

Met with Graeme, Paddy and Simon regarding a request for a submission to the IJHCR journal – from the pervasive LBR – Basadaeir paper

http://www.igi-global.com/ijhcr

We decided that even though its not directly related my research, it would be worth submitting, as we would all benefit from a journal publication, and this seems to be fairly low bar….

My job is to manage this project, and let paddy/simon/graeme know what they need to do – Paddy said he might even write something.

Graeme and I went through the basic structure of the project, and came up with some initial ideas.

The project will have to be re-worked quite substantially, and might need to be coded from scratch. I have some concerns about whether this is worth doing if it’s not going to be part of my research. Will discuss with Paddy tomorrow.

Simons Subgroup Meeting 02 Mar 2009

March 2nd, 2009 No comments

Today I met with Simon and his subgroup, to which I have become an adopted member, to get some feedback about my PhD direction.

I had previously met them and gave a 25 word overview of my PhD topic. At that time they were very helpful in giving feedback about the viability of my topic, and we suggested that at the next meeting we would talk in more detail about myself and Olga’s research.

At this meeting, I gave an overview that I was interesting in researching what the combination of social networks, and personal devices, to create a Delay Tolerant Network technique that uses the properties, facets and behaviours of human networks and mobility to send messages. With a view to using this network for metropolitan area environmental sensing.

I described my thoughts that we are reliant upon a infrastructure for our networking needs today, but there are various costs to this. To the user, to the providor, and perhaps to the environment. I gave some rough calculations as to the cost of deploying 1000 motes for a year which based their reporting communications on 3G networking, and whilst an individaul mote only used approx 240kb per day of bandwidth, this equated to 85GB per year, at a roughly estimated cost of 42,000 euros per year.

I said that I felt it is feasible to deploy some other mechanism for comunications that utilises the power in our pockets. I asked for confirmation that this was a valid topic, and that there was enough scope for research in this to make it a valid topic.

The general feeling was that there were some novelties in this, and Davide (Cellai) gave a very good explanation of similar problems in nature (Protein Interaction Networks) and felt that the science was in finding a way to describe such dynamic networks, and that there was allready a lot of research in static networks, but not in these dynamic ones.

Point 1: There is no formal language to describe dynamic networks/ the dynamics of networks

Question 1: How do you descibe how a network is evolving?

Question 2: What parameters do you need/have to describe?

Cosideration 1:  Failure models

Simon pointed out that this type of research is validated by NASA who are looking for ways to use DTN in swarm based autonomous missions to mars/space. Whilst this is not directly related (due to a lack of social networks), the ideas can still be used.

Davide also pointed out that in his and Graeme’s research, they have identified that mobility models provide a structure to, and therefore affect, dynamic networks, and that there is an area of research in this space. (which confirms my previous thoughts and efforts towards generating a reliable mobility model)