Ziming Suo     Yunjia Chen     Wei Wei
RWTH Aachen University     RWTH Aachen University     RWTH Aachen University
ziming.suo@rwth-aachen.de     yunjia.chen@rwth-aachen.de     wei.wei1@rwth-aachen.de


Abstract

Heute sind immer mehr Menschen in sozialen Netzwerken aktiv. Nutzer erhalten täglich eine große Anzahl von Tweets von verschiedenen Plattformen mit Inhalten, die für sie von Interesse sein könnten, oder mit Vorschlägen für andere Nutzer, die sie aufgrund der Informationen, die sie im Internet hinterlassen haben, kennen könnten. Diese Tweets sind jedoch nicht immer korrekt, da es an Präzision bei der Extraktion der Informationen mangelt und einige Informationen während des Speichervorgangs verloren gehen. In diesem Artikel wird kurz erläutert, warum diese Situation entsteht, und wie sie verbessert werden kann, wird das Hauptthema dieses Artikels sein.


Keywords

OCDA, Datenformat, Datenspeicherung, Adjazenzmatrix, Matrix-Rekonstruktionsverfahren


Inhaltsverzeichnis

  1. Einleitung
  2. Verwandte Arbeiten
  3. Methodik
  4. Anwendung
  5. Zusammenfassung

    Referenzen



1.Einleitung

Graphen sind eine wichtige Datendarstellung für komplexe Netzwerke und kommen in einer Vielzahl von realen Szenarien vor. Eine effektive Diagrammanalyse ermöglicht es Entwicklern, ein tieferes Verständnis dafür zu erlangen, was sich hinter den Daten verbirgt, was bei der Entwicklung vieler Anwendungen genutzt werden kann. Ein wichtiger Ansatz für die Graphenanalyse ist die Grapheneinbettung(Cai HongYun et al., 2018), bei der die Graphdaten in einen niedrigdimensionalen Raum transformiert werden, in dem die Informationen über die Graphenstruktur und die Eigenschaften des Graphen möglichst gut erhalten bleiben. Das Deep Learning-Modell ist ein weit verbreitetes Modell für die Einbettung von Graphen. Bei diesem Modell werden die im Graphen enthaltenen Daten normalerweise in Form einer Adjazenzmatrix strukturiert. Es gibt jedoch ein Problem, das sich bei der Verwendung von Adjazenzmatrizen nicht vermeiden lässt: Die räumliche Nachbarschaftsinformation in der Adjazenzmatrix ist unzureichend.

Der Mangel an räumlichen Nachbarschaftsinformationen wird durch die Methode des Clusterns diskreter Daten verursacht. Bei der traditionellen Methode werden die Anfangspunkte nach dem Zufallsprinzip ausgewählt. Anschließend werden Nachbarn ausgewählt, die die “Eigenschaften” der Anfangspunkte erfüllen, der Prozess wird rekursiv abgeschlossen und schließlich erhält man die geclusterten Daten. Das Problem bei diesem Ansatz ist jedoch, dass das Gesamtergebnis des Clusterns erheblich beeinträchtigt werden kann, wenn sich die Anfangspunkte an extremen Positionen befinden, z. B. an den “Rändern” eines diskreten Datensatzes. Es ist daher notwendig, den Datensatz vor der Bearbeitung zu “initialisieren”, d.h. die Adjazenzmatrix zu rekonstruieren.(Han et al., 2012)( Buch: Data Mining:Concepts and Techniques(Second Edition), Jiawei Han, Micheline Kamber) )


Die Deep-Community-Erkennungsmethode, die in diesem Beitrag untersucht wird, ist eines der Deep-Learning-Modelle. Im Vergleich zu anderen Deep-Learning-Methoden kann uns diese Methode dabei helfen, qualitativ hochwertige Gemeinschaften in sozialen Netzwerken zu erkennen und die räumliche Nähe der Matrix zu optimieren, d.h. den Mangel an räumlicher Nachbarschaftsinformation der oben erwähnten Adjazenzmatrix zu optimieren. Zu den Methoden zur Erkennung von Gemeinschaften gehören (1) Methoden zur Matrix-Rekonstruktion (2) Methoden zur Extraktion räumlicher Merkmale (3) Methoden zur Erkennung von Clustern.(Wu et al., 2020) Unter ihnen steht die Methode der Matrix-Rekonstruktion im Mittelpunkt dieses Artikels.



2.Verwandte Arbeiten

Was ist eigentlich Matrix-Rekonstruktion?

