Ask for help: Network-X edge_betweeness_centrality function does not take weight into account

30 views
Skip to first unread message

Emma Van Hoogmoed

unread,
Nov 26, 2022, 2:44:20 PM11/26/22
to networkx-discuss

I am trying to randomize the link weights of a network x graph to change the betweenness centrality of that network. I have verified that the weights do change but it does not change the output of the edge_betweeness_centrality function. I suspect it has something to do with adding objects to the nodes and edges as I was able to get it working as long as I didn't have these. However, I need the objects for other parts of my code so deleting them isn't an option.

I have tried load_centrality and betweenness_centrality and both give me the same issue. I have also verified my inputs are integers or floats. I understand the functions interpret the values as distances so I have tried both the normal weight and the reciprocal of the weight. I've been stuck on this issue for weeks and would appreciate any help or ideas. Thank you.

The following is my code.

import networkx as nx
import numpy as np
from itertools import combinations, groupby
import random

class Link(object):
  def __init__(self,link_id,rate,distance,network):
        self.link_id = link_id
        self.rate = rate
        self.distance = distance
        self.network = network
        self.buffer = []

class Node:
    def __init__(self,node_id,network):
        self.node_id = node_id
        self.len = 0  
        self.queue = []
        self.network = network
        self.packet_delay = []
        self.packets = []

def gnp_random_connected_graph(n, p):
        graph_seed = np.random.default_rng(2021)

        network = nx.Graph()
       
        node_dict = {}
        for node in range(n):
            new_node = Node(node, network)
            node_dict[node] = new_node
           

        network.add_nodes_from(node_dict.items())

        edges = list(combinations(range(n), 2))
        link_dict = {}
        for id, node_edges in groupby(edges, key=lambda x: x[0]):
            rate = random.randint(8000000,40000000) #bps
            distance = random.randint(10,185) #meters
            node_edges = list(node_edges)
            random_edge = tuple(graph_seed.choice(node_edges))
            link_dict[random_edge] = Link(random_edge,rate,distance,network)
       
        for e in node_edges:  
            if graph_seed.random() < p:
                link_dict[e] = Link(e,rate,distance,network)

        for key,value in link_dict.items():
            nodes = list(network.nodes)
            network.add_edge(nodes[key[0]],nodes[key[1]],obj=value,weight=int(value.distance),rp = float(1/(value.distance)))
           
        return network        

def randomize_weights(network):

            for edge in network.edges():
                rand_num = random.randint(10,100)
                network[edge[0]][edge[1]]['weight'] = rand_num
                network[edge[0]][edge[1]]['rp'] = 1/rand_num

            return network  


org_net = gnp_random_connected_graph(10,.1)
#print("edges weight",nx.get_edge_attributes(org_net,'weight'))
bc_dict = nx.edge_betweenness_centrality(org_net, weight='rp')
print("OLD",bc_dict)
new_net = randomize_weights(org_net.copy())
#print("edges weight",nx.get_edge_attributes(new_net,'weight'))
new_bc_dict = nx.edge_betweenness_centrality(new_net, weight='rp')
print("NEW", new_bc_dict)

Dan Schult

unread,
Nov 27, 2022, 4:54:47 AM11/27/22
to networkx...@googlegroups.com
betweenness centrality for each node depends on the number of shortest paths that pass through each node.
So, even if the weights change, if the shortest paths don't change, the BC values will stay the same.
Your network has very few shortest paths. Most node pairs don't even have a shortest path between them.
Those that do have only one possible path and so the weights won't matter. 

You might try using more nodes (gnp graphs form a large connected component in the limit of large n).
Also, you can use code more like:

```python
G = nx.gnp_random_graph(100, 0.2)
biggest_component = next(nx.connected_components(G))
G = G.subgraph(biggest_component).copy()

nx.set_edge_attributes(G, {e: seed.integers(10, 185) for e in G.edges}, "distance")
nx.set_edge_attributes(G, {(u, v): 1 / dd["distance"] for u, v, dd in G.edges.data()}, "rp")

BC = nx.edge_betweenness_centrality(G, weight="distance") 
```

Emma Van Hoogmoed

unread,
Nov 27, 2022, 5:39:03 PM11/27/22
to networkx...@googlegroups.com
Thank you! That does seem to be working now. Just wondering about using the subgraph and connected_components. Is that just making a copy of the graph or is that excluding data from the graph?

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CA%2BXMcTOKAMAUtQ3_wFh58-zmtnukJhPoHPwsfiSi1XJ7qsEJiw%40mail.gmail.com.

Emma Van Hoogmoed

unread,
Nov 27, 2022, 6:02:19 PM11/27/22
to networkx...@googlegroups.com
I take that back. I need to have a graph where all nodes are connected by at least one edge. The nx.gnp_random_graph does not do that. Which is why I needed to use the function I created. Unfortunately, the solution you provided doesn't work with my function.

Dan Schult

unread,
Nov 27, 2022, 6:13:12 PM11/27/22
to networkx...@googlegroups.com
The point of the subgraph with the connected components is to retain only the largest connected component of the graph.

Emma Van Hoogmoed

unread,
Nov 27, 2022, 6:39:58 PM11/27/22
to networkx...@googlegroups.com
Oh! Okay, so I'd just have to figure out a way of adding link and node objects to the preexisting graph. Thanks again.

On Sun, Nov 27, 2022 at 3:14 PM Dan Schult <dsc...@colgate.edu> wrote:
The point of the subgraph with the connected components is to retain only the largest connected component of the graph.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
Reply all
Reply to author
Forward
0 new messages