[BUG]: normalization issue in betweenness_centrality

[zmahoor]

Version

24.10

Which installation method(s) does this occur on?

Conda

Describe the bug.

the normalized values in betweenness_centrality seem to be incorrect when k=cudf.Series. the normalized values are not between [0, 1] and also are different from the values we get from networkx.

Minimum reproducible example

import cugraph
import cudf
df = cudf.DataFrame(
      columns=["dst", "src"],
      data=[('A','i'),('B','A'),('C','B'),('E','C'),('D','E'),('D','A'),('i','D'),('C','D')]
      )

G = cugraph.Graph(directed=True)
G.from_cudf_edgelist(df, source='src', destination='dst')
bc = cugraph.betweenness_centrality(G, normalized=True, k=cudf.Series(["i"], dtype=object))
print(bc)

Relevant log output

betweenness_centrality vertex
0                     1.2      A
1                     0.3      D
2                     0.0      E
3                     0.3      B
4                     0.3      C
5                     0.0      i


the values we get from networkx are {'A': 1.0, 'B': 0.25, 'C': 0.25, 'E': 0, 'D': 0.25, 'i': 0}

Environment details

Other/Misc.

No response

Code of Conduct

• I agree to follow cuGraph's Code of Conduct
• I have searched the open bugs and have found no duplicates for this bug report

[ChuckHastings]

We will investigate. Should be an easy fix, since the scores look proportional but not properly normalized.

[zmahoor]

@ChuckHastings should the betweenness centrality values be integers or real numbers when normalized=False? I'm getting real numbers but I assumed when normalized=False we should get the counts of shortest paths.

import cudf
import cugraph
# download data from https://github.com/rapidsai/cugraph/blob/main/datasets/karate.csv
df = cudf.read_csv(
    "./karate.csv", 
    delimiter=" ", 
    names=["src", "dst", "value"], 
    dtype=["int32", "int32", "float32"]
    )
sg = cugraph.Graph(directed=True)
sg.from_cudf_edgelist(df, source='src', destination='dst')
cdf_bc = cugraph.betweenness_centrality(sg, normalized=False)
cdf_bc.sort_values(by='betweenness_centrality', ascending=False).head(5)

vertex | betweenness_centrality
--        | --
0         | 462.142914
33       | 321.103180
32       | 153.380936
2         | 151.701569
31       | 146.019058

[ChuckHastings]

Real numbers.

The centrality score is computed by taking the ratio of total shortest paths through a vertex over all shortest paths for each s,t pair in the graph, so it's going to be a rational number represented in floating point (either float or double depending on what kind of weight you use).

[ChuckHastings]

I have identified the faulty logic in the normalization. I am working on a fix.

[ChuckHastings]

OK. I take it back.

I did find a fault in the logic (a special case was being handled incorrectly), but it does not - in fact - prevent this normalization issue.

We are mimicking the logic in networkx for normalization. If you test this in networkx you'll see the same issue:

Gnx = nx.DiGraph()
Gnx.add_edges_from([('i','A'),('A','B'),('B','C'),('C','E'),('E','D'),('A','D'),('D','i'),('D','C')])
nxbc = nx.betweenness_centrality(Gnx, normalized=True, k=1, seed=2)
print(nxbc)

Yields the result:

{'i': 0.0, 'A': 1.2000000000000002, 'B': 0.30000000000000004, 'C': 0.30000000000000004, 'E': 0.0, 'D': 0.30000000000000004}

I believe there is an error in the normalization logic in networkx that we have duplicated. The normalization is done by determining a scaling factor. That scaling factor computation is incorrect if you don't include the endpoints and you compute approximate betweenness.

We will put in a fix for this and pursue updating nx as well.