Subgraph-Netzwerke mit Anwendung auf die Erweiterung des strukturellen Merkmalsraums

Reale Netzwerke weisen ausgeprägte hierarchische und modulare Strukturen auf, wobei verschiedene Untergraphen als Bausteine dienen. Die meisten existierenden Studien betrachten einfach unterschiedliche Untergraphen als Motive und verwenden nur ihre Anzahlen, um das zugrundeliegende Netzwerk zu charakterisieren. Obwohl solche Statistiken verwendet werden können, um ein Netzwerkmodell zu beschreiben oder sogar einige Netzwerkalgorithmen zu entwerfen, kann die Rolle von Untergraphen in solchen Anwendungen weiter erforscht werden, um die Ergebnisse zu verbessern. In dieser Arbeit wird das Konzept des Untergraphennetzes (Subgraph Network, SGN) eingeführt und dann auf Netzwerkmodelle angewendet. Es werden Algorithmen entwickelt, um erster- und zweiter-Ordnungs-SGNs zu konstruieren, die leicht erweitert werden können, um höhere Ordnungen zu bilden. Darüber hinaus werden diese SGNs verwendet, um den strukturellen Merkmalsraum des zugrundeliegenden Netzwerks zu erweitern, was für die Netzwerkklassifikation vorteilhaft ist. Numerische Experimente zeigen, dass das Klassifikationsmodell für Netzwerke basierend auf den strukturellen Merkmalen des ursprünglichen Netzwerks zusammen mit den erster- und zweiter-Ordnungs-SGNs stets die besten Ergebnisse liefert im Vergleich zu Modellen, die nur auf einem oder zwei dieser Netzwerke basieren. Mit anderen Worten: Die strukturellen Merkmale der SGNs können die des ursprünglichen Netzwerks ergänzen, um eine bessere Klassifikation zu ermöglichen, unabhängig von der verwendeten Merkmalsextraktionsmethode wie manuell gestaltete Methoden (handcrafted), Netzwerk-Einbettungsmethoden (network embedding) und kernbasierte Methoden (kernel-based methods).