Sezin Maden	Stephanie Kinderreich	Ali Al-Abaidi
RWTH Aachen	RWTH Aachen	RWTH Aachen
sezin.maden@rwth-aachen.de	stephanie.kinderreich@rwth-aachen.de	ali.alabaidi@rwth-aachen.de

Abstract

Im heutigen Zeitalter der sozialen Netzwerke, gewinnen Algorithmen, die diese sinnvoll analysieren und Communitys erkennen können immer mehr an Wichtigkeit. Die strukturierte Analyse und interpretation riesiger Datensätze spielen nicht mehr nur für große Firmen eine Rolle. Einen dieser Algorithmen wollen wir in dieser Arbeit vorstellen, nämlich MONC. Dieser ist ein lokaler, parameterfreier Algorithmus, zur Findung von sich überlappenden Communities in gewichteten Graphen. Von einem Startbereich ausgehend wird mithilfe einer lokalen Funktion Stück für Stück der gesamte Graph erfasst. Hier wählt man den Startbereich explizit aus, was bedeutet das ausgehend von einer Clique, der am stärksten bindende Untergraph als Startbereich übernommen wird. Dieser Vorgang wird sich im Laufe der Arbeit als sehr positiv herrausstellen. Aufbauend auf einigen weiteren Algorithmen wird die Struktur und die herangehensweise des MONC-Algorithmus heraus kristalisiert werden. Die Besonderheit von MONC ist, dass dieser im Gegensatz zu vergleichbaren Algorithmen LFM und GCE- analytisch, statt numerisch vorgeht. Dies, so wird sich zeigen, hat den Vorteil, schneller und genauer zu sein. Im Laufe dieser Arbeit wird der Algorithmus an verschieden Datensätzen ausprobiert und mit anderen verglichen und analysiert, sodass man sich ein gutes Bild über wichtige Aspekte, Vor- und Nachteile, machen kann.

Inhalt

Einleitung
Verwandte Arbeiten
Methodik
Anwendung
Zusammenfassung

1. Einleitung

Das Finden von Communitys hat viele Anwendungsbereiche. Viele Netzwerke enthalten sich überlappende Commuitys. Als Beispiel können soziale Netzwerke oder Netzwerke von sich gegenseitig referenzierenden wissenschaftlichen Arbeiten genannt werden. Dabei greift ein Paper nicht nur einen einzigen, sondern mehrere Ansätze auf und gehört einer Hierachie von ineinander geschachtelten Themen an. Deshalb ist es interessant, verschiedene Algorithmen zur Endeckung dieser sich überlappenden Communities zu betrachten. In der hier vorliegenden Arbeit, werden wir uns vor allem auf den analytischen, lokalen Algorithmus MONC fokussieren und damit die erste deutschsprachige Ausarbeitung in diesem Bereich bilden.

Vor dem MONC-Algorithmus gab es bereits drei Algorithmen, die den selben Ansatz wie MONC nutzen, nämlich werden natürliche Communities von Knoten in Form von Untergraphen konstruiert. Dabei sollte es jedoch nicht bleiben, denn wie es nunmal so ist, strebt der Mensch immer nach besseren und schnelleren Lösungen für ein Problem. Hier kommt dann der, in dieser Arbeit thematisierte, MONC-Algorithmus ins Spiel. MONC bildet -so kann man sagen- eine erweiterte Version der Drei, der darauf aufbauend eine optimierte Fassung darstellt und die Schwachstellen der anderen Drei aufgreift und sie umgeht. Während die anderen drei alle einer numerischen Vorangehensweise folgen, was ineffizient im Bezug auf Schnelligkeit Präzisierbarkeit ist, geht der MONC-Algorithmus analytisch vor. Dies wäre bereits der erste Optimierungsschritt, den Frank Havemann, Michael Heinz, Alexander Struck und Jochen Gläser angegangen sind (“Identification of Overlapping Communities and Their Hierarchy by Locally Calculating Community-Changing Resolution Levels,” 2011). Um nicht zu weit vorzugreifen, werden andere genauere Unterschiede im weiteren Verlauf erläutert. Anhand eines Experiments wird der MONC-Algorithmus beispielhaft erklärt, sowie auch Unterschiede zwischen den Algorithmen graphisch dargestellt. In der Diskussion werden die Algorithmen, speziell der in dieser Arbeit wichtigste MONC-Algorithmus, ausgewertet und zum Schluss werden die Ergebnisse noch einmal zusammengefasst.

