CODEWITHSUNDEEP
rigraph
user3507085
user3507085

Reputation: 720

Maximize the number of isolated nodes in a network

I would like to know which node(s) should I delete if I want to maximize the number of isolated node in my undirected network?

For instance in the following R script, I would like the result to be H if I delete 1 node and H & U if I delete 2 nodes and so on ...

 library(igraph)
 graph <- make_graph( ~ A-B-C-D-A, E-A:B:C:D,
              G-H-I, 
              K-L-M-N-K, O-K:L:M:N,
              P-Q-R-S-P,
                C-I, L-T, O-T, M-S,
              C-P, C-L, I-U-V,V-H,U-H,H-W)
  plot(graph)

network example

Thanks for your help.

Upvotes: 1

Views: 244

Answers (1)

Paul Brodersen
Paul Brodersen

Reputation: 13031

You will want to do something like:

  1. Compute the k-coreness of each node (just called Graph.coreness in the python bindings, don't know about R).

  2. Find the node with k-coreness 2, that connects to the largest number of nodes with k-coreness 1.

Edit:

Your counter-example was spot on, so I resorted to brute force (which is still linear time in this case). This is a brute force python implementation that could be optimised (only loop over nodes with k-coreness 1), but it completes in linear time and should be accessible even if you don't know python.

import numpy as np
import igraph

def maximise_damage(graph):
    coreness = graph.coreness()

    # find number of leaves for each node
    n = graph.vcount()
    number_of_leaves = np.zeros((n))
    for ii in range(n):
        if coreness[ii] == 1:
            neighbour = graph.neighbors(ii) # list of length 1
            number_of_leaves[neighbour] += 1

    # rank nodes by number of leaves
    order = np.argsort(number_of_leaves)

    # reverse order such that the first element has the most leaves
    order = order[::-1]

    return order, number_of_leaves[order]

EDIT 2:

Just realised this will not work in general for cases where you want to delete more than 1 node at a time. But I think the general approach would still work -- I will think about it some more.

EDIT 3:

Here we go; still linear. You will need to process the output a little bit though -- some solutions are less than the number of nodes that you want to delete, and then you have to combine them.

import numpy as np
import igraph

def maximise_damage(graph, delete=1):
    # get vulnerability
    # nodes are vulnerable if their degree count is lower
    # than the number of nodes that we want to delete
    vulnerability = np.array(graph.degree())

    # create a hash table to keep track of all combinations of nodes to delete
    combinations = dict()

    # loop over vulnerable nodes
    for ii in np.where(vulnerability <= delete)[0]:
        # find neighbours of vulnerable nodes and
        # count the number of vulnerable nodes for that combination
        neighbours = tuple(graph.neighbors(ii))
        if neighbours in combinations:
            combinations[neighbours] += 1
        else:
            combinations[neighbours] = 1

    # determine rank of combinations by number of vulnerable nodes dangling from them
    combinations, counts = combinations.keys(), combinations.values()

    # TODO:
    # some solutions will contain less nodes than the number of nodes that we want to delete;
    # combine these solutions

    return combinations, counts

Upvotes: 1

Related Questions