Identifikasi lintas komunitas di Instagram untuk mengidentifikasi minat pengguna

Seberapa banyak yang dapat diketahui profil di jejaring sosial tentang seseorang? Foto, pos, komentar, langganan - bidang yang belum tersentuh untuk analisis. Hari ini kita akan berbicara tentang bagaimana kita menentukan minat pengguna berdasarkan langganan Instagram mereka.

Sumber

Pendekatan yang jelas adalah mengategorikan langganan seseorang. Misalnya, di antara langganan pengguna Ivan kami menemukan dua autoblogger dan tiga akun dengan gambar lucu, sisa profil tidak bertema (kami menganggap bahwa ini adalah teman, kerabat, kolega, dll.). Dari sini kami menyimpulkan: Ivan adalah orang yang ceria, suka mobil. Untung Yang kita butuhkan hanyalah korespondensi “blogger + content theme”, tetapi tidak semuanya begitu sederhana di sini.

Siapa itu blogger? Seorang blogger di Instagram tidak berbeda dengan akun biasa (dan secara umum, itu seperti keadaan pikiran). Idealnya, kami tertarik pada akun tematik dengan sebagian besar pemirsa langsung, sementara kami tidak ingin hanya memotong jumlah pelanggan, kami mungkin kehilangan sesuatu.

Di mana mendapatkan taksonomi yang baik? Jika Anda menemukan sendiri kategorinya, maka sesuatu yang menarik pasti akan tersesat dalam "hal-hal yang berbeda", dan ketika semuanya sudah siap, ternyata kategorinya terlalu luas. Kami ingin mendapatkan partisi alami, dan karenanya kami akan mengelompokkan blogger.

Bisakah satu blogger termasuk dalam beberapa kategori? Seperti itu saja! Sangat sering, dia secara bersamaan adalah seorang Swiss, seorang penuai, dan seorang pria yang bermain pria (serta perjalanan, gaya hidup, istri dan ibu).
Jadi, kita membutuhkan dataset dengan jumlah blogger yang sangat besar dan algoritma pengelompokan dengan cluster yang berpotongan pada output.

Bagaimana semuanya dimulai

Kami didekati oleh pelanggan yang ingin menempatkan iklan mereka dengan para pemimpin opini di Instagram paling efektif. Terkadang ada daftar blogger, dan kemudian kami menyelesaikan masalah optimisasi - untuk menjangkau lebih banyak orang dengan uang lebih sedikit, dan kadang-kadang tidak ada daftar dan blogger yang relevan perlu ditemukan. Kali ini mereka mencari profil dokter mata.

Kami menggunakan pendekatan yang mirip dengan sistem rekomendasi:

1. Pilih 3-7 profil yang sesuai dengan tangan Anda (“komunitas inti”)
   
   
   
   
2. Menggunakan persimpangan pelanggan, kami mengidentifikasi orang-orang yang tertarik pada topik ("antusias")
   
   
   
   
3. Kami mencari dokter baru di langganan orang "antusias"
   
   
   
   
   
4. Jika perlu, ulangi langkah 1-3 (menambahkan dokter baru ke "inti" atau mengubahnya)
   

Sekarang lebih detail pada contoh.

Langkah 1. Dengan menggunakan pencarian Instagram, kami memilih 6 akun dokter mata dari berbagai daerah di Rusia:


Daftar ini cukup acak, tetapi cukup bagi kami bahwa blog benar-benar cocok dengan topik dan pelanggan tidak kurang dari 1000 orang.

Langkah 2. Setelah melewati semua pelanggan, kami melihat distribusi.

Hore! Ada persimpangan.

Selain itu, ada dua orang yang berlangganan keenam profil! Jadi, sekarang Anda perlu menentukan siapa yang kami anggap ophthalmologi "antusias". Kami memutuskan bahwa kami membawa semua orang, mulai dengan tiga langganan. Seperti yang mereka katakan, 1 kali adalah kecelakaan, 2 kali adalah kebetulan, 3 adalah keteraturan. Dengan demikian, 131 (2 + 3 + 24 + 102) pengguna "antusias" ditemukan.

Langkah 3. Unduh langganan orang-orang "antusias" dan kumpulkan lagi dalam setiap cara yang memungkinkan.


