Identifizieren Sie Community-übergreifend auf Instagram, um Benutzerinteressen zu identifizieren

Wie viel kann ein Profil in einem sozialen Netzwerk über eine Person aussagen? Fotos, Beiträge, Kommentare, Abonnements - ein unberührtes Feld für die Analyse. Heute werden wir darüber sprechen, wie wir die Interessen der Nutzer anhand ihrer Instagram-Abonnements ermitteln.

Quelle

Der naheliegende Ansatz besteht darin, die Abonnements einer Person zu kategorisieren. Zum Beispiel haben wir unter den Abonnements von Benutzer Ivan zwei Autoblogger und drei Konten mit lustigen Bildern gefunden, der Rest der Profile ist nicht thematisch (wir gehen davon aus, dass dies Freunde, Verwandte, Kollegen usw. sind). Daraus schließen wir: Ivan ist eine fröhliche Person, die Autos liebt. Gewinn Alles was wir brauchen ist die Korrespondenz „Blogger + Inhaltsthema“, aber hier ist nicht alles so einfach.

Wer ist ein Blogger? Ein Blogger auf Instagram unterscheidet sich nicht von einem normalen Account (und im Allgemeinen ist es so etwas wie ein Geisteszustand). Im Idealfall interessieren wir uns für thematische Berichte mit einem großen Anteil eines Live-Publikums, während wir nicht einfach die Anzahl der Abonnenten reduzieren möchten, sondern möglicherweise etwas verpassen.

Wo bekommt man eine gute Taxonomie? Wenn Sie sich die Kategorien selbst einfallen lassen, geht mit Sicherheit etwas Interessantes in „verschiedenen Dingen“ verloren, und wenn alles fertig ist, stellt sich heraus, dass die Kategorien zu breit sind. Wir möchten eine natürliche Partition erhalten und werden daher Blogger gruppieren.

Kann ein Blogger mehreren Kategorien angehören? Einfach so! Sehr oft ist er gleichzeitig ein Schweizer, ein Schnitter und ein Typ, der einen Typ spielt (sowie Reisen, Lebensstil, Frau und Mutter).
Wir benötigen also einen Datensatz mit einer sehr großen Anzahl von Bloggern und einen Clustering-Algorithmus mit sich überschneidenden Clustern am Ausgang.

Wie alles begann

Wir werden von Kunden angesprochen, die ihre Anzeigen am effektivsten bei Meinungsführern auf Instagram platzieren möchten. Manchmal gibt es eine Liste von Bloggern, und dann lösen wir das Optimierungsproblem - um mehr Leute für weniger Geld zu erreichen, und manchmal gibt es keine Liste und relevante Blogger müssen gefunden werden. Diesmal suchten sie nach Profilen von Augenärzten.

Wir haben einen ähnlichen Ansatz wie ein Empfehlungssystem verwendet:

1. Wählen Sie mit Ihren Händen 3-7 geeignete Profile aus („Kerngemeinschaft“)
   
   
   
   
2. Anhand der Abonnentenschnittstelle identifizieren wir Personen, die sich für das Thema interessieren („begeistert“).
   
   
   
   
3. Wir suchen neue Ärzte für Abonnements von „begeisterten“ Menschen
   
   
   
   
   
4. Wiederholen Sie gegebenenfalls die Schritte 1 bis 3 (Hinzufügen neuer Ärzte zum „Kern“ oder Ändern)
   

Nun ausführlicher zu einem Beispiel.

Schritt 1. Mithilfe einer Instagram-Suche haben wir 6 Konten von Augenärzten aus verschiedenen Regionen Russlands ausgewählt:


Die Liste ist ziemlich zufällig, aber es hat uns gereicht, dass der Blog wirklich zum Thema passt und die Abonnenten nicht weniger als 1000 Personen sind.

Schritt 2. Nachdem wir alle Abonnenten gekreuzt haben, sehen wir uns die Verteilung an.

Hurra! Es gibt Kreuzungen.

