Archive for the ‘Publications’ Category

BubbleH and SMW11

April 19th, 2011 No comments

Our paper for SMW11 was accepted, and now we will be able to include the results from the bug-fixed version of  BubbleH, which performs very well. An addition that Pádraig suggested, was to ignore level information in the hierarchy, and simply use community size. This has the benefit of making the algorithm simpler, but still incorporating hierarchical structure. I ran the two versions side by side and found that they perform almost identically, with some cases ignoring level being slightly better!

MIT-NOV Dataset, with levels included and not included for multiple parameters to H-GCE

MIT-NOV Dataset, with levels included and not included for multiple parameters to H-GCE

This plot is very hard to read, but it is possible to see the similarities at a broad level. The best performing run was with H-GCE parameters of K=3, E=0.15, ST=0.9, MAP=0.9 and Z=2. It’s structure seems to be relatively flat, with a large number of communities:

click to view

   - 1(5)
   - 2(5)
   - 3(8)
   - 4(8)
   - 5(8)
   - 6(4)
   - 7(28)
   - 8(27)
   - 9(22)
   - 10(17)
   - 11(13)
   - 12(20)
   - 13(16)
   - 14(26)
  |  |
  |   - 15(12)
   - 16(7)
   - 17(4)
   - 18(4)
   - 19(3)
   - 20(8)
   - 21(8)
   - 22(3)
   - 23(13)
   - 24(8)
   - 25(27)

This gives us the following graphic for the SMW11 paper.


MIT-NOV Dataset, for multiple parameters to H-GCE, compared to Bubble, PROPHET and Flood

The latency is shown below, which seems to follow the same trend as the previous version, but with BubbleH actually beating all but Flood at the end.

Latency in MIT-NOV dataset for Bubble, BubbleH, PROPHET and Flood.

Latency in MIT-NOV dataset for Bubble, BubbleH, PROPHET and Flood.

This is a positive result, but whilst doing some work towards the next paper for NGMAST11, I realised that we should be doing runs for multiple parameters to K-Clique, however for this paper, probably don’t need to worry so much. Also, for reference, the average value for BubbleH is included in the plot below.


We need to consider whether to evaluate multiple parameters to BubbleRAP, and see whether this affects the algorithm. Also, we need to consider whether the hierarchy is really making things better or is it the sheer number of communities, because the best performing run has a quite flat structure.

next steps

February 17th, 2011 No comments

Met with Pádraig to talk about next steps, discussed the results so far with the four clustering algorithms. The next steps are:


  • Stop using the simulation data for community finding.

Posit: all historic data is available and there is a process that is informing community finding, this data is then being used for routing test period.

  • Tune GCE so it finds more than 1 community
  • (Determine what happens in Bubble-Degree when rank is equal – does it keep or pass) it keeps it – rank must be higher
  • Use weighted edges for GCE – Weight based on:
    • Connected time
    • Number of connections
    • Or, threshold as in BubbleRAP
  • Use threshold to remove edges for MOSES

If we find that we get improvements based on the community finding algorithm, the next step would be to synthesise some new datasets. Alternative datasets include Cabspotting, Rollernet, Social Sensing.

We could then map out an analysis: message routing that is informed by overlapping community finding, and interesting ways of caculating those communities as time goes by. Towards a paper: ad-hoc message routing based on overlapping communities.

It might also be useful to explore the difference in utility of Overlapping vs Partitioning community finding algorithms.

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

Discussion with Graham W

October 26th, 2009 No comments

Had a discussion with GW about other things to test within datasets, for example, what use is it to simulate message passing between users who do not know each other, and if we had some knowledge about this data, can we find a more efficient way to route messages. This led us to talk about:

  • how many nodes can you get to within x hops in a network?
    • how many paths between friends need to use strangers and vice versa – can be used rto define privacy rules too 🙂
    • see miklas paper about defining friends and strangers
    • The point being that you may never need to send a message to any body else

Graham showed me how to run the simulator he wrote, and we talked about writing a paper together for an upcoming conference – but decided the deadline was too soon, and that we didn’t have any new results to put into it.

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

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.

Sensormash paper

February 26th, 2008 No comments

Last week, we submitted a paper to the Pervasive Late Breaking Results section of the Pervasive conference in Sydney.

Attached is the document (pdf).

Sensormash uses construct as its datastore, and allows users to mash-up the readings from sensors, to give a derived location reading for a user, as well as an average reading.

Categories: projects, Publications