Haider Abbas     Felix Voigtländer
RWTH Aachen University     RWTH Aachen University
haider.abbas@rwth-aachen.de     felix.oliver.voigtlaender@rwth-aachen.de

Abstract

Mit der zunehmenden Nutzung sozialer Medien während der Coronakrise und ihrem Einfluss auf das politische Spektrum ist das Auffinden sozialer Gemeinschaften wichtiger geworden. Auch das Einbringen von Medien und Werbung in die richtigen Communities, ohne die Nutzer in Gruppen zu entfremden, ist für soziale Netzwerke unabdingbar, um ihren Kunden ein angenehmes Erlebnis zu bieten und gleichzeitig ihren Umsatz zu steigern. Aufgrund der zunehmenden Komplexität von vorzeichenbehafteten Netzwerken und insbesonderer ihrer Größe sind effiziente Algorithmen vorteilhaft. In diesem Kapitel gehen wir auf erweiterte Overlaping Community Detection (OCD) Algorithmen für vorzeichenbehaftete Netzwerke ein und erklären die Vorteile der Änderungen im Vergleich zu den initiellen Algorithmen. Desweiteren veranschaulichen wir die unterschiedlichen OCD Algorithmen.

Keywords

OCDA, vorzeichenbehaftet, Netzwerke, Communities, Algorithmen, Kantengewichte


Inhaltsverzeichnis

  1. Einleitung
  2. Methodik
  3. OCD Algorithmen
  4. Erweiterte OCD Algorithmen
  5. Zusammenfassung und Ausblick
  6. Referenzen



Einleitung

Komplexe Systeme von der Natur oder soziale Netzwerke können als Graphen dargestellt werden, wie zum Beispiel können Personen als Knoten dargestellt werden und die Beziehungen zwischen den Personen, seien sie freundschaftlich oder feindselig, als Kanten zwischen den Knoten modeliert werden. Kanten können mit Gewichten versehen werden um die stärke der Bindung zwischen den verbundenen Knoten zu modelieren, ein größeres Gewicht könnte also eine starke Freundschaft bedeuten, während ein geringeres Gewicht jediglich eine Bekanntschaft bedeuten kann. Ungewichtete Graphen haben bei jeder Kante das Kantengewicht 1. Feindselige Beziehungen können als negative Kantengewichte interpertiert werden.

Hierbei entsteht die Interesse größere Graphen auf bestimmte Eigenschaften wie die Zugehörigkeit von Knoten zu einen oder mehreren Communities zu untersuchen. Communities sind Mengen an Knoten die untereinander dicht über Kanten, mit positivem Kantengewicht, verbunden sind, zum Beispiel ein Freundschaftskreis in welchem mehrere Personen in einer Gruppe untereinander befreundet sind. Generell gilt, dass in dichten Communities die Interaktion zwischen den Knoten erhöht ist und die Interaktion zwischen unterschiedlichen Communities gering ausfällt, zum Beispiel ist die Interaktion innerhalb eines Fussball Vereins erhöht, während die interaktion zwischen unterschiedlichen Teams vergleichsweise geringer ist.

Knoten können mehreren Communities angehören, zum Beispiel kann eine Person gleichzeitig einer Arbeitsgruppe, einem Freundschaftskreis und einem Sportverein angehören. Damit können mehrer Communities sich überschneiden. Um solche Überlappungen effektiv und effizient zu finden und zu erkennen werden sogennante “Overlapping Community Detection” Algorithmen (OCDA) angewendet, welche insbesondere bei großen Netzwerken an Bedeutung gewinnen. OCDA können zum Beispiel bei politischen Kampagnen verwendet werden.

OCDA behandeln Netzwerke mit ausschließlich ungewichtete Graphen mit positiven Kantengewichten. Dieses Kaptiel stellt verschiedene erweiterte OCDA vor, welche auch Netzwerke mit negativen und positiven Kantengewichten behandeln.



Methodik

In diesem Abschnitt werden die Methodiken erklärt, welche zur besseren Verständnis der unten erläuterten Algorithmen hilfreich sind. Graphen werden als \(G = (V,E,W)\) dargestellt, wobei \(V\) die Menge aller Knoten, \(E\) die Menge aller Kanten zwischen den Knoten und \(W\) die Gewichte aller Kanten sind. In Fig1. sieht man einen Graphen mit Kantengewichten.

