Timeline for Methods to approximate the betweenness centrality on large networks
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 6, 2013 at 20:08 | vote | accept | Vass | ||
| Sep 6, 2013 at 13:50 | answer | added | ianr | timeline score: 5 | |
| Sep 2, 2013 at 10:48 | comment | added | Vass | @JohnMangual, good idea! | |
| Sep 2, 2013 at 10:39 | comment | added | john mangual | @Vass Have you looked at cs.stackexchange.com ? | |
| Sep 2, 2013 at 8:58 | comment | added | Vass | @JohnMangual, I have recently posted a question on stat.stackexchange.com which I am waiting to see some activity. This site is much more active and the answers more in depth | |
| Sep 2, 2013 at 0:33 | comment | added | john mangual | have you tried stats.stackexchange.com ? | |
| Sep 2, 2013 at 0:26 | answer | added | ericf | timeline score: 3 | |
| Sep 1, 2013 at 20:28 | comment | added | Vass | @fedja, they arise from twitter, so large hubs. They vary. Usually a very steep degree distribution decay | |
| Sep 1, 2013 at 20:25 | comment | added | fedja | Do the graphs have any special structure (low vertex degree, small diameter, whatever) that can be relied upon? | |
| Sep 1, 2013 at 20:12 | comment | added | Vass | @fedja, I was hoping for something linear in complexity. I agree with your arguments that in general there are no guarantees with a stochastic approach. But that is the same issue with all sampling approaches. What if I check for consistency of the results with individual runs? Like perform convergence diagnostics on the centrality computed? | |
| Sep 1, 2013 at 12:27 | comment | added | fedja | The little problem is that adding a single edge may change the quantity quite drastically: imagine two copies of a complete graph $K_n$ joined by an edge. If $v$ is on that edge, $g(v)\approx 2n^2$. However, adding one more edge of the same type brings it down to about $n^2$. The random walks (backtracking or not) have very little chance to notice that extra edge: about $L/n^2$ where $L$ is the walk length, so you cannot do it in time much less than $n^2$. However in this time you can do a lot in a deterministic way too. What running time (in terms of graph complexity) are you aiming at? | |
| Sep 1, 2013 at 9:53 | history | edited | Vass | CC BY-SA 3.0 |
added 33 characters in body
|
| Sep 1, 2013 at 9:21 | history | asked | Vass | CC BY-SA 3.0 |