Different results when ncpus> 1

User 112 | 3/24/2015, 4:10:01 PM

Hello. I try implement algoritm with attacks on hubs(vertex with high degree). Attach: attack.cpp.txt I created equivalent algorithm using igraph python package. Attach: attackpython.txt I compare result both algorithm using test graph. Attach: testgraph.txt in tsv format. My Graphlab's algoritm resulted sometimes equal igraph's, but sometimes not. Attach: result_compare.txt When i set ncpus = 1 they always equal.

I'm sorry for big size of source files. But I will be glad any hints about what wrong.

Comments

User 1190 | 3/24/2015, 5:23:47 PM

Is the algorithm deterministic under async parallel execution? If not sure, you can try using synchronous engine which might give you more stable answers.


User 112 | 3/24/2015, 5:50:33 PM

Algorithm not deterministic under both engine: synchronous and asynchronous I tried with --engine=synchronous , but it is still not deterministic


User 112 | 4/6/2015, 5:33:03 PM

Finally, i resolved this issue: if we have several hubs(vertices with higher degree) with equal degree, igraph chose one with small id between them, but my algorithm choose one random. Hubs with equal degree but different betweenness centrality have different impact to gian cluster in graph. Like in image - removing vertex 6 give more destruction. <img src="http://cdn.vanillaforums.com/graphlab.vanillaforums.com/editor/5g/7h6gruyokhjt.jpg" alt="" />

I have another question, what is the fastest way to find N hubs in graph using GraphLab API? I need sort vertices by degree and get N vertex with higher degree from them

Currently i'am using 1. hubcounter hubstat = graph.mapreducevertices<hubcounter>(hubdata, alivevertexset); 2. get N vertices from hub_stat.

hubcounter hubdata(const graphtype::vertextype& vertex) { return hub_counter( vertex.id(), vertex.data().degree); }

struct hubcounter { std::map<uint64t, std::set<uint64t> > hubwith_degree;

explicit hubcounter(uint64t id, uint64t degree) { hubwith_degree[degree].insert(id); }

hubcounter& operator+=(const hubcounter& other) { for(std::map<uint64t, std::set<uint64t> >::constiterator iter = other.hubwithdegree.begin(); iter != other.hubwithdegree.end(); iter++) { for(std::set<uint64t>::constiterator nestediter = iter->second.begin(); nestediter != iter->second.end(); nestediter++) { hubwithdegree[iter->first].insert(*nestediter); } } }


User 112 | 4/6/2015, 5:36:29 PM

attached hub_counter


User 1190 | 4/6/2015, 5:46:18 PM

What you proposed is a good way to find N hubs.


User 112 | 4/6/2015, 5:52:14 PM

Hello Jay Gu. Ok, thanks for reply.