Algoritma deteksi masyarakat memainkan peran penting dalam memahami data dengan mengidentifikasi kelompok tersembunyi dari entitas terkait dalam jaringan. Analisis Jaringan Sosial, Sistem Rekomendasi, Graphrag, Genomik, dan lebih banyak tergantung pada deteksi masyarakat. Tetapi bagi para ilmuwan data yang bekerja di Python, kemampuan untuk menganalisis data grafik secara efisien saat tumbuh dalam ukuran dan kompleksitas dapat menimbulkan masalah ketika membangun sistem deteksi komunitas yang responsif dan dapat diskalakan.
Meskipun ada beberapa algoritma deteksi komunitas yang digunakan saat ini, algoritma Leiden telah menjadi solusi utama bagi para ilmuwan data. Dan untuk grafik skala besar di Python, tugas yang dulu mahal ini sekarang secara dramatis lebih cepat berkat Cugraph dan implementasi Leiden yang dipercepat GPU. Leiden dari Cugraph memberikan hasil hingga 47x lebih cepat dari alternatif CPU yang sebanding. Kinerja ini mudah diakses dalam alur kerja Python Anda melalui Perpustakaan Cugraph Python atau Perpustakaan NetworkX yang populer melalui backend NX-Cugraph.
Posting ini menunjukkan di mana algoritma Leiden dapat digunakan dan bagaimana mempercepatnya untuk ukuran data dunia nyata menggunakan Cugraph. Baca terus untuk tinjauan singkat Leiden dan banyak aplikasinya, tolok ukur kinerja Cugraph Leiden terhadap orang lain yang tersedia dalam Python, dan contoh Leiden yang dipercepat GPU pada data genomik skala yang lebih besar.
Apa itu Leiden?
Leiden dikembangkan sebagai modifikasi pada algoritma Louvain yang populer, dan seperti Louvain, ini bertujuan untuk mempartisi jaringan ke komunitas dengan mengoptimalkan fungsi kualitas yang disebut modularity. Namun, Leiden juga membahas kelemahan yang signifikan dari Louvain: komunitas yang dihasilkan yang dikembalikan oleh Louvain dapat terhubung dengan buruk, kadang -kadang bahkan terputus. Dengan menambahkan fase penyempurnaan menengah, Leiden menjamin semua komunitas yang dihasilkan terhubung dengan baik, menjadikannya pilihan populer untuk berbagai pilihan aplikasi. Leiden dengan cepat menjadi alternatif standar untuk Louvain.
Dimana Leiden digunakan?
Berikut ini hanyalah sampel bidang yang menggunakan teknik deteksi komunitas seperti Leiden, yang semuanya tunduk pada dampak dari ukuran data dunia nyata yang terus tumbuh:
- Analisis Jaringan Sosial: Mengidentifikasi komunitas dapat mengungkapkan kelompok pengguna dengan minat bersama, memfasilitasi iklan yang ditargetkan, rekomendasi, dan studi tentang difusi informasi.
- Sistem Rekomendasi: Clustering pengguna atau item ke komunitas berdasarkan interaksi mereka memungkinkan sistem rekomendasi untuk memberikan saran yang lebih akurat dan dipersonalisasi.
- Deteksi Penipuan: Dengan mengidentifikasi komunitas akun penipuan atau transaksi yang mencurigakan dalam jaringan keuangan, lembaga dapat dengan cepat menandai dan menyelidiki aktivitas penipuan.
- Generasi Pengambilan Berbasis Grafik (GraphRag): Graphrag mengambil informasi yang relevan dari grafik pengetahuan – jaringan fakta yang saling berhubungan – untuk memberikan konteks LLM yang lebih baik. Leiden sering digunakan untuk membuat kategori pengetahuan untuk membantu mencocokkan node yang paling berlaku dalam grafik pengetahuan dengan prompt pengguna.
- Genomik: Leiden digunakan saat menganalisis data genomik sel tunggal untuk mengidentifikasi kelompok sel dengan profil ekspresi gen yang sama.
Bagaimana Leiden bertenaga GPU dari Cugraph membandingkan?
Beberapa implementasi Leiden yang tersedia untuk pengembang Python dibandingkan menggunakan grafik kutipan paten yang terdiri dari 3,8 juta node dan 16,5 juta tepi, di mana masyarakat yang diidentifikasi oleh Leiden mewakili teknologi terkait. Gambar 1 menunjukkan runtime dalam hitungan detik, bersama dengan jumlah komunitas unik yang diidentifikasi.
Perangkat Lunak: NetworkX 3.5, Cugraph/NX-Cugraph 25.10; CPU: Intel Xeon Platinum 8480Cl 2TB RAM; GPU: NVIDIA H100 80GB RAM
Perhatikan bahwa karena implementasi Leiden menggunakan generator bilangan acak, masyarakat yang dikembalikan adalah non-deterministik dan sedikit berbeda di antara berjalan. Jumlah komunitas terbukti menunjukkan bahwa semua hasil kira -kira sama. Sebagian besar implementasi, termasuk Cugraph, memberikan parameter untuk menyesuaikan ukuran komunitas yang lebih besar atau lebih kecil, antara lain. Setiap implementasi dipanggil dengan nilai parameter default bila memungkinkan. Kode sumber untuk tolok ukur ini dapat ditemukan di repo Rapidsai/Cugraph Github.
Seperti yang ditunjukkan pada Gambar 1, implementasi Leiden yang dipercepat GPU CUGRAPH berjalan 8,8x lebih cepat dari iGraph dan 47,5x lebih cepat daripada Graspologic's pada grafik kutipan yang sama. Selain kinerja tinggi, Cugraph juga memberikan kemudahan penggunaan, fleksibilitas, dan kompatibilitas dengan alur kerja sains data python yang ada melalui beberapa antarmuka Python. Untuk membantu Anda memilih yang tepat untuk proyek Anda, Tabel 1 mencantumkan fitur utama dari setiap perpustakaan. Leiden dan banyak algoritma grafik lainnya tersedia di masing -masing.
| Kecepatan | Kemudahan penggunaan | Dependensi | Manfaat NetworkX: Fallback CPU, Objek Grafik Fleksibel, API Populer, Ratusan Algo, Visualisasi Grafik, Lainnya | Dukungan Multi-GPU | Dukungan CUDF dan DASK | |
| NetworkX Plus NX-Cugraph | Cepat | Termudah | Sedikit | ✔ | ||
| Cugraph | Lebih cepat | Mudah | Lebih banyak, termasuk cudf dan dask | ✔ | ✔ |
Untuk instruksi instalasi terperinci, lihat Panduan Instalasi Rapids. Untuk memulai segera dengan Pip atau Conda, gunakan pemilih rilis Rapids.
Cara menggunakan networkx dan nx-cugraph dengan data genomik
Kumpulan data genomik sangat besar, dan tumbuh pada kecepatan eksplosif, sebagian besar karena penurunan baru dan dramatis dalam biaya sekuensing DNA. Sementara NetworkX memiliki pengikut yang sangat besar di antara para ilmuwan data dari semua bidang, implementasinya yang murni-Python berarti bahwa sebagian besar set data genomik terlalu besar untuk itu, memaksa para ilmuwan untuk belajar dan mengintegrasikan perpustakaan yang terpisah untuk analitik. Untungnya, NetworkX dapat dipercepat GPU dengan mengaktifkan backend NX-Cugraph untuk memungkinkan para ilmuwan data untuk terus menggunakan NetworkX bahkan dengan data besar.
Untuk menunjukkan manfaat GPU Accelerated NetworkX pada data genomik skala yang lebih besar, contoh sederhana dibuat yang membaca data ekspresi gen, membangun grafik gen dengan tepi yang menghubungkan gen berdasarkan nilai korelasi ekspresi, menjalankan Leiden untuk mengidentifikasi kelompok gen yang terkait secara fungsional, dan memplot komunitas untuk inspeksi visual. Kode sumber lengkap tersedia di repo Rapidsai/NX-Cugraph Github. Perhatikan bahwa contoh tersebut merupakan operasi umum dalam genomik – deteksi komunitas menggunakan Leiden atau Louvain – pada data genomik yang sebenarnya, tetapi tidak dimaksudkan untuk mewakili alur kerja genomik yang khas.
Data analisis ekspresi gen menggunakan hasil dalam grafik 14,7k node dan 83,8 juta tepi. Kode berikut akan menjalankan Leiden menggunakan NX-Cugraph tetapi akan kembali ke implementasi NetworkX dari Louvain ketika NX-Cugraph tidak tersedia.
Leiden saat ini adalah satu-satunya algoritma yang disediakan oleh NX-Cugraph yang tidak memiliki implementasi alternatif yang tersedia melalui NetworkX. Ini berarti bahwa Leiden tersedia untuk pengguna NetworkX hanya melalui NX-Cugraph. Untuk alasan ini, alur kerja ini menggunakan Louvain dari NetworkX di CPU, karena memberikan perbandingan yang masuk akal untuk pengguna yang ingin terus menggunakan NetworkX ketika GPU tidak ada.
Dengan NX-Cugraph diaktifkan, NetworkX mengidentifikasi empat komunitas dalam waktu kurang dari 4 detik. Namun, kembali ke implementasi NetworkX dari Louvain menunjukkan bahwa hasilnya hampir identik (dalam toleransi non-determinisme Leiden dan Louvain), tetapi kinerja secara dramatis lebih lambat, membutuhkan waktu hampir 21 menit. Selain itu, karena Louvain digunakan, komunitas yang dihasilkan tidak dijamin akan terhubung dengan baik.
Ini membuat NetworkX dengan NX-Cugraph 315x lebih cepat dalam memberikan hasil kualitas yang lebih tinggi daripada NetworkX Louvain pada CPU.
Untuk menjalankan Leiden atau Louvain berdasarkan keberadaan implementasi Leiden (saat ini hanya tersedia melalui NX-Cugraph) Gunakan kode berikut:
%%time
try:
communities = nx.community.leiden_communities(G)
except NotImplementedError:
print("leiden not available (is the cugraph backend enabled?), using louvain.")
communities = nx.community.louvain_communities(G)
num_communities = len(communities)
print(f"Number of communities: {num_communities}")
Perangkat Lunak: NetworkX 3.5, Cugraph/NX-Cugraph 25.10; CPU: Intel Xeon Gold 6128 CPU @ 3.40 GHz 48 GB RAM; GPU: NVIDIA QUADRO RTX 8000 48 GB RAM
Node grafik mewarnai oleh komunitas dan plot sepele di NetworkX (Gambar 3).
Ketika NetworkX menambahkan dukungan CPU untuk Leiden, baik sebagai implementasi python asli atau sebagai backend CPU terpisah, pengguna dapat memanfaatkan fungsionalitas nol-kode-perubahan dengan memiliki satu panggilan fungsi “portabel” tunggal yang berfungsi, meskipun mungkin lebih lambat, pada platform tanpa GPU.
Contoh sebelumnya dimaksudkan untuk hanya menunjukkan bagaimana NX-Cugraph dapat GPU mempercepat algoritma NetworkX yang biasa digunakan dalam genomik pada data genomik dunia nyata. Untuk mengeksplorasi contoh yang lebih realistis dan dibangun khusus, lihat proyek Rapids-Singlecell, yang menawarkan perpustakaan yang dirancang khusus untuk masalah genomik.
Rapids-Singlecell adalah paket inti Scverse berdasarkan pustaka scanpy populer, mendukung API yang kompatibel dengan Anndata, dan dioptimalkan untuk analisis sel tunggal pada dataset besar. Kecepatan yang mengesankan dari skala rapids-singlecell pada skala berasal dari Cugraph dan perpustakaan Cuda-X DS lainnya yang menyediakan akselerasi GPU untuk panggilannya ke Leiden dan banyak algoritma lainnya. Untuk mempelajari lebih lanjut, lihat mengemudi menuju analisis sel miliar dan terobosan biologis dengan rapids-singlecell.
Mulai menjalankan alur kerja Leiden bertenaga GPU
Cugraph menyediakan kinerja deteksi komunitas terbaik di kelasnya melalui implementasi Leiden yang dipercepat GPU, tersedia untuk para ilmuwan data di Python dari Cugraph Python Library atau perpustakaan NetworkX yang populer dan fleksibel melalui backend NX-Cugraph. Kinerja hingga 47x lebih cepat, mungkin lebih, lebih dari implementasi CPU yang sebanding berarti genomik dan banyak aplikasi lain yang mengandalkan deteksi masyarakat dapat meningkatkan data mereka dan memecahkan masalah yang lebih besar dalam waktu yang jauh lebih sedikit.
Untuk memulai, lihat Panduan Instalasi Rapids atau kunjungi repo Rapidsai/Cugraph atau Rapidsai/NX-Cugraph untuk menjalankan alur kerja Leiden bertenaga GPU Anda.
Cara mempercepat deteksi komunitas di Python menggunakan Leiden bertenaga GPU