I am interested in algorithms that do not use shortest paths to estimate node and edge centralities in directed weighted networks.
I have considered the algorithm by M.E.J. Newman, which was derived from a current flow analogy, therefore it seems to me it would not apply to a directed network: http://arxiv.org/pdf/cond-mat/0309045.pdf
I am also trying out the algorithm by Alahakoon et. al., from which I can get an approximation of the betweenness centralities for nodes, but the error terms and required run time have been derived for node and not edge betweenness: http://www.csee.usf.edu/~tripathi/kpath-centrality.pdf
Are there other (random-walk) algorithms can estimate both node and edge betweenness for my type of network?
Thank you very much, Henning: I am looking at the 'spanning edge' paper, and it does seem to provide an interesting alternative to current-flow-type centralities. My network is however not strongly connected, so there are quite a few node pairs with no directed paths connecting them.
I also found a method that generalizes Newman's random-walk betweenness to directed graphs and allows for self-loops via the "counting betweenness": http://journals.aps.org/pre/pdf/10.1103/PhysRevE.83.046127
Still, I would be happy to learn about more methods that assess centrality without using optimal paths (shortest paths, maximum flow, etc).
hi
Your q was interesting. A conjecture with Pspice simulation maybe of interest as explained in attached pdf. If this is acceptable there seems to be more interesting transient type " betweenness centrality" (using L and C) which would require some interpretation. Directed graph values can be simulated with Diodes.
...hope it is useful.
Cheers
Have you tried the modularity function instead as in The Louvain method?
@Henning: I think that the two are related. Find the hubs rank them according to the density of traffic that they let through
Narasim, that's an interesting method, though I am not sure if it is in some way similar to the current flow analogy by Newman. Using diodes to simulate directed links seems to be new in the context of betweenness.
Asher and Henning, I knew about community finding methods based on high-betweenness edges, but had not thought about going in the opposite direction. Very curious about whether there is an algorithm out there!
Also, until recently there were not many and established methods for finding communities in directed networks, but that's another question altogether...
Many thanks! -V
Dear Violeta, I ran into the same question as you and was wondering if there would be updates to this, since the thread is a bit old by now. Thanks!
- Badges
- Science method
- Similar topics
- Teaching