Joana Schmidt	Torben Wittek
RWTH Aachen University	RWTH Aachen University
joana.schmidt@rwth-aachen.de	torben.wittek@rwth-aachen.de

Zusammenfassung (Abstract):

In einer sich digitalisierenden Welt nimmt die Zahl generierter Daten in sozialen Netzwerken stark zu. Zur Untersuchung der Communities und der Überlappungen zwischen diesen Gruppen, bietet der so bezeichnete Ameisenalgorithmus eine Möglichkeit diese zu erkennen und besser zu interpretieren. Basierend auf dem Verhalten von Ameisen bei der Futtersuche, bilden dabei verschiedene Wege (=Kanten) zum Problem eine Möglichkeit eine effiziente Lösung zu finden. So werden zu Beginn zufällig verschiedene Wege gewählt, um eine Lösung zu erreichen. Je effizienter, also kürzer der Weg ist, desto höher wird dieser bewertet. Die folgenden Durchläufe der Problemlösung orientieren sich dabei an den Bewertungen der Wege und nehmen mit größerer Wahrscheinlichkeit höher bewertete Wege. Beispielsweise scheiden Ameisen entlang ihres Weges einen Duftstoff aus. Wobei Ameisen auf dem kürzeren Weg schneller von der Futterstelle zurückkehren, so dass mit der Zeit auf dem kürzesten Pfad eine höhere Duftstoffkonzentration als auf den Anderen vorherrscht. Resultierend daraus wird dieser Weg von nachkommenden Ameisen bevorzugt. Durch dieses Verfahren lassen sich aus einem Graphen die kürzesten Wege zwischen Knoten erkennen und somit auch Overlapping Communities darstellen.

Einleitung

Die sozialen Netzwerke sind in den letzten Jahren immer beliebter geworden und gehören zu den weltweit genutzten Websites, denen immer mehr Aufmerksamkeit geschenkt wird. Die Gründe dafür sind, dass sie als Ort des Informationsaustauschs dienen, sowie als eine Möglichkeit zur Kommunikation im Internet. Im Zusammenhang mit sozialen Netzwerken wird das Konzept der Gemeinschaften immer relevanter. Diese sogenannten Communities bezeichnen eine Gruppe von Menschen, die gemeinsame Interessen und Ziele verfolgen und sich gemeinsamen Wertvorstellungen verpflichtet fühlen. Zwischen Communities kann es auch zu Überlappungen kommen, da ein Nutzer auch gleichzeitig in mehreren Communities aktiv sein kann. In der Netzwerkanalyse nutzt man Graphen zur Repräsentation, welche algorithmisch untersucht werden, um überlappende Communities zu entdecken. In dieser Arbeit wird der Ant-Colony Algorithmus zur Entdeckung von überlappenden Communities vorgestellt. Zu Beginn betrachten wir verwandte Arbeiten, welche ähnliche Ansätze verfolgen, wobei der Schwerpunkt unserer Arbeit, im Vergleich zu anderen Ansätzen, nicht auf der Optimierung von Problemen liegt, sondern die Struktur von Communities in einem sozialen Netzwerk analysiert. Daraufhin beginnen wir mit der angewandten Methodik, indem wir die Notation einführen und das Problem definieren. Dabei gehen wir zunächst auf dem biologischen Hintergrund und die Inspiration des Algorithmus ein und danach auf die Funktionsweise, sowie die Implementierung als Pseudocode. Die Ausführung des Algorithmus auf bestimmten Datensätzen zeigt, dass …. . Diese Ergebnisse werden am Ende der Arbeit nochmals evaluiert und zusammengefasst, um aufzuzeigen, dass der Ant-Colony Algorithmus besonders effektiv zur Analyse von überlappenden Communities ist.

Verwandte Arbeiten

