Эффективно переберите все возможные графики взвешенных узлов и рассчитайте вероятность того, что максимальный размер клики> k

Question

Этот вопрос является продолжением следующего: Максимальная полная сетка на графике - код Python очень медленный .

Этот вопрос касался нахождения максимального размера клики ввзвешенный подграф.Моей конечной целью было найти вероятность того, что граф со связями, имеющими вероятности q активности и некоторые веса на всех его узлах, будет иметь максимальный взвешенный размер клики, превышающий k.Для этого я бы перебрал все возможные графы на n узлах и добавил бы к вероятности, если максимальный взвешенный размер клики был> = k.Тем не менее, @Диллон Дэвис упомянул в другом вопросе, что есть способ сделать это более эффективным.Итак, разместив этот вопрос, вы узнаете, сможет ли кто-нибудь помочь сделать циклизацию по графам более эффективной, повторно используя ранее вычисленные графы.Размещение моего кода, который делает наивный цикл для справки.

def networking_resiliency(k=4, q=0.5, wts=np.ones(4)):    
    edges = []
    n = len(wts)
    for i in range(n):
        for j in range(i+1,n):
            edges.append((i,j))
    edges = np.array(edges)
    ans = 0.0
    for e_idx in range(2**len(edges)):
        arr = to_binary(e_idx, len(edges))
        broken_edges = edges[arr==0]
        if type == "full_mesh":
            fm = FullMesh(broken_edges,wts)
            if fm.find_max()[0] >= k:
                up_edges = sum(arr)
                ans += q**up_edges*(1-q)**(len(edges)-up_edges)        
    return ans

Answer 1

Можно рассчитать оптимальную полную сетку некоторых графов из других вычисленных графов.Для данной полной сетки, если мы отметим узлы, которые были вырезаны из исходного графа для создания текущего подграфа, мы обнаружим, что любые другие ребра, соединяющиеся с этими узлами разреза, могут свободно, но без последствий вырезать.Используя эту информацию, мы можем взять декартово произведение узлов разреза и всех других узлов, удалить любые эквивалентные дубликаты и получить набор всех ребер, которые мы можем свободно вырезать.Затем мы берем powerset всех этих ребер и соединяем каждый с нашим текущим списком ломаных ребер, чтобы определить другие подграфы, которые неизбежно приведут к той же оптимальной полной сетке.Модифицированный класс FullMesh, который реализует это поведение, можно увидеть ниже:

class FullMesh:
    def __init__(self, weights, pairs=[]):
        self.weights = weights
        self.elements = set(range(len(weights)))
        self.set_pairs(pairs)

    def set_pairs(self, pairs):
        self.pairs = pairs
        self.skips = {e:set() for e in self.elements}
        for i, (a, b) in enumerate(pairs):
            self.skips[a].add(i)
            self.skips[b].add(i)

    def powerset(self, elements):
        return chain.from_iterable(combinations(elements, r) for r in range(len(elements)+1))

    def find_all(self):
        to_search = self.powerset(list(combinations(self.elements, 2)))
        pairs_searched = dict()
        for pairs in to_search:
            if pairs in pairs_searched: continue
            self.set_pairs(pairs)
            val, nums = self.find_max()
            new_pairs = set(product(set(self.elements) - set(nums), set(self.elements))) - set(pairs)
            new_pairs = self.powerset({(x, y) for x, y in new_pairs if x < y})
            pairs_searched.update({tuple(sorted(pairs + np)):(val,nums) for np in new_pairs})
        return pairs_searched

    def find_max(self):
        max_score = sum(self.weights)
        val, nums = self.exclude(0, max_score + 1, set(range(len(self.pairs))))
        return max_score - val, sorted(self.elements - set(nums))

    def exclude(self, curr_score, min_score, search):
        if not search or min_score <= curr_score:
            return curr_score, []

        min_nums = []
        for e in self.pairs[next(iter(search))]:
            score, nums = self.exclude(curr_score + self.weights[e], min_score, search - self.skips[e])
            if score < min_score:
                min_score, min_nums = score, nums + [e]
        return min_score, min_nums

Этот код занял ~ 50 секунд для создания всех оптимальных полных сеток для всех подграфов случайно взвешенного 7-узлового полностью связного графа.