Knotenähnlichkeiten aus Aktivierungsausbreitungen

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:6f707a067283ac31a65f0d039dbc4ef8

THIEL, Kilian, 2012. Knotenähnlichkeiten aus Aktivierungsausbreitungen [Dissertation]. Konstanz: University of Konstanz

@phdthesis{Thiel2012Knote-18779, title={Knotenähnlichkeiten aus Aktivierungsausbreitungen}, year={2012}, author={Thiel, Kilian}, address={Konstanz}, school={Universität Konstanz} }

Knotenähnlichkeiten aus Aktivierungsausbreitungen Thiel, Kilian deposit-license 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.<br /><br /><br /><br />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.<br /><br /><br /><br />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.<br /><br /><br /><br />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.<br /><br /><br /><br />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.<br /><br /><br /><br />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. deu Thiel, Kilian 2012 Node Similarities from Spreading Activation 2012-03-13T06:36:40Z 2012-03-13T06:36:40Z

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

Dissertation_Thiel.pdf 221

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto