Youssef Mansour	Anastasiya Valoshyna
RWTH Aachen University	RWTH Aachen University
youssef.mansour@rwth-aachen.de	anastasiya.valoshyna@rwth-aachen.de

Abstrakt

Es ist kein Wunder, dass die Funktionalität von sozialen Netzwerken auf jeden Fall die Privatdaten von Benutzern erfordert. Genau das gibt den sozialen Netzwerken die Eigenschafften, die bei allen beliebt sind, und gleichzeitig steigert die Sorgen von Benutzern um ihre Privatsphäre. Es ist nicht grundlos, Netzwerke sind auch mangelhaft und können von Angreifern stark verletzt werden, wobei die Privatdaten anfällig werden. Aus diesem Grund ist das Thema von Robustheit der sozialen Netzwerke besonders zu beachten. In diesem Kapitel erläutern wir die Funktionsweise von einigen Algorithmen, die uns helfen werden erfolgreich die Effizienz von OCDAs zu erniedrigen um Gemeinschaften vor möglichen Angreifern zu schützen. Anschließend gehen wir auf die Verstärkung der Robustheit von Netzwerken ein.

Keywords

Attack, CDA, DBA, SCDA, LPA, LCC, Robustheit

Inhaltsverzeichnis

1. Einleitung
2. Verwandte Arbeiten
3. Methodik
   - Heuristiken
   - Label Propagaion Algorithm
   
4. Gemeinschaftstarnung
   - Community Detection Attack
   
5. Verteidigung gegen Angreifer
   - Similarity-based Community Detection Algorithm
   - Similarity Berechnung
   - Funktionsweise von SCDA
   
6. Zusammenfassung/Ausblick
7. Referenzen

Einleitung

In der Graphentheorie ist die Gemeinschaftsfindung eines der meistbesprochenen Themen, und es gibt bereits viele Methoden und Algorithmen, um so effizient wie möglich Gemeinschaften in einem Netzwerk finden zu können. Der Begriff “Angriff” hat hierbei mehrere Bedeutungen. Nach einer kann man auf einem OCDA angreifen, um dessen Effizienz zu erniedrigen. Dies macht man mit dem Ziel die genaue Struktur von komplexen Netzwerken zu sabotieren, um Communities zu verstecken. Diese Effizienz von OCDAs bringt nämlich einige Probleme mit sich. Vor allem sind soziale Netzwerke, wo wir täglich mit anderen Leuten auf verschiedenen Weisen kommunizieren, Goldminen für Drittmitgliedern, um private Informationen zu stehlen. Mit diesen Angriffen auf OCDAs können wir die Effizienz der Algorithmen erniedrigen, und eine “Gemeinschaftstarnung” erzielen, wobei es für Drittmitglieder in bestimmten Communities erschweren.

Nach anderer Bedeutung kann ein “Angriff” auch von der Seite der Eindringlinge passieren. Ein Angreifer kann irgendeine Entität sein, die unerwünscht in bestimmten Communities eindringt, indem sie mit anderen Angreifern, sich mit echten Mitgliedern der Gemeinschaft bindet. Dies kann im Kontext sozialen Netzwerken zum Beispiel durch den Spam von Freundschaftsanfragen unter Nachrichten geschehen. Wir werden in dieser Arbeit einen Community Detection Algorithm vorstellen, der basierend auf verschiedenen Ähnlichkeitsmetriken Gemeinschaften findet, und Angreifer aus bereits angegriffenen Netzwerken entfernt.

Wenn man über Angriffe spricht, denkt man auf jeden Fall auch über Robustheit. Unter Robustheit versteht man die Fähigkeit von Netzwerken, die beschreibt, zu welcher Maß Netze die Ausfälle oder die Angriffe auf einige ihre Teile widerstehen können. Die Robustheit soll vor allem die Möglichkeit geben, die Netzwerke miteinander zu vergleichen und die Auswirkungen von lokalisierten Änderungen im System zu bewerten. Aus diesem Grund werden die Methoden dargestellt, die Robustheit von Netzwerken zu messen. Aber allein zu wissen, wie man die Robustheit von einem Netzwerk misst, hilft nicht bösartige Angriffe zu widerstehen. Aus dem Grund werden in diesem Kapitel auch die Methoden erläutert, wie man die Robustheit erhöhen kann.

Verwandte Arbeiten

