Command Palette
Search for a command to run...
Effiziente Graphlet-Kerne für den Vergleich großer Graphen
Effiziente Graphlet-Kerne für den Vergleich großer Graphen
S. V. N. Vishwanathan Karsten Borgwardt. Kurt Mehlhorn Tobias Petri Nino Shervashidze
Zusammenfassung
Staat der Technik befindliche Graphkerne skaliert nicht auf große Graphen mit Hunderten von Knoten und Tausenden von Kanten. In diesem Artikel schlagen wir vor, Graphen durch das Zählen von Graphlets zu vergleichen, also von Teilgraphen mit k Knoten, wobei k ∈ {3; 4; 5} gilt. Da die vollständige Enumeration aller Graphlets prohibitiv kostspielig ist, führen wir zwei theoretisch fundierte Beschleunigungsschemata ein: eines basierend auf Stichprobentechniken und ein zweites speziell für Graphen mit beschränktem Grad entworfen. In unserer experimentellen Bewertung zeigen unsere neuartigen Kerne, dass wir große Graphen effizient vergleichen können, die mit bestehenden Graphkernen nicht behandelbar sind.