Add closeness vitality to python- igraph

[viraj96]

It is metric that is implemented in python, in networkx

It has also been added as an additional feature request in r-igraph here.

I have written a small function for the same purpose. Can you review it and tell if it needs further improvement.

def closenessVitality(graph):
	temp = np.matrix(graph.shortest_paths_dijkstra(mode = 3))
	initial = temp[temp != np.inf].sum()
	closeness_vitality = []
	for i in range(graph.vcount()):
		tempGraph = graph.copy()
		tempGraph.delete_vertices(i)
		vertex_cont = np.matrix(tempGraph.shortest_paths_dijkstra(mode = 3))
		closeness_vitality.append(initial - vertex_cont[vertex_cont != np.inf].sum())
	return closeness_vitality

[ntamas]

I don't think that closeness vitality will be added as a separate function to igraph. Simple solutions like the one proposed here or the one proposed in the r-igraph repository do the job well for small graphs with only a few lines of code so it could be published separately; however, an implementation that scales up properly for large graphs requires much more thinking and testing than what I could dedicate to it right now. The implementation above and the implementation in the r-igraph repository are problematic for multiple reasons:

• First of all, the implementation above depends on numpy, which is not a dependency of igraph, and it's not worth making it a dependency just for the sake of a single function.

• Second, the implementation calculates the full shortest path matrix. For a graph with N vertices, this would be N*N items - but note that the entire matrix is needed only so you can get the sum of its items. You could simply calculate the matrix row-by-row in a loop to reduce the memory requirement of the algorithm significantly.

• This implementation makes several copies of the graph (one for every vertex), which does not scale up nicely to larger graphs with tens of thousands of vertices (or even more). It seems like the only reason why the current implementation needs a copy is to be able to perform shortest path searches while excluding a single vertex from the search. In a scalable implementation, we would need to implement the shortest path search in the C layer in a way that does not require one to remove the vertex explicitly from the graph (it is a costly operation); we could tweak the implementation of the shortest path search instead to ignore this vertex.

• It is unclear how the metric should handle disconnected graphs or graphs with multiple edges or loop edges. If we decide to adopt this feature for the core of igraph, all these corner cases would have to be considered carefully.

So, in summary:

• Simple implementations of the metric can be coded in a few lines of code either in Python or R so there is no need to add the function to the core of the library.

• Scalable, advanced implementations require much more time than what I have right now, so I only see a chance for adding this to igraph if someone files a pull request to igraph/igraph with a C implementation along with test cases and documentation that describes how the implementation handles graphs with multiple edges, loop edges and disconnected graphs.

[szhorvat]

We should either close this, or complete the feature request by writing up all the important details. There are two key questions:

1. Is there an opportunity to compute this much faster than by the naïve method proposed above (i.e. repeated vertex deletion and re-computing shortest paths)? Is it possible to re-use information from previous shortest path runs and speed up the computation?
2. Is this a widely used network measure?

If the question is "no" to both, we should close it. If one is yes, the other is no, we can have a discussion and the issue should be transferred to the C core repo.

@viraj96 Can you help us answer these two questions by doing a bit of research?