Außerdem gibt es zwei Personen, die alle sechs Profile abonniert haben! Nun müssen Sie herausfinden, wen wir als „begeisterte“ Augenheilkunde betrachten. Wir haben beschlossen, dass wir alle nehmen, beginnend mit drei Abonnements. Wie sie sagen, 1 Mal ist ein Unfall, 2 Mal ist ein Zufall, 3 Mal ist eine Regelmäßigkeit. So wurden 131 (2 + 3 + 24 + 102) "begeisterte" Benutzer gefunden.

Schritt 3. Laden Sie die Abonnements von „begeisterten“ Personen herunter und aggregieren Sie sie erneut auf jede mögliche Weise.


Wir haben eine beeindruckende Liste von Berichten, aus denen wir nun neue Augenärzte auswählen werden. Die rechte Spalte zeigt, wie viele der 131 Personen, die im zweiten Schritt ausgewählt wurden, das Profil abonniert haben. Oben waren Profile unserer ursprünglichen sechs, was nicht überraschend ist. Wenn wir jetzt den Schwellenwert auswählen und sagen: „Alle Profile mit einem Zählwert von mehr als zehn sind neue Ärzte“, riskieren wir, Augenärzten beliebte Konten wie Olga Buzova zuzuweisen und gleichzeitig kleine, aber relevante Profile zu verlieren. Fügen Sie also ein weiteres hinzu Geben Sie die Anzahl der Abonnenten ein und berechnen Sie den Prozentsatz der begeisterten Benutzer unter den Abonnenten.


Der Einfachheit halber wird der Bruch mit 100 multipliziert (Anteil ist also tatsächlich der Prozentsatz). Infolgedessen erhielten mit der Zustandszahl> = 6 und dem Anteil> = 0,05 166 neue Augenärzte. Klasse!

Schritt 4. 172 Konten wurden zum neuen „Kern“ der Community. Dies half, etwa 500 weitere neue Augenärzte zu finden, aber das Ergebnis wurde bereits auf ausländische Konten verschoben.

Ähnliche Konten in Instagram-Empfehlungen

Das ist natürlich alles interessant, und jetzt wissen wir, wie man Konten findet, die einander ähnlich sind, aber wir träumen immer noch davon, alle Installer in Kategorien aufzuteilen. Und dann kam mir die Idee, mir die vorgefertigten Instagram-Empfehlungen anzusehen.


Tatsache ist, dass thematische Berichte Empfehlungen enthalten, gewöhnliche Menschen jedoch nicht. Hier ist die Antwort auf die Frage, wer Blogger in Betracht ziehen soll und minus ein Kopfschmerz. Hurra!

In den Empfehlungen hat ein Blogger bis zu 80 ähnliche Profile. Wir hatten eine Liste von 1000 russischen Blogs, wir haben damit angefangen. Sie haben ähnliche genommen, dann ähnliche, dann ... na ja, verstehst du :)

Der Plan war, dass dieser Prozess eines Tages enden wird, da kleine Profile mit ein paar Hundert Abonnenten nicht in die Empfehlungen aufgenommen werden, aber tatsächlich haben wir aufgehört, als die Geduld endete. Sie können den Datensatz jederzeit weiter sammeln, aber bisher hat er sich nicht als nützlich erwiesen. Mit hoher Wahrscheinlichkeit haben wir fast alle russischen Blogger abgedeckt, und okay.

Jetzt haben wir ein Diagramm mit 3.428.453 Eckpunkten (Blogger) und 96.967.974 Kanten (Ähnlichkeit zweier Blogger untereinander).

So sieht unser Diagramm auf einer sehr kleinen Stichprobe aus

Es stellte sich übrigens heraus, dass wir nicht die ersten waren, die diesen Ansatz gewählt haben.

Anscheinend werden Empfehlungen auf Instagram basierend darauf gebildet, wem die Anhänger dieses Profils noch folgen, sodass ein Arzt aus Brjansk beliebte Brjansk-Konten und andere Ärzte in den Empfehlungen haben wird. Dies ähnelt unserer Suche nach Augenärzten, aber jetzt können wir alle Communities berücksichtigen, zu denen der Blogger gleichzeitig gehört. Außerdem erhöht sich die Verarbeitungsgeschwindigkeit erheblich, da nicht alle Abonnenten des Bloggers analysiert werden müssen. Es reicht aus, nur 80 empfohlene Konten zu verwenden.

Auswahl und Beschreibung des Algorithmus

Großartig! Die Daten wurden vorbereitet, jetzt müssen wir ein Werkzeug und einen Algorithmus auswählen, die mit einem so großen Graphen fertig werden können, vorzugsweise in angemessener Zeit. Ich möchte Sie daran erinnern, dass wir bei der Ausgabe eine Reihe von Communitys erhalten möchten, in denen ein Blogger mehreren von ihnen angehören kann.

Wir haben uns für die Stanford Network Analysis Platform (SNAP) -Bibliothek entschieden

Die Stanford Network Analysis Platform (SNAP) ist eine universelle Netzwerkanalyse- und Graph Mining-Bibliothek. Es ist in C ++ geschrieben und lässt sich leicht auf massive Netzwerke mit Hunderten von Millionen Knoten und Milliarden von Kanten skalieren. Es bearbeitet große Diagramme effizient, berechnet strukturelle Eigenschaften, generiert regelmäßige und zufällige Diagramme und unterstützt Attribute an Knoten und Kanten.

Unsere Aufmerksamkeit wurde auf den AGMfit-Algorithmus (AGM - Affilated Graph Model) gelenkt, und als Ergebnis verwendeten wir BIGCLAM (Cluster Affiliation Model for Big Networks). Sie unterscheiden sich nur darin, dass im ersten Fall das Optimierungsproblem kombinatorisch gelöst wird, wodurch es weniger skalierbar ist, und im zweiten Fall können Sie nur Diagramme wie das unsere füttern.

Die wichtigste und eher intuitive Idee: Je mehr zwei Knoten gemeinsame Gemeinschaften haben, desto größer ist die Wahrscheinlichkeit der Kommunikation zwischen diesen beiden Knoten. Beide Algorithmen basieren auf dem Affilated Graph Model. Lassen Sie uns daher näher darauf eingehen:

Angenommen, wir haben einen zweigeteilten Graphen, in dem runde Spitzen Gemeinschaften sind ( $$$A$und $$$B$) und square - Benutzer des sozialen Netzwerks und jede Person ( $$$u$) bezieht sich auf verschiedene Communities mit bestimmten Gewichten ( $$$F_ {uA}$und $$$F_ {uB}$) Je größer das Gewicht, desto größer ist die Wahrscheinlichkeit, dass der Teilnehmer mit anderen Mitgliedern der Community verbunden (vertraut) ist.


Beispiel: Kollegen, die an derselben Universität studiert haben, folgen einander auf Instagram. Beide sind Absolventen derselben Universität (Community 1) und arbeiten in derselben Firma (Community 2). Wir wissen nicht, was die „Freundschaft“ im Netzwerk verursacht hat und wann sie sich kennengelernt haben. Lassen Sie einen nur die Universität abschließen und einen Job bekommen, und den zweiten Absolventen vor fünf Jahren, der die ganze Zeit im Unternehmen gearbeitet hat, dann wird das Gewicht der Zugehörigkeit zur ersten Gemeinschaft 1 höher sein und die Gemeinschaft 2 weniger und umgekehrt.

Für jede gemeinsame Gemeinschaft von ein paar Menschen erhalten wir eine unabhängige Chance, vertraut zu werden:

$$

$$1 - exp (-F_ {uc} \ cdot F_ {vc})$$

Je häufiger die Gemeinschaften sind, desto wahrscheinlicher ist es, dass sie sich kennen:

$$

$$1 - exp (- \ sum_c F_ {uc} \ cdot F_ {vc})$$

