Path: Top > S3-Dissertations > Electrical Engineering and Informatics-STEI > 2018

STRATEGI PEMBENTUKAN SAMPEL GRAF PADA JEJARING SOSIAL SKALA BESAR UNTUK REDUKSI PROSES PERHITUNGAN METRIK BETWEENNESS CENTRALITY

GRAPH SAMPLING FORMATION STRATEGY IN LARGE SCALE SOCIAL NETWORK FOR REDUCING BETWEENNESS CENTRALITY METRIC COMPUTATION PROCESS

PhD Theses from JBPTITBPP / 2018-03-01 10:32:03
Oleh : Andry Alamsyah (NIM : 33212017), S3 - Electrical Engineering and Informatics-STEI
Dibuat : 2018-03-01, dengan 1 file

Keyword : Graph Theory, Social Network Analysis, Betweenness Centrality, Large-Scale Social Network, Computational Complexity, Graph Sampling, Random Walks, Graph Pruning

Aktivitas manusia pada layanan jejaring sosial online seperti Twitter, Facebook, Linkedin dan lainnya meningkat dewasa ini. Peningkatan aktivitas diiringi dengan peningkatan jumlah konten yang diproduksi oleh para pengguna layanan tersebut. Ekstraksi informasi dari jejak digital manusia yang berupa konten tersebut dapat digunakan untuk memahami perilaku manusia dan lingkungan sosialnya. Pada umumnya atribut data pada layanan tersebut tidak tersedia lengkap atau disebut sebagai data tidak terstruktur. Untuk itu diperlukan suatu metode yang bisa menangkap pola yang ada berdasarkan data tidak terstruktur tersebut. Salah satu dimensi data yang bisa diambil adalah data interaksi antar aktor. Bentuk interaksi antar aktor bisa berupa percakapan, pertemanan, pemanggilan ataupun yang lainnya. Data interaksi tersebut bisa dimodelkan berdasarkan teori graf, yang mana aktor direpresentasikan sebagai node dan interaksi antar aktor direpresentasikan dalam bentuk edge. Metode ini dinamakan sebagai Social Network Analysis (SNA).


SNA sebagai suatu model jejaring sosial, mempunyai sekumpulan metrik untuk kuantifikasi suatu jejaring sosial. Salah satu metrik terpenting adalah keluarga metrik centrality yang digunakan untuk identifikasi aktor aktor yang paling berpengaruh pada suatu jejaring sosial pada konteks tertentu. Betweenness centrality (BC) mengidentifikasi pentingnya aktor berdasarkan seberapa sering aktor tersebut dilewati jalur terpendek alur informasi antar sembarang pasang aktor dalam jejaring sosial.


Pertumbuhan pengguna dan konten layanan jejaring sosial online membentuk jejaring sosial skala besar yang mencapai jutaan node dan edge. Beberapa masalah muncul dengan adanya jejaring sosial skala besar tersebut, antara lain perhitungan metrik yang tidak scalable, kompleksitas visualisasi, identifikasi struktur inti, dan lain lain. Metrik BC merupakan salah satu metrik yang tidak scalable. Kompleksitas waktu perhitungan metrik BC sebesar O(n3), dengan n ada jumlah node di dalam jaringan. Dengan banyak bermunculannya jejaring sosial skala besar di sekitar kita, maka perhitungan metrik BC tersebut menjadi sangat mahal.

Penelitian terkini untuk mereduksi proses perhitungan metrik BC selama ini berfokus pada usaha usaha untuk membuat metrik BC yang scalable, namun hal ini bukan merupakan pekerjaan yang mudah. Salah satu usaha yang dilakukan adalah memodifikasi algoritma sehingga tidak melibatkan semua node dan edge dalam perhitungan metrik. Salah satu algoritma yang paling penting dan dijadikan standard perhitungan metrik BC berdasarkan prinsip tersebut adalah algoritma Brandes, yang berhasil mereduksi kompleksitas waktu komputasi menjadi O(nm), dengan n adalah jumlah node dan m jumlah edge. Akan tetapi seiring bertambahnya ukuran jaringan maka waktu yang dibutuhkan untuk operasi tersebut masih tetap tinggi.


Terdapat 3 kandidat skenario untuk mempercepat proses perhitungan metrik BC yaitu: memodifikasi algoritma metrik BC, menggunakan komputasi paralel, dan mereduksi ukuran input graf. Pada disertasi ini pilihan mereduksi ukuran input graf dipilih dengan alasan proses lebih scalable karena tidak terpaku oleh ukuran jejaring yang diproses, memperoleh informasi struktur inti dari jejaring sosial, dan struktur inti graf bisa digunakan untuk kepentingan lainnya. Dua pilihan proses reduksi input graf adalah graf ringkasan dan pemilihan sampel graf atau graph sampling (GS). Diantara kedua pilihan tersebut GS merupakan pilihan lebih cepat dan lebih murah dari pada proses membuat graf ringkasan berdasarkan prinsip enumerasi subgraf dalam menemukan motif graf.


Kondisi terkini penelitian metode GS terdiri dari teknik teknik sampling graf menggunakan teknik pemilihan node secara acak, edge secara acak, dan teknik eksplorasi graf menggunakan prinsip random walk (RW). Metrik BC terdiri dari komponen yang menghitung rasio jalur terpendek dalam graf, sehingga untuk menjaga sifat jalur terpendek tersimpan dalam sampel graf, maka teknik GS yang digunakan adalah teknik RW. Pada umumnya teknik RW digunakan untuk mengambil sampel dari graf berdasarkan representasi nilai pengukuran tunggal (single value measurement (SVM)) atau nilai pengukuran distribusi (distribution measurement (DM)). Metropolis Hastings Random Walk (MHRW) dan Forest Fire (FF) adalah dua modifikasi teknik RW yang akurat dalam membuat sampel graf yang menjaga nilai SVM dan DM dari graf asli. Dalam kasus metrik BC yang termasuk dalam pengukuran peringkat (rank measurement (RM)) belum pernah ada klaim metode GS yang representatif.


Dalam disertasi ini metode GS dibangun berdasarkan dua komponen utama yaitu: 1). Metode graph pruning (GP) yang berfungsi untuk mereduksi ukuran jejaring sosial secara cepat, dengan syarat jejaring sosial harus mengikuti distribusi power law. 2). Metode optimized random walk (ORW) yang berfungsi untuk mengambil sampel secara akurat yang mewakili populasi graf dan memastikan bahwa bagian graf yang terpilih merupakan bagian yang paling penting dalam menjaga sifat jalur terpendek pada graf. Metode GP adalah metode yang dikonstruksi sendiri pada disertasi ini, sedangkan metode ORW adalah modifikasi metode umum RW. Fungsi kedua metode tersebut saling melengkapi dalam membuat sampel yang representatif, oleh karena itu dibuat metode gabungan yang diberi nama Hybrid Graph Pruning – Optimized Random Walk (HGPORW). Pada metode Hybrid GPORW, metode GP bertindak sebagai langkah preprocessing dan metode ORW bertindak sebagai metode utama GS.


Pada bagian akhir, dilakukan pengujian performansi metode Hybrid GPORW dalam hal kecepatan waktu pemrosesan dan akurasi peringkat metrik BC pada sampel graf. Metode ini juga diperbandingkan dengan metode konvensional RW, MHRW, FF, dan juga algoritma Brandes. Kesimpulan yang diperoleh bahwa metode Hybrid GPORW unggul dalam hal kecepatan waktu pemrosesan, sedangkan dalam hal akurasi peringkat metrik BC sepadan dengan metode sampling lainnya.

Deskripsi Alternatif :

Human activities on online social networking services such as Twitter, Facebook, Linkedin and others are increasing nowadays. Those increasing activity is followed by an increase in the amount of content produced by these service users. The extraction of information from human digital traces in the form of such content can be used to understand human behavior and its social environment. In general, the data attribute in the services is not completely available or referred as unstructured data. For that, we need a method that can capture existing patterns based on unstructured data. One dimension of data that can be taken is the interaction data between actors. Interaction form between actors can be conversation, friendship, mention or others. The interaction data can be modeled based on graph theory, where actors are represented as nodes and interactions between actors are represented in edge form. This method is named as Social Network Analysis (SNA).


