Hi, AFAIK you need to compute all shortest paths to compute the betweenness of a single vertex, at least igraph does it this way and I am not aware of a better algorithm.
So it is not worth running betweenness in parallel, you gain nothing. Gabor On Wed, Apr 24, 2013 at 8:19 PM, 四正（红砖） <[email protected]> wrote: > Hi everyone, > > I want to calculate the betweenness of each node for a network with 13498 > nodes and 101565 edges. > > by simply call betweenness(nodes,directed=False), it takes about 32 > seconds on my 8-core computer. That seems good. > > However, I just considering use full of my CPU to accelerate it. So I use > PPL, which is a parallel library for C++ in VS2012, and I made following > code: > > igraph_vector_t test; > igraph_vector_init(&test, 0); > parallel_for(0,vcount-1,[&g,&test](igraph_integer_t i){ > clock_t t1=clock(); > igraph_betweenness(&g,&test,igraph_vss_1(i),IGRAPH_UNDIRECTED,0,1); > clock_t t2=clock(); > cout<<i<<"\t"<<igraph_vector_e(&test,0)<<"\t"<<t2-t1<<endl; > }); > finish=clock(); > cout<<finish-start<<endl; > > BUT! It is very slow! It takes about 2 minutes to calculate betweenesses > of 7 nodes in parallel! > > It is faster if I use: > > parallel_for(0,vcount-1,10000,[&g,&test](igraph_integer_t i){ > clock_t t1=clock(); > > igraph_betweenness(&g,&test,igraph_vss_seq(i,i+9999),IGRAPH_UNDIRECTED,0,1); > clock_t t2=clock(); > cout<<i<<"\t"<<igraph_vector_e(&test,0)<<"\t"<<t2-t1<<endl; > }); > > It takes about 1 minute... > > So why is it? > > In my opinion, if we put many nodes into a same thread, they can share the > information of visited paths by other nodes. Am I right? > > Has anybody tried parallel computing of igraph? > > Gang > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > > -- Gabor Csardi <[email protected]> MTA KFKI RMKI
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
