Algorytmy wykrywania społeczności dla grafów dwustronnych?

Czy są jakieś algorytmy wykrywania społeczności dla grafów dwustronnych (sieci 2-trybowe) zaimplementowane w igraph, networkX, R lub Python itp.? W szczególności, czy istnieje takie wdrożenie, w którym można by ograniczyć wykrywanie społeczności tylko w jednym z dwóch trybów?

python graph-theory adamo
źródło

Jak „ograniczyć wykrywanie społeczności tylko w jednym z dwóch trybów”, nie wiedząc z góry, które węzły tworzą te tryby? Wydaje się okrągły.

hardmath

W sieci dwustronnej znasz już dwa tryby. Na przykład, jeśli połowa węzłów należących do trybu „A” łączy się z węzłem należącym do trybu „B”, wówczas istnieje tam społeczność.

adamo

Jeśli wiesz z góry, które węzły należą do każdego trybu, to odpowiada na moje pytanie dotyczące ograniczenia wykrywania. Jednak twój przykład i jego dorozumiane pojęcie „wspólnoty” jest niejasne. Jeśli wierzchołek na wykresie dwustronnym nie łączy się z żadnym wierzchołkiem przeciwnego trybu, to nie łączy się z żadnym wierzchołkiem (byłby izolowany). Na połączonym wykresie dwudzielnym każdy wierzchołek trybu „A” łączy się z wierzchołkiem jakiegoś trybu „B” i odwrotnie. „Społeczność” zwykle oznacza coś więcej niż połączony podgraf.

hardmath

Po zastanowieniu podejrzewam, że „połączenie z węzłem” miało na celu połączenie z jednym wspólnym węzłem, dając klikę na rzutowanym wykresie (patrz Odpowiedź), a tym samym „społeczność tam”. Przepraszamy za niezrozumienie twojego punktu w pierwszym czytaniu.

hardmath

Przeprosiny nie są potrzebne. Mój angielski i tak nie był tak jasny.

adamo

Odpowiedzi:

Wyrażenie „wykrywanie społeczności” jest luźno zdefiniowane jako podział wierzchołków wykresu na „społeczności” tak, że każdy ma członków bardziej gęsto powiązanych ze sobą niż z członkami innych „społeczności”.

Naszym pierwszym zadaniem jest ustalenie, co to powinno znaczyć w przypadku grafu dwustronnego, który z definicji składa się z dwóch „trybów”, tak że elementy jednego trybu są powiązane tylko z elementami drugiego trybu. Można to wyrazić, przynajmniej dla prostych wykresów, jako posiadające macierz przylegania o specjalnej strukturze bloków:

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

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

Wydaje mi się, że najbardziej trafna interpretacja „ograniczenia wykrywania zbiorowości tylko w jednym z dwóch trybów” zastosowałaby wspomniane algorytmy do „rzutowanych” wykresów odpowiadających blokom , tj. Pierwszego trybu z macierzą przyległości i drugi tryb z macierzą przyległości . Zauważ, że nawet jeśli oryginalny dwuczęściowy wykres jest prosty (tak, że jest binarny), rzutowane wykresy będą na ogół wielogramograficzne. Na szczęście igraph ma dla nas metodę skonstruowania ich . $A^2$ $BB^T$ $B^TB$ $A$

Mamy również tyle szczęścia, że algorytmy wykrywania społeczności igraph i powiązane zostały „zaktualizowane, aby obsługiwać ważone wykresy” (takie jak wykresy wielogramowe).

S. Fortunato (2010) bada kryteria wykrywania społeczności ( wykrywanie społeczności na wykresach ) i ich zastosowanie w sieciach dwustronnych i wieloczęściowych. Interpretacja, którą sugeruję powyżej, jest wyrażona na stronie 8:

Wykresy wieloczęściowe są zwykle redukowane do rzutów jednoczęściowych każdej klasy wierzchołków. Na przykład z dwustronnej sieci naukowców i artykułów można wydobyć tylko sieć naukowców, którzy są powiązani przez współautorstwo.

matematyka
źródło