Vorhersagen von Social Media-Verbindungen: Verwenden von Übergangspunkten

    Aktuelle Forschungen auf dem Gebiet der prädiktiven Netzwerkmodellierung verwenden verschiedene Metriken, die Indikatoren für die Bildung von Verbindungen zwischen Agenten sind. Sie ignorieren jedoch die Verteilung des Prozesses der Entstehung neuer Verbindungen im Netzwerk.
    In diesem Artikel werde ich anhand des Flickr-Netzwerks erläutern , wie Änderungspunkte zum Lösen des Problems der Linkvorhersage angewendet werden .



    Übergangspunkte: Theorie und Praxis


    In der Statistik werden also die Punkte genannt, an denen sich die Verteilung einer bestimmten Menge ändert. In Bezug auf soziale Netzwerke ist einer der Prozesse, in denen Übergangspunkte bestimmt werden können, der Prozess der Entstehung neuer Verbindungen in einem dynamischen Netzwerk. Um diese Punkte zu identifizieren, können Sie eine der folgenden Messwerte verwenden: die Dichte des Graphen , die durchschnittliche Between zentrale oder mittlere Nähe Zentralität .

    Erläutern wir kurz das Wesentliche dieser drei Metriken. Beginnen wir mit der einfachsten Grafikdichte . Wenn sich zu einem bestimmten Zeitpunkt die Dynamik der Graphendichte stark ändert, ist dies wahrscheinlich auf eine zeitabhängige Änderung der Verteilung der Anzahl neuer Bindungen zurückzuführen.
    Wenn wir über Zentralitätsmetriken sprechen, ist die Zwischenzentralität ein Maß dafür, wie oft die kürzesten Wege durch einen bestimmten Scheitelpunkt verlaufen, und die Nähezentralität ein Maß dafür, wie schnell Sie von einem bestimmten Scheitelpunkt des Diagramms zu allen anderen gelangen können.

    In einem Artikel von McCulloh, Matthew Webb und John Graham über „Aufdeckung von Veränderungen in sozialen Netzwerken“ wurde über mehrere Jahre eine Studie über das internationale Al-Qaida-Terrornetzwerk (Verbindungen zwischen Gruppenmitgliedern) durchgeführt. Die folgende Abbildung zeigt die Eigenschaften des Netzwerks zu verschiedenen Zeitpunkten.



    Offensichtlich wird sich die Verteilung nach 2001 voraussichtlich ändern. Dies wird empirisch bestätigt, da Al-Qaida nach dem Terroranschlag vom 11. September 2001 unter die strikte Kontrolle der weltweiten Sonderdienste geriet und die Aktivitäten der Organisation behindert wurden (gleichzeitig verlangsamte sich das Wachstum der Anzahl der Verbindungen zwischen den Netzwerkteilnehmern erheblich). Wir erhalten, dass die oben genannten Metriken theoretisch zur Identifizierung von Übergangspunkten in sozialen Netzwerken geeignet sind.

    Flickr Network Experiment


    Versuchen wir, die Dynamik der Verbindungen im Flickr-Netzwerk vorherzusagen. Als Metriken wählen wir den Jacquard-Koeffizienten (Nachbarschaftsmethode), die Summe der lokalen Cluster-Koeffizienten (eine Metrik, die auf den Eigenschaften von Eckpunkten basiert), die Werte der drei Hauptmaße der Knoten-Zentralität (für jedes Paar von Eckpunkten die Summe der Grad-Zentralität, die Summe der Nähe-Zentralität und die Summe der Zwischen-Zentralität) und den Wert des kürzesten der Abstand zwischen den Scheitelpunkten mit einem Minuszeichen.

    Angenommen, die Wahrscheinlichkeit, dass sich ein Paar von Scheitelpunkten zum nächsten Zeitpunkt verbindet, hängt nicht nur vom Wert der Metriken zum vorherigen Zeitpunkt ab, sondern auch zu Zeitpunkten mit einer gewissen Zeitverzögerung. Diese Wahl wird durch die Tatsache erklärt, dass, wenn eine Zunahme des Indikators eines Klassifikators mit der Zeit beobachtet wird, bei jedem nächsten Schritt die Wahrscheinlichkeit erhöht wird, dass zwei Eckpunkte verbunden werden.

    Separat weisen wir auf die Einbeziehung von Indikatoren hin, die für die Identifizierung von Übergangspunkten im Netzwerk verantwortlich sind. Die Wahl wird zugunsten der absoluten Werte für Dichte, mittlere Zentralität zwischen den Gleichungen und mittlere Zentralität zwischen den Gleichungen getroffen , da bei Verwendung von beispielsweise Random Forest in einem einzelnen Baum der Schwellenwert eines der aufgelisteten (oder mehrerer) Prädiktoren automatisch den Zeitpunkt der Netzwerkverteilung bestimmt.

    Als Zielvariable wählen wir den Link- Indikator - das Vorhandensein oder Fehlen einer Verbindung zwischen einem Paar ausgewählter Scheitelpunkte (1 - für durch eine Kante verbundene Scheitelpunkte, 0 - ansonsten). Die Lösung des Zweiklassen-Klassifizierungsproblems nach der Random Forest-Methode ergab bei einer Testprobe die folgenden Ergebnisse:



    In unserem Fall wird nicht nur das Problem der binären Klassifizierung in Klassen gleicher Wichtigkeit gelöst, sondern auch die Unterteilung in „negative“ und „positive“ Klassen - daher können wir die AUC-Metrik verwenden, um die Qualität des Modells zu bestimmen. Mit AUC = 0,88 können wir auf die hohe Qualität des konstruierten Modells schließen.

    Zur aussagekräftigen Interpretation von Prädiktoren erstellen wir ein Diagramm der Dynamik einer Abnahme des Gini-Index in unabhängigen Variablen:



    Schlussfolgerungen


    • Die beiden wichtigsten Indikatoren waren AvClose und Close (Maß dafür, wie schnell Sie von diesem Scheitelpunkt zu allen anderen gelangen können) => Diese Variablen können zukünftige, nicht reale Verbindungen vorhersagen
    • Bei den drei wichtigsten Indikatoren handelt es sich um zwei Indikatoren, die nicht auf der Grundlage der einzelnen Merkmale der Eckpunkte, sondern auf der Grundlage der Indikatoren im gesamten Diagramm berechnet wurden
    • Die Bedeutung der mittleren Nähe und der Zentralität zwischen den Punkten legt nahe, dass die Hypothese des Vorhandenseins von Übergangspunkten bestätigt wird

    Die Signifikanz der Übergangspunktindikatoren lässt im Allgemeinen darauf schließen, dass die Stichprobe während des Trainings in den Blättern des Entscheidungsbaums in Diagramme mit unterschiedlichen Zeitintervallen unterteilt wird, wodurch der weitere Aufbau des Modells in jedem der Zweige mit unterschiedlichen Schwellenwerten für dieselben Prädiktoren erfolgt. Somit trägt die Einführung einer Übergangspunktmetrik zu einer genaueren Vorhersage von Klassen bei.

    Jetzt auch beliebt: