最大化网络中孤立节点的数量

Question

我想知道如果我想在我的无向网络中最大化孤立节点的数量，我应该删除哪些节点？

例如在下面的 R 脚本中，如果我删除 1 个节点，我希望结果为 H，如果我删除 2 个节点，我希望结果为 H & U，依此类推...

 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

你会想做这样的事情：

计算每个节点的k-coreness（只是在python绑定中调用了Graph.coreness，不知道R）。
找到 k-coreness 为 2 的节点，该节点连接到 k-coreness 为 1 的节点数量最多。

编辑：

你的反例很正确，所以我求助于蛮力（在这种情况下仍然是线性时间）。这是一个可以优化的蛮力 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]

编辑 2：

刚刚意识到这通常不适用于您希望一次删除超过 1 个节点的情况。但我认为一般方法仍然有效——我会再考虑一下。

编辑 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

最大化网络中孤立节点的数量

Maximize the number of isolated nodes in a network

r

igraph

编辑：

编辑 2：

编辑 3：