Alt-Text (Chen et al., 2010) Fig1. Graph mit Kantengewichten

Adjazenz-Matrix

Die Kanten \(E\) eines Graphen können als eine Adjazenz-Matrix \(V \times V = A\) modelliert werden. Sind die Knoten \(v\), \(u\) nicht verbunden so ist \(A_{vu} = 0\). Sind die Knoten \(v\), \(u\) mit einander verbunden so gilt \(A_{vu} > 0\) oder \(A_{vu} < 0\). Folgend sieht man eine Adjazenz-Matrix für den Graphen, welcher in Fig1. gezeigt wird.

  1 2 3 4 5 6 7 8 9 10
1 0 0.7 0.7 0.3 0 0 0 0 0 0
2 0.7 0 0.5 0.5 0 0.5 0 0.2 0 0
3 0.7 0.5 0 0.2 0.6 0 0 0 0 0
4 0.3 0.5 0.2 0 0.4 0.2 0 0 0 0
5 0 0 0.6 0.4 0 0 0.6 0 0  
6 0 0.5   0.2 0 0 0 0.1 0.6 0
7 0 0 0 0 0.6 0 0.2 0.5 0.5  
8 0 0.2 0 0 0 0.2 0.2 0 0.3 0.4
9 0 0 0 0 0 0.6 0.5 0.3 0 0.6
10 0 0 0 0 0 0 0.5 0.4 0.6 0

Knotenstärke

Die Knotenstärke \(K_{v}\) für den Knoten \(v\) ist die Summe aller Kantengewichte welche mit dem Knoten \(v\) verbunden sind. Die Knotenstärke vom Knoten 3, welcher im Graphen in Fig1. zu sehen ist hat die Knotenstärke 1.4.

Alt-Text (Chen et al., 2010) Knotenstärke

Zugehörigkeitsgrad

Der Zugehörigkeitsgrad \(B(u,c)\) eines Knoten \(u\) zu einer Community \(c\), ist die Summe aller Kantengewichte vom Knoten \(u\) zur Community \(c\) geteilt durch die Knotenstärke \(K_{u}\) von Knoten \(u\).

Alt-Text (Chen et al., 2010) Zugehörigkeitsgrad

Modularität

Die Modularität einer eines Netzwerks ist eine Skala zur Messung der Partitionierung eines Netzwerkes, welche von Newman und Girvan (Newman, Mark E. J. & Girvan, 2004) vorgeschlagen wird. Die Modularität, welche vom Algorthmus welcher im folgenden Kapitel beschrieben wird wendet folgende abgewandelte Form zur Berechnung der Modulartät an:

Alt-Text (Chen et al., 2010) Modularität

\(m :=\) Anzahl der Kanten im Graphen

\(C :=\) Die Menge der Communities im Graphen

\(V :=\) Die Menge der Knoten im Graphen

\(k_{i} :=\) Die Knotenstärke von Knoten i

\(\alpha_{ci} :=\) Der Zugehörigkeitsgrad von Knoten i zur Community c

Die Breitensuche ist ein Algorithmus welcher alle zusammenhängende Knoten in einem Graphen findet. Dazu wird von einem gegebenen oder zufällig ausgewählten Knoten \(v\) im Graphen angefangen. Mit steigendem Grad werden die jeweiligen Nachbarn besucht und notiert. Sodass im ersten Schritt nur der Knoten \(v\) besucht wird, im darauf folgenden Schritt werden alle Nachbarn von \(v\) besucht, dannach die Nachbarn der Nachbarn vom Knoten \(v\) und so weiter bis alle zusammenhängende Knoten besucht wurden.

Alt-Text Quelle Breadth-First-Search-Algorithm



OCD Algorithmen

Overlapping Community Detection Algorithmen finden sich überschneidende Communities in Netzwerken mit positiven Kantengewichten durch die Benutzung von verschiedenen Konzepten und Formeln wie Modularität, lokalen und externen Strategien und diversen Matrizen etc.

