[Networkit] I think we need a centrality index construction kit

Christian Staudt christian.staudt at kit.edu
Thu Jun 18 00:11:20 CEST 2015


Dear all,
browsing the nice collection of centrality indices at http://centiserver.org, I thought about the following: Are there really 113 different node centrality measures? And how many of them should we implement in a network analysis software package then?

On a closer look, it seems that many of them are actually just variations based on the same core computations.

Example: NetworKit currently has...
	Betweenness
	ApproxBetweenness
	ApproxBetweennes2
	Closeness
	ApproxCloseness
which are all based on shortest path searches of some sort. I have already modularized BFS and Dijkstra’s algorithm so that their code doesn’t have to be copy-pasted into all these classes, which would be a bit crazy. Still, we probably have redundant code here and certainly redundant computation if we apply them all to one network. It’s probably possible to modularize this better to avoid both forms of redundancy.

Here are some more centrality indices to which this may apply:
	Average Distance: just the inverse of closeness
	Barycenter Centrality: "Closeness scores are calculated using the formula 1 / (average distance from vertex v to all other vertices) and Barycenter scores are calculated as 1 / (total distance from vertex v to all other vertices).”
	Eccentricity Centrality: "The greatest distance between v and any other vertex.”
	Stress Centrality: "The simple accumulation of a number of shortest paths between all node pairs"
	κ-Betweenness Centrality (?): "κ-betweenness centrality subsumes Freeman’s definition of betweenness centrality for κ = 0"

What about other families of indices? Are there similarities between Eigenvector Centrality, PageRank and Katz Centrality that could be used for modularization?

I’d like to encourage anyone working on centrality indices to start thinking about this when adding yet another centrality algorithm class to NetworKit. There may be tradeoffs between modularization and optimization, but with proper modularization, improvements to one component benefit all algorithms sharing that component.

The same principles could also apply to updating centralities in dynamic networks, though I think we should focus on getting it right in the static case first. Furthermore, we should clarify how this relates to current projects on edge centrality measures at ITI as well as recent work on centrality by Ulrik Brandes (which may go further than what I have in mind right now).

I would appreciate comments on this.

Best regards
Chris


christian.staudt at kit.edu
http://parco.iti.kit.edu/staudt/index-en.shtml
Institute of Theoretical Informatics - Parallel Computing Group
Building 50.34 Room 034
Karlsruhe Institute of Technology (KIT)








-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150618/cce30853/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150618/cce30853/attachment.sig>


More information about the NetworKit mailing list