EdMot: Ein Kantenverstärkender Ansatz für motifbewusste Gemeinschaftserkennung

Die Erkennung von Netzwerkcommunitys ist ein aktuelles Forschungsthema in der Netzwerkanalyse. Obwohl zahlreiche Methoden zur Community-Erkennung vorgeschlagen wurden, berücksichtigen die meisten lediglich die niedrigstufigen Strukturen des Netzwerks auf der Ebene einzelner Knoten und Kanten. Daher können sie die höherstufigen Eigenschaften auf der Ebene kleiner, dichter Untergraphmuster – beispielsweise Motive – nicht adäquat erfassen. In jüngster Zeit wurden einige hochstufige Methoden entwickelt, die jedoch typischerweise auf hypergraphbasierten Modellen basieren, die als zusammenhängende Graphen angenommen werden. Diese Annahme lässt sich jedoch in bestimmten realen Netzwerken nicht gewährleisten. Insbesondere kann der Hypergraph fragmentiert sein, d. h., er besteht aus einer großen Anzahl von zusammenhängenden Komponenten und isolierten Knoten, obwohl das ursprüngliche Netzwerk selbst zusammenhängend ist. Folglich leiden bestehende hochstufige Methoden erheblich unter diesem Fragmentierungsproblem, da Knoten, die im Hypergraphen nicht miteinander verbunden sind, trotz gemeinsamer Zugehörigkeit zu derselben Community nicht zusammengefasst werden können. Um dieses Fragmentierungsproblem zu lösen, schlagen wir eine Edge-Enhancement-Methode für motiveinsichtige Community-Erkennung (EdMot) vor. Der zentrale Ansatz ist wie folgt: Zunächst wird ein auf Motiven basierender Hypergraph aufgebaut, und die K größten zusammenhängenden Komponenten dieses Hypergraphs werden in Module partitioniert. Anschließend wird die Verbindungsstruktur innerhalb jedes Moduls durch den Aufbau einer Kantenmenge verstärkt, um aus jedem Modul eine Clique zu generieren. Auf Basis dieser neuen Kantenmenge wird die ursprüngliche Verbindungsstruktur des Eingabenetzes verbessert, um ein umgebautes Netzwerk zu erzeugen, wodurch die auf Motiven basierende hochstufige Struktur effektiv genutzt und das Problem der Hypergraph-Fragmentierung effizient adressiert wird. Schließlich wird das umgebaute Netzwerk partitioniert, um die hochstufige Community-Struktur zu ermitteln.