Максимальное количество изолированных узлов в сети

Question

Я хотел бы знать, какие узлы я должен удалить, если я хочу максимизировать количество изолированных узлов в моей неориентированной сети?

Например, в следующем R сценария, я хотел бы результат быть H, если я удалю 1 узел и H & U, если удалить узлы 2 и так далее ...

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) 

Спасибо за помощь.

Answer 1

Вы хотите сделать что-то вроде:

1. Compute к-сердцевинности каждого узла (только называется Graph.coreness в питона привязок, не знаю, о R).

2. Найти узел с к-сердцевинностью 2, который соединяется с наибольшим числом узлов с к-сердцевинностью 1.

Edit:

Ваш контрпример был на месте, так Я прибегал к грубой силе (которая в этом случае по-прежнему линейна). Это реализация python грубой силы, которая может быть оптимизирована (только петля над узлами с k-coreness 1), но она завершается в линейном времени и должна быть доступна, даже если вы не знаете 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:

Просто понял, что это не будет работать вообще в тех случаях, когда требуется удалить более чем на 1 узел в то время. Но я думаю, что общий подход все равно будет работать - я подумаю об этом еще немного.

EDIT 3:

Здесь мы идем; все еще линейный. Вам потребуется обработать вывод немного, хотя некоторые решения меньше количества узлов, которые вы хотите удалить, а затем вы должны их объединить.

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