2. Verwandte Arbeiten

In der Arbeit von Palla, Dernyi, Farkas und Vicsek (“Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society,” 2005), haben die Autoren erstmals die Idee eingeführt, dass in Graphen die aus der Natur oder aus unserer Gesellschaft erfassten Daten zusammengesetzt sind, die Knoten bei Aufteilung des Graphen in stark zusammengehörige Module normalerweise Teil mehrerer solcher Communitys sind. Für gewöhnlich überlappen die Communitys in solchen Graphen sich also gegenseitig. Als Beispiel für einen Graphen mit sich überlappenden Communitys kann ein Netzwerk aus wissenschaftlichen Papieren genannt werden, in dem die Knoten die Papiere und die Kanten die Referenzen der Papiere untereinander darstellen. Ein Papier referenziert normalerweise mehrere Ansätze und Papiere aus verschiedenen Teilbereichen oder verbindet diese sogar, wodurch eine wissenschaftliche Arbeit mehreren Modulen zugeordnet werden kann. Dadurch entstehen, die sich überlappenden Communitys in solchen Netzwerken. Um sich überlappenden Communitys in solchen Graphen zu finden, wurden drei Lösungsansätze implementiert und getestet.

Einer dieser Ansätze fängt mit sich nicht überlappenden Communities an und erweitert diese Module mit Knoten aus Ihrer Nachbarschaft (Baumes et al., 2005; Wang et al., 2009).
Der zweite Ansatz ist es, die Kanten des Graphen einer festen Community zu zuordnen, wodurch einzelne Knoten automatisch Mitglied einer Commuity sind, wenn mindestens einer ihrer Kanten zu dieser Community gehört (Ahn et al., 2010; Evans & Lambiotte, 2010). Dies ermöglicht damit also auch die Zugehörigkeit eines Knotens in mehreren Communities.
Der dritte Ansatz ist derjenige, mit dem wir uns in dieser Arbeit genauer beschäftigen möchten. Die Idee hierbei ist es, für jeden Knoten oder für ausgewählte Gruppen sogenannte “natürliche” Communities zu konstruieren, welche auch die Möglichkeit haben sich zu überlappen (Lancichinetti et al., 2009). Eine solche natürliche Community ist das Resultat eines Greedy-Algorithmus’, der ausgehend von dem Startknoten versucht, eine Auflösungsabhängige lokale Funktion Schritt für Schritt zu maximieren. Eine natürliche Community könnte also z.B. als die thematische Umgebung aus der Perspektive einer wissenschaftlichen Arbeit interpretiert werden. Dieser Ansatz liefert zusätzlich zu den überlappenden Communitys, zusätzlich auch ihre Hierarchie untereinander. Also kann insbesondere, um zu dem Beispiel der wissenschaftlichen Papiere zurück zu kommen, fest gestellt werden, ob ein Thema vollständig innerhalb eines anderen Themas liegt oder nicht und, wenn ja, welches das Oberthema ist.

Allerdings sind viele der Algorithmen, die zu diesem Lösungsansatz veröffentlicht wurden nicht optimal. Sowohl der von Lancichnetti, Fortunado und Kertesz (LFK) vorgeschlagene Algorithmus (“Detecting the Overlapping and Hierarchical Community Structure in Complex Networks,” 2009), als auch der von Lee, Reid und McDavid veröffentlichte Variation Greedy Clique Expansion (GCE) (Detecting Highly Overlapping Community Structure by Greedy Clique Expansion, 2010), sind numerische Verwirklichungen des beschriebenen Lösungsansatzes.
LFK basiert auf der Annahme, dass Knoten einer Community stark miteinander verknüpft sind, während sie nach außen eher weniger Kanten haben. Aus dieser Annahme folgt das Herzstück von LFK, die Funktion, die für einen Untergraphen und einen Auflösungsparameter \(\alpha\), der angibt wie starker Zusammenhalt gefordert wird, einen Wert berechnet mit dem der Zusammenhalt eines Moduls beschrieben werden kann. Die Funktion ist das Verhältnis der Summe der inneren Grade zu der Summe der Grade aller Knoten. Anschließend wird der Nenner noch um \(\alpha\) Potenziert:

