Search code examples
pythongraph-theoryigraphnode-centrality

Unreasonable output generated by python-igraph closeness centrality

I am currently working on several graphs for generating their edge betweenness and node closeness, using python-igraph, setting as not directed, weighted, and having cut-off.

Edge betweenness could be acquired successfully. However, for closeness, the results can only be returned when no cut-off has been set; or the output would be 1 or NaN only. This issue happens regardless of the size and weight of the graph.

The following is one example graph. Please see the graph here.

I firstly created the edges dataframe by Pandas.

   u_index  v_index  length
0        0        1       1
1        0        2       1
2        0        3       2
3        0        4       3
4        1        2       1
5        3        4       2

Then create the graph based on information in the dataframe.

ntwrg = ig.Graph()
ntwrg.add_vertices(1+max(edges["u_index"].max(), edges["v_index"].max()))
ntwrg.add_edges(list(zip(edges["u_index"], edges["v_index"])))
ntwrg.es["length"] = edges["length"]

Then I started calculating centrality. When no cut-off, the results can be generated successfully:

ntwrg.closeness(weights="length")

    cls_cen
0  0.571429
1  0.444444
2  0.444444
3  0.400000
4  0.307692

However, when adding cutoff = 3, the expected result would be:

ntwrg.closeness(weights="length", cutoff=3)

    cls_cen
0  0.571429
1  0.600000
2  0.600000
3  0.400000
4  0.400000

While the result returned comes to be:

   Cls_cen
0      1.0
1      1.0
2      1.0
3      NaN
4      NaN

On the other side, edge betweenness can be generated normally even with cutoff=3:

ntwrg.edge_betweenness(weights="length", cutoff=3)

   Btw_cen
0      2.0
1      2.0
2      3.0
3      1.0
4      1.0
5      1.0
Solution

  • tl;dr This was a bug in python-igraph 0.10.0 – 0.10.3. It is fixed in 0.10.4.

    This is a bug in python-igraph, which I just fixed. Thanks for pointing it out. The problem is present only in the Python interface of igraph, not in the igraph C library, or in other high-level interfaces of igraph.

    Here is a transcript of checking this after the fix:

    In [1]: import igraph as ig

In [2]: g = ig.Graph([(0,1),(0,2),(0,3),(0,4),(1,2),(3,4)])

In [3]: g.es['length']=[1,1,2,3,1,2]

In [4]: g.closeness(weights='length')
Out[4]: 
[0.5714285714285714,
 0.4444444444444444,
 0.4444444444444444,
 0.4,
 0.3076923076923077]

In [5]: g.closeness(weights='length',cutoff=3)
Out[5]: [0.5714285714285714, 0.6, 0.6, 0.4, 0.4]

    You can compile the development version to get the fix immediately.