Diese Arbeit befasst sich mit der Durchsuchung von Netzwerken mittels Aktivierungsausbreitungsverfahren. Netzwerke, formell oft als Graphen dargestellt, sind Datensätze bestehend aus Datenobjekten (Knoten) und Beziehungen zwischen diesen (Kanten). In vielen Bereichen, wie z.B. Information Retrieval, werden Netzwerke bezüglich bestimmter Anfragen nach in Beziehung stehenden, relevanten oder interessanten Datenobjekten durchsucht. Unter anderem werden dazu Aktivierungsausbreitungsverfahren eingesetzt. In diesen Verfahren werden die Knoten, welche die Datenobjekte der Anfrage repräsentieren, initial aktiviert. Die Aktivierung jedes Knotens breitet sich iterativ über verbundene Kanten zu benachbarten Knoten aus, wobei diese ebenfalls zu einem bestimmten Grad aktiviert werden. Das finale Aktivierungsniveau nach einer bestimmten Anzahl an Iterationen wird als heuristisches Maß für Relevanz, Interessantheit oder Wichtigkeit etc. interpretiert. Als Ergebnis auf eine Anfrage werden die Datenobjekte nach ihrem Aktivierungsniveau sortiert aufgelistet.



Unbeschränkte Aktivierungsausbreitungsverfahren haben jedoch verschiedene Nachteile, weshalb bisher meist heuristische Beschränkungen zum Einsatz gekommen sind, um diese zu vermeiden. In dieser Arbeit wird ein weiterer Nachteil, die Konvergenz zu einem anfrageunabhängigen Fixpunkt, gezeigt sowie Verfahren zur Vermeidung dieses Nachteils beschrieben, die ohne den Einsatz von Beschränkungen auskommen.



Des Weiteren wird gezeigt, wie auf Basis der Konvergenz zwei Arten von Ähnlichkeiten zwischen Knoten in Graphen aus Aktivierungsausbreitungsprozessen bestimmt werden können. Durch die Sortierung der Knoten bezüglich beider Ähnlichkeiten zu Anfrageknoten ergeben sich, zusätzlich zur Sortierung aufgrund ihres Aktivierungsniveaus, weitere Möglichkeiten Netzwerke zu durchsuchen.



Die Aktivierungsähnlichkeit basiert auf der Überlappung der direkten und indirekten Nachbarschaft zweier Knoten und ist eine Relaxierung der maximalen strukturellen Äquivalenz. Je stärker die Überlappung, desto höher ist der Grad der Ähnlichkeit zweier Knoten. Zwei Knoten, die einen hohen Grad an Ähnlichkeit aufweisen, müssen demnach im Graphen eine geringe Distanz haben, was eine Einschränkung der Möglichkeiten zur Durchsuchung anhand der Aktivierungsähnlichkeit bedeutet. Diese Ähnlichkeit ist geeignet um dichte umgebende Teilgraphen oder Knotengemeinschaften, um Anfrageknoten zu extrahieren.



Die Signaturähnlichkeit basiert auf dem Vergleich der Struktur der direkten und indirekten Nachbarschaft zweier Knoten, nicht auf der Überlappung dieser. Es wird gezeigt, dass Knoten, die strukturell nicht unterschieden werden können, also automorphe Abbilder voneinander sind, stets maximal ähnlich sind. Die Signaturähnlichkeit ist eine Relaxierung der maximalen Orbit-Äquivalenz und ein heuristisches Maß für die strukturelle Ähnlichkeit der Nachbarschaft von Knoten. Zwei Knoten, die einen hohen Grad an Ähnlichkeit aufweisen, müssen im Graphen nicht notwendigerweise eine geringe Distanz haben, sondern können sich weit entfernt voneinander befinden. Dies ist bei der Aktivierungsähnlichkeit bzw. beim Aktivierungsniveau nicht der Fall und eröffnet neue Möglichkeiten beim Durchsuchen von Netzwerken mittels Aktivierungsausbreitung.



Anhand von künstlichen Daten werden bestimmte Eigenschaften beider Ähnlichkeiten empirisch überprüft. Des Weiteren werden zwei Netzwerke mit unterschiedlicher Struktur, bestehend aus realen Daten, anhand beider Ähnlichkeiten durchsucht. Dabei werden beispielhaft die Nachbarschaften und Knotengemeinschaften von Knoten mit hoher Signaturähnlichkeit mit geeigneten Layoutverfahren visualisiert, um strukturelle Kohärenzen zu zeigen.

This thesis discusses how networks can be searched via methods of spreading activation. Networks, often represented as graphs, are datasets consisting of data objects (nodes or vertices) and the relations among them (edges). In many areas, e.g. information retrieval, networks are searched according to specific queries for related, interesting and relevant data objects, by applying methods such as spreading activation. In these methods, nodes, which represent the queries' data objects, are initially activated. The activation of each node subsequently spreads iteratively via connected edges to activate adjacent nodes with a certain level. The final level of activation after a certain number of iterations is interpreted as a heuristic measure of relevance, interestingness or importance. The result of the query is a list of data objects, sorted according to their level of activation.



There are, however, several drawbacks to methods involving pure (constraint free) spreading activation, which is why until now, heuristic constraints have usually been applied to counteract these disadvantages. In this work another drawback, the convergence to a query-independent fix point is shown and discussed as well as methods to avoid this drawback without the usage of constraints.



This work goes on to show how two kinds of similarities between nodes in graphs can be determined by applying the spreading activation process based on convergence. Sorting nodes according to both types of similarities to query nodes produces further possibilities of searching networks in addition to sorting based on levels of activation.



Activation similarity is based on the overlap of the direct and indirect neighborhood of two nodes and is a relaxation of the maximal structural equivalence. The more overlap, the higher the degree of similarity of two nodes. Thus, two nodes with a high degree of similarity are reflected by a small distance in the graph, limiting the possibilities of searching based on activation similarity. This similarity measure is suitable for extracting dense surrounding subgraphs or communities surrounding query nodes.



Signature similarity is based on comparing the structure of the direct and indirect neighborhoods of two nodes, and not on the overlap. It is shown that nodes that cannot be structurally distinguished, i.e. nodes that are automorphic images of each other, always have a maximal degree of similarity. The signature similarity is a relaxation of the maximal orbit equivalence and a heuristic measure of structural similarity of the neighborhood of nodes. Two nodes with a high degree of similarity do not necessarily have to be positioned close to each other in the graph, but can be located far away from each other. This is not the case with activation similarity or the level of activation and therefore provides new possibilities for searching networks via methods of spreading activation.



Using artificial data, it is possible to empirically verify certain properties of both similarity measures. Furthermore, two networks of different structures, containing real world dara are searched based on both types of similarities. In doing so neighborhoods and communities of nodes with high signature similarity are visualized with adequate layout methods exemplary in order to illustrate structural coherences.