Da die ursprüngliche Reihenfolge der Knoten in der Adjazenzmatrix unsinnig ist, wird die Methode zur Matrix-Rekonstruktion verwendet, um die Reihenfolge der Knoten in der Adjazenzmatrix so anzupassen, dass die Nachbarknoten mit hoher Korrelation angeordnet werden können. Daher können einige räumliche Merkmale zwischen den Knoten nach der Rekonstruktion der Adjazenzmatrix formatiert werden, um räumliche Merkmale zu extrahieren und eine soziale Gemeinschaft zu erkennen. Die vorgeschlagene Methode zur Rekonstruktion der Matrix besteht aus drei Schritten, nämlich (1) Methode zur Wahl des Meinungsführers, (2) Methode zur Auswahl von Nachbarknoten und (3) Methode zur Rekonstruktion, die in den folgenden Abschnitten beschrieben werden.



3.Methodik

Verzeichnis

(0) [Einführung]: Adjazenzmatrix
(1) Methode zur Wahl des Meinungsführers
(2) Methode zur Auswahl von Nachbarknoten
(3) Methode zur Rekonstruktion



(0) Adjazenzmatrix

In diesem Paper wird eine Adjazenzmatrix \(A\) anhand der Kanten zwischen jeweils zwei Knoten erstellt.

Der Parameter \(V\) (d.h. {\(v_1\) , \(v_2\) ,\(\ldots\), \(v_n\) }) \(:=\) Knotenmenge.
Der Parameter \(E\) \(:=\) für eine Kantenmenge.

Wenn die Kante zwischen dem Knoten \(v_i\) und dem Knoten \(v_j\) existiert, ist der Wert von \(a_i,j\) 1; andernfalls ist der Wert von \(a_i,j\) 0 (siehe Gleichung (1)).

\[\mathbf { A}=\left[ { { {\begin{array} {cccccccccccccccccccc} {a_{1,1} } &\quad {a_{1,2} } &\quad \cdots &\quad {a_{1,n} } \\ {a_{2,1} } &\quad {a_{2,2} } &\quad \cdots &\quad {a_{2,n} } \\ \vdots &\quad \vdots &\quad \ddots &\quad \vdots \\ {a_{n,1}} &\quad {a_{n,2} } &\quad \cdots &\quad {a_{n,n} } \\ \end{array} } } }\right] \tag{1}\]

wobei

\[a_{i,j} = \begin{cases} 1, e_{i,j} \in E \\[3pt] 0, e_{i,j} \notin E \\[3pt] \end{cases}\]



(1) Methode zur Wahl des Meinungsführers

Der Meinungsführer ist ein wichtiger Knoten in einer Adjazenzmatrix, der kann die Einstellungen der anderen Mitglieder beeinflussen. In praktischen sozialen Netzwerken können mehrere Mitglieder einem Meinungsführer in einer Gemeinschaft folgen und mit ihm befreundet sein.

Daher analysiert die vorgeschlagene Methode zur Wahl des Meinungsführers den Einfluss jedes Knotens, um den wichtigsten Knoten (d.h. den einflussreichsten Meinungsführer) in der Adjazenzmatrix als Anfangsknoten für die Matrixrekonstruktion zu finden.

Eine Übergangswahrscheinlichkeitsmatrix \(C\) (siehe Gleichung (2)) kann entsprechend der Adjazenzmatrix \(A\) erstellt werden:

①Wenn ein Knoten mit mehreren Knoten verbunden ist, ist das Gewicht jeder Kante niedriger;
②wenn ein Knoten mit weniger Knoten verbunden ist, ist das Gewicht jeder Kante höher.

Beispielsweise wenn der Knoten \(v_i\) nur mit dem Knoten \(v_j\) verbunden ist, ist der Knoten \(v_j\) ein wichtiger Knoten für den Knoten \(v_i\), und die Übergangswahrscheinlichkeit \(c_{i,j}\) ist 1.

\[\mathbf { C}=\left[ { { {\begin{array} {cccccccccccccccccccc} {c_{1,1} } &\quad {c_{1,2} } &\quad \cdots &\quad {c_{1,n} } \\ {c_{2,1} } &\quad {c_{2,2} } &\quad \cdots &\quad {c_{2,n} } \\ \vdots &\quad \vdots &\quad \ddots &\quad \vdots \\ {c_{n,1}} &\quad {c_{n,2} } &\quad \cdots &\quad {c_{n,n} } \\ \end{array} } } }\right] \tag{2}\]

wobei

\[c_{i,j} = \frac {a_{i,j} } {\sum \limits_{k=1}^{n} {a_{i,k}} }\]