Es haben sich schon zahlreiche Algorithmen in der Vergangenheit bewährt. Unter anderem der GN community structure algorithm, welcher 2004 von Newmann (Newman, Mark E. J., 2004) entwickelt wurde. Dieser Algorithmus basiert auf der Idee der Modularität und erstellt Communities anhand der bestmöglichen Modularität. Anstatt mühevoll Kanten wegzuschneiden und hinzuzufügen, berechnet der GN-Algorithmus durch wiederholte Bildung von Zweierpaaren Communities, sodass die Modularität maximiert wird in konstanter Schrittzeit und mit einer Gesamtlaufzeit von \(O(n^{2})\).

Chen et al. (Chen et al., 2009) haben im Jahre 2008 einen robusten Algorithmus konzipiert, welcher auf durchschnittlich großen Netzwerken schnell funktioniert. Dieser Algorithmus identifiziert den Knoten mit der größten Knotenstärke, baut mit diesem Knoten eine lokale Community, bis alle benachbarten Knoten eine schwache Verbindung zu den Knoten dieser Community haben. Schließlich wird diese Community aus dem Netzwerk entfernt. Diese Schritte werden rekursiv wiederholt, bis das gesamte Netzwerk in Communities unterteilt ist.

Der Algorithmus von Duch und Arenas (Duch & Arenas, 2005) benutzt ebenfalls den Begriff der Modularität und versucht, diese im Netzwerk zu maximieren. Jedoch werden die Communities nicht lokal aufgebaut wie beim GN-Algorithmus, sondern wird der Graph extern in Teile unterteilt, bis die Modularität einen bestimmten Schwellenwert erreicht hat. Dieser Algorithmus eignet sich bestens bei größeren Netzwerken, im Vergleich zu lokal arbeitenden Algorithmen.

Im folgenden Kapitel werden erweiterte OCD Algorithmen anhand von zwei Beispielen vorgestellt.



Erweiterte OCD Algorithmen

Ein Großteil an OCD Algorithmen schafft es, effektiv und schnell überlappende Communities in Netzwerken zu finden. Jedoch ist das Interesse an Algorithmen, welche ebenfalls auf vorzeichenbehafteten Graphen funktionieren, mit der Zeit gewachsen. Im folgenden Kapitel werden erweiterte OCD Algorithmen eingeführt und anhand von zwei Beispielen erklärt.


Detecting overlapping communities of weighted networks via a local algorithm

Dieser Algorithmus findet überschneidende Communities in gewichteten Netzwerken durch einen Lokalen Algorithmus (Chen et al., 2010). Dieser wird durch zwei Schritte ausgeführt, im ersten Schritt wird eine partielle Community gefunden welche im zweiten Schritt erweitert wird.

1. Schritt: Findung der Initial Community

  1. Die Knotenstärke aller Knoten im Graphen werden berechnet und jeder Knoten wird mit \(F\) gekennzeichnet.
  2. Der Knoten mit der größten Knotenstärke und dessen Nachbarn mit der kennzeichnung \(F\) werden ausgewählt und zur Community \(c\) hinzugefügt. In der Fig2. hat der Knoten 2 die höchste Knotenstärke, somit wird der Knoten 2 und seine Nachbarn \({1,3,5,6,8}\) ausgewählt.

Alt-Text (Chen et al., 2010) Fig2. Schritt 1.2

  1. Jeder Knoten der Community mit Zugehörigkeitsgrad weniger als \(0.5\) wird aus der Community wieder entfernt, da dieser nicht eng genug in der Community ist. In der Fig3. hat der Knoten 8 einen zu niedrigen Zugehörigkeitsgrad und wird daher aus der initial Community entfernt.

Alt-Text (Chen et al., 2010) Fig3. Schritt 1.3

  1. Schritt 3. wird so oft wiederholt, bis jeder Knoten in der Community einen Zugehörigkeitsgrad größer als \(0.5\) hat.