Kami mendapat daftar akun yang mengesankan, dari mana kami sekarang akan memilih dokter mata baru. Kolom kanan menunjukkan berapa banyak dari 131 orang yang terpilih pada langkah kedua yang berlangganan profil. Di atas adalah profil dari enam asli kami, yang tidak mengejutkan. Jika sekarang kita memilih ambang dan mengatakan: "Semua profil dengan nilai hitungan lebih dari sepuluh adalah dokter baru", maka kita berisiko menghubungkan akun populer seperti Olga Buzova ke dokter mata dan pada saat yang sama kehilangan profil yang kecil tetapi relevan, jadi tambahkan satu lagi kolom jumlah pelanggan dan menghitung persentase pengguna antusias di antara pelanggan.


Untuk kenyamanan, fraksi dikalikan dengan 100 (jadi bagian sebenarnya adalah persentase). Akibatnya, dengan kondisi yang dihitung> = 6 dan berbagi> = 0,05, 166 dokter mata baru diterima. Kelas!

Langkah 4. 172 akun menjadi "inti" baru dari komunitas, ini membantu menemukan sekitar 500 dokter mata baru, tetapi hasilnya sudah bergeser ke akun asing.

Akun serupa di rekomendasi Instagram

Ini semua menarik, tentu saja, dan sekarang kita tahu bagaimana menemukan akun yang mirip satu sama lain, tetapi kami masih bermimpi mendapatkan pengelompokan semua penginstal ke dalam kategori. Dan kemudian muncul ide di benak saya untuk melihat rekomendasi instagram yang sudah jadi.


Faktanya adalah bahwa akun tematik memiliki rekomendasi, tetapi orang biasa tidak. Inilah jawaban untuk pertanyaan tentang siapa yang harus dipertimbangkan blogger dan minus satu sakit kepala. Hore!

Dalam rekomendasinya, seorang blogger memiliki hingga 80 profil serupa. Kami memiliki daftar 1000 blog Rusia, kami mulai dengan itu. Mereka mengambil yang serupa, lalu yang serupa, lalu ... well, Anda mengerti :)

Rencananya adalah bahwa suatu hari proses ini akan berakhir, karena profil kecil dengan beberapa ratus pelanggan tidak akan dimasukkan dalam rekomendasi, tetapi kami benar-benar berhenti ketika kesabaran berakhir. Anda selalu dapat terus mengumpulkan dataset, tetapi sejauh ini tidak berguna, dengan probabilitas tinggi kami telah membahas hampir semua blogger Rusia, dan oke.

Sekarang kita memiliki grafik dengan 3.428.453 simpul (blogger) dan 96.967.974 tepi (kesamaan dua blogger satu sama lain).

Ini adalah bagaimana grafik kita terlihat pada sampel yang sangat kecil

Ngomong-ngomong, ternyata kami bukan yang pertama memilih pendekatan ini.

Rupanya, rekomendasi di Instagram dibentuk berdasarkan siapa pengikut profil ini yang masih mengikuti, sehingga dokter dari Bryansk akan memiliki akun Bryansk yang populer dan dokter lain dalam rekomendasinya. Ini mirip dengan pencarian kami untuk dokter mata, tetapi sekarang kami dapat memperhitungkan semua komunitas yang menjadi milik blogger pada saat yang sama. Plus, kecepatan pemrosesan meningkat secara signifikan, karena tidak perlu menganalisis semua pelanggan blogger, cukup untuk hanya mengambil 80 akun yang disarankan.

Seleksi dan deskripsi algoritma

Hebat! Data telah disiapkan, sekarang kita perlu memilih alat dan algoritma yang dapat mengatasi grafik sebesar itu, lebih disukai dalam waktu yang memadai. Biarkan saya mengingatkan Anda bahwa pada output kami ingin mendapatkan satu set komunitas di mana satu blogger dapat menjadi milik beberapa dari mereka.

Kami memilih perpustakaan Stanford Network Analysis Platform (SNAP)

Platform Analisis Jaringan Stanford (SNAP) adalah analisis jaringan tujuan umum dan perpustakaan penambangan grafik. Ini ditulis dalam C ++ dan mudah menskala ke jaringan besar dengan ratusan juta node, dan milyaran tepi. Ini secara efisien memanipulasi grafik besar, menghitung properti struktural, menghasilkan grafik biasa dan acak, dan mendukung atribut pada node dan edge.

Perhatian kami tertarik oleh algoritma AGMfit (AGM - Affilated Graph Model), dan pada akhirnya kami menggunakan BIGCLAM (Cluster Affiliateation Model for Big Networks). Mereka berbeda hanya dalam kasus pertama, masalah optimasi diselesaikan secara kombinatorial, yang membuatnya kurang terukur, dan yang kedua hanya memungkinkan Anda untuk memberi makan grafik seperti kita.