In dieser Arbeit orientieren wir uns hauptsächlich um die Arbeiten von (Jiang et al., 2020) für den SCDA Algorithmus, und (Chen et al., 2019) für den CDA Algorithmus. Bei der Erläuterung der Möglichkeiten Robustheit zu messen, haben wir als Grundlage (Liu et al., 2017) genommen. Außerdem für den Vergleich der Methoden zur Erhöhung der Robustheit wurden die Daten hauptsächlich aus (Yang et al., 2015) und (Carchiolo et al., 2019) benutzt.

Methodik

In dieser Arbeit setzen wir uns hauptsächlich mit drei Unterthemen von Angriffen auf soziale Netzwerke auseinander. Dazu stellen wir einen Algorithmus zur Gemeinschaftstarnung sowie einen Algorithmus zum Schutz gegen Angreifer vor. Für diese Algorithmen wurde zum Anschaulichen der Label Propagation Algorithmus benutzt, der ebenfalls kurz vorgestellt wird. Anschließend wird erläutert, wie man die Robustheit eines Netzwerks messen kann und welche Wege es gibt, ein Netzwerk robuster zu machen.

Heuristiken

Angriffe auf Community Detection Algorithmen sowie der Schutz vor Angreifern auf ein Netzwerk, basieren auf die Modifikation der Netzwerke selbst. Dazu gehören unter anderem die von (Holme et al., 2002) vorgestellten Strategien, ID removal, IB removal, RD removal und RB removal. Diese Strategien enthalten das Entfernen von Knoten oder Kanten Wenn man bei einem Attack Knoten entfernt, kann man die Größe des Largest Connected Component (LCC) (Bellingeri et al., 2014) für die Einschätzung der Effizienz benutzen. Der LCC stellt den größten Sub-Graphen im Netzwerk dar. Dabei ist wichtig zu wissen, ob es sich um einen real-world Graphen handelt. Es wurde beschrieben, dass die Effizienz einer Strategie umso höher ist, je schneller die große des Graphen abfällt. Wir werden uns jedoch nicht mit dem Entfernen von Knoten selbst beschäftigen, sondern die Entfernung und Änderung von Kanten, was die Prämisse unserer Algorithmen darstellt.

Label Propagaion Algorithm

Der Label Propagation Algorithmus (Raghavan et al., 2007) ist der OCD, den wir für die Beispiele benutzen werden. Wir geben zum besseren Verständnis eine kurze Beschreibung von LPA. Es werden als erstes die Knoten mit bestimmten Community Labels initialisiert, die im Verlauf des OCDs in dem Netzwerk propagieren. Bei jeder Iteration wird der Label jedes Knotens zu dem am meist auftretenden Label der Nachbarknoten geändert. Dies wird gemacht, bis jeder Knoten zum dem meist auftretenden Label der Nachbarknoten hat (oder falls die vorgegebene Anzahl an Iterationen erreicht wurde). Knoten mit demselben Label gehören zu einer Community.

Gemeinschaftstarnung

Community Detection Attack

Nun beschreiben wir den Community Detection Attack (CDA) von (Chen et al., 2019). Unser Ziel ist es den benutzten OCDA so zu erweitern, sodass dessen Effizienz erniedrigt wird, und die gefundenen Communities nicht ganz zutreffen. Dies erzielt CDA mit Hilfe von rewiring Attacks, die auf beliebige Knoten N durchgeführt werden können. Die Anzahl an Iterationen bezeichnen wir als i. Sei der Knoten \(N_{1}\) der zufällig ausgewählte Knoten, dann entfernen wir eine zufällig ausgewählte Kante \(K_{I}\) zu einem Knoten der Menge \(IC_{n}\),und fügen eine zufällig ausgewählte Kante \(K_{N1}\) zu einem Knoten in \(NC_{n}\). Somit versichern wir, dass alle Knoten ihren Grad behalten. Die erkannten Communities ändern sich aber, von der Form oder Anzahl her. Je nachdem wie wir i wählen ändert sich die Effizienz des OCD.

In dem Kontext soziale Netzwerke bedeutet dies, dass wir zu einer Person zum Beispiel einen falschen Freund hinzufügen, und einen echten Freund entfernen (oder ausblenden). Somit behält die Person offensichtlich dieselbe Anzahl an Freunden, und es werden nicht zu viele Modifikationen zum gesamten Netzwerk gemacht.

