The Target Set Selection Problem with Arbitrary Edge Weights

Diese Masterarbeit erörtert, warum das Target Set Selection Problem (TSSP) für Forschungsfelder, die an Bedeutung zunehmen, von großer Wichtigkeit ist. Der Einfluss von Eigenschaften von Graphen auf die Komplexität der Lösung des TSSP wird gezeigt. Für den Fall von Graphen mit beliebigen Kantengewichten wird eine neue Formulierung der ganzzahligen linearen Optimierung eingeführt und gezeigt, wo die Tücken beim Finden eines Target Sets im Falle von Graphen mit beliebigen Kantengewichten sind. Für Instanzen mit unterschiedlichen strukturellen Eigenschaften, sowie für reale Datensätze, wurden Lösungen des TSSP gefunden und analysiert. Eine Erkennt- nis ist, dass eine hohe Dichte des Graphen, mehr noch als die Anzahl der Knoten, zu einer hohen Rechenzeit zur Ermittlung der Lösung des TSSP führt.This master’s thesis reasons why the Target Set Selection Problem (TSSP) is of high relevance to research topics of gaining importance. The impact of graph properties on the complexity of solving the TSSP is shown. For the case of graphs with arbitrary edge weights, a novel integer linear programming formulation is established, and it is shown where the pitfalls of finding target sets in graphs with arbitrary edge weights are. For instances with different structural features, as well as for real-world data, solutions have been found and analyzed. One of the findings is, that even more than the number of nodes, a high graph density leads to a great increase in calculation time for determining the solution of the TSSP