Gagasan utama dan agak intuitif: semakin banyak dua node memiliki komunitas yang sama, semakin besar kemungkinan komunikasi antara dua node ini. Kedua algoritma didasarkan pada Affilated Graph Model, jadi mari kita bahas lebih rinci:

Misalkan kita memiliki grafik bipartit di mana puncak bulat adalah komunitas ( $$$A$dan $$$B$), dan persegi - pengguna jaringan sosial, dan setiap orang ( $$$u$) mengacu pada komunitas yang berbeda dengan bobot tertentu ( $$$F_ {uA}$dan $$$F_ {uB}$) Semakin besar bobotnya, semakin besar kemungkinan partisipan terhubung (akrab) dengan anggota komunitas lainnya.


Contoh: kolega yang belajar di universitas yang sama saling mengikuti di Instagram. Keduanya adalah lulusan dari universitas yang sama (komunitas 1) dan bekerja di perusahaan yang sama (komunitas 2), kita tidak tahu apa yang menyebabkan "persahabatan" di jaringan dan kapan mereka bertemu. Biarkan yang baru saja lulus dari universitas dan mendapatkan pekerjaan, dan yang kedua lulus lima tahun yang lalu dan telah bekerja di perusahaan selama ini, maka bobot kepemilikan di komunitas pertama 1 akan lebih banyak, dan komunitas 2 lebih sedikit dan sebaliknya.

Untuk setiap komunitas umum dari beberapa orang, kami mendapatkan kesempatan independen untuk menjadi akrab:

$$

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

Dengan demikian, semakin umum komunitas tersebut, semakin besar kemungkinan mereka untuk saling mengenal:

$$

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

Jika kita menghitung kemungkinan koneksi antara masing-masing pasangan pengguna, maka pada output kita mendapatkan grafik di mana simpulnya adalah orang-orang dan ujung-ujungnya adalah fakta kenalan atau berlangganan satu sama lain.

Jadi, dari tampilan di sebelah kiri, kami pindah ke gambar di sebelah kanan.


Sekarang mari kita memahami bagaimana model ini digunakan dalam penemuan komunitas.

Kami memiliki grafik blogger yang serupa dan tujuan kami adalah untuk menemukannya $$$K$masyarakat menggunakan model yang dijelaskan di atas, dengan memilih matriks bobot yang paling tepat $$$F$(dimensinya $$$N$node aktif $$$K$komunitas) sehingga grafik yang diperoleh pada output mirip dengan yang asli. Ini dilakukan dengan memaksimalkan fungsi kemungkinan.

$$

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

Namun semua ini dapat direpresentasikan sebagai dekomposisi matriks non-negatif, yang hanya memberi nilai tambah dalam skalabilitas algoritma BIGCLAM dibandingkan dengan AGMfit.

Baca lebih lanjut di sini dan di sini .

Penomoran dan Peluncuran Komunitas

Di BIGCLAM, Anda dapat menentukan jumlah komunitas dan interval yang tepat. Algoritme memilih 20% dari pasangan node per tes, dan 80% adalah kecocokan model dengan jumlah komunitas yang berbeda.

Kami membentuk file input dengan daftar tepi dan menjalankan:

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

Parameter memungkinkan Anda untuk menentukan jumlah upaya, jumlah minimum dan maksimum komunitas (atau tepat, jika perlu), jumlah utas untuk paralelisasi dan awalan dari file output. Dalam kasus kami, kami menetapkan interval dari 50 hingga 200 ribu komunitas dengan 20 upaya pada 10 utas. Semua kemegahan ini dihitung lima hari pada 2 Intel® Xeon® Gold 6150 CPU @ 2.70GHz. Output menerima dua file, satu untuk Gephi, teks kedua, di mana setiap baris adalah sebuah komunitas.

Faktanya, kami menjalankan algoritme dua kali dan untuk pertama kalinya berlari ke batas atas 50 ribu komunitas, hasilnya tidak buruk, tetapi komunitas campuran sering muncul. Kali ini kami kembali mencapai nilai maksimum 200 ribu komunitas, tetapi mereka jauh lebih baik, dan kami berhenti di situ. Anda mungkin bisa mendapatkan hasilnya lebih baik, tetapi dua ratus ribu komunitas yang tidak disebutkan namanya takut imajinasi kita.

Gambar yang indah

Apa yang harus dilakukan sekarang dengan semua ini?

