Die Unmöglichkeit von Niederrangdarstellungen für dreieckreiche komplexe Netzwerke

Die Untersuchung komplexer Netzwerke ist eine bedeutende Entwicklung in der modernen Wissenschaft und hat die Sozialwissenschaften, Biologie, Physik und Informatik bereichert. Modelle und Algorithmen für solche Netzwerke sind in unserer Gesellschaft allgegenwärtig und beeinflussen das menschliche Verhalten über soziale Netzwerke, Suchmaschinen und Empfehlungssysteme, um nur einige zu nennen. Eine weit verbreitete algorithmische Technik zur Modellierung solcher komplexer Netzwerke besteht darin, eine niederdimensionale euklidische Einbettung der Knoten des Netzwerks zu konstruieren, wobei die Nähe der Knoten als die Wahrscheinlichkeit einer Kante interpretiert wird. Entgegen der gängigen Ansicht argumentieren wir, dass solche Grapheneinbettungen signifikante Eigenschaften komplexer Netzwerke nicht erfassen. Die beiden Eigenschaften, auf die wir uns konzentrieren, sind niedriger Grad und hohe Clusterkoeffizienten, die empirisch für reale Netzwerke als wahr erwiesen wurden. Wir beweisen mathematisch, dass jede Einbettung (die Skalarprodukte zur Messung der Ähnlichkeit verwendet), die diese beiden Eigenschaften erfolgreich erzeugen kann, einen Rang haben muss, der nahezu linear in der Anzahl der Knoten ist. Unter anderem bedeutet dies, dass beliebte Einbettungstechniken wie die singuläre Wertzerlegung und node2vec wesentliche strukturelle Aspekte realer komplexer Netzwerke nicht erfassen. Darüber hinaus untersuchen wir empirisch eine Reihe unterschiedlicher Einbettungstechniken basierend auf Skalarprodukten und zeigen, dass sie alle versagen, die Dreiecksstruktur zu erfassen.