\[f(G,\alpha) = {(k_{in}(G)) \over ((k_{in}(G)+k_{ext}(G))^\alpha)}\]

Hierbei bezeichnet \(k_{in}\) den inneren Grad, sprich die Summe des Grades der Knoten im Untergraphen, wenn man nur die Kanten zwischen diesen betrachtet. \(k_{ext}\) bezeichnet dann den externen Grad des Untergraphen. Die Summe aus \(k_{in}\) und \(k_{ext}\) ist also gleich der Summe der Grade der Knoten des Untergraphen. (Lancichinetti et al., 2009) Die natürliche Community wird nun konstruiert, indem derjenige Nachbar hinzugefügt wird, der die Funktion am stärksten erhöht. Anschließend wird für jeden Knoten aus dem neuen Untergraphen überprüft, ob sie den Wert der Funktion noch erhöhen oder gestrichen werden könnten, wenn sie es nicht tun. Diese Schritte werden so lange durchgeführt, bis das Hinzufügen keines der Nachbarknoten des Moduls die Funktion erhöhen würde. An diesem Punkt haben wir die natürliche Community konstruiert. Durch Variation des Auflösungsparameters \(\alpha\) und eine neue Berechnung der Communitys, kann nun die gesamte hierarchische Struktur der sich überlappenden Communitys aufgedeckt werden. Genau wegen dieser Neuberechnung der Module für verschiedene Auflösungen, hat der LFK eine hohe Laufzeit. Deshalb schlagen die Autoren einige Optimierungsmöglichkeiten vor. So wird zum Beispiel vorgeschlagen, als Startgraphen bereits die zuvor gefunden Communitys zu nutzen, da bei kleineren Auflösungen die Communities nicht kleiner werden können (Lancichinetti et al., 2009).

Auch eine als “randomisierte local fitness maximisation” (LFM) bezeichnete Variante von LFK wird von den Autoren vorgeschlagen. Hierbei wird der Startknoten zufällig gewählt und nach fertigstellen der natürlichen Commuity ein neuer Knoten von den noch nicht zugewiesenen Knoten zufällig gewählt, bis alle Knoten einer Community zugewiesen worden sind. Sowohl der LFM als auch der LFK verletzen in zwei Punkten jedoch die Lokalitätseigenschaft des Algorithmus’. Der erste Punkt ist, dass keiner der beiden erlaubt, dass Knoten alleine bleiben, da für beliebige \(\alpha\) ein Knoten alleine immer den Funktionswert 0 hat. Der zweite Punkt ist, dass durch den Mechanismus der Entfernung die Community in den Mittelpunkt gestellt wird, was dazu führen kann, dass der Startknoten selbst, durch dessen Entfernung nicht mehr in seiner eigenen natürlichen Community enthalten ist.

Der Algorithmus GCE ist der LFK ohne diesen Mechanismus der Herausnahme einmal hinzugefügter Knoten aus einer Community. Der GCE startet des Weiteren im Unterschied zum LFK mit maximalen Cliquen statt einzelnen Knoten und entfernt Module, die bereits gefundenen Communities zu ähnlich sind. (Conrad Lee, Fergal Reid, Aaron McDaid, Neil Hurley, 2010). Im weiteren werden hauptsächlich mit dem Algorithmus merging of overlapping natural Communities (MONC), von Haverman, Heinz, Struck und Gläser (“Identification of Overlapping Communities and Their Hierarchy by Locally Calculating Community-Changing Resolution Levels,” 2011) befassen. Wir wollen ihn in dieser Arbeit auf deutsch vorstellen und anschließend testen, um ihn mit den anderen Algorithmen zu vergleichen.