Di satu sisi, komunitas yang dihasilkan membantu kami dengan cepat mencari kelompok blogger yang sempit (seperti halnya dengan dokter mata pada waktu itu). Jika ada beberapa blogger sebagai contoh, maka kami mengambil semua komunitas tempat mereka berada, membuang yang tidak perlu dan hanya itu. Anda dapat menggunakan pencarian berdasarkan nama, misalnya, salah satu komunitas tentang dekorasi dan desain interior:


Di sisi lain, untuk menentukan minat pengguna, semua komunitas ini entah bagaimana harus dipanggil secara bermakna. Atau mungkin semua itu tidak perlu.

CRank

Sayangnya, tidak semua komunitas yang diterima sama baiknya, dan untuk menemukan yang paling menarik, kami memutuskan untuk mencoba menggunakan metode prioritas CRank dari perpustakaan SNAP yang sama. Ini dirancang untuk secara otomatis mencocokkan peringkat setiap komunitas berdasarkan pada struktur grafik: semakin besar nilainya, semakin baik komunitas.

Pada input program, kami mengirimkan komunitas yang kami temukan sebelumnya, untuk masing-masing komunitas, metrik prioritas (4 buah) dihitung, lalu metrik ini dikumpulkan, dan kami mendapatkan perkiraan.


Baca lebih lanjut di sini .

Luncurkan

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

Selama peluncuran, mereka mengalami masalah kompatibilitas dengan Ubuntu 18.04, mereka menawarkan solusi di sini .

Karena file komunitas bloggers_cmtyvv.txt kami dan daftar tepi query_graph_all.edgelist awalnya berisi nama julukan (tipe string), kami harus hash mereka sehingga int, jika tidak, bersumpah crank.

Mari kita lihat bagaimana ini bekerja dengan sebuah contoh:

Kami akan memilih beberapa komunitas di mana ada profil yang berisi string "lokomotiv" dalam nama, seperti yang direncanakan, ini harus menjadi komunitas penggemar sepak bola dari klub "Lokomotiv", mari kita lihat apa itu sebenarnya. Anggota komunitas ditandai dengan warna merah, di bawah setiap gambar ada skor yang sesuai.

Komunitas 1, skor 0,4
Komunitas 2, skor 0,41
Komunitas 3, skor 0,34
Komunitas 4, skor 0,13

Kemudian, setelah melihat semua profil dari subgraph ini, kami memilih mereka yang benar-benar milik komunitas yang diinginkan, ternyata seperti ini:

Ternyata dua komunitas pertama benar-benar berisi apa yang kita butuhkan, hampir tanpa kesalahan (kecuali untuk profil tim sepakbola Rusia), komunitas ketiga baik, tetapi mencakup lebih sedikit akun daripada dua yang pertama, oleh karena itu nilainya lebih kecil, dan keempat komunitas, meskipun terdiri dari akun tentang topik sepak bola (di sini adalah pemain dari klub lain, istri mereka, dan manajer), tetapi oleh, itu tidak cocok untuk kita.
Kita dapat menyimpulkan bahwa CRank bekerja dengan sangat baik.

Penandaan manual untuk pewarnaan dan hasil.

Untuk memecahkan masalah mewarnai pengguna berdasarkan minat, kami juga menganalisis teks kiriman dan kami ingin melihat di mana hasilnya lebih baik / lebih menarik (dalam teks atau dalam langganan) dan apakah ada kecocokan sama sekali. Untuk sampel kecil orang, sekitar 800 komunitas harus diberi label secara independen. Kami lebih dari puas dengan hasilnya dan memutuskan bahwa pendekatan ini harus dikembangkan. Metode deteksi komunitas memungkinkan Anda menemukan kategori minat yang sangat sempit dan tidak biasa, misalnya, berlangganan profil tikus (dalam arti tikus abu-abu kecil) dan hal-hal luar biasa lainnya, Anda dapat mengetahui jenis olahraga apa yang seharusnya diminati seseorang, dan tidak memasukkan semuanya ke dalam kategori “ekstrem” dan sebagainya

Kami mungkin tidak akan menandai semua 200 ribu komunitas, tetapi mungkin kami akan bermain-main dengan hasil CRank dan hanya meninggalkan komunitas dengan kecepatan tinggi, dan mungkin kami akan menandainya seperlunya. Hal-hal seperti itu :)

Terima kasih

Artikel ini ditulis bersama dengan penyelia saya Artyom Korolev ( korolevart ) R&D Dentsu Aegis Network Russia

Sumber