Ant algorithms for self-organization in social networks

Abstract

Peer-to-Peer Netzwerke und Folksonomies ähneln lebendigen Organismen, die stetig wachsen und sich kontinuierlich ändern. Ameisenalgorithmen sind dem emergenten und selbstorganisierenden Verhalten von Ameisenkolonien bei der Futtersuche nachempfunden. Die vorliegende Dissertation beschäftigt sich mit der Anwendbarkeit von Ameisenalgorithmen in diesen Netzwerken für (1) die semantische Suche in unstrukturierten Peer-to-Peer Netzwerken, und für (2) die Extrahierung von adaptiven Benutzungsprofilen von Folksonomies.<br />Das Hauptproblem bei der Suche in unstrukturierten Peer-to-Peer Netzwerken ist es, für jede Anfrage jene Peers zu finden, die dem anfragenden Peer topologisch nahe liegen und über Ressourcen verfügen, die als Antwort auf die Anfrage geeignet sind. Der im Rahmen dieser Dissertation für diesen Zweck erstellte Ameisenalgorithmus SemAnt verfolgt einen Ansatz, in dem die Informationen über die an den entfernten Peers verfügbaren Ressourcen auf passive Art und Weise, durch das Überwachen der am lokalen Peer empfangenen und weitergeleiteten Anfragen und Antworten, gewonnen werden. Jede erfolgreiche Anfrage hinterlässt eine Spur im Netzwerk. Für das Weiterleiten aktueller Anfragen wird ein probabilistisches Modell benutzt, das die Summe der bestehenden Spuren auswertet. Dieses Modell kombiniert eine verwertende mit einer explorierenden Strategie. In der verwertenden Strategie werden immer jene Spuren benutzt, die am besten geeignet sind. In der explorierenden Strategie werden auch schlechtere Spuren benutzt, um potentiell noch nicht bekannte bessere Wege zu finden und damit die Leistung des Gesamtsystems zu erhöhen.<br />Die Leistung von semantischen Ansätzen zur Peer-to-Peer Suche wird stark von der Verteilung der Inhalte im Netzwerk beeinflusst. Das gilt auch für den \semant{} Algorithmus. Unter der Annahme, dass alle Ressourcen im Netzwerk mit aus einer Taxonomie stammenden Metadaten ausgezeichnet sind und dass die Anfragen auf demselben Metadatenvokabular beruhen, ist es möglich, die hierarchische Information aus der Taxonomie in die Entscheidung mit einzubeziehen, zu welchem Nachbar-Peer eine Anfrage weitergeleitet werden soll.<br />Damit wird die Leistung des Suchalgorithmus verbessert.<br />Ameisenalgorithmen inkludieren einen Evaporierungsfaktor zur Berücksichtigung von zeitlichen Aspekten bei der inkrementellen Generierung von Lösungen für Optimierungsprobleme. Der Add-A-Tag Algorithmus für die Extrahierung von adaptiven Benutzungsprofilen von Folksonomies nutzt diesen Evaporierungsfaktor in Kombination mit einem Co-occurrence Ansatz zur Anpassung von Benutzungsprofilen an die Änderungen im Tagging Verhalten eines Benutzers oder einer Benutzerin. Die mit Add-A-Tag erstellten Profile sind semantische Netzwerke, deren gewichtete Kanten die Stärke der Beziehungen zwischen den einzelnen Tags im Profil ausdrücken. Durch die Integration des Evaporierungsfaktors in den Algorithmus beinhalten die Profile sowohl die Langzeitinteressen als auch die Kurzzeitinteressen der BenutzerInnen zum Zeitpunkt der Profilberechnung. Die Profile können für das personalisierte Browsen von annotierten Datenquellen verwendet werden.<br />

Peer-to-peer networks and folksonomies are like living organisms, ever growing and changing as time goes on. This thesis addresses the applicability of algorithms derived from the self-organizing and emergent behavior observed from ant colonies to these complex networks for two specific purposes, namely (1) content-based search in unstructured peer-to-peer networks, and (2) the extraction of adaptive user profiles from folksonomies.<br />For search in unstructured peer-to-peer networks, the main goal is to find the shortest path from every querying peer to one or more answering peers that possess resources which are appropriate answers for the given query. The SemAnt algorithm, which is designed for this task, is based on reputation learning. In reputation learning, the information about the remote peers' resources is gained passively by observing the user queries and their answers that are forwarded through the local peer. Every successful query evokes small updates in the routing tables of those peers that are included in the path between the querying and the answering peer. The routing tables are used for subsequent queries to decide which link to follow in order to find appropriate resources.<br />The SemAnt algorithm is compliant with the Ant Colony Optimization meta-heuristic, and it employs a probabilistic procedure to select outgoing links for query forwarding. This procedure combines an exploiting strategy, which selects those links currently known as the most appropriate ones, with an exploring strategy, which also follows links not currently known as the best ones with the aim of finding better paths not yet explored. A weight defines the ratio between the strategies.<br />Since the SemAnt algorithm is a content-based approach to peer-to-peer search, its performance depends on how the content is distributed in the network. The evaluation of the algorithm includes an investigation to which extent this is the case. Based on these results, we develop strategies for improvement.<br />Under the assumption that the resources in the network are annotated according to a taxonomy, and that the query vocabulary is restricted to the leaf topics from the same taxonomy, it is possible to consider also the upper-level topics in the query routing procedure of the algorithm in order to increase its performance.<br />Ant algorithms include an evaporation feature for integrating a time factor when incrementally creating solutions. This feature is beneficial for the task of learning adaptive user profiles from tagging data. For this purpose we design the Add-A-Tag algorithm, which is based on a combination of an evaporation feature for adapting the user profile to trends over time, and the co-occurrence technique for determining the relationships between tags.<br />The user profiles created with the Add-A-Tag algorithm are semantic networks derived from the structure of the tagging data, and they are adaptive in the sense that they change according to changes in a user's tagging behavior. In addition to the long-term interests of a user, also his or her short-term interests are included in the profile at any given point of time. We present a tool for visualizing the changes in the profile over time, and we show how to exploit the profile for personalized browsing of annotated data sources.<br />