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 ….

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 listtapi 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 …

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:
   1	python setup.py install

4. Code yang digunakan di artikel ini bisa di unduh disini.

 The Code

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112

import json,time,operator,community,networkx as nx,matplotlib.pyplot as plt from tqdm import * fnames=["data\\RidwanKamil_Tweets_28Nov-19Des_2015.json"]#bisa ditambahkan data lain di list ini Nimportant=12 #Number of important Nodes MaxDegree=100 fimportant='important_users.txt' fcommunity='community_users.txt' fdegree='high_degree_users.txt' def LoadData(fnames):     print("Loading Data .... ")     data=[]     for file in fnames:         ftweet=open(file,encoding='utf-8', mode='r')         tmp=ftweet.readlines()         tmp=[line.strip() for line in tmp]         ftweet.close()         data=data+tmp     return data def build_graph(data):     print("Tunggu sebentar, membentuk Graph Networknya.... ")     G=nx.Graph()     for status in tqdm(data):         try:             status=json.loads(status)#tweet=status["text"].lower()             usr=status["user"]["screen_name"]             G.add_node(usr)             mentions=status["entities"]["user_mentions"]             for mention in mentions:                 usr_mention=mention["screen_name"]#No need G.add_node(usr_mention)                 G.add_edge(usr,usr_mention)# node automatically added if don't exist         except:             pass     Nn=G.number_of_nodes();Ne=G.number_of_edges()     print('Selesai! G= %d vertices dan %d edges' %(Nn,Ne))     return G,Nn,Ne def most_important(G,Nimportant):     print("Centrality Analysis, mencoba menemukan user-user penting ...")     # phi = (1+math.sqrt(5))/2.0 # largest eigenvalue of adj matrix     # ranking = nx.katz_centrality_numpy(G,1/phi)     ranking = nx.eigenvector_centrality_numpy(G)     important_nodes = sorted(ranking.items(), key=operator.itemgetter(1))[::-1][0:Nimportant]#list 2 kolom label dan derajat centralitynya     dnodes=[n[0] for n in important_nodes]     Gt = G.subgraph(dnodes)     return Gt,important_nodes def trim_nodes(G,d):     """ returns a copy of G without the nodes with a degree less than d """     dn = nx.degree(G)     chosen=[]     for n in G.nodes():         if dn[n] >= d:             chosen.append(n)     Gt=G.subgraph(chosen)     return Gt def writetofile(file,var):     n=len(var)     with open(file,'w') as f:         for i in range(n):             f.write('%s\t %.3f\n' %(var[i][0],var[i][1])) def writecommunity(fcommunity,part_len,part_members):     with open(fcommunity,'w') as f:         for com in part_len:             f.write('community %d\t N=%d\t users= ' %(com,part_len[com]))             for usr in part_members[com]:                 f.write('%s ' %(usr))             f.write('\n') if __name__ == '__main__':     data=LoadData(fnames)     G,Nn,Ne=build_graph(data) #Membuat Graph sosial Networknya     # Draw hanya network important user saja, untuk menghemat komputasi     print("Network of 'important' users...",flush=True)     Gt,important_nodes = most_important(G,Nimportant)#output graph user penting & list:[names,rankingscore]     pos=nx.spring_layout(Gt,k=33)     nx.draw_networkx_nodes(Gt,pos,node_color='r',alpha=0.2,node_size=254,with_labels=True)     nx.draw_networkx_labels(Gt,pos,font_size=12,font_color='black')# also the labels this time     nx.draw_networkx_edges(Gt,pos,edge_color='blue',alpha=0.1)#width=4     # Please rubah sendiri settingnya utuk mendapatkan hasil yang bagus, saya ndak bakat untuk hal ini...     plt.savefig("Graph_User_Penting.png")     writetofile(fimportant,important_nodes)# Simpan ke File untuk analisa lebih lanjut     plt.show() #Menampilkan graphnya     partition = community.best_partition(G) # Menemukan community dengan partisi terbaik     Np=len(set(partition.values()))     part_members=dict();part_len=dict()     for usr,par in partition.items():         if par not in part_members.keys():             part_members[par]=[usr]             part_len[par]=1         else:             part_members[par]=part_members[par]+[usr]             part_len[par]+=1     writecommunity(fcommunity,part_len,part_members) # Simpan ke File untuk analisa lebih lanjut     # Menggunakan degree untuk menentukan important user     Gtrim = trim_nodes(G,MaxDegree)     Gtdegree=nx.degree(Gtrim)#return dictionary[nodes]=degree     nodeDeg=[[n,Gtdegree[n]] for n in Gtdegree]     writetofile(fdegree,nodeDeg)     NGtrim=Gtrim.number_of_nodes()     print('Graph dengan vertex ber-degree > %d , total %d nodes' %(MaxDegree,NGtrim))     pos=nx.spring_layout(Gtrim,k=33)#pos=nx.random_layout(Gt)     nx.draw(Gtrim,pos,with_labels=True,font_color='black',edge_color='blue')#nx.draw(Gt,node_size=1,node_color='w',edge_color='b',alpha=.2)     plt.savefig("Graph_Chosen_Degree.png")     plt.show()

• 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:

1	C:\Folder_dimana_code_anda_berada\python GcomCentral.py

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