SNA as a social network model, has a set of metrics for social network quantification. One of the most important metrics is centrality metrics family that used to identify the most influential actors in a social network for a particular context. Betweenness centrality (BC) identifies the importance of actors based on how often the actor passed through the shortest path of information between any pair of actors in social networks.


The growth of the user and the content in online social networking services forms a large-scale social network that reaches millions of nodes and edges. Some problems arise with the emergence of such large-scale social network, among others are the unscalable metrics calculations, the complexity of visualization, the identification of the core structure, and others. BC is one of the unscalable metric. The BC metric computation give time complexity O(n3), with n is number of the nodes in the network. With the appearance of large-scale social network around us, then BC metric computation will be expensive.


The state of the art research to reduce BC metric calculation process has so far focused on attempts to create scalable BC metric, but this is not a straightforward task. One attempt is to modify the algorithm so that it does not involve all nodes and edges in the calculation of metrics. One of the most important algorithms used as a standard of BC metric calculation in many applications is Brandes Algorithm, which succeeds in reducing complexity to O(nm), where n is number of nodes and m is number of edges. However, as the network size increases, the time required for such operations remains high.


There are 3 candidate scenarios to speed up the BC metric calculation process: modify the BC metric algorithm, using parallel computation, and reduce the graph input size. In this dissertation, the choice of reducing gaph input size is chosen since the process is more scalable because it is not depended by the size of the processed network, can obtain the core structure of the social network, and the graph core structure can be used for other purposes. Two choices of graph input reduction process are graph summary and graph sampling (GS). Between these two options GS is a faster and cheaper option than the process of creating a graph summary based on the subgraph's enumeration principle in finding the graph motif.


The GS current research method consists of sampling technique using random node selection, random edge selection, and graph exploration technique using random walk (RW) principle. The BC metric consist of components that calculate the shortest path ratios in the graph, so to keep the shortest path properties stored in the sample graph, the GS technique used is the RW technique. In general, RW techniques are used to extract samples from graphs based on single value measurement (SVM) or distribution measurement (DM) values. Metropolis Hastings Random Walk (MHRW) and Forest Fire (FF) are two RW technique modification that accurately keeps SVM and DM values in sample graph from the original graph. BC metric included in rank measurement (RM)) family, until now there has never been a claim of a representative GS method for RM.


In this dissertation, GS method built based on two main components namely: 1). Graph pruning method (GP) that serves to reduce the size of social network quickly, provided that social network must follow the distribution of power law. 2). The optimized random walk (ORW) method for sampling accurately graph population and ensures that the selected graph portion is the most important part in maintaining the shortest path properties in the graph. The functions of the two methods above are complementary in making representative samples, therefore a combined method called Hybrid Graph Pruning - Optimized Random Walk (HGPORW) is developed. In Hybrid GPORW, GP method acts as a preprocessing step and the ORW method acts as the main method of GS.


At the final stage, a performance test of the Hybrid GPORW method in terms of processing speed and accuracy of BC metric rank on the sample graph is conducted. This method is also compared with RW conventional methods, MHRW, FF, and the Brandes algorithm. The conclusion obtained that the Hybrid GPORW method is superior in terms of time-processing speed, whereas in terms of BC metric accuracy is comparable with other sampling methods.

Copyrights : Copyright (c) 2001 by Perpustakaan Digital ITB. Verbatim copying and distribution of this entire article is permitted by author in any medium, provided this notice is preserved.

Beri Komentar ?#(0) | Bookmark

PropertiNilai Properti
ID PublisherJBPTITBPP
OrganisasiS
Nama KontakUPT Perpustakaan ITB
AlamatJl. Ganesha 10
KotaBandung
DaerahJawa Barat
NegaraIndonesia
Telepon62-22-2509118, 2500089
Fax62-22-2500089
E-mail Administratordigilib@lib.itb.ac.id
E-mail CKOinfo@lib.itb.ac.id

Print ...

Kontributor...

  • Prof. Dr. Ir. Kuspriyanto

    Ir. Budi Rahardjo, M.Sc., Ph.D

    Dr. Ir. Yoga Priyana, Editor: cecep hikmat

File PDF...