An unserem Beispielgraphen haben wir LPA benutzt, und haben hauptsächlich 2 Communities gefunden. In der ersten Interation wird der Knoten “5” aus der ersten Community \(C_1\) ausgewählt. Mögliche Knoten, mit denen die Verbindung gelöscht werden können \(IC_5\) = (1,2,12). Intracommunity nonneighbors sind \(NC_5\) = (6,10,11,14,8,9). Wir löschen zufällig die Kante mit dem Knoten “12” und fügen eine Kante mit dem Knoten “8” hinzu.

Wir führen nun eine zweite Iteration des Algorithmus auf den Knoten “4” durch:

Man kann erkennen, dass die originale Struktur des Graphen nicht mehr ganz erkennbar ist. Bei unserem Beispielgraphen wird bei der Verwendung von LPA zwar immer noch 2 Communities erkannt, aber manche Knoten wurden zu der anderen Community eingeteilt. Somit haben wir die Communnity Struktur erfolgreich geändert. Um die Effizienz unseres Algorithmus zu steigern, kann noch die Hierarchie in Betracht genommen werden. Wir führen hierbei den CDA Algorithmus auf die Knoten mit dem höchsten Grad aus. Das Modifizieren der Nachbarn von “wichtigen” Knoten, kann die Gemeinschaftsstruktur rapide ändern.

Verteidigung gegen Angreifer

Similarity-based Community Detection Algorithm (SCDA)

Nun betrachten wir den SCDA Algorithmus von (Jiang et al., 2020) Wir behalten im Hinterkopf, dass wir effizient Communities finden, und gleichzeitig unsere Angreifer ausschließen wollen. Da unser Algorithmus auf die Similarity der Knoten basiert, geben wir jedem Knotenpaar einen charakteristischen Wert \(score_{uv}\), der die Similarity zweier benachbarter Knoten u und v auszeichnet. Wir nehmen an, dass ein Angreifer sich mit der Wahrscheinlichkeit p zu einem Knoten bindet. Die Schwelle \(\tau\) gibt uns die Möglichkeit zu bestimmen, ab welcher Ähnlichkeit die Verbindung zwischen den Knoten behalten werden, wie streng unser Algorithmus sein soll. Somit bestimmt \(\tau\) zugleich wie weit wir in der Hierarchie des Graphen eingehen.

Similarity Berechnung

Zur Bestimmung der Similarity gibt es einige Eigenschaften, die wir nutzen können (Lorrain & White, 1971). Wir werden hauptsächlich strukturbasierte Eigenschaften betrachten. Diese Eigenschaften beinhalten (gemeinsame) Nachbarn \(\delta(u)\), sowie der Grad g des Knotens. Hier sind einige Similarity Metriken gegeben:

Similarity Metriken

CA: \(score_{uv} = |\delta(u) \cap \delta(v)|\) In dieser Formel wird die Äquivalenz zweier Knoten als Metrik genommen, wobei die score genau die Anzahl der gemeinsamen Nachbarn beträgt. CN wird von uns als Metrik für das Beispiel genommen.

Funktionsweise von SCDA

Nachdem wir einen OCDA auf unseren Graphen laufengelassen haben, und Communities gefunden haben, werden die Angreifer (je nach OCDA) zu einer Community eingeteilt. Wir konstruieren aus diesem Graphen einen neuen Graphen, indem wir für jedes Knotenpaar die jeweilige \(score_{uv}\) ausrechnen, und genau die Kanten zwischen den Knoten mit \(score_{uv} \geq \tau\) in unseren neuen Graphen einfügen. Somit enthält unser neuer Graph genau die Kanten, deren Knoten über der Schwelle \(\tau\) stehen. Da die Mitglieder innerhalb einer Community allgemein gemeinsame Nachbarn haben, besitzen sie eine hohe \(score_{uv}\). Nach der Ausführung von SCDA, werden die entsprechenden Kanten nicht entfernt, wobei Kanten mit Intra-Community Knoten entfernt werden. Alle Subgraphen in den neuen Graphen bilden Communities.

Im obigen Beispiel haben wir in dem Karate Graphen [Zachary] zufällig 3 Angreifer (A1, A2, A3) eingefügt. Wir benutzen die CN Similarity Metrik, um SCDA auszuführen. Dazu wählen wir \(\tau = 2\) es werden also alle Kanten behalten, die eine \(score_{uv} \geq 2\). Mit CN bezeichnet dies also die Anzahl an gemeinsamen Nachbarn. Und so sieht unser Graph nach der Ausführung von SCDA aus:

Es wurden mit \(\tau=2\) erfolgreich alle Angreifer aus den Communities ausgeschlossen. Ein Nachteil des Algorithmus ist es, dass nicht-Angreifer einer Community aus ihren Communities ausgeschlossen werden. Auch die Metrik CD gilt als eine sehr strenge, ineffiziente Metrik zur Similarity Berechnung. Außerdem wurden die 2 großen Gemeinschaften des Karate Graph ganz voneinander getrennt und somit von unserem SCDA Algorithmus nicht gefunden, da der Knoten “9” leider \(\geq 2\) gemeinsame Nachbarn mit dem Knoten “3” hatte. Wir haben das jedoch zur Anschaulichkeit mit dem LPA visualisiert. Mit RA als Metrik wurde auf den Karate Graphen aber eine effizientere Ausgabe gebracht (Jiang et al., 2020). Es wurden nämlich mit dieser Metrik die Angreifer ausgeschlossen, die 2 Communities wurden getrennt ausgegeben und es wurden viel weniger nicht-Angreifer im Graphen behalten.

Robustheit

In diesem Teil des Kapitels wird das Thema “Robustheit” erläutert. Wie schon in der Anleitung erwähnt wurde, die Robustheit ist die Eigenschaft eines Netzwerks, auch unter ungünstigen Bedingungen noch zuverlässig zu funktionieren. Für uns ist es wichtig vergleichen zu können, welches Netzwerk stabiler ist. Dafür müssen wir wissen, wie man die Robustheit misst. Aus diesem Grund werden wir jetzt verschiedene Robustheitsmasse darstellen.

Robustheitsmaße

1. Die Netzwerkmetriken als die Robustheitsmaße

1.1 Auf den Gemeinschaften basierte Maße
Viele Netzwerke, die reale Systeme repräsentieren, bestehen aus Gemeinschaften von Individuen, innerhalb denen die Interaktion viel stärker ist als die Interaktion zwischen den verschiedenen Gemeinschaften. Aus diesem Grund werden vier Robustheitsmaße dargestellt, die auf den Gemeinschaften in dem Netzwerk basieren.

• Durchschnittlicher Abstand zwischen allen Knoten in einer Gemeinschaft (ADB)
  Es ist zu erwarten, dass in einem robusten Netzwerk kurze Pfade zwischen mehr Knoten existieren, im Vergleich zu einem weniger robusten Netzwerk. Also je kleiner ADB ist, desto robuster ist das Netzwerk.
• Durchschnittlicher Clustering-Koeffizient (ACC)
  Dieses Maß kann nur die Bewertung von der Robustheit innerhalb der Gemeinschaft geben, wobei die Interaktion zwischen den Gemeinschaften ignoriert wird. Der ACC ist definiert als
  \(C_i= \frac{2N_i}{k_i (k_i-1) }\)
  d.h., die Anzahl der Kanten \(N_i\) (in einem Community-Subgraphen) wird durch die maximal mögliche Anzahl von Kanten (wenn alle \(k_i\)-Knoten in dieser Community miteinander verbunden wären) geteilt (Barabâsi et al., 2002).
• Durchschnittliche Gemeinschaftsgröße (ACS)
  Es ist erwartet, dass größere Gemeinschaften stabiler sind, denn kleine werden mit höherer Wahrscheinlichkeit uneffektiv, wenn auch nur eine kleine Anzahl von Kanten oder Knoten gelöscht wird.
• Durchschnittlicher Grad innerhalb der Gemeinschaften (ADC)
  Der Grund dafür ist ähnlich wie bei ACS.

1.2 Auf den Knoten basierte Maße
Bei der Bewertung der Robustheit achtet man auch darauf, wie nachhaltig die einzelnen Knoten bei den Änderungen in dem ganzen Netz sind. Hier sind drei Maße dargestellt, die auf den Knoten basieren:

• Degree Centrality (DC)
  Es bewertet die Anzahl der Knoten, die mit einem gewählten Knoten verbunden sind. Dabei wird der Knoten als robust bezeichnet, falls er hohe DC besitzt. Der Grund dafür ist, dass die große Anzahl von Verbindungen den Knoten lässt, mit weniger Wahrscheinlichkeit vom Netzwerk getrennt zu sein.
