NetworkX Составьте список итераций комбинаций ребер

Question

У меня есть матрица смежности 180x180, которую я пытаюсь сгенерировать всеми вероятными комбинациями для работы с использованием NetworkX.

Я хочу последовательно удалить части графика, а затем определить влияние на глобальную эффективность новогоотредактированный график.

Вероятным набором комбинаций в этом представлении являются все наборы узлов, которые являются смежными друг с другом, и все возможные комбинации подграфов, если предположить, что они являются смежными друг с другом вплоть до подграфа.

Подход с использованием грубой силы для запуска всех комбинаций слишком медленный и имеет время выполнения около 21 часа для любой серии удаления более 15. Поэтому мы хотим решить эту проблему, рассматривая только комбинации, смежные с каждой из них.прочее.

В основном код должен выполнять следующие действия:

1. Импортировать CSV-файл, содержащий двоичную матрицу смежности, где 1 означает физическую непрерывность (в данном случае в мозге)
2. Импорт в график сети
3. Определитьвсе наборы комбинаций, длина которых не превышает 1 пути друг от друга .... другими словами, если два узла или два набора узлов больше 1 на обоих концах, они игнорируются
4. Генерироватьсписок этих наборов узлов для каждой вероятной комбинации

Вот основная проблема

, предполагающая, что физическое пространство области мозга включает в себя несколько областей, которые приблизительно расположены так.... предположим, что это неправильные многоугольники, тесселяция плоскости

1 2 3 4 5

6 7 8 9

10 11

мы можем сделать это вматрица смежности, где 1 означает, что регионы имеют общую границу, а 0 означает, что они физически не граничат друг с другом

+--+---------------------------------+
|  | 1  2  3  4  5  6  7  8  9  10 11|
+--+---------------------------------+
|1 | 0  1  0  0  0  1  0  0  0  0  0 |
|2 | 1  0  1  0  0  0  1  1  0  0  0 |
|3 | 0  1  0  1  0  0  0  1  1  0  0 |
|4 | 0  0  1  0  1  0  0  0  1  0  0 |
|5 | 0  0  0  1  0  0  0  0  1  0  0 |
|6 | 1  0  0  0  0  0  1  0  0  1  0 |
|7 | 0  1  0  0  0  1  0  1  0  1  1 |
|8 | 0  1  1  0  0  0  1  0  1  0  1 |
|9 | 0  0  1  1  0  0  0  1  0  0  0 |
|10| 0  0  0  0  0  1  1  0  0  0  1 |
|11| 0  0  0  0  0  0  1  1  0  1  0 |
+--+---------------------------------+

В основном эта матрица смежности представляет части мозга, которые находятся рядом друг с другом .....Мы хотим пройти и сгенерировать списки группировок этих узлов, которые начинаются с отдельных узлов и работают до каждой возможной комбинации узлов с оговоркой, которую мы не делаем.хотите, чтобы комбинации не находились в физическом контакте друг с другом .....

так, например, в таком списке должно быть 1,2, .... 11, а также 1 + 2 и 7 + 8 и т. д.у нас было бы 2 + 7 + 8 и 6 + 7 + 8 + 10, потому что все эти узлы соприкасаются друг с другом и образуют связанный компонент 1-11, не будет разрешено, потому что они не разделяют границу, равно как и 4 + 5 + 10, потому чтоони не касаются

причина, по которой это важно, заключается в том, что мы являемся мозговыми хирургами, и мы удаляем части графиков для жизни ... то есть графики мозга .... но вы никогда не удалите узлы, которые не находятся рядом сдруг друга ... мы пытаемся использовать графики, чтобы определить, как далеко мы можем пойти в хирургии .... поэтому нам нужно использовать python для генерации всех возможных комбинаций узловых удалений, которые имеют смысл в реальном мире ... двоичный файлМатрица смежности представляет реальность в физическом пространстве

как только у меня есть список вероятных комбинаций узловых удалений, у меня есть код, который принимает другой фрейм данных панд .... обнуляет узлы и ребра изатем создает график networkx, на котором мы запускаем показатели эффективности ..... мне просто нужен способ определить все возможные наборы недостоверных компонентов, чтобы мы не запускали анатомически неправдоподобные комбинации

так, как я думал, чтобы решить эту проблему, былоиспользуя какую-то функцию некомпетентных компонентов в networkx, но я не могу найти, чтобы экспортировать все возможные комбинации связанных компонентов из графика

, по сути, код будет выглядеть примерно так:

boundary=pd.read_csv(adjacency.csv)
G=networkx.from_pandas_adjacency(boundary)
combo="something to iterate the graph g to create a list of all connected components"


for row in combo:
        values = row
        datasafe=pandas.read_csv("connections.csv", index_col=0)
        datasafe.loc[values, :] = 0

        datasafe[values] = 0

        g=networkx.from_pandas_adjacency(datasafe)
        h=networkx.from_pandas_adjacency(datasafe)
        le=local_efficiency(g)
        LE_list.append(le)
        ge=global_efficiency(h)
        GE_list.append(ge)
output=pandas.DataFrame(list(zip(combo, GE_list,LE_list)))
output.to_csv('multi.csv',index=None)

Примечаниечто мы используем один CSV для определения списка и используем этот список в другом CSV

заранее спасибо ... это важная проблема, которую вы помогаете решить и которая спасет жизни

Answer 1

Правильное наименование вашего подключенного компонента - это полный подграф (не связывайтесь с настоящими подключенными компонентами ).Ваша проблема известна как проблема клики .networkx имеет несколько алгоритмов для решения этой проблемы: networkx клик

Ваша проблема может быть решена с помощью этой функции: networkx.algorithms.clique.enumerate_all_cliques

Обратите внимание, что эта функция возвращает все возможные клики, также с длиной 1 и 2 (т. Е. Каждый узел и каждое ребро), поэтому вы должны фильтровать клики по 1-2 длины.Например, для вашего графика эта функция возвращает:

list(nx.enumerate_all_cliques(G))

[[0],
 [1],
 [2],
 [3],
 [4],
 [5],
 [6],
 [7],
 [8],
 [9],
 [10],
 [0, 1],
 [0, 5],
 [1, 2],
 [1, 6],
 [1, 7],
 [2, 3],
 [2, 7],
 [2, 8],
 [3, 4],
 [3, 8],
 [4, 8],
 [5, 6],
 [5, 9],
 [6, 7],
 [6, 9],
 [6, 10],
 [7, 8],
 [7, 10],
 [9, 10],
 [1, 2, 7],
 [1, 6, 7],
 [2, 3, 8],
 [2, 7, 8],
 [3, 4, 8],
 [5, 6, 9],
 [6, 7, 10],
 [6, 9, 10]]

, но если мы отфильтруем все бесполезные клики, мы получим это:

list(filter(lambda x: len(x) > 2, nx.enumerate_all_cliques(G)))

[[1, 2, 7],
 [1, 6, 7],
 [2, 3, 8],
 [2, 7, 8],
 [3, 4, 8],
 [5, 6, 9],
 [6, 7, 10],
 [6, 9, 10]]