Community Detection & Centrality: Teori & Aplikasi

Pada sebuah data graph (network) seperti data dari media sosial bagaimana kita mengetahui user yang paling berpengaruh? Jika diterapkan pada riset pemasaran atau bahkan riset secara umum, bagaimana kita mengetahui sebenarnya berapa banyak komunitas yang ada di data? Artikel ini akan berusaha menjawab kedua pertanyaan tersebut.

Walau berkaitan, artikel ini bukanlah sekuel dari artikel sebelumnya (crawling twitter dan preprocessing data text). Karena apa yang dibahas di artikel ini sebenarnya dapat diterapkan pada sembarang graph analysis, tidak harus twitter/Facebook, atau bahkan sebenarnya tidak harus data sosial media. Lagi pula kalau artikelnya nyambung terus, nanti jadi kayak script sinetron ‘Gan … :D …

Pendahuluan: sekilas teori

Dasar Teori graph (Matematika-Diskrit)

Mari kita mulai dengan mengenal apa itu graph. Bagi mereka yang memiliki latar belakang Matematika atau Teknik mungkin sudah tidak asing dengan istilah ini.  Graph mirip sebuah network/atau jaringan yang terdiri dari nodes dan sesuatu yang menghubungkan antar nodes tersebut. Secara sedikit lebih formal sebuah graph G adalah pasangan dua buah himpunan: vertex (jamak vertices) dan edges. Yes bro, graph punya pasangan, jadi yang masih Jones bisa belajar dari si graph … :v … kidding ‘Gan … ayo kita lanjut…. :) #JangandiBataYa … :D ….

Beberapa contoh Graph

Gambar 1. Beberapa contoh Graph (G) yang identik (isomorfis).

  • Nodes/vertex (Indonesia: simpul): ‘Biasa’nya memiliki simbol V={v1,v2,…,vn}, pada gambar 1 V={1,2,3,4}. Nodes/vertex dalam data media sosial dapat menyatakan  user, dalam GIS (geographical information system) bisa menyatakan tempat/kota,  dalam jaringan komputer menyatakan nodes (workstation), dan dalam statistik (stokhastik) dapat menyatakan keadaan (state). Misal keadaan ngenes, jones, dan tongpes … :v … intinya vertex bisa menjadi simbol apa saja.
  • Edges (Indonesia: tepi): ‘Biasa’nya memiliki simbol E={e1,e2,…,em},  pada gambar 1 adalah garis yang menghubungkan antar vertex: {(1,2),(2,3),(3,4),(1,4)}. Makna edge bergantung dari makna simbolis vertexnya dan definisi sang pengguna graph. Edge dalam media sosial dapat berupa mention, friend, follower ,… atau bisa juga stalker alias barisan para mantan … :v … Maaf ndak maksud nyindir para jones lagi … :p

Properties/Sifat graph:

  • Pemarah, bawel, dan ga perhatian … oh wait … bukan bukan ….
  • Karena graph tadi didefinisikan sebagai pasangan “Himpunan”, maka tidak ada sifat keterurutan. Maksudnya? … ingat kan pelajaran himpunan waktu SD dulu di MIT/Harvard? ketiga himpunan A={1,2,3,4}, B={3,1,2,4}, dan C={2,2,4,1,3} sebenarnya sama, atau A=B=C. Itulah mengapa kalau di bahasa pemrograman seperti Python, struktur data “set” pasti unik nilainya dan tidak memiliki index (seperti kata Emak, set di Python itu not callable seperti list tapi iterable).
  • Terus kalau tidak terurut apa konsekuensinya? apa berarti tidak boleh dipijat juga?… bukan ‘Gan, graph ndak lagi keseleo …. konsekuensinya cara kita menamakan vertex/edge menjadi tidak kaku. Jadi lebih luwes gitu deh, walau ga dipijet/urut tadi ‘Gan … :D ….
  • Graph “biasanya” tidak meng-indahkan lokasi, tapi hanya sifat keterhubungannya. Artinya si graph ga tau si Indah lagi ada dimana sekarang … eh salah … gampangnya gini deh, ke empat graph di Gambar 1 sebenarnya semua sama bin idem. Istilah kerennya ke-4 graph di gambar 1 Isomorfis. Walau bentuknya berbeda-beda, tapi mereka tetap satu juga … eh… maksudnya pasangannya tetap sama. Misal vertex 1 terhubung dengan 4 dan 2, 3 dengan 4 dan 2, dsb. …Gampangnya gini deh… ke-4 graph di gambar 1 itu vertex selingkuhannya sama kan ‘Gan? … nah ngerti dah dia …. (TS ga ngajarin selingkuh ya … :D … )

