Apparently, both node betweenness and edge betweenness calculated with networkx and networkit give different values than what supposed to be.
Lets consider the following undirected graph (pag. 20/85 in these Lecture notes), written as edge list and saved in mygraph.txt:
1 2
1 5
2 3
2 5
3 4
4 5
4 6
The node betweenness should be (pag. 20/85 in these Lecture notes):
Node | Betweenness
1 0
2 1.5
3 1
4 4
5 3
6 0
However, by running the following code (I used G1 and G2 as different names for the graph in networkx and networkit, but they are exactly the same graph, coming from the same file mygraph.txt):
import networkx as nx
from networkit import *
import networkit as nk
G1 = nx.read_edgelist("mygraph.txt",create_using=nx.Graph(), nodetype = int)
G1.number_of_nodes()
node_btw = nx.betweenness_centrality(G1, normalized=False)
edge_btw = nx.edge_betweenness_centrality(G1, k=None, normalized=False, weight=None, seed=None)
print('NETWORK-X')
print(node_btw.values())
print(edge_btw.values())
edgeListReader = nk.graphio.EdgeListReader(' ', 1)
G2 = nk.readGraph("/home/JohnRambo/Documents/myFolder/mygraph.txt", nk.Format.EdgeListTabOne)
print(G2.numberOfNodes(), G2.numberOfEdges())
G2.indexEdges()
btwn = nk.centrality.Betweenness(G2, normalized=False, computeEdgeCentrality=True)
btwn.run()
print('NETWORK-IT')
print(btwn.scores()[:10])
print(btwn.edgeScores()[:10])
I got these results (P.S.: I added manually the texts node betweenness and edge betweenness):
NETWORK-X
node betweenness: [0.0, 1.5, 3.0, 1.0, 4.5, 0.0]
edge betweenness: [2.0, 3.0, 3.5, 2.5, 5.5, 3.5, 5.0]
NETWORK-IT
node betweenness: [0.0, 3.0, 2.0, 9.0, 6.0, 0.0]
edge betweenness: [4.0, 7.0, 7.0, 6.0, 5.0, 11.0, 10.0]
My calculation gives different results (the node betweenness scores are in agreement with those ones shown at pag. 20/85 in these Lecture notes)
node betweenness: [0.0, 1.5, 1.0, 4.5, 3.0, 0.0]
edge betweenness: [2.0, 3.0, 3.5, 2.5, 3.5, 5.5, 5.0]
Could you be please clarify and suggest a way to fix this issue?
As Kyle mentions in his comment, the nodes in the network are added in the sequence associated with the edgelist. To remedy this, a simple sort will fix it. The third line of output shows the actual sequence of nodes.
With respect to the edges, something unexpected happened with reading the edge list from file: the edge (4, 5) is loaded as (5, 4). See second line of output. This causes the expected sort order of the edges, which would be like the file, to be different: the sixth and seventh node are swapped.
The code below sorts the node betweenness dictionary by key values (the node number), while putting the betweenness values in a tuple, output in the fourth line.
The last lines show each edge with its betweenness value.
import networkx as nx
G1 = nx.read_edgelist("mygraph.txt",create_using=nx.Graph(), nodetype = int)
G1.number_of_nodes()
node_btw = nx.betweenness_centrality(G1, normalized=False)
edge_btw = nx.edge_betweenness_centrality(G1, k=None, normalized=False, weight=None, seed=None)
print('NETWORK-X')
print(tuple(node_btw.keys()))
print(tuple(edge_btw.keys()))
nn_btw = tuple(v for _,v in sorted(node_btw.items(), key=lambda x: x[0]))
print(nn_btw)
en_btw = tuple(v for _,v in sorted(edge_btw.items(), key=lambda x: x[0]))
print(en_btw)
for k,v in sorted(edge_btw.items(),key=lambda x: x[0]):
print(k, v)
Output:
# NETWORK-X
# (1, 2, 5, 3, 4, 6)
# ((1, 2), (1, 5), (2, 3), (2, 5), (5, 4), (3, 4), (4, 6))
# (0.0, 1.5, 1.0, 4.5, 3.0, 0.0)
# (2.0, 3.0, 3.5, 2.5, 3.5, 5.0, 5.5)
# (1, 2) 2.0
# (1, 5) 3.0
# (2, 3) 3.5
# (2, 5) 2.5
# (3, 4) 3.5
# (4, 6) 5.0
# (5, 4) 5.5