30 views

Skip to first unread message

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)

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")

```

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.

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.

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.

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CA%2BXMcTM1C1BzV3yxn%3DJjTQAZTC3aA84ps-9yMoMGah0Wd23v8g%40mail.gmail.com.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu