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. However, even during the 1st super step , the 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 ![]() ![]() ![]() ![]() ![]() |
Hi Yi,
by debugging a bit your code, it seems that the problem is in the pre-processing step and more specifically in the filtering you do on the self edges, in the helper transferGraph method. I will have to dig a bit more to figure out the issue, but until then you should be able to work around this in one of the following ways: - use the original Edge DataSet (distanceEdges) as the Edge DataSet of the vertex-centric iteration input graph. - skip the filter entirely and check for self-edges inside the messaging / vertexUpdate functions, so that you do a no-op for these. Let me know if any of these workarounds solve your problem! Cheers, -Vasia. On 19 April 2015 at 15:00, Yi ZHOU <[hidden email]> wrote: > 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. However, > even during the 1st super step , the 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 > > |
Free forum by Nabble | Edit this page |