3. Methodik

Im folgenden Abschnitt stellen wir den Algorithmus MONC vor. Es handelt sich hierbei um einen analytischen, lokalen, parameterfreien Algorithmus, der sich überlappende Comunities in gewichteten Graphen findet. Ausgehend von der oben genannten Formel, des LFK Algorithmus haben Haverman, Heinz, Struck und Gläser (“Identification of Overlapping Communities and Their Hierarchy by Locally Calculating Community-Changing Resolution Levels,” 2011) eine Formel erstellt, um für einen Untergraphen und einen Knoten, die Auflösung zu bestimmen, bei der der Knoten zur Community dieses Untergraphen hinzugefügt werden müsste. Um modellieren zu können, dass die natürliche Community eines Knotens bei unendlicher Auflösung aus genau diesem Knoten besteht, wandeln die Autoren die Formel des LFK Algorithmus’ ab, indem sie im Zähler \(+1\) rechnen somit folgende Formel entsteht:

\[f(G,\alpha) = {k_{in}(G)+1 \over ((k_{in}(G)+k_{ext}(G))^\alpha)}\]

Die Autoren leiten anschließend eine Formel für \(\alpha_{inc}(G,V)\) her, was für einen Knoten V und einen Untergraphen G den größten Auflösungswert \(\alpha\) angibt, bei dem V zur Community, bestehend aus den Knoten in G, hinzugefügt werden würde (Havemann et al., 2011).

Es ergibt sich:

\[\alpha_{inc}(G,V)) = {\log{(k_{in}(G/V)+1)} \cdot \log{(k_{in}(G)+1)} \over \log{(k_{tot}(G/V))} \cdot \log{(k_{tot}(G))}}\],

wobei \(k_{ges}(G)\) die Summe der Grade der Knoten in G ist und \(G/V\) den Graphen bezeichnet der zusätzlich zum gesamten Graphen G auch V und die Kanten zwischen V und Knoten aus G enthält. Mit Hilfe dieser Formel berechnet MONC für einen Graphen und einen Startknoten genau, bei welchem Auflösungslevel welcher Knoten zur natürlichen Community hinzugefügt wird, indem immer der Knoten aus der Nachbarschaft dem Modul hinzugefügt wird, der bei dem höchsten \(\alpha\) hinzugefügt werden würde und wiederholt diesen Vorgang für die sich ändernde Community bis es keine Knoten mehr in der Nachbarschaft gibt.

Als mögliche Optimierung schlagen die Autoren vor, \(k_{in}(G/V)\) und \(k_{tot}(G/V)\) aus den zuvor berechneten Werten ohne den Knoten V zu berechnen. Durch die gewählte Funktion kommt es dazu, dass während das Modul noch klein ist Knoten hinzugefügt werden, die zwar nicht besonders stark mit dem Modul vernetzt sind aber durch ihren niedrigen Grad ein hohes \(\alpha_{incl}\) haben. Genau dies soll durch den Exklusionsmechanismus von LFK und LFM verhindert werden. Um das Problem zu umgehen schlagen die Autoren vor statt einem Startknoten einen Startbereich zu wählen und stattdessen auf den Exclusionsmechanismus zu verzichten. Zur Bestimmung von Startbereichen werden Cliquen gewählt und anschließend reduziert, indem der Knoten entfernt wird, der den Wert der Fitness Funktion bei der niedrigsten Auflösung verringert. Die Formel zur Bestimmung dieser Ausschluss-Auflösung \(\alpha_{aus}\) ist \[\alpha_{aus}(G,V)) = {\log{(k_{in}(G)+1)} \cdot \log{(k_{in}(G/V)+1)} \over \log{(k_{tot}(G)} \cdot \log{(k_{tot}(G/V))}}.\]
\(G/V\) bezeichnet dabei Das Modul G ohne den Knoten V und seinen Kanten. Der beschriebene Prozess wird wiederholt, bis nur noch zwei Knoten in der Clique enthalten sind. Anschließend wird aus der Folge schrumpfender Untercliquen, die Clique ausgewählt, bei dem der nächste ausgeschlossene Knoten den höchsten Wert \(\alpha_{aus}\) hat. Knoten die in keiner auf diese Art ausgewählten Clique enthalten sind verbleiben als einzelne Knoten (Havemann et al., 2011).

