Gelly, problem vertex centric iteration

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Gelly, problem vertex centric iteration

Yi ZHOU-2
Hello everyone,
I need some suggestions about debuging the Affinity Appropogation
algorithm for gelly.

In my implementation, there is a problem with the MessagingFunction in
Vertex Centric Iteration

The test graph is a completed directed graph (25 vertices in total),
i.e. there are two opposite directed edges between every two vertices.
The value of each vertex is a hashmap, in which contians information of
all of the vertex's neigbor vertices.

My MessagingFunction is implemented as follow,

            if (getSuperstepNumber() % 2 == 1){
                 /*Odd step: Propagate availability*/
                 int msgCnt = 0;     //Debug variable, count out going
edge number
                 for (Edge<Long, Double> e: getOutgoingEdges()){
                     Long dest = e.getTarget();
                     sendMessageTo(dest, new Tuple2<Long,
Double>(vertexKey, vertexValue.get(dest).f2));
                     msgCnt++;
                 }
                 System.err.format("Step %d: Vertex %d send %d\n",
getSuperstepNumber(), vertexKey, msgCnt);
            }else{
                 /*Even step: propagate responsibility*/
                 for (Edge<Long, Double> e: getOutgoingEdges()){
                     Long dest = e.getTarget();
                     sendMessageTo(dest, new Tuple2<Long,
Double>(vertexKey, vertexValue.get(dest).f1));
                 }
             }

I use a msgCnt for conuting the neigbor edges in the odd step. During
the 1st super step , every vertex should send message to 24 neighbor
vertices.  However,  the real result is quite strange. For some
vertices, they appropogate messages to all the adjacent vertices.
however, for serveral other vertices, they send nothing or only part of
their neighbors. i.e the getOutgoingEdges() returns none.

Step 1: Vertex 3 send 0
Step 1: Vertex 1 send 0
Step 1: Vertex 5 send 0
Step 1: Vertex 8 send 0
Step 1: Vertex 14 send 0
Step 1: Vertex 16 send 0
Step 1: Vertex 2 send 24
Step 1: Vertex 7 send 18
Step 1: Vertex 9 send 24
Step 1: Vertex 6 send 24
Step 1: Vertex 11 send 0
Step 1: Vertex 15 send 0
Step 1: Vertex 12 send 0
Step 1: Vertex 21 send 0
Step 1: Vertex 13 send 0
Step 1: Vertex 25 send 0
Step 1: Vertex 22 send 24
Step 1: Vertex 18 send 0
Step 1: Vertex 23 send 24
Step 1: Vertex 19 send 0
Step 1: Vertex 20 send 0
Step 1: Vertex 24 send 24

I do not know how to detect the problem, can anyone give me some
suggestions?
I attached the code and data also. The iteration is loaded in line 118
in AffinityPropogation.java

Thank you
Best regards.

ZHOU Yi


AffinityPropogation.java (11K) Download Attachment
AffinityPropogationExample.java (3K) Download Attachment
pom.xml (5K) Download Attachment
ToyProblemPreferences.txt (512 bytes) Download Attachment
ToyProblemSimilarities.txt (14K) Download Attachment