Wenn wir die Wahrscheinlichkeit einer Verbindung zwischen jedem Benutzerpaar berechnen, erhalten wir am Ausgang ein Diagramm, in dem die Eckpunkte Personen sind und die Kanten zwischen ihnen eine Tatsache der Bekanntschaft oder des Abonnements sind.

Aus der Ansicht links sind wir also zum Bild rechts übergegangen.


Lassen Sie uns nun verstehen, wie dieses Modell bei der Community-Erkennung verwendet wird.

Wir haben eine Grafik ähnlicher Blogger und unser Ziel ist es, diese zu entdecken $$$K$Gemeinschaften, die das oben beschriebene Modell verwenden, indem sie die am besten geeignete Gewichtsmatrix auswählen $$$F$(seine Dimension $$$N$Knoten auf $$$K$Communities), so dass der am Ausgang erhaltene Graph unserem ursprünglichen ähnlich ist. Dies erfolgt durch Maximieren der Wahrscheinlichkeitsfunktion.

$$

$$l (F) = log P (G | F)$$

Und doch kann diese ganze Sache als nicht negative Matrixzerlegung dargestellt werden, was nur ein Plus an Skalierbarkeit des BIGCLAM-Algorithmus im Vergleich zu AGMfit ergibt.

Lesen Sie hier und hier mehr .

Community-Nummerierung und Start

In BIGCLAM können Sie sowohl die genaue Anzahl der Communitys als auch das Intervall angeben. Der Algorithmus wählt 20% der Knotenpaare pro Test aus, und 80% entspricht dem Modell mit einer unterschiedlichen Anzahl von Communitys.

Wir haben eine Eingabedatei mit einer Liste von Kanten erstellt und ausgeführt:

./bigclam -o:bloggers -i:query_graph_all.edgelist -c:-1 -nc:20 -mc:50000 -xc:200000 -nt:10 

Mit den Parametern können Sie die Anzahl der Versuche, die minimale und maximale Anzahl der Communitys (oder gegebenenfalls die genaue Anzahl), die Anzahl der Threads für die Parallelisierung und das Präfix der Ausgabedateien angeben. In unserem Fall legen wir das Intervall von 50 bis 200.000 Communitys mit 20 Versuchen für 10 Threads fest. All diese Pracht wurde fünf Tage lang auf 2 Intel® Xeon® Gold 6150-CPUs mit 2,70 GHz gezählt. Die Ausgabe erhielt zwei Dateien, eine für Gephi, den zweiten Text, in dem jede Zeile eine Community ist.

Tatsächlich haben wir den Algorithmus zweimal ausgeführt und zum ersten Mal die Obergrenze von 50.000 Communities erreicht. Das Ergebnis war nicht schlecht, aber gemischte Communities stießen häufig darauf. Diesmal haben wir wieder den Maximalwert von 200.000 Gemeinden erreicht, aber sie waren viel besser, und wir haben damit aufgehört. Sie könnten das Ergebnis wahrscheinlich noch besser erzielen, aber zweihunderttausend unbenannte Gemeinschaften haben unsere Vorstellungskraft erschreckt.

Schönes Bild

Was tun mit all dem?

Einerseits helfen uns die resultierenden Communities, schnell nach engen Gruppen von Bloggern zu suchen (wie damals bei Augenärzten). Wenn es ein paar Blogger als Beispiel gibt, nehmen wir alle Communitys, zu denen sie gehören, und verwerfen unnötige. Sie können eine Suche nach Namen verwenden, z. B. eine der Communitys zu Dekor und Innenarchitektur:


Um andererseits die Interessen der Benutzer zu bestimmen, müssen alle diese Gemeinschaften irgendwie sinnvoll aufgerufen werden. Oder vielleicht ist nicht alles nötig.

Kurbel

Leider sind nicht alle erhaltenen Communitys gleich gut. Um die interessantesten zu finden, haben wir uns entschlossen, die CRank-Priorisierungsmethode aus derselben SNAP-Bibliothek zu verwenden. Es ist so konzipiert, dass der Rang jeder Community basierend auf der Struktur des Diagramms automatisch angepasst wird: Je höher der Wert, desto besser die Community.