Eines der größten Praktischen Probleme von MONC ist es, genauso wie GCE (Conrad Lee, Fergal Reid, Aaron McDaid, Neil Hurley, 2010), dass sehr viele einander sehr ähnliche Module gefunden werden. Dieses Verhalten kann auf die Lokalitätseigenschaft von MONC zurückgeführt werden. Für ein reales Modul werden viele leicht verschiedene Module gefunden, die das gleiche Modul aus einer anderen Sicht beschreiben. Als Lösung wird vorgeschlagen mithilfe der von Lee u.a. vorgeschlagenen Metrik zur Bestimmung der Überlappung zweier Module (Conrad Lee, Fergal Reid, Aaron McDaid, Neil Hurley, 2010) zu entscheiden welche Module zusammengelegt werden können. So kann die Anzahl der gefundenen Module verringert werden.

MONC bessert somit die Eingeständnisse der Algorithmen LFK und LFM bezüglich der strikten Lokalität aus. Im Vergleich zu LFK, LFM und GCE liefert der Algorithmus zusätzlich, dadurch das er analytisch ist, ein genaueres Ergebnis. Der direkte Laufzeit-Vergleich der Algorithmen zeigt, dass während LFM eine Laufzeit von \(n^2\log(n)\) (Lancichinetti et al., 2009) , damit LFK eine von \(n^3\log(n)\) und GCE eine von \(n^2\log(n)\). MONC ist in der Lage diese Laufzeit auf \(n^2\) zu reduzieren (Havemann et al., 2011). Zusätzliche Vorteile von MONC sind zum einen, dass MONC ausgehend von einem einzelnen Knoten, eigenständig die beste Clique findet und von ihr aus das Netzwerk analysiert, zum anderen, dass der Algorithmus alle Auflösungen \(\alpha\) findet, bei der die natürliche Community sich verändert womit ganz neue Möglichkeiten entstehen, die Ergebnisse auszuwerten.

4. Anwendung

Um MONC mit dem Algorithmus LFM von Lancichinetti u.a. (“Detecting the Overlapping and Hierarchical Community Structure in Complex Networks,” 2009) zu vergleichen, haben Haverman u.a. (“Identification of Overlapping Communities and Their Hierarchy by Locally Calculating Community-Changing Resolution Levels,” 2011) den Algorithmus auf drei verschiedenen Datensätzen getestet. Der erste dieser Datensätze ist der “Karate-Klub-Graph”, welcher auch schon von Zachary (“An Information Flow Model for Conflict and Fission in Small Groups,” 1977) analysiert worden ist. Der Graph modelliert die sozialen Beziehungen der 34 Mitglieder des Karate-Klubs. Bei der Anwendung des Algorithmus’ auf den Karate-Klub Graphen haben die Autoren einzelne Knoten als Startknoten ausgewählt. Das Auswählen von Cliquen als Startpunkt führte in diesem Fall zu sehr ähnlichen Ergebnissen. Im direkten Vergleich liefert auch MONC in diesem Beispiel ähnliche Ergebnisse, wobei die meisten Communities davon auch vom LFM gefunden werden. Aber gerade im Bereich kleinerer Auflösungen findet LFM Communities, die MONC nicht findet. Die Unterschiede in den Ergebnissen liegen teilweise an den leicht verschiedenen Funktionen und teilweise an der Zufälligkeit von LFM (Havemann et al., 2011).
Der zweite Graph, auf dem die Autoren LFM und MONC getestet haben, ist ein Netzwerk aus sich gegenseitig referenzierenden informationswisenschaftlichen Papieren mit 492 Knoten. Die Autoren begründen mit Hilfe dieses Beispieles, dass MONC anwendbare Ergebnisse liefert. So entdeckt MONC, je nach Startbereich, eine Community von Informationsrückgewinnungspapieren, die sich deutlich von der Gruppe der Papiere zum Thema Bibliometrie unterscheiden (Havemann et al., 2011). Auch in diesem Fall sind die Ergebnisse von LFM und MONC sehr ähnlich. Hierbei war MONC in der getesteten Implementierung 75% schneller und ist dennoch, durch die analytische Berechnung der Auflösungen, genauer.
Der dritte Datensatz auf dem MONC getestet wurde, sind die 1100 verschiedenen, mit der LFR Methode erstellten, synthetischen Benchmark Graphen.
Diese Graphen haben die Eigenschaft, dass die Communities eine einfache Hierarchie haben. Dadurch kommt der große Vorteil des Entdeckens der ganzen hierarchischen Struktur der Communities aufeinmal, nicht zum Vorschein. Anhand dieses Datensatzes, vergleichen die Autoren MONC mit GCE. Auffällig ist jedoch, dass der GCE eine fast identische Kurve aufweist, wenn man den durchschnittlichen omega Index in Abhängigkeit des Anteils der sich in überlappender Communities befindlichen Knoten zeichnet. Der omega Index ist ein Kriterium, um fest zu stellen, wie gut die gefundenen Communities mit den wirklichen Communities in dem Graphen übereinstimmen. (Collins & Dent, 1988)