• Closeness Centrality (CC)
  Es ist ein Kehrwert der Summe der Längen aller kürzesten Pfaden von einem gewählten Knoten zu allen anderen Knoten im Graph. Es ist zu erwarten, wenn CC von einem Knoten hoch ist, dass seine Robustheit auch hoch ist.
• PageRank (PR)
  Das Prinzip ist, dass jeder Knoten ein Gewicht (PageRank) besitzt, das umso größer ist, je mehr Knoten (mit möglichst hohem eigenem Gewicht) auf diese Knoten verweisen. Da die wichtigen Knoten auch robust sein müssen, haben die robuste Knoten hohes PR.

1.3 Auf dem Zusammenhang basierte Maße
Im Jahr 1979 wurde die Robustheit eines Netzwerks mittels des Grundkonzepts der Graphenzusammenhang analysiert (Frank, 1970). Hier werden nun zwei darauf basierende Robustheitsmaße dargestellt:

• Kantenzusammenhang (\(v(G)\))
  Das ist die minimale Anzahl von Kanten, die aus einem zusammenhängenden Graphen entfernt werden müssen, um ihn zu trennen. Der Kantenzusammenhang ist wie folgt definiert
  \(v(G) =\min \limits_{s,t \neq s \in V } \{ v_{s-t}(G)\}\).
  Dabei ist t vs−t(G) die Anzahl der Kanten, die entfernt werden müssen, um die Knoten s und t zu trennen. Es folgt, dass je höher der Kantenzusammenhang ist, desto robuster ist das Netz.
• Knotenzusammenhang (\(w(G)\))
  Es ist, ähnlich den Kantenzusammenhang, die Anzahl von Knoten, die aus einem zusammenhängenden Graphen entfernt werden müssen, um ihn zu trennen. Und wie bei dem Kantenzusammenhang ist erwartet, dass je höher Knotenzusammenhang eines Graphen ist, desto höher ist die Robustheit eines Netzes.

2. Neue Robustheitsmaße

2.1 Basiertes auf dem Zufallsgraphtheorie Maß
Aus der Sicht von Zufallsgraphtheorie wurde im Jahr 2000 ein einfaches und effektives Maß der strukturellen Robustheit vorgeschlagen (Albert; Jeong; Barabási, 2000). Es geht um den kritischen Entfernungsanteil (critical removal fraction) von Knoten (Kanten) für den Zerfall von Netzwerken. Der Zerfall von Netzwerken wird über die Netzwerkleistung gemessen. Zu den häufigsten Leistungsmaße gehören der Durchmesser, die Größe der größten Komponente, die durchschnittliche Pfadlänge und die Kommunikationseffizienz. Hier wird der kritische Entfernungsanteil für zufällige Angriffe vorgestellt. Der kritische Entfernungsanteil (\(p_c^r\)) wird laut (Liu et al., 2017) für eine beliebige Gradverteilung (\(P(k)\)) berechnet als
\(p_c^r=1-\frac{1}{(k_0-1)}\),
wobei \(κ_0\) gleich \(⟨k^2 ⟩⁄⟨k⟩\) ist, \(⟨k⟩\) der durchschnittliche Knotengrad des ursprünglichen Netzwerks ist, und \(⟨k^2⟩\) der Durchschnitt des Quadrats des Knotengrades ist. Je größer der Wert von prc ist, desto robuster ist das Netzwerk. Wenn die Gradverteilung und jeder Knotengrad unveränderlich sind, dann ist \(κ_0\) unveränderlich.

2.2 Robustheitsmaß R
Da das Maß der strukturellen Robustheit den kritischen Anteil von Angriffen bewertet, bei denen das Netz komplett zerfällt, ignoriert es außerdem Situationen, in denen das Netzwerk große Schaden erleidet, ohne vollständig zerstört zu sein. Darauf wurde in 2010 hingewiesen und ein neues einzigartiges Robustheitsmaß \(R\) vorgeschlagen (Schneider et al., 2011), das wie folgt definiert ist
\(R= \frac{1}{N} \sum_{Q=1}^{N} s(Q)\) ,
wobei \(s(Q)\) der Anteil der Knoten der größten Zusammenhangskomponente nach Entfernen von \(Q\) Knoten ist. Der Normierungsfaktor \(\frac{1}{N}\) stellt sicher, dass die Robustheit von Netzwerken mit unterschiedlichen Größen verglichen werden kann. Je größer der Wert von \(R\) ist, desto robuster ist das Netzwerk. Damit man die Angriffe an Kanten auch berücksichtigen kann, wurde \(R\) wie folgt erweitert
\(R_l= \frac{1}{M} \sum_{P=1}^{M} s(P)\),
wobei \(s(P)\) der Anteil der Knoten in der größten Zusammenhangskomponente nach Entfernen von \(P\) Kanten ist. Der Normierungsfaktor \(\frac{1}{M}\) stellt außerdem sicher, dass die Robustheit von Netzwerken mit unterschiedlichen Größen verglichen werden kann. Je größer der Wert von \(R_l\) ist, desto robuster ist das Netzwerk.

