Home > Uncategorized > The problem parents

The problem parents

After we submitted the paper to FindingNEMO2011, I started to work on the Social Sensing dataset, and Pádriag’s suggestion to create a Random community finding algorithm. Initial tests showed a peculiar phenomenon: All runs of BUBBLERap and for KCLIQUE with multiple parameters were coming up with exactly the same results. Now, this really shouldn’t happen, so I looked further.

Unfortunately, or fortunately, depending on how you look at it, it is not a bug in the code. It was because of a decision we made a long while back, to force each community finding algorithm to output a top level community including all nodes. This works well for BubbleH, which uses targeted community routing. But, and in hindsight, this is obvious, BUBBLERap simply looks as community membership, and so, when it meets another node, they are ALWAYS in the same community, and therefore it routes using ONLY local ranking. This has the effect of making our implementation simply centrality based routing.

I spent the last couple of days re-engineering the configuration, so that now, we can get results for communites with a global parent, and without a global parent. Shown below are the results from the FindingNEMO11 paper, and below that the updated results. Where we have used no-global-parent for BUBBLERap and a global parent for BubbleH.

Results used in FindingNEMO11 paper

Results used in FindingNEMO11 paper

Results for ALL CFAs and Datasets, using Global Parents only for BubbleH

Results for ALL CFAs and Datasets, using Global Parents only for BubbleH

The new results shows a slightly different picture, in that the improvement in delivery ratio and latency are less pronounced. One interesting thing is that for InfoMap, which partitions the graph, the results are exactly the same. This is because there is no ovelap, which both algorithms to work in the same way, i.e. BUBBLERap uses global centrality to route between nodes of different communities, and BubbleH uses the local centrality in the GLOBAL parent to route to nodes not in smaller communities. This means that BubbleH is actually designed solely for overlapping community structure. With regards to the Heirarchichal clustering of HGCE, we see that it performs poorly for Cambridge, but roughly equally for the others.  LinkClustering for BUBBLERap in InfoCom2005 and MIT-NOV performs very poorly on Delivered Hops. This could be down it creating a large number of communities.

ngpvsgp-bubble-mit-nov-linkclustering

Global versus No Global parent for LinkClustering BUBBLERap on MIT November,

It seems the difference is very pronounced in LinkClustering, but it is not a problem with the results. The differences between the results for HGCE is the result of randomness (pertubations) for each run.  This may result in withdrawing the paper from SMW11. Which is very unfortunate.

My next step is to finish getting the Social Sensing dataset prepared, (by testing muliple CFA parameters against it) and add it to the matrix plot. Then, I will finish doing the Random runs against all of the datasets, to see if the CFAs have any real effect on performance, or whether it is insignificant. (!)

Finally, if things go to plan, I will continue working on the twitter based dataset, and perhaps the new sensor dataset from St Andrews.

Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.