Bereits mit der Zunahme der Bedeutung Sozialer Netze entstanden unzählige wissenschaftliche Arbeiten, die sich mit der Analyse, der daraus ergebenen Strukturen befassen. Fast genauso unzählige Arbeiten gibt es schon über die Ansätze von Ant-Colony Algorithmen, welche diesen als Wegfindungs-Algorithmus auffassen um NP-Probleme in einer polynomiellen Laufzeit näher betrachten und mögliche Lösungen optimieren können. In diesem Abschnitt beschreiben wir ähnliche Arbeiten, die sich mit dem ACO auseinandersetzen und erklären, wie sich unsere Implementation zur Erkennung von Communitys in sozialen Netzwerken zu dem ursprünglichen ACO unterscheidet. Das Ursprüngliche Modell des ACO (Noveiri et al., 2015) beschreibt, dass Objekte (Ants) auf einem Graphen platziert werden und dort nach einer Wahrscheinlichkeit, Kanten zwischen einem Start und Endknoten beschreiten, um jeden Knoten einmal abgelaufen zu sein. Dabei wird auf jeder Kante eine Verweildauer markiert, sodass sich durch Beeinflussung der Wahrscheinlichkeiten die Ameisen künftig an den kürzeren Wegen orientieren werden[…] Wie aus allen Beschreibungen oben erkenntlich, fokussieren sich diese schwerpunktmäßig auf die Erkennung von Pfaden und nicht auf die Erkennung von Communities. So stellt diese Arbeit in dem Bereich der Erkennung von Communities einen recht jungen Zweig der Anwendung von ACO dar. Eine in diesem Bereich ebenso erschienene Arbeit ist (missing reference), welche eine mögliche Implementierung eines Algorithmus unter Verwendung des ACO aufzeigt. Sie beschreibt die technischen Möglichkeiten des ACO und vergleicht diese Ergebnisse mit anderen vergleichbaren Algorithmen. Jedoch beschäftigte sich dieser Ansatz auch mit ameisenbasierten Algorithmen zur Erkennung hierarchischer Community-Strukturen in einem sozialen Netzwerk. Dabei wird die Netzwerkmodularität Q von Newman (Newman & Girvan, 2004), als heuristische Information, um nahezu optimale Lösungen zu finden. Eine weitere Anwendung des Ant-Colony Algorithmus bestand darin, in einem auf Datenaustausch basierendem Netzwerk, die ACO-Technik anzuwenden mithilfe einer künstlichen Ameisenkolonie, um den kürzesten Weg zwischen zwei Mitgliedern zu finden, sodass Routing-Overhead und Netzwerkkosten reduziert werden können.(missing reference) Anders als die aufgezeigten Arbeiten beschränken wir uns auf die Anwendung des ACO auf soziale Netzwerke, ohne dort durch weitere Verfahren eine Optimierung des Algorithmus vorzunehmen. So können hier aufgezeigte Arbeiten einen effizienteren Algorithmus präsentieren. Dies ist nicht Ziel dieser Arbeit. Wir zeigen den klassischen ACO in einer modifizierten Art um Überlappungen zwischen Communities zu entdecken.

Ursprünge und Inspiration für den Algorithmus

Ameisenalgorithmen sind eine effektive Technik zur Lösung von Optimierungsproblemen mit künstlich generierten Ameisen. Diese Ameisen ahmen dabei das Verhalten einer Ameisenkolonie in der Natur nach, um Nahrung zu suchen. Auf ihrer Reise legen Ameisen sogenannte Pheromone ab, die im Laufe der Zeit jedoch verdunsten können. Je höher die Pheromonkonzentration auf einem Pfad ist, desto wahrscheinlicher ist es, das er von den zukünftigen Ameisen ausgewählt wird. Die Ameise, die den kürzesten Weg nimmt, kehrt dabei früher wieder zurück, als eine andere Ameise, die einen längeren Weg ausgewählt hat. Dadurch ist die Pheromonkonzentration auf dem kürzeren Weg höher. Folglich wird die nächste Ameise aufgrund des höheren Pheromonspiegels eher den kürzeren Weg wählen. Dies führt wieder zu einer Erhöhung der Pheromonkonzentration auf diesem Pfad und schließlich nehmen alle Ameisen den kürzeren Weg. Somit können Ameisen verwendet werden, um kürzeste Pfade innerhalb eines Graphen zu finden.

Funktionsweise

In unserem Model wird das soziale Netzwerk, als ein Graph \(G=(N,L)\) modelliert, wobei die Menge \(N = {V_1,V_2,...,V_n}\) eine (endliche) Menge von Knoten ist, welche jeweils die Nutzer in dem Netzwerk repräsentieren, und \(L ⊆ N\times N\) eine (endliche) Menge Kanten ist, die für eine soziale Interaktion stehen. Zwei Knoten, die miteinander verbunden sind, stellen also eine soziale Interaktion zwischen zwei Nutzern da und werden als Nachbarn bezeichnet.In unserer Implementierung wird ein gewichteter Graph betrachtet, dieser hat eine Funktion \(w: L → R\), die jeder Kantee\in Leinen Wert w zuordnet. Wir betrachten dabei Pfade in diesem Graphen, also eine Sequenz von Knoten \(V_1,V_2,...,V_n\) mit \((V_i,V_{(i+1)})\in L\),für \(1\le i< n\). Die Länge dieser Pfade ergibt sich durch die Summe der Gewichte der Kanten. Somit ist die Distanz \(d_{ij}\) zwischen zwei Knoten die Länge des Pfades von dem Knoten \(V_i\) zum Knoten \(V_j\). Dabei ist das primäre Ziel des Algorithmus die Communities in dem Graph zu identifizieren und dabei anschließend Überlappungen zwischen den einzelnen Gruppen herauszusuchen. Um dieses Ziel zu realisieren muss der Graph in überlappende Untergraphen \(G_1,...,G_n\) partitioniert werden, wobei \(U_{(1\le i\le n)ß}\ G_i=G\) und \(G_i\cap G_j\neq\emptyset\) für alle \(1\le i,j\le n\). Wenn nun ein Knoten \(V\in G_i,G_j\) mit \(i\neq j\) ist, dann existiert dort eine Überlappung zwischen zwei Communities.

