Home > Thoughts, what i've been doing, What Matt Says > BubbleRAP using Heirarchical Community Structure

## 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) &gt; LocalRank(N) pass message M to P (and delete from buffer) else if (P shares a community with D) OR (GlobalRank(P) &gt; 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) &gt; 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

1. use global rank (as per original bubble rap), or
2. 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?).

Categories:
1. March 3rd, 2011 at 17:26 | #1

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

2. March 3rd, 2011 at 21:04 | #2

OK, that makes sense.