2. Schritt: Erweiterung der Community

  1. Für jeden Nachbarn u unserer Community \(c\) wird der Zugehörigkeitsgrad \(B(u,c)\) berechnet.
  2. Jeder Knoten u mit \(B(u,c) > 0.5\) wird zur Menge \(N_{u}\) hinzugefügt und jeder Knoten mit \(0.4 <= B(u,c) <= 0.5\) wird zur Menge \(N_{lu}\) hinzugefügt.
  3. Ist die Menge \(N_{u}\) leer gehe zum nächsten Schritt, sonst wird jeder Knoten aus \(N_{u}\) zur Community \(c\) hinzugefügt und bei Schritt 1. wird fortgesetzt.
  4. Ist die Menge \(N_{lu}\) leer gehe zum nächsten Schritt, sonst füge einen Knoten \(u\) von \(N_{lu}\) zur Community \(c\) hinzu. Erhöht sich die Modularität gehe zu Schritt 1. sonst wiederhole diesen Schritt.
  5. Sind die Mengen \(N_{u}\) und \(N_{lu}\) leer, markiere jeden Knoten \(v\) in der Community \(c\) mit \(T\).

Alt-Text (Chen et al., 2010) Fig4. Schritt 2

Schritt 1. und Schritt 2. werden solange wiederholt, bis alle Knoten mit \(T\) gekennzeichnet sind. Anhand diesen Algorithmus werden überlappende Communities gefunden, damit erhält man zu jedem Knoten die jeweilge Zugehörigkeit zu Communities. In Fig5. sind die gefundenen Communities aufgeführt, Knoten 10 hatte bei der zweiten initial Community die größte Knotenstärke und Knoten 6 ist in beiden Communities vorhanden.

Alt-Text (Chen et al., 2010) Fig5. Final

Fazit

Der beschriebene Algorithmus hat eine Worst-Case Laufzeitkomplexität von \(O(n^{3})\) bei \(n\) Knoten, wobei generell eine Laufzeitkomplexität von \(O(n^{2})\) bei \(n\) Knoten besteht. Der Algorithmus wurde an sieben Real-Welt Netzwerken und einem Synthetischen Netzwerk angewendet und so evaluiert, die Ergebnisse beschreiben einen effektiven und insbesondere effizienten Algorithmus zur Findung von überlappenden Communities bei Netzwerken mit Kantengewichten.


Community Mining in Signed Social Networks – An Automated Approach

Der Clustering Reclustering Algorithmus (CRA) findet in Netzwerken mit positiven und negativen Kanten überschneidende Communities innerhalb von zwei Phasen (Sharma et al., n.d.). In der ersten Phase wird mit Hilfe einer abgewandelten Version der Breitensuche, wobei negative Kanten ignoriert werden, Knotenbündel (engl. Cluster) gefunden. Mit den gefundenen Knotenbündeln werden in der zweiten Phase die Bündel um weitere Knoten ergänzt.

Vorbereitung

Alle Knoten vom gegebenen Graphen haben folgende Eigenschaften:

  1. VC ist der VisitCounter, hier wird die Anzahl der Besuche der Knoten durch die Breitensuche mitgezählt
  2. AV ist die Anzahl aller Kanten zum gegebenen Knoten
  3. NCV ist die Anzahl der Kanten zu anderen Knoten, welche sich nicht im selben Knotenbündel befinden
  4. CV ist die Anzahl der Kanten zu anderen Knoten, welche sich im selben Knotenbündel befinden
  5. MPC ist das Knotenbündel zu dem der Knoten am ehesten gehört

Phase 1: Breitensuche

Der Algorithmus startet von einem gegebenen oder zufällig gewählten Knoten \(v\) und die Breitensuche wird von \(v\) aus gestartet. Beim Besuchen der benachbarten Knoten wird \(VC\) der Nachbarn erhöht und beim besuchen weiterer Knoten wird \(VC\) ebenfalls erhöht. Wird ein Knoten mit \(VC >= 2\) gefunden signalisiert dies, dass der Knoten Teil eines Knotenbündels ist. Gibt es einen Nachbarn mit ebenfalls \(VC>=2\) wird der Knoten zum Knotenbündel des Nachbars hinzugefügt, sonst wird ein neues Knotenbündel gegründet und der Knoten und dessen Nachbarn werden hinzugefügt. Schließlich erhält man alle Knotenbündel.

Phase 2: Knotenbündel Ergänzung

Mit Hilfe des Graphen mit den gefundenen Knotenbündeln und negativen Kanten werden die Knoten neu zugeordenet. Dazu wird für jeden Knoten der Wert VP zu jedem Knotenbündel berechnet:

