Алгоритмы обнаружения сообщества для двудольных графов?

Существуют ли алгоритмы обнаружения сообщества для двудольных графов (двухрежимные сети), реализованные в igraph, networkX, R или Python и т. Д.? В частности, существует ли такая реализация, в которой можно было бы ограничить обнаружение сообществ только одним из двух режимов?

python graph-theory Adamo
источник

Как можно «ограничить обнаружение сообществ только одним из двух режимов», не зная заранее, какие узлы составляют режимы? Это кажется круглым.

hardthth

В двухсторонней сети вы уже знаете два режима. Например, если половина узлов, принадлежащих режиму «А», связана с узлом, принадлежащим режиму «Б», то у вас есть сообщество.

Адамо

Если вы заранее знаете, какие узлы принадлежат каждому режиму, то это ответит на мой вопрос о том, как ограничить обнаружение. Однако ваш пример и подразумеваемое понятие «сообщество» неясны. Если вершина в двудольном графе не связывается ни с одной вершиной противоположного режима, то она не связывается ни с одной вершиной (она будет изолирована). В связном двудольном графе каждая вершина режима «A» связана с вершиной некоторого режима «B» и наоборот. «Сообщество» обычно означает нечто большее, чем связанный подграф.

hardthth

Размышляя, я подозреваю, что ваша «связь с узлом» подразумевала связь с одним общим узлом, давая клику на проецируемом графе (см. Ответ) и, следовательно, «сообщество там». Извиняюсь за то, что не понял вашу точку зрения при первом чтении.

hardthth

Никаких извинений не требуется. В любом случае мой английский был не так ясен.

Адамо

Ответы:

Фраза «обнаружение сообщества» в общих чертах определяется как разбиение вершин графа на «сообщества», так что в каждом из них есть члены, более плотно связанные друг с другом, чем с членами других «сообществ».

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

A = (\begin{matrix} 0 & B \\ B^{T} & 0 \end{matrix})

$A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$

$A^2$ $BB^T$ $B^TB$ $A$

Нам одинаково повезло в том, что алгоритмы обнаружения сообщества igraph и связанные с ними были «обновлены для обработки взвешенных графов» (таких как мультиграфы).

С. Фортунато (2010) рассматривает критерии обнаружения сообщества ( обнаружение сообщества на графиках ) и их использование в двухсторонних и многочастных сетях. Интерпретация, которую я предлагаю выше, сформулирована на странице 8:

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

hardmath
источник