graphinius Reduce #shortest_paths(u,v) in uniform-weight graphs by manipulating edge weights

Reduce #shortest_paths(u,v) in uniform-weight graphs by manipulating edge weights

Open cassinius opened this issue 7 years ago • 0 comments

if all edges in a graph have the same weight, there are exponentially many equal shortest paths between two nodes (u,v)
this drastically increases computational costs for calculating centralities that rely on SPs, like betweenness
randomly jostling edge weights will preserve overall network structure, but could drastically reduce the amount of SPs in the network and therefore computational costs
on the other hand, the actual centralities might be greatly affected / distorted by that approach, so we need to come up with some experiments that will allow us to estimate that effect

Jan 18 '18 22:01 cassinius