004 Datenverarbeitung; Informatik
Refine
Document Type
- Diploma Thesis (1)
- Doctoral Thesis (1)
Keywords
- Künstliche Intelligenz (2) (remove)
Institute
In this thesis, I study the spectral characteristics of large dynamic networks and formulate the spectral evolution model. The spectral evolution model applies to networks that evolve over time, and describes their spectral decompositions such as the eigenvalue and singular value decomposition. The spectral evolution model states that over time, the eigenvalues of a network change while its eigenvectors stay approximately constant.
I validate the spectral evolution model empirically on over a hundred network datasets, and theoretically by showing that it generalizes arncertain number of known link prediction functions, including graph kernels, path counting methods, rank reduction and triangle closing. The collection of datasets I use contains 118 distinct network datasets. One dataset, the signed social network of the Slashdot Zoo, was specifically extracted during work on this thesis. I also show that the spectral evolution model can be understood as a generalization of the preferential attachment model, if we consider growth in latent dimensions of a network individually. As applications of the spectral evolution model, I introduce two new link prediction algorithms that can be used for recommender systems, search engines, collaborative filtering, rating prediction, link sign prediction and more.
The first link prediction algorithm reduces to a one-dimensional curve fitting problem from which a spectral transformation is learned. The second method uses extrapolation of eigenvalues to predict future eigenvalues. As special cases, I show that the spectral evolution model applies to directed, undirected, weighted, unweighted, signed and bipartite networks. For signed graphs, I introduce new applications of the Laplacian matrix for graph drawing, spectral clustering, and describe new Laplacian graph kernels. I also define the algebraic conflict, a measure of the conflict present in a signed graph based on the signed graph Laplacian. I describe the problem of link sign prediction spectrally, and introduce the signed resistance distance. For bipartite and directed graphs, I introduce the hyperbolic sine and odd Neumann kernels, which generalize the exponential and Neumann kernels for undirected unipartite graphs. I show that the problem of directed and bipartite link prediction are related by the fact that both can be solved by considering spectral evolution in the singular value decomposition.
Rescueanalyser
(2007)
Im Forschungsgebiet der Künstlichen Intelligenz und Multiagenten-Systeme stellt die Erkennung von Plänen eine besondere Herausforderung dar. Es gilt aus einer Menge von Beobachtungen Agentenpläne effektiv, zuverlässig und eindeutig zu identifizieren. Im Bereich des RoboCup ist es von entscheidender Bedeutung, dass Agenten über die Pläne und Intensionen anderer Agenten schlussfolgern können, um gemeinsame Ziele zu erreichen. Diese Diplomarbeit umfasst die Konzeption und Entwicklung eines Werkzeugs für die RoboCupRescue-Simulation, welches die Abläufe einer Rescue-Simulation analysiert und die beobachteten Aktionsfolgen Plänen einer vorspezifizierten Planbibliothek zuordnet. Das entwickelte Analysewerkzeug zeichnet sich einmal durch seine Unabhängigkeit von den verschiedenen Rescue-Agententeams aus, sowie durch die Verwendung neuester Methoden zur effektiven Planerkennung. Damit ermöglicht der entwickelte Rescueanalyser sowohl die Fehlersuche und Optimierung des eigenen Agententeams als auch die Erforschung und Auswertung unterschiedlicher Strategien der Rescue-Agenten konkurrierender Teams. Neben der Visualisierung der Ergebnisse mittels eines optimierten Monitors des Rescue-Simulators, können die Resultate und Auswertungen der Planerkennung auch durch textbasierte Ausgaben detailliert eingesehen werden.