Im Rahmen dieses ProSeminars wurden sämtliche, hier im Online-Buch vorgestellten OCD- Algorithmen anhand verschiedener Gütekriterien analysiert und mittels verschiedener Graphen miteinander verglichen. Die drei essentiellen Merkmale bilden die Laufzeit des Algorithmus, der sogenannte Omega-Index und letztlich die „Extended Normalized Mutual Information ( ENMI ), welches auch ein weiteres Charakteristikum hinsichtlich der Übereinstimmung darstellt. Hierbei finden sich die Definitionen bzw. die Interpretation der Merkmale auf das „Visualisierungs“-Kapitel im Online-Buch. In der folgenden zu untersuchenden Versuchsreihe wurden drei Graphen erstellt, die sich in der Anzahl der Knoten, Kanten und Communities unterscheiden. Im Folgenden wird primär der MONC-Algorithmus mit den anderen OCD-Algorithmen verglichen. Der erste erzeugte Graph, nämlich einer mit 128 Knoten, 2048 Kanten und 4 Communitys, weist bei der Laufzeitanalyse bei den meisten OCD-Algorithmen ähnliche Ergebnisse auf. Der MONC-Algorithmus schneidet hierbei etwas schlechter als CLIZZ, DMID und SSK ab. Auf der anderen Seite ist er schneller als SLPA. Weiter liefert MONC bei Betrachtung des Übereinstimmungs-Kriterium schlechte Ergebnisse, ähnlich verhalten sich CLIZZ, DMID und SSK. Dementsprechend lässt sich behaupten, dass der MONC-Algorithmus bei kleinen Graphen keine gute Übereinstimmungs-Quote erzielt. Der zweite produzierte Graph, besteht aus 500 Knoten, 9424 Kanten und 23 Communitys. Hier erzielte MONC bei einer durchschnittlichen Laufzeit eine vergleichsweise schwachen Übereinstimmung mit dem Ausgangsnetzwerk. Bei diesem Testgraphen erzielte lediglich der SLPA bei einer moderaten Laufzeit eine gute Übereinstimmungsquote. Auf dem letzten erstellten Graph, angelegt mit 10000 Knoten, 194751 Kanten und 400 Communitys hatte der MONC-Algorithmus eine sehr guten Omega-Index von 0,93, was darauf schließen lässt, dass eine hohe Übereinstimmungsrate erzielt wurde. Ähnlich verhält es sich hier mit CLIZZ und SLPA. Bezüglich der Laufzeit verhielten sich CLIZZ und SLPA ähnlich, nämlich sehr gut. MONC spielte hier im oberen Durchschnitt mit. Zusammenfassen lässt sich Aussagen das sich die wahren Stärken des MONC-Algorithmus in den „großen“ Graphen zeigen. Nämlich jene mit vielen Knoten und Kanten. Bei einer durchschnittlichen Laufzeit erzielt hier MONC, eine vergleichsweise überdurchschnittliche Übereinstimmungsquote bezüglich des durchforsteten Netzwerkes. Meistens schneidet allerdings einer der anderen Algoritmen dieses Online-Buches besser ab und wäre in vilen Fällen die bessere Wahl.