2.3 Integraler Effizienz des Netzwerks (integral efficiency of network)
VHP Louzada und andere (Liu et al., 2017) achteten auf die Kommunikationeffizienz von Netzwerken nach jedem Angriff und schlugen ein neues Robusheitsmaß, und zwar integraler Effizienz des Netzwerks (\(IntE\)), der wie folgt definiert ist
\(IntE= \frac{1}{N} \sum_{Q=1}^{N} E(Q)\),
wobei \(E(Q)\) die Kommunikationseffizienz von Netzwerken nach Entfernen von \(Q\) Knoten ist. Der Normierungsfaktor \(\frac{1}{N}\) stellt wie früher sicher, dass die Robustheit von Netzwerken mit unterschiedlichen Größen verglichen werden kann. Je größer der Wert von \(IntE\) ist, desto robuster ist das Netzwerk.

Sensibilität der Robustheitsmaße

Die wichtigste Aufgabe eines Robustheitsmaßes ist die Fähigkeit, auf die Änderungen in dem Netzwerk empfindlich zu reagieren, um die Netzwerkrobustheit richtig bewerten zu können. In (Liu et al., 2017) wurden einige von hier dargestellten Robustheitsmaße verglichen, und zwar \(v(G)\), \(w(G)\), \(p_c^r\), \(R\), \(R_l\), \(IntE\), wobei zahlreiche Experimente durchgeführt wurden. Die Ergebnisse zeigen, dass \(υ(G)\) und \(ω(G)\) die Änderungen fast nicht widerspiegeln und die anderen Maße die Änderungen in unterschiedlichem Ausmaß zeigen können. Hier ist zu beachten, dass \(υ(G)\) und \(ω(G)\) die Netzwerkmetriken sind. Daraus kann man erwarten, dass die Netzwerkmetriken den neuen Robustheitsmaßen deutlich nachstehen. Aus der Forschung folgt auch, dass das Robustheitsmaß soll abhängig von vielen Faktoren z.B. Art der Änderungen im Netzwerk gewählt werden. Die am meisten verwendete Robustheitsmaß ist aber \(R\), aus diesem Grund wird im folgendem in diesem Kapitel dieses Robustheitsmaß benutzt.

Erhöhung der Robustheit

Jetzt wissen wir, wie man die Robustheit von einem Netzwerk messen kann. Und dann kommen wir zu einem praktischen Teil des Themas, und zwar wie man ein Netzwerk robuster machen kann.

1. Standartmethoden

Am Anfang werden kurz einige Strategien zur Erhöhung der Robustheit vorgestellt, die auf der Erstellung neuer Links basieren (Carchiolo et al., 2019).

• Zufallsbasiert (R):
  Eine der am häufigsten verwendeten Strategien fügt einfach neue Verbindungen zwischen zufällig ausgewählten, unverbundenen Knotenpaaren. Natürlich ist die Zeitkomplexität dieser Strategie sehr gering \((O(1))\).
• Gradbasiert:
  Eine weitere Klasse von Strategien, die eine bevorzugte Verbindung zwischen Knoten in Abhängigkeit von ihrem Grad verwendet. Z. B. High-Degree-Strategie (HK) verbindet die Knoten mit dem höchsten Grad. Die Zeitkomplexität dieser Strategie hängt von dem Sortieralgorithmus ab, der verwendet wird, um die Knoten in der Reihenfolge des Grades zu sortieren, daher nehmen wir an, dass sie \(O(NlogN)\) beträgt, wobei N die Anzahl der Knoten im Netzwerk ist.
