CODEWITHSUNDEEP
python-3.xgraphnetworkx
TinaTz
TinaTz

Reputation: 311

how to remove edges from largest connected component?

i am working on dynamic graph, i want to remove edges from the largest connected component,here is the example of code i wrote

    graph=dn.read_snapshots('mytxt', nodetype=int, timestamptype=int)

 print(nx.number_connected_components(graph))
S=[len(c) for c in sorted(nx.connected_components(graph), key=len, reverse=True)]
print(S)----[150, 1]

here i have two components, and i need to work with the largest one, the one with 150

y=[]
 rand_set = set(random.sample(range(20), 5))
for (u,v,t) in **largest**.interactions():
        #m,n = pair(u, v)
        if r in rand_set:
            s.remove_edge((u,v,t))
            if(nx.is_connected(s)==True):
                y.append(u,v,t)
            else:
                graph.add_interaction((u,v,t))
            r+=1

here largest means need to work on largest connected component of this graph in this code, I randomly remove edge from the connected component and append to y,however this code is not giving me any result. Any help will be appreciated

Upvotes: 1

Views: 499

Answers (1)

yatu
yatu

Reputation: 88236

Let's use an example graph to more easily see how this could be done:

l = [('maths', 'physics'), ('astronomy', 'physics'), ('history', 'archaeology'), ('environmental science', 'physics'), ('maths', 'astronomy'), ('history', 'literature'), ('astronomy', 'astrophysics'), ('literature', 'philosophy'), ('biology', 'physics')]
graph = nx.from_edgelist(l)

So we've built a graph which looks as follows:

pos = nx.spring_layout(graph, scale=20, k=3/np.sqrt(graph.order()))
nx.draw(graph, pos=pos,
        node_color='lightblue', 
        with_labels=True, 
        node_size=500)

enter image description here

So the graph has 2 connected components, the largest one of which is the one that appears at the left of the figure. To find the largest component subgraph, you could use connected_component_subgraphs, and find the maximum, using len as a key function. 

S = max(nx.connected_component_subgraphs(graph), key=len)

Then get a random choice of the existing edges in this subgraph using random.choices, setting k to the value of interest:

edges_to_remove = random.choices(list(S.edges()), k=2)
# [('physics', 'biology'), ('physics', 'environmental science')]

In this case for instance we'll be removing the edges connecting the nodes ('physics', 'biology') and ('physics', 'environmental science')

And then similarly to what you where doing, we can iterate over the random choice of edges edges_to_remove and remove them from the graph using remove_edge:

for edge in edges_to_remove:  
    graph.remove_edge(*edge)

Resulting in the following graph:

enter image description here

Upvotes: 1

Related Questions