Implementierung des Algorithmus

Eingabe: zufallsgenerierter gewichteter Graph \(g1\) Ausgabe: gewichteter Graph repräsentiert Struktur der Communitiy c Start: Initialisierung einiger Parameter Beliebigen Graph erzeugen for i=0;i< anzahlAnts; i++ do Erzeuge eine Ameise a Platziere Ameise in einem beliebigen Startknoten i end for i=0; i maxIterations;i++ do for each a Ameise do Ermittle den nächsten unbesuchten Nachbarknoten j Platziere Ameise in j basierend auf Wahrscheinlichkeit p_{ij} end end for each a Ameise do Aktualisiere Pheromone durch Erhöhung des Kantenlevels zwischen allen besuchten Knoten end Konstruiere neuen Graphen c Sortiere alle Kanten aus g1 in einer Liste basierend auf der Anzahl der Pheromone absteigend for each e Kante zwischen Knoten i und Knoten j aus Kantenliste do if i ist in Knoten v aus c enthalten und j nicht → füge j diesem Knoten v hinzu else if j ist in Knoten v aus c enthalten und i nicht → füge i diesem Knoten v hinzu else if i und j sind in verschiedenen Knoten aus c enthalten → füge neue Kante zwischen diese Knoten hinzu else if i und j sind in keinem Knoten aus c enthalten → füge neuen Knoten hinzu end return c

Anwendung des Algorithmus

