Betweenness Centrality

User 442 | 7/5/2014, 4:22:13 PM

Does anyone have example of Betweenness Centrality in a distributed mode? Please share with me if you have one.

Thanks.

Comments

User 447 | 7/6/2014, 4:38:45 PM

Currently working on one, but it is not yet finished. I am hoping to have a beta ready before the end of the week. Please keep in mind that if you need distributed mode, traditional betweenness centrality is prohibitively expensive: the best known version is O(2nl) where n is number of nodes and l is the number of links. There are workarounds that will be implemented that are not exact.


User 442 | 7/9/2014, 11:46:40 PM

Thank you so much for the reply. I am desperately waiting for the code to be released.


User 447 | 7/10/2014, 1:43:17 AM

I have multiple open source projects running simultaneously. I can prioritize. Chat with me offline.


User 447 | 7/25/2014, 11:11:55 PM

the code is up at https://github.com/dmcennis/graphlab on the master branch


User 6 | 7/26/2014, 1:45:47 AM

Where is the source code? Did not find it inside the repo. Thanks


User 442 | 7/26/2014, 5:12:52 PM

The code is inside apps folder https://github.com/dmcennis/graphlab/tree/master/apps/djikstra I tried to run the program but it is not loading the data

INFO: distributedgraph.hpp(setingressmethod:3201): Automatically determine ingress method: grid INFO: omniengine.hpp(omni_engine:191): Using the Synchronous engine. Loading graph using line parser

vertices: 0 #edges:0

And my input data is

1 2 3 4 2 3 4 5 3 0 1 2

Thanks


User 535 | 7/27/2014, 2:50:27 AM

Looks like there is a missing line in code

<code class="CodeInline">graph.load(graphdir, lineparser); graph.finalize();</code>

And some comments would be nice to catch up with the logic of the code.


User 545 | 7/29/2014, 2:25:10 PM

Hi mcros

i have added the graph load and graph finalize but it is not working. I am getting all the score zero. Can you please help me?


User 447 | 8/4/2014, 1:01:53 AM

The parser has the input format vertexid id strength id strength ...

Another person who accessed my code has recently posted without attribution nearly identical code for inclusion in graphlab. I'm sure it was independent discovery. I will be uploading descriptions of my algorithm and other documentation in the not too distant future.


User 447 | 8/10/2014, 1:00:55 AM

The most recent version on my fork has the fixes in and the documentation that was requested.


User 593 | 8/11/2014, 8:32:15 AM

@kjosh @dmcennis how does overcome this problem and I also use the lastest code. But when I loading the graph, it resulted in #vertices: 0 #edges:0. thanks


User 586 | 8/25/2014, 12:45:05 AM

Very cool and interesting, but hasn't worked for me on a small test graph.. just outputs vertex ids, the for loop in djikstra_writer() isn't entered

wasn't aware of a vertex-centric betweenness centrality algorithm, does djikstra shortest path work with the vertex-centric abstraction?

Thanks


User 447 | 12/6/2014, 6:44:38 PM

Multiple updates to my Github account have disappeared and contents to several posts have changed from happy users to complaints. I seem to have been hit by a hacker redirect on my production box and there was source code damage on the box itself. I'm doing what I can.


User 447 | 3/9/2015, 1:32:17 AM

@DannyBickson Please confirm you have access to the working version of Betweeness and other algorithms I sent you by email.


User 1630 | 3/25/2015, 3:39:34 AM

Hi Dmcennis:

I have noticed that there are Betweenness and Closeness in the folder. ~/graphlab/release/toolkits/graph_algorithms

According to the description:~/graphlab/toolkits/graphalgorithms/graphanalytics.dox, the Betweeness sounds like an approximate Betweenness Centrality algorithm. "The output estimates betweeness using ~3000 randomly selected spanning trees"

I have run the Betweenness algorithm based on a graph file following the format requirement (i.e., <long node_id> [<long nodeid> <float edgevalue>]). ./betweeness --graph ~/graphfiles/soc-Epinions1.txt --samplesize 480 --ncpu 3 --saveprefix BC. However, the algorithm finished in seconds, and all Betweenness scores are zero. So, I guess the Betweenness algorithm does not function properly.

I wondering do you have similar experience with me, as well as what are the difference between your Betweenness Centrality algorithms and the above mentioned algorithms.

Thanks and look forward to your reply!


User 447 | 4/12/2015, 11:15:21 AM

Here is a link to the github repository I sent to Danny manually. Let me know if it works. The records should show the github upload with different content then currently included. If it doesn't or doesn't work, check back and I'll try something else.

https://drive.google.com/open?id=0Bx9PY06zuheNbDVEUTBCeUVqN1U&authuser=0


User 1032 | 4/13/2015, 5:20:10 PM

Hi,

I tried downloading the betweeness.tgz at the drive.google link. However, when I tried extracting from it, I keep failing, with the problem being an unexpected end of file. I tried to download the file a couple of times and each time I was unable to extract. Maybe something went wrong with the compression?

Thanks


User 447 | 4/14/2015, 4:00:20 PM

The file was fine on my end. I have no idea how to fix this. If I can figure something out, I will re-post.


User 1032 | 4/15/2015, 10:36:18 PM

Just to be sure, the command you used to extract from the file is "tar -xzvf betweeness.tgz", correct?