In der Anfangsphase ist das Gewicht jedes Knotens 1, und eine Knotengewichtsmatrix \(S\) wird in Gleichung (3) konstruiert. Die begrenzende Gewichtsmatrix \(S^∗\) wird auf der Grundlage der Übergangswahrscheinlichkeitsmatrix \(C\) berechnet (siehe Gleichung (4)). Schließlich wird der Knoten \(i_{leader}\) mit dem höchsten Gewicht (d.h. der Meinungsführer) gemäß Gleichung (5) gefunden:



\(\mathbf { S}=\left [{ { {\begin{array}{cccccccccccccccccccc} {s_{1} } \quad {s_{2}} \quad {\ldots } \quad {s_{n} } \\[3pt] \end{array} } } }\right] \tag{3}\)

wobei

\[s_{i}=1{~\textrm {in der Anfangsphase}}\]



\[\mathbf {S}^{\ast} = \lim \limits_{m\to \infty } \mathbf { S}\times \mathbf { C}^{m} \tag{4}\] \[= \lim \limits_{m\to \infty } \left[{ { {\begin{array}{cccccccccccccccccccc} {s_{1}} \quad {s_{2}} \quad \cdots \quad {s_{n}} \\[3pt] \end{array} } } }\right] \times \left [{ { {\begin{array}{cccccccccccccccccccc} {c_{1,1}} \quad {c_{1,2}} \quad \cdots \quad {c_{1,n}} \\[3pt] {c_{2,1}} \quad {c_{2,2}} \quad \cdots \quad {c_{2,n}} \\[3pt] \vdots \quad \vdots \quad \ddots \quad \vdots \\[3pt] {c_{n,1}} \quad {c_{n,2}} \quad \cdots \quad {c_{n,n}} \\[3pt] \end{array} } } } \right]^{m} \\[3pt]\] \[=\left[{ { {\begin{array}{cccccccccccccccccccc} {s_{1}^{\ast } } {s_{2}^{\ast } } \cdots {s_{n} ^{\ast } } \\[3pt] \end{array} } } } \right]\]



\[i\_{}leader = \mathop {\arg \max } \limits_{1\le i\le n} s_{i}^\ast. \tag{5}\]



Die Pseudocodes der vorgeschlagenen Meinungsführer-Wahlmethode sind in Algorithmus 1 dargestellt.

Algorithm 1: Methode zur Wahl des Meinungsführers

an adjacency matrix An×n with n nodes and the number of iterations Imax

the node ID of opinion leader

Construct the adjacency matrix An×n .

for i=1 to n

    for j=1 to n

        Determine the weight of edge from node vi to node vj based on the amount of connections of node vi .

    end for

end for


for i=1 to n

    Set the weight of node vi in the initial stage as 1.

end for


while (the number of iterations is less thanImax )

    for i=1 to n

        Set the weight of node vi in the next iteration as 0.

        for j=1 to n

            Calculate the weight of node vj multiplied by the weight edge from node vj to node vi as the value of temp.

            Set the weight of node vi in the next iteration plus the value of temp.

        end for

    end for

end while

Return the ID of the node with a highest weight.



(2) Methode zur Auswahl von Nachbarknoten

Nach der Ermittlung des Meinungsführers (d.h. des Knotens \(i_{leader}\)) wird eine Methode zur Auswahl der Nachbarknoten vorgeschlagen, um den Nachbarknoten \(j_{neighbor}\) zu finden, der für den Knoten \(i_{leader}\) am relevantesten ist.

Der Knoten \(i_{leader}\) wird als Knoten \(v_i\) dargestellt, und ein euklidischer Abstand \(r(i , j )\) wird angewendet, um den Abstand zwischen Knoten \(v_i\) und Knoten \(v_j\) auf der Grundlage von Gleichung (6) zu messen. Der Knoten \(j_{neighbor}\) mit dem kürzesten Abstand (d.h. der nächste Nachbar) wird gemäß Gleichung (7) gefunden.

\[r\left ({ {i,j} }\right)=\sqrt {\sum \limits _{k=1}^{n} {d\left ({ {i,j,k} }\right)^{2}}}, \textrm {wobei}~d\left ({ {i,j,k} }\right)=a_{i,k} -a_{j,k}. \tag{6}\]



\[j\_{}neighbor=\mathop {\arg \min }\limits _{1\le j\le n} r\left ({ {i,j} }\right),~\textrm {wobei}~j\ne i.\tag{7}\]



(3) Methode zur Rekonstruktion

Die Rekonstruktion ist in Wirklichkeit eine zusätzliche Behandlung der Reihenfolge der Knoten in der Adjazenzmatrix \(A\).

Basierend auf den vorgeschlagenen Methoden (1) und (2) könnten jeweils der Meinungsführer-Knoten bzw. Nachbarknoten bestimmt werden.