In unserer Implementierung besitzen die Ameisen eine eigene Klasse. Dort werden die Attribute, für die Länge des Weges und für die von der Ameise auf ihrem Weg besuchten Knoten, realisiert durch ein Array, deklariert. Ameisen besitzen dabei eine Methode, um einen weiteren Knoten zu besuchen, dieser wird dann in dem Array für die besuchten Knoten aufgenommen. Zudem besitzen sie eine Methode, um den aktuellen Knoten auszugeben, an dem sie sich gerade befinden. Jeder Knoten besitzt eine eindeutige Bezeichnung, welche zur Identifikation dient, um ihn später den entsprechenden Communities zuzuordnen. Die Kanten sind mit Gewichten versehen, welche jeweils die Anzahl an Pheromonen speichern,die die Ameisen auf ihrem Weg hinterlassen. Zu Beginn wählt man zufällig einen Knoten \(V_i\) aus dem Netzwerk aus. Dieser repräsentiert das Ameisennest und dient als Startknoten. Nun beginnt der Ant-Colony Algorithmus, indem die erste Ameise in dem Startknoten \(V_i\) platziert wird. Diese wählt nun zufällig einen direkten Nachbarn von \(V_i\) aus, basierend auf der Wahrscheinlichkeit \(p_{ij}\). Diese Wahrscheinlichkeit wird dabei der Kante \(e_{ij}=(V_i,V_j)\) vom Knoten \(V_i\) zum Knoten \(V_j\) zugeordnet und ist definiert durch : \(p_{ij}=(\tau_{ij}^α ⋅η_{ij}^β)/(∑_{(k∈U)} τ_{ik}^α⋅η_{ik}^β ),j∈U\) und 0 für \(j∉U\). Die Menge U besteht dabei aus allen noch unbesuchten Nachbarn von Knoten \(V_i\). Dabei gibt \(\tau_{ij}\) die Menge der Pheromone auf dem Knoten \(V_j\) an und \(\eta_{ij}\) steht für die heuristische Information des Knoten \(V_j\) vom Knoten \(V_i\), definiert durch \(1/d_{ij}\) mit \(d_{ij}\) als Distanz von Knoten \(i\) zu Knoten \(j\). Der Parameter \(\alpha\) reguliert dabei den Einfluss von \(\tau_{ij}\), wobei der Parameter \(\beta\) den Einfluss von \(\eta_{ij}\) reguliert. Nachdem die Ameise nun den Knoten \(V_j\) ausgewählt hat, wird dieser in dem Array der besuchten Knoten gespeichert. Die Ameise bewegt sich nun zu diesem Knoten \(V_j\) und wiederholt den Vorgang bis alle Knoten besucht wurden. Auf ihrem Weg werden die Pheromone aktualisiert, sodass kürzere Pfade mehr Pheromone erhalten als länger Pfade. Die Formel für die Pheromonaktualisierung ist definiert durch : \(\tau_{ij}\ (t+1)=p\cdot\tau_{ij}\ (t)+\mathrm{\Delta\tau}_{ij}, \mathrm{\Delta\tau}_{ij}=\sum_{(k=1)}^l\ \mathrm{\Delta\tau}_{ij}^k\) und \(\mathrm{\Delta\tau}_{ij}^k=\frac{Q} { L_k}\) wenn Ameise k auf Kante (i,j) wandert, sonst \(\mathrm{\Delta\tau}_{ij}^k=0\). Dabei gibt \(L_k\) die Länge des Weges an und \(t\) die Anzahl der Iterationen. Der Parameter \(p\) steht für den Verdunstungsfaktor und reguliert somit die Reduktion der Pheromone. Die Differenz \(\mathrm{\Delta\tau}_{ij}\) bestimmt die totale Erhöhung des Weglevels auf der Kante \((V_i,V_j)\) durch alle Ameisen, wobei \(\mathrm{\Delta\tau}_{ij}^k\) nur für die Erhöhung des Weglevels auf der Kante \((V_i,V_j)\) durch eine Ameise \(k\) entsteht. Nachdem einige Iterationen des Ant-Colony Algorithmus aufgeführt wurden, beginnen wir mit der Konstruktion eines neuen Graph, welcher die Communities darstellt durch die einzelnen Knoten. Die Kanten zwischen zwei Knoten innerhalb des Graphen stehen für die Überlappungen. Die Konstruktion beginnt damit, dass die Kanten in dem alten Graphen anhand ihrer Anzahl an Pheromonen absteigend in einer Liste sortiert werden. Nun wird ein neuer Graph erstellt, indem die Liste der sortierten Kanten durchlaufen wird. Wenn keiner der Knoten, die durch die Kante verbunden sind, in einer Community enthalten ist, dann wird eine neue Community mit den beiden Knoten erstellt. Wenn nur einer der Knoten in einer Community enthalten ist, dann wird der andere Knoten auch dieser Gruppe zugeordnet. Wenn beide Knoten jeweils in zwei verschiedenen Communities enthalten sind, wird eine neue Kante erzeugt, die diese beiden Communities verbindet. Diese Verbindung kann als eine Überlappung interpretiert werden. Am Ende des Algorithmus wird der nach der Konstruktion entstandene Graph ausgegeben, welcher nun die Struktur des gesamten Netzwerkes repräsentiert.

Evaluierung der Resultate

In unserem Algorithmus haben wir die Parameter maxIteration=1000, p=0,5 als Verdunstungsfaktor und anzahlAnts für die Anzahl an Ameisen auf die Größe des Netzwerkes gesetzt, also auf die Kardinalität der Knotenmenge. Für die Anzahl der Knoten haben wir uns für drei verschiedene Datensätze zum Vergleich entschieden : 80 Knoten (kleiner Graph), 3000 Knoten (mittlerer Graph), 5000 Knoten (großer Graph).

Zusammenfassung

Zusammenfassend lässt sich sagen, das man mit dem Ant-Colony Algorithmus effektive Ergebnisse erzielt, um die Struktur von Communities in einem sozialen Netzwerk zu erkennen und auszuwerten. Dennoch benötigt dieser Algorithmus besonders auf großen Graphen eine längere Laufzeit und einen erhöhten Speicheraufwand, aufgrund der Nutzung vieler Datenstrukturen. Unser Fokus in der Implementierung des Algorithmus lag jedoch schwerpunktmäßig nicht auf der Optimierung und Effizienz, sondern vielmehr auf der Erkennung von Überlappungen zwischen Communities und deren Repräsentation in einem Graphen.

Referenzen

1. Noveiri, E., Naderan, M., & Alavi, S. E. (2015). Community detection in social networks using ant colony algorithm and fuzzy clustering. 2015 5th International Conference on Computer and Knowledge Engineering (ICCKE), 73–79.
2. Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.
3. https://de.wikipedia.org/wiki/Ameisenalgorithmus
4. https://moodle.rwth-aachen.de/pluginfile.php/915071/mod_resource/content/1/Mathmatische%20Grundlagen%20von%20OCD%20Algorithmen.pdf
5. https://www.youtube.com/watch?v=wfD5xlEcmuQ