VP = Anzahl der positiven Kanten zu Knoten im selben Knotenbündel / Anzahl aller Kanten zu Knoten im selben Knotenbündel

Dabei liegt der Wert \(VP\) zwischen \(0\) und \(1\), liegt der Wert bei \(0\) hat der Knoten nur negative Kanten zu Knoten im Knotenbündel, liegt der Wert bei \(1\) hat der Knoten nur positive Kanten zu Knoten im Knotenbündel. Beim druchlaufen der Knoten werden die Knoten dem Knotenbündel zugeordnet, in dem VP am größten ist. Zum Beispiel tritt man einer Gruppe mit fünf Freunden eher zu als einer Gruppe mit drei Feinden und zwei Freunden.

Schließlich erhält man alle Communities im gegebenen Graphen.

Fazit

CRA ist ein simpler und stabiler Algorithmus, der keine externen Parameter benötigt im vergleich zu anderen Algorithmen zur Findung von Communities in positiv und negativ gewichteten Netzwerken. Ein weiterer Vorteil von diesem Algorithmus ist, dass bei sich änderenden Netzwerken mit neuen Knoten der Algorithmus im Gegensatz zu anderen Algorithmen nicht neu berechnet werden muss, und so nur die neuen Knoten hinzugefügt werden müssen.



Zusammenfassung und Ausblick

Die behandelten erweiterten OCD Algorithmen erlauben die Analyse von komplexeren Netzwerken im Gegensatz zu einfachen OCD Algorithmen. Dieses Kapitel hat die Methodik von zwei erweiterten OCD Algorithmen erläutert Detecting overlapping communities of weighted networks via a local algorithm und Community Mining in Signed Social Networks – An Automated Approach. Der erste Algorithmus erlaubt die Analyse von Netzwerken mit gewichteten Kanten und unterteilt sich dabei in zwei Phasen, in der ersten Phase bildet der Algorithmus eine initiale Partielle Community von dem Knoten mit der größten Knotenstärke und in der zweiten Phase wird die initiale Community erweitert. Dieser Algorithmus hat generell eine Laufzeitkomplexität von \(O(n^{2})\) und im Worst-Case eine Laufzeitkomplexität von \(O(n^{3})\), desweiteren ist die Untersuchung von Netzwerken mit gewichteten Graphen möglich. Im zweiten Algorithmus werden Netzwerke mit positiven und negativen Kanten behandelt, dieser Algorithmus wird ebenfalls in zwei Phasen unterteilt, in der ersten Phase werden durch Breitensuche verschiedene Knotenbündel erzeugt welche in der zweiten Phase durch verbesserte Zugehörigkeit der Knoten verfeinert werden. Dadurch dass diese Arbeit noch in Arbeit ist wurde der Algorithmus noch nicht formalisiert und hat daher keine Laufzeitkomplexität angegeben. Erweitertete OCD Algorithmen erlauben die Analyse von komplexeren Netzwerke, durch verbesserte effizienz und effektivität.



Referenzen

  1. Chen, D., Shang, M., Lv, Z., & Fu, Y. (2010). Detecting overlapping communities of weighted networks via a local algorithm. Physica A: Statistical Mechanics and Its Applications, 389(19), 4177–4187.
  2. Newman, Mark E. J., & Girvan, M. (2004). Finding and Evaluating Community Structure in Networks. Physical Review, 69(026113).
  3. Newman, Mark E. J. (2004). Fast algorithm for detecting community structure in networks. PHYSICAL REVIEW E, 69(6), 066133. https://doi.org/10.1103/PhysRevE.69.066133
  4. Chen, D., Fu, Y., & Shang, M. (2009). A fast and efficient heuristic algorithm for detecting community structures in complex networks. Physica A: Statistical Mechanics and Its Applications, 388(13), 2741–2749.
  5. Duch, J., & Arenas, A. (2005). Community detection in complex networks using extremal optimization. Physical Review E, 72(2), 027104.
  6. Sharma, T., Charls, A., & Singh, P. K. Community Mining in Signed Social Networks - An Automated Approach. 2009 International Conference on Computer Engineering and Applications, 2, 152–157. http://www.ipcsit.com/vol2/28-A217.pdf