\[\mathbf { X}=\left[ { { {\begin{array} {cccccccccccccccccccc} {x_{1,1} } &\quad {x_{1,2} } &\quad \cdots &\quad {x_{1,n} } \\ {x_{2,1} } &\quad {x_{2,2} } &\quad \cdots &\quad {x_{2,n} } \\ \vdots &\quad \vdots &\quad \ddots &\quad \vdots \\ {x_{n,1}} &\quad {x_{n,2} } &\quad \cdots &\quad {x_{n,n} } \\ \end{array} } } }\right] \tag{8}\]

wobei

\[x_{i,j} = \begin{cases} 1, e_{i,j} \in E \\[3pt] 0, e_{i,j} \notin E \\[3pt] \end{cases}\]



Die Adjazenzmatrix \(A\) kann durch Algorithmus 2 als Matrix \(X\) rekonstruiert werden.

Algorithm 2 Methode zur Rekonstruktion
an adjacency matrix An×n with n nodes

the reconstructed adjacency matrix Xn×n

Construct the adjacency matrix An×n .

Create the list Ln .

Create the list On .


for i=1 to n

    Push node vi into the list Ln .

end for


Set the node i_leader from the opinion leader election method as node vi .


while(the length of the list Ln is larger than 0)

    Pull node vi from the list Ln .

    for j=1 to n

        Calculate the Euclidean distance between node vi and node vj .

    end for


    Find and Set node j_neighbor from the neighbor node selection method as node vi .

    Push node vi into the list On .


end while


Construct the adjacency matrix Xn×n according to the list On .

Return the reconstructed adjacency matrix Xn×n .



4.Anwendung

Im Rahmen der Studie wurden offene Datensätze von vier existierenden, realen sozialen Netzwerken verwendet, um mit Methoden der Deep Community Detection zu experimentieren und diese zu bewerten.

4.1 Experimentelle Umgebungen

4.1.1 Datensätze

Für die Bewertung der vorgeschlagenen Methode wurden vier offene Datensätze praktischer sozialer Netzwerke gesammelt, darunter (1) Netzwerk19, (2) Karate, (3) Delphine und (4) Fußball. Tabelle 1 zeigt die Beschreibung der Datensätze.

Alt-TextDatensätze von praktischen sozialen Netzwerken.

4.2 Rekonstruktion der Matrix

Das vorgeschlagene Verfahren zur Rekonstruktion der Matrix umfasst drei Schritte: (1) Auffinden des Meinungsführers in einem sozialen Netzwerk, (2) Auffinden von Nachbarknoten und (3) Rekonstruktion der Adjazenzmatrix des sozialen Netzwerks. Die rekonstruierte Adjazenzmatrix des tatsächlichen sozialen Netzwerks im offenen Datensatz sind in den folgenden Abbildungen dargestellt.

Alt-TextDie Methode der Matrixrekonstruktion für “network19”.

Für die Analyse des “network19”-Datensatzes zeigt Abbildung 4.2.1(a) die ursprüngliche Adjazenzmatrix und Abbildung 4.2.1(b) die rekonstruierte Adjazenzmatrix. Der siebte Knoten in der ursprünglichen Adjazenzmatrix wurde als Meinungsführer ausgewählt. Einige Gemeinschaften in der ursprünglichen Adjazenzmatrix hatten überlappende Grenzen und extrem verstreute Knoten, was zu einem hohen Grad an Hashing führte, was die weitere Verarbeitung nicht erleichterte. Nach der Umsetzung der vorgeschlagenen Matrixrekonstruktionsmethode liegen die Knoten in derselben Gemeinschaft näher beieinander, und die Grenzen der Gemeinschaften sind in der rekonstruierten Nachbarschaftsmatrix besser erkennbar.

Alt-TextDie Methode der Matrixrekonstruktion für “Karate”.

Für die Analyse des Datensatzes “Karate” zeigt Abbildung 4.2.2(a) die ursprüngliche Adjazenzmatrix, und Abbildung 4.2.2(b) zeigt die rekonstruierte Adjazenzmatrix. Der 34. Knoten in der ursprünglichen Adjazenzmatrix wurde als Meinungsführer ausgewählt. Ähnlich wie bei der ursprünglichen Adjazenzmatrix des vorherigen Datensatzes waren die Grenzen der Gemeinschaften in der ursprünglichen Adjazenzmatrix des Karate-Datensatzes schwer zu erkennen. Die rekonstruierte Adjazenzmatrix hat deutlichere Grenzen, aber der Vorteil gegenüber den rekonstruierten Ergebnissen des vorherigen Datensatzes ist nicht offensichtlich, und obwohl die rekonstruierte Adjazenzmatrix in diesem Fall eine kleine Verbesserung für die Identifizierung von Gemeinschaften darstellt, gibt es weniger isolierte Punkte in der rekonstruierten Adjazenzmatrix.