• Betweenness-basiert:
  Ähnlich wie bei der Grad-Strategie wird versucht, die Knoten mit der gleichen Betweenness (z.B. the lowest betweenness (LB)) zu verbinden. Die Betweenness eines Knoten ist ein Zentralitätsmaß, das als die Anzahl der kürzesten Pfade definiert ist, die durch eine Kante in einem Graphen oder Netzwerk gehen (Newman, 2004). Die Zeitkomplexität ist polynomial wegen der Betweenness-Berechnung und der Sortierung der Knoten nach ihrem Wert, so dass sie \(O(NM + NlogN)\) beträgt, wobei M die Anzahl der Verbindungen im Netzwerk ist.

2. Neue Methode

Es ist zu erwähnen, dass die oben genannte Methoden, nicht nur auf die Robustheit eines Netzwerks einwirken, sondern auch die Gradverteilung und Gemeinschaftsstruktur ändern. Die Gradverteilung erfasst eindeutig eine Menge von Informationen über ein Netzwerk, die wichtige Angaben über die Struktur eines Netzwerks geben. Die Gemeinschaftsstruktur kann die Information darüber geben, wie sich Netzwerkfunktion und Topologie eines Graphen gegenseitig beeinflussen. Aus diesen Gründen kann man feststellen, dass für reale Netzwerke sinnvoll ist, bei der Erhöhung von Robustheit Neukonfiguration eines Netzwerks möglichst zu minimieren. Also, wird unten 3-Schritt-Strategie zur Erhöhung der Robustheit unter Beibehaltung der Gemeinschaftsstruktur des Netzwerks (Yang et al., 2015) dargestellt.
Um die Robustheit von Netzwerken zu erhöhen, ohne die Gemeinschaftsstruktur stark zu verändern und die Gradverteilung eines Netzwerks zu behalten, wurde folgende Methode vorgeschlagen. Die Hauptidee ist, dass man die interne Struktur jeder Gemeinschaft in eine zwiebelartige Struktur umwandelt und verschiedene Gemeinschaften durch die Knoten mit niedriger Wichtigkeit verbindet. Die Wichtigkeit der Knoten wird durch die Zentralitätsmaße (in diesem Fall Grad-Zentralität) bestimmt. Der Algorithmus sieht folgendermaßen aus:

1. Jede Gemeinschaft soll eine zwiebelartige Struktur haben, d. h., die Kanten werden solcherart verschoben, dass die Knoten mit gleicher Wichtigkeit miteinander verbunden werden.
2. Die Kanten sollen vertauscht werden so, dass die Knoten mit hoher Wichtigkeit nur mit den Knoten in der gleichen Gemeinschaft verbunden sind.
3. (optionaler Schritt) Man soll die Kanten nochmal vertauschen, um die Anzahl der Kanten zwischen den Gemeinschaften zu erhöhen.

3. Vergleich der Methoden

Um alle vier oben genannten Methoden zu vergleichen, wurden die zu den Netzwerken angewendet, die das Barabási–Albert Model (Albert; Jeong; Barabási, 2000) entsprechen, und es wird gezeigt, wie die Robustheit der optimierten Netzwerke bei den bösartigen Angriffen ändert. Für die Standartmethoden wurde angenommen, dass bei ihren Anwendung 50 Kanten hinzugefügt werden. Dafür wurde recalculated degree attack (RD) gewählt, d.h., vor jedem Entfernungsschritt werden die Graden aller Knoten berechnet und nur den mit dem höchsten Grad entfernt. Die Daten wurden aus (Yang et al., 2015) und (Carchiolo et al., 2019) genommen und in ein Kurvendiagramm zusammengefasst.

Das Diagramm zeigt, dass insgesamt alle drei Standartmethode ähnliches Verhalten haben. Sie zeigen gute Ergebnisse im Zwischenraum [0.08,0,16], bei dem größeren Anteil der entfernten Knoten sinkt die Robustheit bei diesen Methoden rasant, bei dem Anteil größer 0.19 ist die Robustheit sogar niedriger als die bei dem originalen Netzwerk. Die Robustheit des Netzes, das bei der 3-Schritt-Strategie optimiert wurde, hat zwar niedrigere Ergebnisse als bei den Standardmethoden im Zwischenraum [0.08,0,19], ist um 48,6% robuster als das originale Netz. Es ist auch auf jedem Fall zu beachten, dass bei der Anwendung von der 3-Schritt-Strategie werden etwa 90% Prozent Knoten beibehalten.

