Ilmu Data Grafik Dengan Python/NetworkX

Kami kebanjiran data. Basis data dan spreadsheet yang terus berkembang penuh dengan wawasan bisnis tersembunyi. Bagaimana kita bisa menganalisis data dan mengekstrak kesimpulan ketika ada begitu banyak? Grafik (jaringan, bukan grafik batang) memberikan pendekatan yang elegan.

Kita sering menggunakan tabel untuk merepresentasikan informasi secara umum. Tetapi grafik menggunakan struktur data khusus: Alih-alih baris tabel, simpul mewakili elemen. Tepi menghubungkan dua node untuk menunjukkan hubungan mereka.

Struktur data grafik ini memungkinkan kita untuk mengamati data dari sudut yang unik, itulah sebabnya ilmu data grafik digunakan di setiap bidang mulai dari biologi molekuler hingga ilmu sosial:

Jadi bagaimana pengembang dapat memanfaatkan ilmu data grafik? Mari kita beralih ke bahasa pemrograman ilmu data yang paling banyak digunakan: Python.

Memulai Dengan Grafik "Teori Grafik" dengan Python

Pengembang Python memiliki beberapa pustaka data grafik yang tersedia untuk mereka, seperti NetworkX, igraph, SNAP, dan graph-tool. Selain pro dan kontra, mereka memiliki antarmuka yang sangat mirip untuk menangani dan memproses struktur data grafik Python.

Kami akan menggunakan perpustakaan NetworkX yang populer. Mudah dipasang dan digunakan, dan mendukung algoritme deteksi komunitas yang akan kami gunakan.

Membuat grafik baru dengan NetworkX sangatlah mudah:

 import networkx as nx G = nx.Graph()

Tapi G belum banyak menjadi grafik, karena tidak memiliki node dan edge.

Cara Menambahkan Node ke Grafik

Kita dapat menambahkan node ke jaringan dengan merantai nilai kembalian Graph() dengan .add_node() (atau .add_nodes_from() untuk beberapa node dalam daftar). Kami juga dapat menambahkan karakteristik atau atribut arbitrer ke node dengan melewatkan kamus sebagai parameter, seperti yang kami tunjukkan dengan node 4 dan node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Ini akan menghasilkan:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Tapi tanpa tepi antar node, mereka terisolasi, dan dataset tidak lebih baik dari tabel sederhana.

Cara Menambahkan Tepi ke Grafik

Mirip dengan teknik untuk node, kita dapat menggunakan .add_edge() dengan nama dua node sebagai parameter (atau .add_edges_from() untuk beberapa edge dalam daftar), dan secara opsional menyertakan kamus atribut:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

Pustaka NetworkX mendukung grafik seperti ini, di mana setiap tepi dapat memiliki bobot. Misalnya, dalam grafik jaringan sosial di mana node adalah pengguna dan edge adalah interaksi, bobot dapat menandakan berapa banyak interaksi yang terjadi antara sepasang pengguna tertentu—metrik yang sangat relevan.

NetworkX mencantumkan semua edge saat menggunakan G.edges , tetapi tidak menyertakan atributnya. Jika kita menginginkan atribut edge, kita dapat menggunakan G[node_name] untuk mendapatkan semua yang terhubung ke sebuah node atau G[node_name][connected_node_name] untuk mendapatkan atribut edge tertentu:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Ini akan menghasilkan:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

Tetapi membaca grafik pertama kami dengan cara ini tidak praktis. Untungnya, ada representasi yang jauh lebih baik.

Cara Menghasilkan Gambar Dari Grafik (dan Grafik Berbobot)

Memvisualisasikan grafik sangat penting: Ini memungkinkan kita melihat hubungan antara node dan struktur jaringan dengan cepat dan jelas.

Panggilan cepat ke nx.draw(G) adalah semua yang diperlukan:

Mari kita buat tepi yang lebih berbobot juga lebih tebal melalui panggilan nx.draw() kita:

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Kami menyediakan ketebalan default untuk tepi tanpa bobot, seperti yang terlihat pada hasil:

Metode dan algoritme grafik kami akan menjadi lebih kompleks, jadi langkah selanjutnya adalah menggunakan kumpulan data yang lebih dikenal.

Grafik Data Science Menggunakan Data Dari Film Star Wars: Episode IV

Untuk membuatnya lebih mudah untuk menafsirkan dan memahami hasil kami, kami akan menggunakan dataset ini. Node mewakili karakter penting, dan tepi (yang tidak diberi bobot di sini) menandakan penampilan bersama dalam sebuah adegan.

Catatan: Dataset berasal dari Gabasova, E. (2016). Jejaring sosial Star Wars. DOI: https://doi.org/10.5281/zenodo.1411479.

Pertama, kita akan memvisualisasikan data dengan nx.draw(G_starWars, with_labels = True) :

Karakter yang biasanya muncul bersamaan, seperti R2-D2 dan C-3PO, tampak berhubungan erat. Sebaliknya, kita dapat melihat bahwa Darth Vader tidak berbagi adegan dengan Owen.

Tata Letak Visualisasi Python NetworkX

Mengapa setiap node terletak di tempat pada grafik sebelumnya?

Ini adalah hasil dari algoritma spring_layout default. Ini mensimulasikan kekuatan pegas, menarik simpul yang terhubung dan menolak yang terputus. Ini membantu menyoroti node yang terhubung dengan baik, yang berakhir di tengah.

NetworkX memiliki tata letak lain yang menggunakan kriteria berbeda untuk memposisikan node, seperti circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

Hasil:

Tata letak ini netral dalam arti bahwa lokasi sebuah node tidak bergantung pada kepentingannya—semua node direpresentasikan secara setara. (Tata letak melingkar juga dapat membantu memvisualisasikan komponen terhubung yang terpisah —subgraf yang memiliki jalur antara dua node mana pun—tetapi di sini, seluruh grafik adalah satu komponen besar yang terhubung.)

Kedua tata letak yang telah kita lihat memiliki tingkat kekacauan visual karena tepinya bebas untuk melintasi tepi lainnya. Tapi Kamada-Kawai, algoritme lain yang diarahkan secara paksa seperti spring_layout , memposisikan node untuk meminimalkan energi sistem.

Ini mengurangi persilangan tepi tetapi dengan harga: Ini lebih lambat daripada tata letak lain dan oleh karena itu tidak sangat disarankan untuk grafik dengan banyak simpul.

Yang ini memiliki fungsi undian khusus:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Itu menghasilkan bentuk ini sebagai gantinya:

Tanpa intervensi khusus, algoritme menempatkan karakter utama (seperti Luke, Leia, dan C-3PO) di tengah, dan karakter yang kurang menonjol (seperti Camie dan General Dodonna) di perbatasan.

Memvisualisasikan grafik dengan tata letak tertentu dapat memberi kita beberapa hasil kualitatif yang menarik. Namun, hasil kuantitatif adalah bagian penting dari analisis ilmu data apa pun, jadi kita perlu mendefinisikan beberapa metrik.

Analisis Node: Derajat dan PageRank

Sekarang kita dapat memvisualisasikan jaringan kita dengan jelas, mungkin menarik bagi kita untuk mengkarakterisasi node. Ada beberapa metrik yang menggambarkan karakteristik node dan, dalam contoh kita, karakter.

Satu metrik dasar untuk sebuah simpul adalah derajatnya: berapa banyak tepi yang dimilikinya. Derajat simpul karakter Star Wars mengukur berapa banyak karakter lain yang mereka ajak berbagi adegan.

Fungsi degree() dapat menghitung derajat karakter atau seluruh jaringan:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

Output dari kedua perintah:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

Pengurutan node dari tertinggi ke terendah menurut derajat dapat dilakukan dengan satu baris kode:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

Hasil:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

Menjadi hanya total, derajat tidak memperhitungkan detail tepi individu. Apakah tepi yang diberikan terhubung ke simpul yang terisolasi atau ke simpul yang terhubung dengan seluruh jaringan? Algoritme PageRank Google mengumpulkan informasi ini untuk mengukur seberapa "penting" sebuah simpul dalam jaringan.

Metrik PageRank dapat diartikan sebagai agen yang bergerak secara acak dari satu node ke node lainnya. Node yang terhubung lebih baik memiliki lebih banyak jalur yang melaluinya, sehingga agen akan cenderung lebih sering mengunjunginya.

Node tersebut akan memiliki PageRank yang lebih tinggi, yang dapat kita hitung dengan library NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

Ini mencetak peringkat Luke dan karakter kami diurutkan berdasarkan peringkat:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Owen adalah karakter dengan PageRank tertinggi, melampaui Luke yang memiliki gelar tertinggi. Analisis: Meskipun Owen bukanlah karakter yang paling banyak berbagi adegan dengan karakter lain, dia adalah karakter yang berbagi adegan dengan banyak karakter penting seperti Luke sendiri, R2-D2, dan C-3PO.

Sebaliknya, C-3PO, karakter dengan derajat tertinggi ketiga, adalah karakter dengan PageRank terendah. Meskipun C-3PO memiliki banyak koneksi, banyak dari mereka dengan karakter yang tidak penting.

Kesimpulan: Menggunakan beberapa metrik dapat memberikan wawasan yang lebih mendalam tentang karakteristik berbeda dari simpul grafik.

Algoritma Deteksi Komunitas

Saat menganalisis jaringan, mungkin penting untuk memisahkan komunitas : kelompok node yang sangat terhubung satu sama lain tetapi minimal terhubung dengan node di luar komunitas mereka.

Ada beberapa algoritma untuk ini. Sebagian besar dari mereka ditemukan dalam algoritme pembelajaran mesin yang tidak diawasi karena mereka menetapkan label ke node tanpa perlu diberi label sebelumnya.

Salah satu yang paling terkenal adalah propagasi label . Di dalamnya, setiap node dimulai dengan label unik, dalam komunitas satu. Label node diperbarui secara iteratif sesuai dengan mayoritas label node tetangga.

Label menyebar melalui jaringan sampai semua node berbagi label dengan sebagian besar tetangga mereka. Kelompok node yang terhubung erat satu sama lain akhirnya memiliki label yang sama.

Dengan pustaka NetworkX, menjalankan algoritme ini hanya membutuhkan tiga baris Python:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

Hasil:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

Dalam daftar set ini, setiap set mewakili komunitas. Pembaca yang akrab dengan film akan melihat algoritme berhasil memisahkan "orang baik" dari "orang jahat", membedakan karakter secara bermakna tanpa menggunakan label atau metadata (komunitas) yang sebenarnya.

Wawasan Cerdas Menggunakan Ilmu Data Grafik dengan Python

Kami telah melihat bahwa memulai dengan alat ilmu data grafik lebih mudah daripada kedengarannya. Setelah kami merepresentasikan data sebagai grafik menggunakan pustaka NetworkX dengan Python, beberapa baris kode pendek dapat mencerahkan. Kami dapat memvisualisasikan kumpulan data kami, mengukur dan membandingkan karakteristik simpul, dan mengelompokkan simpul secara bijaksana melalui algoritme deteksi komunitas.

Memiliki keterampilan untuk mengekstrak kesimpulan dan wawasan dari jaringan menggunakan Python memungkinkan pengembang untuk berintegrasi dengan alat dan metodologi yang biasa ditemukan di jalur layanan ilmu data. Dari mesin pencari hingga penjadwalan penerbangan hingga teknik elektro, metode ini dapat diterapkan dengan mudah ke berbagai konteks.

Bacaan yang Direkomendasikan tentang Ilmu Data Grafik

Algoritma Deteksi Komunitas
Zhao Yang, Rene Algesheimer, dan Claudio Tessone. “Analisis Perbandingan Algoritma Deteksi Komunitas pada Jaringan Buatan.” Laporan Ilmiah, 6, no. 30750 (2016).

Pembelajaran Mendalam Grafik
Thomas Kipf. “Jaringan Konvolusi Grafik.” 30 September 2016.

Aplikasi Ilmu Data Grafik
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein, dan Pablo Balenzuela. “Memprediksi Pergeseran Individu Menggunakan Penambangan Teks dan Pembelajaran Mesin Grafik di Twitter.” (24 Agustus 2020): arXiv:2008.10749 [cs.SI].

Cohen, Elior. “Pertemuan PyData Tel Aviv: Node2vec.” Youtube. 22 November 2018. Video, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.