Udah dulu dah bahas sifatnya, kata Pak Ustadz takutnya nanti jatuhnya Ghibah …. nanti kita bahas lebih lanjut saja di lain waktu ketika saya buat artikel khusus tentang graph.

Tipe Graph

Graph ada beberapa tipe kayak perumahan : tipe 21, 36, dan 45…. eh … salah maksudnya bukan itu. Ada yang punya arah ada yang nggak, ada yang sederhana ada yang edge-nya multiple, ada yang kayak tree ada yang kayak … macam-macam dah. Seperti yang ditunjukkan di gambar 2, atau kalau mau mengetahui lebih lanjut bisa baca disini. Karena artikel ini tidak khusus membahas tentang Graph, jadi kita ndak usah bahas terlalu dalam, kata anak jaman sekarang ndak usah BaPer … :D …

Contoh berbagai tipe Graph

Gambar 2. Contoh berbagai tipe Graph

Aplikasi Graph

Teori Graph memiliki banyak aplikasi, tentu saja tidak hanya untuk menganalisa data media sosial. Graph bisa di aplikasikan di masalah Biologi, sosiologi, ilmu komputer, fisika, dan masih banyak lagi. Sebagian kecilnya dijelaskan disini. Saking jamaknya graph ini, bahkan saat ini ada NoSQL (read more here) yang khusus untuk data graph (Neo4J).

Centrality

Akhirnya kita sampai ke inti dari artikel ini. Di teori graph centrality mencoba mengidentifikasi vertex-vertex yang paling “penting”. Untuk apa? Misal mencari orang yang paling berpengaruh di media sosial, tapi ndak cuma itu saja. Konsep centrality juga digunakan di berbagai penelitian di berbagai bidang ilmu lain, mulai dari teknik sipil, sosiologi, biologi, dll. Apakah Agan termasuk orang penting di media sosial? Silahkan dicoba saja di analisis dengan teknik yang dibahas di artikel ini … :D … Kalau iya, mungkin Agan bisa mencalonkan diri di Pilkada besok …. :)

Ada keterbatasan yang harus diingat. vertex-vertex yang dinyatakan penting oleh suatu algoritma dan pada suatu data graph tertentu, jarang bisa digeneralisasi pada kasus yang lain dengan setting yang sama. Keterbatasan berikutnya adalah centrality menggunakan konsep ranking, walau centrality memiliki ukuran skor, namun kadang tidak terlalu bermanfaat selain untuk mengurutkan tingkat kepentingan. Bayangkan hasil pencarian Google, walau hasilnya diurutkan berdasarkan skor ranking, namun di halaman-halaman berikutnya seringnya tidak relevan dengan apa yang kita cari.