Bei der Eingabe des Programms übermitteln wir die zuvor gefundenen Communitys. Für jede von ihnen werden Prioritätsmetriken berechnet (4 Teile), dann werden diese Metriken aggregiert und wir erhalten eine Schätzung.


Lesen Sie hier mehr.

Starten

 ./crank -i:bloggers_cmtyvv.txt -c:query_graph_all.edgelist -o:bloggers_prioritization.txt 

Während des Starts sind sie auf ein Kompatibilitätsproblem mit Ubuntu 18.04 gestoßen. Hier bieten sie eine Lösung an .

Da unsere Community-Datei bloggers_cmtyvv.txt und die Liste der Kanten query_graph_all.edgelist ursprünglich Spitznamen (vom Typ string) enthielten, mussten wir sie hashen, damit sie int waren, andernfalls schwört crank.

Mal sehen, wie das mit einem Beispiel funktioniert:

Wir werden mehrere Communitys auswählen, in denen es Profile gibt, die wie geplant die Zeichenfolge "lokomotiv" im Namen enthalten. Dies sollte die Community der Fußballfans des Lokomotiv-Clubs sein, und wir werden sehen, was es wirklich ist. Mitglieder der Community sind rot markiert, unter jedem Bild befindet sich eine entsprechende Punktzahl.

Community 1, Punktzahl 0,4
Community 2, Punktzahl 0,41
Community 3, Punktzahl 0,34
Community 4, Punktzahl 0,13

Nachdem wir uns alle Profile aus diesem Untergraphen angesehen haben, wählen wir diejenigen aus, die wirklich zur gewünschten Community gehören. Es stellte sich folgendermaßen heraus:

Es stellt sich heraus, dass die ersten beiden Gemeinschaften tatsächlich das enthalten, was wir brauchen, fast fehlerfrei (mit Ausnahme des Profils der russischen Fußballmannschaft Russland). Die dritte Gemeinschaft ist gut, deckt aber weniger Konten ab als die ersten beiden, daher ist die Punktzahl kleiner und die vierte Die Community besteht zwar aus Berichten zu einem Fußballthema (hier sind die Spieler anderer Vereine, deren Frauen und Manager), passt aber nicht zu uns.
Wir können daraus schließen, dass CRank recht gut funktioniert.

Manuelle Kennzeichnung für Färbung und Ergebnisse.

Um das Problem des Färbens von Benutzern nach Interessen zu lösen, haben wir auch die Texte von Posts analysiert und wollten herausfinden, wo das Ergebnis besser / interessanter ist (in Texten oder Abonnements) und ob es überhaupt Übereinstimmungen gibt. Für eine kleine Stichprobe von Menschen mussten etwa 800 Gemeinden unabhängig voneinander gekennzeichnet werden. Wir waren mit dem Ergebnis mehr als zufrieden und beschlossen, diesen Ansatz zu entwickeln. Mit der Community-Erkennungsmethode können Sie sehr enge und ungewöhnliche Interessenkategorien finden, z. B. Rattenprofile (im Sinne kleiner grauer Nagetiere) und andere erstaunliche Dinge abonnieren. Sie können herausfinden, an welcher Art von Sport eine Person angeblich interessiert ist, und nicht alles in die Kategorie „extrem“ verschieben usw

Wir werden wahrscheinlich nicht alle 200.000 Communitys markieren, aber vielleicht werden wir mit den CRank-Ergebnissen herumspielen und nur Communitys mit hoher Geschwindigkeit belassen, und vielleicht werden wir sie als notwendig markieren. Solche Dinge :)

Vielen Dank!

Dieser Artikel wurde gemeinsam mit meinem Vorgesetzten Artyom Korolev ( korolevart ), F & E Dentsu Aegis Network Russia, verfasst

Quelle