BubbleRAP using Heirarchical Community Structure
The existing BubbleRAP mechanism works as follows:
on N connected with encountered node P for each message M (for destination D) in buffer of N if P == D pass message M to P else if N and P share a community with D if LocalRank(P) > LocalRank(N) pass message M to P (and delete from buffer) else if (P shares a community with D) OR (GlobalRank(P) > GlobalRank(N)) pass message M to P (and delete from buffer) // keep message
The proposed version of Bubble-H (Bubble Heirarchical) works as follows
on N connected with encountered node P
for each message M (for destination D) in buffer of N
if P == D
pass message
else
if P is in a CLOSER community, that also contains D
pass message M to P
else if P and N share CLOSE community with D
if(LocalRank(P) > LocalRank(N))
pass message M to P
else
keep message
// we need to still push messages to the top when there is no overlap
else if(P is in a BRIDGING community with D, that N is not)
pass message M to P
else
keep message
Bubble-H as above uses the notion of CLOSE(R) communities, and BRIDGING communities:
- A CLOSER community, is the one that is lower down in the hierarchical structure of communities, for example, when N has the message destined for O, on meeting P, he would pass the message, as P is in a community lower in the hierarchy. Being CLOSER suggests that P is somehow more likely to be connected to O.
- The shared CLOSE community is one that is low down in the heirarchy scale, that the destination is a member of, but that both nodes also share. They compare local ranks to decide who should have the message. For example. N and M share a CLOSE community with O and P.
- A BRIDGING community, is at a lowest point that bridges a gap between branches of the structure, in the example, the community C2 containing CDEA, GF and H, would be considered a bridge. (not the best example?). This is handy for when a node who is not in a low level community with the destination needs to get the message closer.
I think there might be something missing from this new algorithm, and I am not convinced it is any different to the existing BubbleRAP protocol, especially as nodes are not clustered hierarchically.
A note on hierarchical GCE: this algorithm produces communities that are hierarchically organised, however, the nodes within these communities can and will overlap, so that a node in a community in one partition of the tree, may also appear in a community on the other side, which means I have now realised that the illustration above is not a correct representation.
UPDATE (3/3/11): Pádraig’s comments make sense, and so the following is a better algorithm:
on N connected with encountered node P for each message M (for destination D) in buffer of N Identify bridging community (BC), smallest community containing N and D. IF P ==D then pass the message ELSE IF P shares a community with D that is smaller than BC then pass the message. ELSE IF P is more central in BC than N then pass the message.
UPDATE (7/3/11): I have managed to get Conrad’s code to run today and output the correct data, and it seems that the output is very different from what I had imagined; the MIT-Nov-Training dataset produces lots of non-heirarchical communities, and one or two parent-child structures (depending on parameters) – this means that in some/most cases, there will nodes who do not have bridging communities.
I am currently implementing BubbleH in the simulator and need to decide what to do in the case of no bridging community; two choices as I see it are: When a bridging community is not found either
- use global rank (as per original bubble rap), or
- Keep message until a bridging/smaller community is found.
My favourite is option 2, as this helps to hold the message by default, until a useful encounter comes along (a small world property?).
Here is my go at Bubble H
1. Identify bridging community (BC), smallest community containing N and D.
2. If P shares a community with D that is smaller than BC then pass the message.
3. IF P is more central in BC than N then pass the message.
In this scenario 3 is the UP step and 2 is the DOWN step.
For the example on the blog the list of sets below should be pretty much what GCE returns.
ACDE
H
FG
HFG
ACDEHFG
ACDEHFGI
O
P
OP
MNOP
ACDEHFGIMNOP
OK, that makes sense.