Zur Wirkung des durchschnittlichen Clustering-Koeffizienten auf die topologiebasierte Linkprädiktion in merkmalslosen Graphen

Die Linkvorhersage ist ein zentrales Problem der Graphentheorie mit vielfältigen Anwendungen, darunter Empfehlungssysteme, Gemeinschaftserkennung und die Identifikation irrelevanter Verbindungen. Während merkmalsbasierte Methoden hohe Genauigkeit erzielen, ist ihre Anwendbarkeit auf Graphen ohne Knotenmerkmale eingeschränkt. Für solche Graphen werden üblicherweise strukturbasierte Ansätze eingesetzt, darunter Methoden basierend auf gemeinsamen Nachbarn und Grad-abhängige Verfahren. Die Effektivität dieser Ansätze hängt jedoch von der Dichte des Graphen ab: Algorithmen auf Basis gemeinsamer Nachbarn erzielen in dichten Graphen gute Ergebnisse, während Grad-abhängige Methoden besser für spärliche oder baumartige Graphen geeignet sind. Dennoch fehlt in der Literatur ein klarer Kriterium zur Unterscheidung zwischen dichten und spärlichen Graphen. In diesem Beitrag wird der durchschnittliche Klusterkoeffizient als Kriterium zur Beurteilung der Graphendichte vorgestellt, um die Auswahl geeigneter Linkvorhersagealgorithmen zu unterstützen. Um die Knappheit an Datensätzen für empirische Analysen zu überwinden, schlagen wir eine neuartige Graphgenerierungsmethode basierend auf dem Barabasi-Albert-Modell vor, die eine kontrollierte Variation der Graphendichte ermöglicht, während strukturelle Heterogenität erhalten bleibt. Durch umfassende Experimente an synthetischen und realen Datensätzen etablieren wir eine empirische Grenze für den durchschnittlichen Klusterkoeffizienten, die die Auswahl effektiver Linkvorhersagemethoden erleichtert.