Alt-TextDie Methode der Matrixrekonstruktion für “Delphine”.

Für die Analysen des Datensatzes “Delphine” zeigt Abbildung 4.2.3(a) die ursprüngliche Adjazenzmatrix, und Abbildung 4.2.3(b) zeigt die rekonstruierte Adjazenzmatrix. Der 15. Knoten in der ursprünglichen Adjazenzmatrix wird als Meinungsführer gewählt. Die Kanten in der ursprünglichen Adjazenzmatrix waren verstreut und machten es schwierig, soziale Gemeinschaften zu identifizieren. Nach der Implementierung der vorgeschlagenen Matrixrekonstruktionsmethode mit einer größeren Datenmenge als die beiden vorherigen Datensätze weist die rekonstruierte Matrix klarere Grenzen und eine geringere Anzahl isolierter Knoten auf, so dass die Vorteile deutlicher hervortreten.

Alt-TextDie Methode der Matrixrekonstruktion für “Fußball”.

Für die Analyse des Datensatzes “Fußball” zeigt Abbildung 4.2.4(a) die ursprüngliche Adjazenzmatrix, und Abbildung 4.2.4(b) zeigt die rekonstruierte Adjazenzmatrix. Der 2-te Knoten in der ursprünglichen Adjazenzmatrix wird als Meinungsführer gewählt. Die räumliche Netzwerkstruktur der Gemeinschaften in der ursprünglichen Nachbarschaftsmatrix war aufgrund der schieren Größe und Streuung der Daten im Vergleich zum vorherigen Datensatz schwieriger zu erkennen. Es ist jedoch anzumerken, dass dieser Datensatz eher den Merkmalen der sich schnell entwickelnden Gemeinschaftsnetze von heute entspricht. Nach der Anwendung der vorgeschlagenen Matrixrekonstruktionsmethode sind die Grenzen der 12 Gemeinschaften in der rekonstruierten Nachbarschaftsmatrix klarer und leichter zu erkennen. Im Internet gibt es unter anderem auch Datensätze der ersten deutschen Bundesliga und der Fußballweltmeisterschaft, die zum Testen verwendet werden könnten, da sie vom gleichen Typ sind und sich nur in der Datenmenge unterscheiden, weshalb sie nicht erneut getestet werden.



5.Zusammenfassung

In dieser Arbeit wird eine Matrix-Rekonstruktion der gespeicherten Datenstruktur verwendet, um die Optimierung der Datenspeicherung und ihrer Typen zu vervollständigen und die Datenspeicherungsbasis des Gemeinschaftsnetzes aufzubauen, was die anschließende Datenanalyse des Projekts erheblich erleichtert. Die Methode wurde an vier offenen Datensätzen getestet und implementiert, und die Richtung der Datenanalyse des Gemeinschaftsnetzes wurde detaillierter geplant. Das Projektteam konnte auf der Grundlage der Stärken und Schwächen der Rekonfigurationsmatrix bessere Modelle zum Testen der verschiedenen Datensätze erstellen und die verräumlichten diskreten Daten mit Hilfe der neuen Modelle analysieren. Da die Datenüberwachung dynamischer Gemeinschaften zu potenziell dynamischen Beziehungen zwischen einzelnen Knoten führt, muss die Datenanalysefunktion in der weiteren Entwicklung des Projekts mit der Datenspeicherfunktion verschmolzen werden, wobei Zeitreihenmodelle zur Extraktion von Merkmalen beliebiger sozialer Netzwerke verwendet werden.



Referenzen

  1. Cai HongYun, Zheng Vincent W., & Chang Kevin Chen-Chuan. (2018). A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications. IEEE Transactions on Knowledge and Data Engineering, 30(9), 1616–1637. https://doi.org/10.1109/TKDE.2018.2807452
  2. Han, J., Kamber, M., & Pei, J. (2012). Data mining: Concepts and techniques / Jiawei Han, Micheline Kamber, Jian Pei (3rd ed.). Morgan Kaufmann and Oxford : Elsevier Science.
  3. Wu, L., Zhang, Q., Chen, C.-H., Guo, K., & Wang, D. (2020). Deep Learning Techniques for Community Detection in Social Networks. IEEE Access, 8, 96016–96026. https://doi.org/10.1109/ACCESS.2020.2996001