Ada beberapa cara mencari centrality pada suatu graph, berikut contoh beberapa caranya:

  1. Yang paling mudah adalah dengan melihat derajat (degree) dari vertex di graphnya. Derajat disini bukan suhu/temperatur ya, degree juga bukannya sarjana, master, atau doktor … :D …. derajat/degree dari suatu vertex di sebuah graph dihitung dengan cara menghitung edge yang terhubung dengan vertex tersebut. Misal di gambar satu degre semua vertexnya sama, yaitu 2. Di graph pertama pada gambar 2, derajatnya 3, 2, 3, dan 2.
  2. Closeness: Pada graph yang terhubung (connected), kata si Bavelas centrality suatu vertex berbading terbalik dengan total jarak ke vertex lain (disebut farness). Atau menggunakan bahasa allien ditulis sebagai $latex C(x)=\frac{1}{\sum_y d(y,x)}$, dimana d(y,x) adalah jarak dari vertex x ke vertex y.
  3. Betweenness: Betweeness centrality dilakukan dengan cara menghitung berapa kali sebuah vertex digunakan sebagai penghubung (bridge) antar 2 jarak terpendek dari suatu path. Riweuh ya ? cara hitungnya gini:
    a. untuk setiap pasang vertex (vi,vj) hitung shortest path-nya.
    b. Hitung berapa kali vertex x dilalui shortest path-shortest path di langkah sebelumnya.
    c. Jumlahkan.
    Dengan bahasa planet Namek langkah diatas ditulis sebagai: $latex C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}} $, dimana  $latex \sigma_{st}$ adalah total banyaknya jarak terpendek dari vertex s ke t, dan $latex \sigma_{st}(v) $ adalah banyaknya yang melalui v.
  4. Eigenvector Centrality: Tau eigenvektor kan Gan? kalau ngga berarti ente bolos pas kuliah ALin (Aljabar Linier). Kalau belum pernah ambil mata kuliah ini, ambil lah ‘Gan…. ini mata kuliah keren Gan, banyak yang terharu sepanjang semester … :) … Eigenvektor centrality dihitung dengan persamaan Matematis sederhana berikut: $latex Ax = \lambda x $. Dimana A adalah graph kita, namun dinyatakan dengan graph adjacency (keterhubungan). Menurut teorema Frobenius, katanya solusi positif dari eigenvalue terbesar menyatakan tingkat kepentingan (centrality) dari vertexnya.
    .
    Google PageRank (algoritma awal Google) memakai konsep ini. keren kan ? … ^_^ … O iya, anak Matematik/Statistik kalau punya waktu luang, bisa juga mengkaitkan ini dengan Long-Run Markov Chain di Stokhastik lo…. coba deh … ya coba ya … mau kan? … #maksa :v Bagi yang tertarik, silahkan baca lebih lanjut di kitab berikut Gan, gratis kok, silahkan langsung disedot … :D …
    Phillip Bonacich: Power and Centrality: A Family of Measures. American Journal of Sociology 92(5):1170–1182, 1986
  5. Katz Centrality: Centrality yang ini menghitung banyaknya vertex yang bisa dihubungkan melalui suatu path, tapi dengan memberikan penalti vertex yang jauh (kontribusi vertex yang jauh lebih kecil). Picolo dari planet Namek pernah bilang: [latex] x_i = \alpha \sum_{j} A_{ij} x_j + \beta [/latex], dimana A adalah matriks adjacency dari graph G dengan eigenvalues $latex \lambda $.
    Parameter ß mengatur centrality awal dan [latex] \alpha < \frac{1}{\lambda_{max}} [/latex] menghitung pengaruh relatif dari suatu vertex dengan menghitung vertex-vertex yang terhubung langsung dengan vertex x dan vertex lain yang terhubung dengan vertex-vertex tersebut.
    _
    Katz centrality dikupas tuntas di paper berikut, silahkan di unduh sebelum kehabisan … :D … Leo Katz: A New Status Index Derived from Sociometric Index. Psychometrika 18(1):39–43, 1953

Community :

Dalam media sosial kita sebenarnya ada komunitas-komunitas kan ya? misal keluarga/saudara, teman SMA, teman kuliah, teman kerja, barisan para mantan (kalau belum di remove), atau mereka yang potensial jadi jodoh (bagi yang jones) … :D … Intinya secara eksplisit atau implisit ada suatu komunitas-komunitas tertentu dalam data graph/network dari media sosial kita. “Community detection” berusaha secara automatis untuk menangkap struktur-struktur ini. Kalau Agan pernah belajar clustering (unsupervised learning), community detection melakukan hal yang kurang lebih sama seperti itu.

Buat apa menemukan komunitas di data kita? banyak alasannya, misal untuk teknik sampling yang lebih baik (baca cluster sampling disini), atau targeted advertising (SEO), atau analisa lain seperti yang kita lakukan ketika kita melakukan analisa cluster (pengelompokkan). Ada cukup banyak algoritma untuk menemukan community dalam suatu graph, sebut saja Minimum-cut method, Hierarchical clustering, Girvan–Newman algorithm, Modularity maximization, dan Clique based methods. Namun dalam artikel ini community detection yang akan digunakan adalah yang ini nih : Fast unfolding of communities in large networks, Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Renaud Lefebvre, Journal of Statistical Mechanics: Theory and Experiment 2008(10), P10008 (12pp)

Requirements

Karena saya sudah agak bosan ngetik tentang teori, mari kita mulai saja aplikasi langsung dari centrality dan community detection. Sebagaimana kalau mau masak harus disiapkan terlebih dahulu bahan-bahannya, kita juga mulai dengan memeriksa terlebih dahulu daftar hal yang harus disiapkan.

  1. Kita akan menggunakan data tweet seputar Pak Walikota ganteng Ridwan Kamil dari post sebelumnya (Link).
  2. Modul Python yang kita butuhkan untuk artikel kali ini adalah NetwokX, matplotlib, operator, dan community. Cara install modul-modul tersebut sama seperti yang sudah dijelaskan di artikel saya sebelumnya. Kecuali Community!!!… Stop jangan lakukan perintah ini “pip install community”. Kalau sudah terlanjur uninstall terlebih dahulu dengan perintah “pip uninstall community”.
  3. Cara install modul community:
    a. unduh modulnya disini https://bitbucket.org/taynaud/python-louvain/downloads [Linknya di kiri bawah].
    b. Extract file zip yang baru saja di unduh.
    c. dengan terminal/shell/command prompt ketikkan perintah berikut:
  4. Code yang digunakan di artikel ini bisa di unduh disini.

 The Code

