Stapelmodelle für nahezu optimale Linkvorhersage in komplexen Netzwerken

Die meisten realen Netzwerke sind unvollständig beobachtet. Algorithmen, die genau vorhersagen können, welche Links fehlen, können die Datensammlung im Netzwerk erheblich beschleunigen und die Validierung von Netzwerkmodellen verbessern. Es gibt mittlerweile viele Algorithmen zur Vorhersage fehlender Links, basierend auf einem teilweise beobachteten Netzwerk, aber es ist weiterhin unklar, ob ein einziger bester Prädiktor existiert, wie die Vorhersagbarkeit von Links zwischen verschiedenen Methoden und Netzwerken aus unterschiedlichen Domänen variiert und wie nah die aktuellen Methoden an der Optimalität sind. Wir beantworten diese Fragen, indem wir 203 individuelle Linkvorhersagealgorithmen systematisch bewerten, die drei beliebte Familien von Methoden repräsentieren und auf ein großes Korpus von 550 strukturell unterschiedlichen Netzwerken aus sechs wissenschaftlichen Domänen angewendet werden. Wir zeigen zunächst, dass individuelle Algorithmen eine breite Vielfalt an Vorhersagefehlern aufweisen, sodass kein Prädiktor oder keine Familie über alle realistischen Eingaben hinweg der beste oder schlechteste ist. Anschließend nutzen wir diese Vielfalt mithilfe von netzwerkbasiertem Metalearning, um eine Serie von "gestapelten" Modellen zu konstruieren, die Prädiktoren in einen einzelnen Algorithmus kombinieren. Angewendet auf eine breite Palette synthetischer Netzwerke, für die wir analytisch die optimale Leistung berechnen können, erreichen diese gestapelten Modelle optimale oder nahezu optimale Genauigkeitsniveaus. Angewendet auf reale Netzwerke sind gestapelte Modelle überlegen, aber ihre Genauigkeit variiert stark nach Domäne, was darauf hindeutet, dass die Linkvorhersage in sozialen Netzwerken grundlegend einfacher sein könnte als in biologischen oder technologischen Netzwerken. Diese Ergebnisse deuten darauf hin, dass der Stand der Technik für die Linkvorhersage aus der Kombination individueller Algorithmen stammt, die nahezu optimale Vorhersagen erzielen können. Wir schließen mit einer kurzen Diskussion über Einschränkungen und Möglichkeiten für weitere Verbesserungen.