5. Zusammenfassung

Mit MONC haben wir nun einen lokalen, deterministischen und parameterfreien Algorithmus, der in einem gewichteten und ungerichteten Netzwerk sich überlappende Communities findet, mit dem Vorteil, dass dieser - im Gegensatz zu den vorherigen Algorithmen - analytisch vorgeht, wodurch er effizienter ist.Es kann z.B. passieren, dass es Fälle - z.B. in der Bibliometrie- gibt, in denen Communities zunächst unbekannter Untergraphen interessanter sind, als die des gesamten Graphen. Hierbei wird MONC angewandt, um dieses Problem zu lösen.
Gerade in sehr großen, lokalen Modulen, kann MONC angewendet werden. Durch die strikte Lokalität ist es möglich, einen starken Anfangsknoten so weit expandieren zu lassen, sodass Subgraphen entstehen. Diese konstruierte Community ist dann für ein Intervall an Auflösungsparametern stabil, wenn es keinen Knoten mehr gibt, der den Wert der gegebenen Funktion innerhalb dieses Auflösungsintervalls erhöhen würde. Verglichen zu LFK, LFM und GCE ist zu erkennen, dass oftmals ähnliche Ergebnisse geliefert werden, jedoch MONC - was das Laufzeitkriterium angeht - schneller ist. Im Vergleich zu Algorithmen, die auf einer grundlegend anderen herangehensweise als MONC basieren schneidet der Algorithmus nicht mehr so gut ab und ein anderer Algorithmus ist in den meisten Fällen MONC vorzuziehen.

6. Referenzen

Havemann, F., Heinz, M., Struck, A., & Gläser, J. (2011). Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels. Journal of Statistical Mechanics: Theory and Experiment. https://doi.org/10.1088/1742-5468/2011/01/P01023
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814–818. https://doi.org/10.1038/nature03607
Baumes, J., Goldberg, M., & Magdon-Ismail, M. (2005). Efficient Identification of Overlapping Communities. In P. Kantor, G. Muresan, F. Roberts, D. D. Zeng, F.-Y. Wang, H. Chen, & R. C. Merkle (Eds.), Intelligence and Security Informatics (Vol. 3495, pp. 27–36). Springer Berlin Heidelberg. https://doi.org/10.1007/11427995\backslash\textunderscore 3
Wang, X., Jiao, L., & Wu, J. (2009). Adjusting from disjoint to overlapping community detection of complex networks. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 388(24), 5045–5056. https://doi.org/10.1016/j.physa.2009.08.032
Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466(7307), 761–764. https://doi.org/10.1038/nature09182
Evans, T. S., & Lambiotte, R. (2010). Line graphs of weighted networks for overlapping communities. Eur Phys J B (European Physical Journal B), 77(2), 265–272. https://doi.org/10.1140/epjb/e2010-00261-8
Lancichinetti, A., Fortunato, S., & Kertész, J. (2009). Detecting the Overlapping and Hierarchical Community Structure in Complex Networks. New J Phys (New Journal Of Physics), 11(3), 033015. https://doi.org/10.1088/1367-2630/11/3/033015
Conrad Lee, Fergal Reid, Aaron McDaid, Neil Hurley. (2010). Detecting highly overlapping community structure by greedy clique expansion. https://arxiv.org/abs/1002.1827
W. Zachary. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33, 452–473.
Collins, L. M., & Dent, C. W. (1988). Omega: A general formulation of the rand index of cluster recovery suitable for non-disjoint solutions. Multivariate Behavioral Research, 23(2), 231–242.