Mari kita perhatikan terlebih dahulu code kita, penjelasan singkat diberikan dibawah:

  • Baris 1 & 2: import Modul yang dibutuhkan.
  • Baris 4-9: Bisa dirubah sesuai keinginan. Nimportant adalah variabel berapa banyak user penting yang ingin dikeluarkan di output. MaxDegree adalah ambang (threshold) untuk menemukan user dengan derajat yang terbesar.
  • Baris 11-20: Fungsi untuk load data Json dari crawling yang kita lakukan di artikel sebelumnya.
  • Baris 22-38: merubah data tweet menjadi data Graph. Saya mengggunakan user sebagai vertex dan mention sebagai edge. Please note, edge juga bisa didefiniskan dengan “follower” dan bukannya mention. Biasanya nanti hasil graphnya lebih bagus. Saya gunakan mention untuk kemudahan saja.
  • Baris 40-48: ini fungsi untuk melakukan centrality analysis. Defaultnya saya menggunakan eigenvector. Tapi kalau mau diganti dengan algoritma Katz, silahkan hapus tanda “#” di baris 42 dan 43, lalu tambahkan tanda “#” di depan baris 44.
  • Baris 50-58: Fungsi ini memilah user berdasarkan derajat (degree)-nya. Penjelasan sederhananya, jika user sering di mention atau melakukan mention maka derajatnya akan semakin besar.
  • Baris 60-72: menyimpan hasil perhitungan ke dalam file teks untuk keperluan lebih lanjut.
  • Please lakukan perubahan di baris 82-84 sendiri, saya ndak sempat eksperimen dengan setting ini untuk mendpaatkan hasil graph yang terbaik.

Done!!!… seperti biasa, programnya dapat dijalankan dengan menekan tombol “F5” di Spyder atau jalankan melalui command prompt (shell/terminal) dengan perintah berikut:

Silahkan lihat hasilnya di folder dimana code python anda berada.

Catatan dan Code Limitations:

  • Anda bisa custom baris 79-88 untuk menggambar Full Networknya (Ganti Gt dengan G). Tapi hati-hati biasanya butuh komputasi yang cukup banyak, yakinkan dijalankan di komputer anda yang paling cepat.
  • Buat latihan, coba modifikasi code-nya jadi Graph berdasarkan follower.
  • Saya baru menerangkan bagaimana mendeteksi community-nya, saya belum membahas bagaimana meng-interpretasi hasil communitynya. Di artikel yang lain saya akan membahas topik modelling, cluster summarization, dan kawan-kawannya.
  • Seperti biasa kalau ada pertanyaan atau muncul error, silahkan komen dibawah dengan pesan error yg muncul.

Cheers,

< / TES >® ~ BNE 01/17/2016,11:35:06

8 thoughts on “Community Detection & Centrality: Teori & Aplikasi

    • Secara umum Community detection adalah graph clustering, di kasus tertentu lebih cocok disebut graph partitioning.
      Clustering sendiri domainnya lebih luas: numeric, nominal, ordinal, text, dll (termasuk graph)

  1. Loading Data ….
    Tunggu sebentar, membentuk Graph Networknya….

    0%| | 0/596 [00:00<?, ?it/s]
    100%|##########| 596/596 [00:00<00:00, 5900.99it/s]
    Selesai! G= 637 vertices dan 206 edges
    Network of 'important' users…
    Centrality Analysis, mencoba menemukan user-user penting …
    Traceback (most recent call last):
    File "C:\Users\AteServer\Desktop\GcomCentral.py", line 80, in
    Gt,important_nodes = most_important(G,Nimportant)#output graph user penting & list:[names,rankingscore]
    File “C:\Users\AteServer\Desktop\GcomCentral.py”, line 44, in most_important
    ranking = nx.eigenvector_centrality_numpy(G)
    File “C:\Users\AteServer\Desktop\lib\site-packages\networkx\algorithms\centrality\eigenvector.py”, line 199, in eigenvector_centrality_numpy
    import scipy as sp
    ImportError: No module named ‘scipy’

    sy pake command prompt windows. pas install scipy

    cmd: python -m pip install scipy

    Running setup.py bdist_wheel for scipy error

    failed building wheel for scipy

    mohon arahan sifu

Leave a Reply