Zusammenfassung

Wir haben angezeigt, dass es durch verschiedene Methoden möglich ist, ein Netzwerk robuster, und sicherer gegen Angreifer zu machen. Es gibt vor allem bestimmte Metriken und Maße, die benutzt werden können, um zu bestimmen, wie streng das Netzwerk gegen Angreifer geschützt werden soll. Dabei muss man aber anpassen, dass selbst nicht-Angreifer aus Communities nicht ausgeschlossen werden. Was das Verstecken von Communities angeht haben wir herausgestellt, dass es durch “rewiring attacks” möglich ist, die generelle Struktur eines Netzwerks zu ändern, sodass die Effizienz von OCDAs erniedrigt wird.
Bei der Erforschung von Robustheit eines Netzwerks haben wir gezeigt, dass es eine große Menge von Robustheitsmaßen gibt. Aus diesem Grund muss man sehr aufmerksam sein, da die Genauigkeit der Ergebnisse sehr stark davon abhängt, ob die passende Maße gewählt wurde. Außerdem haben wir aufgeklärt, dass bei der Erhöhung der Robustheit die Struktur eines Netzes verletzt werden kann, was schlimm auf die Funktionalität des Systems beeinflusst.

Referenzen

1. Jiang, Z., Li, J., Ma, J., & Yu, P. S. (2020). Similarity-based and Sybil Attack Defended Community Detection for Social Networks. IEEE Transactions on Circuits and Systems II: Express Briefs, 1. https://doi.org/10.1109/TCSII.2020.3001182
2. Chen, J., Chen, L., Chen, Y., Zhao, M., Yu, S., Xuan, Q., & Yang, X. (2019). GA-Based Q-Attack on Community Detection. IEEE Transactions on Computational Social Systems, 6(3), 491–503. https://doi.org/10.1109/TCSS.2019.2912801
3. Liu, J., Zhou, M., Wang, S., & Liu, P. (2017). A comparative study of network robustness measures. Front. Comput. Sci. (Frontiers of Computer Science), 4. https://doi.org/10.1007/s11704-016-6108-z
4. Yang, Y., Li, Z., Chen, Y., Zhang, X., & Wang, S. (2015). Improving the Robustness of Complex Networks with Preserving Community Structure. PLOS ONE (PLOS ONE), 2. https://doi.org/10.1371/journal.pone.0116551
5. Carchiolo, V., Grassia, M., Longheu, A., Malgeri, M., & Mangioni, G. (2019). Network robustness improvement via long-range links. Computational Social Networks, 1. https://doi.org/10.1186/s40649-019-0073-2
6. Holme, P., Kim, B. J., Yoon, C. N., & Han, S. K. (2002). Attack vulnerability of complex networks. Physical Review E, 65(5), 056109.
7. Bellingeri, M., Cassi, D., & Vincenzi, S. (2014). Efficiency of attack strategies on complex model and real-world networks. Physica A: Statistical Mechanics and Its Applications, 414, 174–180. https://doi.org/https://doi.org/10.1016/j.physa.2014.06.079
8. Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.
9. Lorrain, F., & White, H. C. (1971). Structural equivalence of individuals in social networks. The Journal of Mathematical Sociology, 1(1), 49–80. https://doi.org/10.1080/0022250X.1971.9989788
10. Barabâsi, A.-L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., & Vicsek, T. (2002). Evolution of the social network of scientific collaborations. 590–614. https://doi.org/10.1016/S0378-4371(02)00736-7
11. Frank, I., H.; Frisch. (1970). Analysis and Design of Survivable Networks. IEEE Trans. Commun. (IEEE Transactions on Communications), 5, 501–519. https://doi.org/10.1109/TCOM.1970.1090419
12. Albert; Jeong; Barabási, A.-L. (2000). Error and attack tolerance of complex networks. Nature, 6794, 378–382. https://doi.org/10.1038/35019019
13. Schneider, C. M., Moreira, A. A., Andrade, J. S., Havlin, S., & Herrmann, H. J. (2011). Mitigation of malicious attacks on networks. Proceedings of the National Academy of Sciences, 10, 3838–3841. https://doi.org/10.1073/pnas.1009440108
14. Newman, M., M. E. J.; Girvan. (2004). Finding and evaluating community structure in networks. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 2. https://doi.org/10.1103/PhysRevE.69.026113