Algorithmen zur Community-Erkennung für zweigeteilte Graphen?

Gibt es Algorithmen zur Community-Erkennung für zweigeteilte Graphen (2-Mode-Netzwerke), die in igraph, networkX, R oder Python usw. implementiert sind? Gibt es insbesondere eine solche Implementierung, bei der die Erkennung von Communities nur in einem der beiden Modi eingeschränkt werden kann?

python graph-theory Adamo
quelle

Wie würde man "die Erkennung von Communities nur auf einen der beiden Modi beschränken", ohne vorher zu wissen, aus welchen Knoten die Modi bestehen? Es scheint kreisförmig.

Hardmath

In einem zweiteiligen Netzwerk kennen Sie die beiden Modi bereits. Wenn beispielsweise die Hälfte der Knoten, die zum Modus "A" gehören, mit einem Knoten verknüpft ist, der zum Modus "B" gehört, haben Sie dort eine Community.

Adamo

Wenn Sie im Voraus wissen, welche Knoten zu den einzelnen Modi gehören, beantwortet dies meine Frage, wie die Erkennung eingeschränkt werden kann. Ihr Beispiel und sein impliziter Begriff "Gemeinschaft" sind jedoch unklar. Wenn ein Scheitelpunkt in einem zweigeteilten Graphen nicht mit einem Scheitelpunkt des entgegengesetzten Modus verknüpft ist, ist er nicht mit einem Scheitelpunkt verknüpft (er wäre isoliert). In einem verbundenen zweigeteilten Graphen ist jeder Scheitelpunkt des Modus "A" mit einem Scheitelpunkt des Modus "B" verknüpft und umgekehrt. "Community" bedeutet normalerweise mehr als einen verbundenen Untergraphen.

Hardmath

Ich vermute, dass Ihre "Verknüpfung mit einem Knoten" dazu gedacht ist, eine Verknüpfung mit einem einzelnen gemeinsamen Knoten herzustellen, wodurch eine Clique im projizierten Diagramm (siehe Antwort) und damit "eine Community dort" entsteht. Entschuldigung, dass Sie Ihren Standpunkt bei der ersten Lesung nicht verstanden haben.

Hardmath

Keine Entschuldigung nötig. Mein Englisch war sowieso nicht so klar.

Adamo

Antworten:

Der Ausdruck "Community-Erkennung" wird lose definiert als Aufteilen der Eckpunkte eines Diagramms in "Communitys", sodass die Mitglieder jeweils dichter miteinander verbunden sind als die Mitglieder anderer "Communitys".

Unsere erste Aufgabe besteht darin, herauszufinden, was dies im Fall eines zweigeteilten Graphen bedeuten soll, der per Definition aus zwei "Modi" besteht, sodass Mitglieder eines Modus nur mit Mitgliedern des anderen Modus verknüpft sind. Zumindest für einfache Graphen kann ausgedrückt werden, dass es eine Adjazenzmatrix mit spezieller Blockstruktur aufweist:

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$

Wir sind gleichermaßen das Glück, dass die IGRAPH Gemeinschaft Erkennungsalgorithmen und bezogen wurden „aktualisiert gewichtete Graphen zu handhaben “ (wie Multi-Grafiken).

S. Fortunato (2010) untersucht Community-Erkennungskriterien ( Community-Erkennung in Diagrammen ) und deren Verwendung mit zweiteiligen und mehrteiligen Netzwerken. Die Interpretation, die ich oben vorschlage, ist auf Seite 8 artikuliert:

Mehrteilige Graphen werden normalerweise auf unteilige Projektionen jeder Scheitelpunktklasse reduziert. Zum Beispiel kann man aus dem zweiteiligen Netzwerk von Wissenschaftlern und Veröffentlichungen nur ein Netzwerk von Wissenschaftlern extrahieren, die durch Koautorschaft verwandt sind.

Hardmath
quelle