PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

ANALISIS PERBANDINGAN NODE CENTRALITY PADA JARINGAN MANUSIA RIIL TERHADAP JARINGAN TEORITIS (RANDOM NETWORK, DAN SCALE-FREE NETWORK) SKRIPSI Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Komputer Program Studi Teknik Informatika

Oleh: Dwi Prabowo 115314060

PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2016

i


COMPARATIVE ANALYSIS OF NODE CENTRALITY ON REAL HUMAN NETWORK FOR THEORITICAL NETWORK (RANDOM NETWORK, AND SCALE-FREE NETWORK)

A Thesis

Presented as Partial Fulfillment of the Requirements to Obtain the Sarjana Komputer Degree in Informatics Engineering

By: Dwi Prabowo 115314060

DEPARTMENT OF INFORMATICS ENGINEERING FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2016

ii


iii

HALAMAN PERSETUJUAN iii


iv

iv


HALAMAN PERSEMBAHAN

Skripsi ini saya persembahkan untuk Tuhan Yesus Kristus, Kedua Orang tua saya, Keluarga kedua AOG GMS Yogyakarta Eaglekidz Yogyakarta Teman-teman semua

TERIMA KASIH

v


PERNYATAAN KEASLIAN KARYA Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak memuat karya atau bagian dari karya orang lain, kecuali yang telah disebutkan dalam kutipan dan daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 29 Februari 2016 Penulis

Dwi Prabowo

vi


LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma: Nama : Dwi Prabowo NIM Demi

: 115314060

pengembangan

ilmu

pengetahuan,

saya

memberikan

kepada

Perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul:

ANALISIS PERBANDINGAN NODE CENTRALITY PADA JARINGAN MANUSIA RIIL TERHADAP JARINGAN TEORITIS (RANDOM NETWORK, DAN SCALE-FREE NETWORK)

Dengan demikian saya memberikan kepada Universitas Sanata Dharma hak untuk menyiapkan, mengalihkan dalam bentuk media lain, mengelola dalam bentuk pangkalan data, mendistribusikan secara terbatas, dan mempublikasikan di internet atau media lain untuk kepentingan akademis tanpa perlu meminta izin dari saya maupun memberi royalty kepada saya selama tetap mencantumkan nama saya sebagai penulis. Demikian pernyataan ini saya buat dengan sebenarnya. Dibuat di Yogyakarta Pada tanggal: 29 Februari 2016 Yang menyatakan,

(Dwi Prabowo)

vii


ANALISIS PERBANDINGAN NODE CENTRALITY PADA JARINGAN MANUSIA RIIL TERHADAP JARINGAN TEORITIS (RANDOM NETWORK, DAN SCALE-FREE NETWORK) ABSTRAK Metrik centrality adalah sebuah cara untuk mengidentifikasi individu yang paling penting (popular) dalam sebuah jaringan relasi manusia. Pada penelitian ini, metrik centrality direpresentasikan pada jaringan manusia riil (facebook), di jaringan acak (random network), dan di jaringan skala bebas (scale-free network). Dalam metrik centrality setidaknya terdapat 3 buah metode dasar untuk dapat menghitung bobot centrality dari setiap node dalam suatu graf, yaitu: degree centrality, closeness centrality, dan betweenness centrality. Dalam teori graf atau analisa jaringan, metrik centrality merupakan metode untuk mengidentifikasi individu yang menjadi pusat dalam sebuah jaringan. Dalam penelitian ini penulis mencoba mempelajari karakteristik jaringan manusia yang dibandingkan dengan jaringan (graph) teoritis: random graph dan scale-free graph dan mengimplementasikan metrik centrality untuk menentukan individu yang paling populer (degree centrality), menentukan individu yang memiliki hubungan yang dekat dengan individu lainnya (closeness centrality), dan menentukan individu yang menjadi jembatan antara individu lainnya pada jaringan manusia riil (facebook), random network, dan scale-free network (betweenness centrality). Oleh karena itu, penulis mencoba untuk meneliti topik tentang “Analisis Perbandingan Node Centrality pada Jaringan Manusia Riil terhadap Jaringan Teoritis (Random Network, dan Scale-Free Network)”. Kata kunci: metrik centrality, jaringan manusia, random network, scale-free network

viii


COMPARATIVE ANALYSIS OF NODE CENTRALITY ON REAL HUMAN NETWORK FOR THEORITICAL NETWORK (RANDOM NETWORK, AND SCALE-FREE NETWORK) ABSTRACT Centrality metric is a way to identify individuals most important (popular) in a network of human relationships. In this research, metric centrality represented on real human network (facebook), on random networks, and on scale-free networks. In metric centrality at least there are 3 basic methods to be able to calculate the weight of centrality of each node in a graph, namely: degree centrality, closeness centrality, and betweenness centrality. In graph theory or network analysis, centrality metric is a method to identify individuals at the center of a network. In this research the author tries to learn the characteristics of human network were compared to a network (graph) theoretical: random graph and scale-free graph and implement metrics centrality to determine an individual's most popular (degree centrality), determine an individual who has a close relationship with other individuals (closeness centrality), and specify the individual to be a bridge between the other individuals in the human network (facebook), random network, and the scale-free network (betweenness centrality). Therefore, the author tries to examine the topic of "Comparative Analysis of Node Centrality on Real Human Network for Theoritical Network (Random Network and Scale-free Network)". Keywords: centrality metrics, human network, random network, scale-free network

ix


KATA PENGANTAR Puji syukur kepada Tuhan Yesus Kristus yang telah memberikan karunia dan kesempatan sehingga penulis dapat menyelesaikan skripsi dengan judul “Analisis Centrality pada Social Network Facebook, Random Graph, dan Scale-Free Network Graph”. Penyusunan skripsi ini tidak lepas dari semua pihak yang turut memberikan dukungan dan doanya. Pada kesempatan ini penulis ingin mengucapkan terimakasih kepada: 1. Bapak Bambang Soelistijanto, selaku dosen pembimbing yang senantiasa membimbing dan membantu penulis untuk menyelesaikan skripsi ini. 2. Kedua orang tua, Bapak Untung Widayat dan Ibu Sagasina yang selalu memberi perhatian, dukungan, semangat, serta doa kepada penulis. 3. Kakak Hadiyanto Prabowo yang selalu memberikan dukungan kepada penulis. 4. Connect Group AOG Pure Heart (M23) Maria Andreina Niken Ayu Sekarwangi, Delvie Naberia, Novia Siulani, Purwati yang memberikan dukungan motivasi kepada penulis. 5. Eaglekidz Yogyakarta, kak Ayu, kak Andre, Roy, Maria, Ebi, Reta, Ghea, Meta, kak Vina, kak Dian yang memberikan dukungan dan doa kepada penulis. 6. Teman-teman seperjuangan Agatya Kurniawan, Paulus Dian Wicaksana, Richo Prasojo, Nur Indanik, Benedicta Maria Laras Anggrahini, Priska Ambarsari, Dio, Beny, Sisil, Pasca. 7. Perumahan Taman Krajan Blok E-15, tempat di mana penulis tinggal dan bersosialisasi. Penulis

Dwi Prabowo

x


DAFTAR ISI

HALAMAN JUDUL .......................................................................................................... i HALAMAN PERSETUJUAN ........................................................................................... ii HALAMAN PENGESAHAN ........................................................................................... iii HALAMAN PERSEMBAHAN ......................................................................................... v PERNYATAAN KEASLIAN KARYA ............................................................................ vi LEMBAR PERNYATAAN PERSETUJUAN .................................................................. vii ABSTRAK ..................................................................................................................... viii ABSTRACT ..................................................................................................................... ix KATA PENGANTAR ....................................................................................................... x DAFTAR ISI .................................................................................................................... xi DAFTAR GAMBAR ....................................................................................................... xv DAFTAR TABEL .......................................................................................................... xvi BAB I PENDAHULUAN .................................................................................................. 1 1.1

Latar Belakang..................................................................................................... 1

1.2

Rumusan Masalah ................................................................................................ 2

1.3

Tujuan ................................................................................................................. 2

1.4

Batasan Masalah .................................................................................................. 2

1.5

Metodologi Penelitian .......................................................................................... 3

1.5.1

Studi literatur ................................................................................................ 3

1.5.2

Metode Pengumpulan Data ........................................................................... 3

1.5.3

Perancangan ................................................................................................. 3

1.5.4

Analisis Data ................................................................................................ 3

xi


1.5.5 1.6

Penarikan Kesimpulan dan Saran .................................................................. 3

Sistematika Penulisan .......................................................................................... 3

BAB II LANDASAN TEORI ............................................................................................ 5 2.1

Social Network (Jaringan Sosial) .......................................................................... 5

2.2

Social Network Analysis (SNA) ........................................................................... 8

2.3

Algoritma Dijkstra ............................................................................................... 9

2.4

Metrik Centrality ............................................................................................... 12

2.4.1

Degree Centrality ....................................................................................... 12

2.4.2

Betweenness Centrality ............................................................................... 12

2.4.3

Closeness Centrality ................................................................................... 13

2.5

Teori Graf .......................................................................................................... 14

2.5.1

Definisi Graf ............................................................................................... 16

2.5.2

Jenis-jenis Graf ........................................................................................... 17

2.5.3

Macam-macam Graf ................................................................................... 18

2.5.4

Representasi Graf ....................................................................................... 20

2.5.5

Random Graph ........................................................................................... 21

2.5.6

Scale-Free Network Graph (SFNG) ............................................................ 24

2.5.6.1 2.6

Barabasi-Albert Model ........................................................................ 26

Matriks Adjacency ......................................................................................... 28

BAB III PERANCANGAN MODEL ............................................................................... 29 3.1

Sumber Data ...................................................................................................... 29

3.2

Perancangan Model............................................................................................ 29

3.3

Preprocessing .................................................................................................... 30

3.3.1

Pembuatan Matriks ..................................................................................... 31

xii


3.4

Parameter Simulasi ............................................................................................ 35

3.5

Skenario Simulasi .............................................................................................. 35

3.5.1

Real Human Network .................................................................................. 36

3.5.2

Random Graph ........................................................................................... 36

3.5.3

Scale-free Graph ........................................................................................ 36

BAB IV PENGUJIAN DAN ANALISIS ......................................................................... 37 4.1

Perhitungan Centrality ....................................................................................... 37

4.2

Real Human Network ......................................................................................... 38

4.2.1


4.2.2


4.2.3


4.2.4

Hubungan Betweenness, Closeness, dan Degree Centrality ......................... 41

4.3

Random Graph (Erdos Reyni) ............................................................................ 42

4.3.1


4.3.2


4.3.3


4.3.4


4.4

Scale-Free Network Graph (SFNG) ................................................................... 45

4.4.1


4.4.2


4.4.3


4.4.4


4.5

Rekap Perbandingan Real Human Network dengan Random Graph ................... 48

4.6 Rekap Perbandingan Real Human Network dengan Scale-free Network Graph ..... 49

xiii


BAB V PENUTUP .......................................................................................................... 50 5.1

Kesimpulan........................................................................................................ 50

DAFTAR PUSTAKA ...................................................................................................... 51 LAMPIRAN .................................................................................................................... 52

xiv


DAFTAR GAMBAR

Gambar 2.1 Relasi DYAD ................................................................................................. 6 Gambar 2.2 Relasi Triad .................................................................................................... 6 Gambar 2.3 Penggambaran monomodal networks .............................................................. 7 Gambar 2.4 Penggambaran Two Mode Networks .............................................................. 7 Gambar 2.5 Social Network................................................................................................ 8 Gambar 2.6 Flowchart algoritma Dijkstra........................................................................ 10 Gambar 2.7 Contoh graf algoritma Dijkstra ..................................................................... 10 Gambar 2.8 Rumus Degree Centrality ............................................................................. 12 Gambar 2.9 Rumus Betweenness Centrality ..................................................................... 13 Gambar 2.10 Rumus Closeness Centrality ....................................................................... 13 Gambar 2.11 Gambar graf setiap titik mewakili kota dan garis mewakili jalan. ................ 16 Gambar 2.12 Gambar graf sederhana (G) ......................................................................... 16 Gambar 2.13 Graf tidak berbobot .................................................................................... 18 Gambar 2.14 Graf berbobot............................................................................................. 18 Gambar 2.15 Graf tidak berarah ....................................................................................... 19 Gambar 2.16 Graf berarah ................................................................................................ 19 Gambar 2.17 Gambar kiri merupakan graf (G),gambar kanan merupakan adjacency lists. ................................................................................................................................. 20 Gambar 2.18 Gambar kiri merupakan graf (G), gambar kanan merupakan matriks ........... 20 Gambar 3.1 Perancangan Model ...................................................................................... 29 Gambar 3.2 Proses Preprocessing .................................................................................... 30 Gambar 3.3 Real Graf Facebook ..................................................................................... 31 Gambar 3.4 Representasi Matriks nxn Social Network Facebook dengan n=50 ................ 32 xv


Gambar 3.5 Random Graph ............................................................................................. 33 Gambar 3.6 Representasi Matriks nxn Random Graph .................................................... 33 Gambar 3.7 Scale-free graph ............................................................................................ 34 Gambar 3.8 Representasi Matriks nxn Scale-Free Graph ................................................ 34 Gambar 4.1 Grafik hasil betweenness centrality pada Real Human Network .................... 38 Gambar 4.2 Grafik hasil closeness centrality pada Real Human Network ......................... 39 Gambar 4.3 Grafik hasil degree centrality pada Real Human Network ............................. 40 Gambar 4.4 Grafik hasil betweenness centrality pada Random Graph .............................. 42 Gambar 4.5 Grafik hasil closeness centrality pada Random Graph .................................. 43 Gambar 4.6 Grafik hasil degree centrality pada Random Graph ....................................... 44 Gambar 4.7 Grafik hasil betweenness centrality pada Scale-free graph ........................... 45 Gambar 4.8 Grafik hasil closeness centrality pada Scale-free graph ................................. 46 Gambar 4.9 Grafik hasil degree centrality pada Scale-free graph .................................... 47

DAFTAR TABEL Tabel 3.1 Parameter simulasi random graph .................................................................... 35 Tabel 3.2 Parameter simulasi scale-free graph ................................................................. 35

xvi


BAB I PENDAHULUAN 1.1

Latar Belakang Kehidupan orang-orang tidak lepas dengan yang namanya kehidupan sosial. Setiap orang saling berhubungan satu dengan yang lainnya baik secara langsung maupun tidak langsung. Namun secara tidak sadar hal itu menggunakan konsep graf dalam struktur diskrit yang secara sederhana dapat kita pahami. Tiap individu terhubung dengan suatu relasi ke individu lainnya, dan saling menghubungkan beberapa individu lainnya sehingga tercipta grup atau koneksi dengan relasi khusus. Dengan konsep yang sederhana dan telah ada sejak pertengahan 1990-an yaitu Social Network Analysis. Social network Analysis sendiri adalah perluasan dari teori Graf, yang digunakan dalam banyak hal untuk menganalisis relasi antar individu yang mempunyai keterkaitan tertentu. Masalah yang dihadapi adalah bagaimana cara mengetahui individu yang paling penting (popular) dan memberikan pengaruh dalam sebuah jaringan manusia. Dalam menentukan apakah seseorang tersebut memberikan pengaruh dalam sebuah jaringan manusia dapat dibuktikan menggunakan metrik centrality. Dalam teori graf atau analisa jaringan, metrik centrality merupakan metode untuk mengidentifikasi individu yang menjadi pusat dalam sebuah

jaringan.

Dalam

tugas

akhir

ini

penulis

mencoba

mengimplementasikan metrik centrality untuk menentukan individu yang paling populer, menentukan individu yang memiliki hubungan yang dekat dengan individu lainnya, dan menentukan individu yang menjadi jembatan antara individu lainnya pada real graph (facebook), random graph, dan scalefree network graph. Oleh karena itu, penulis mencoba untuk meneliti topik tentang “Analisis Perbandingan Node Centrality pada Jaringan Manusia Riil terhadap Jaringan Teoritis (Random Network, dan Scale-Free Network)”.

1


1.2

2

Rumusan Masalah Berdasarkan latar belakang masalah yang dikemukakan di atas, maka rumusan masalah dalam tugas akhir ini adalah sebagai berikut: 1. Bagaimana

mengimplementasikan

metrik

centrality

dalam

mengidentifikasi individu yang paling populer (penting) dalam sebuah jaringan relasi manusia? 2. Bagaimana

mempelajari

karakteristik

jaringan

manusia

dan

membandingkannya dengan random graph dan scale-free network graph?

1.3

Tujuan Tujuan yang ingin dicapai dalam penulisan tugas akhir ini adalah membandingkan

metrik

centrality

di

Freeman:

Degree

Centrality,

Betweenness Centrality, dan Closeness Centrality dalam menentukan popularitas individu di suatu jaringan sosial riil (facebook) dan teoritis (random graph dan scale-free graph).

1.4

Batasan Masalah 1. Ruang lingkup dalam penelitian ini untuk menghitung popularitas individu dan membandingkan jaringan manusia riil (facebook) terhadap random network, dan scale-free network. 2. Sampel data yang digunakan diambil dari 50 node dari facebook, random graph dan scale-free network graph.


1.5

3

Metodologi Penelitian Metodologi yang digunakan untuk mencapai tujuan dan manfaat di atas adalah sebagai berikut: 1.5.1 Studi literatur Mengumpulkan referensi dari berbagai narasumber untuk mempelajari dan memahami bagian-bagian mengenai Social Network Analysis, degree centrality, closeness centrality, dan betweenness centrality. 1.5.2 Metode Pengumpulan Data Metode pengumpulan data yang digunakan adalah mengambil sampel data dari facebook, random graph, dan scale-free network graph dalam bentuk graf yang diubah menjadi matriks sehingga didapatkan beberapa data yang bersifat informatif. 1.5.3 Perancangan Pada bagian ini setelah dilakukan tahap pengumpulan data, akan dilakukan perhitungan dengan metrik centrality. Menghitung degree, closeness, serta betweeness centrality dengan menggunakan data yang sudah diubah ke dalam bentuk matriks kemudian dihitung di dalam matlab. 1.5.4 Analisis Data Menganalisa sebuah data yang sudah diperoleh dari proses simulasi yang dilakukan untuk menarik kesimpulan dari hasil yang didapat. 1.5.5 Penarikan Kesimpulan dan Saran Penarikan kesimpulan dan saran berdasarkan hasil yang diperoleh dari proses analisa data.

1.6

Sistematika Penulisan BAB I

PENDAHULUAN


4

Bab ini berisi tentang latar belakang masalah, rumusan masalah, tujuan penelitian, manfaat penelitan, metodologi penelitan, dan sistematika penulisan. BAB II

LANDASAN TEORI Bab ini membahas dan menjelaskan berbagai landasan teori yang berkaitan dengan judul di tugas akhir.

BAB III

PERANCANGAN PENELITIAN Bab ini menjelaskan proses-proses analisa dan perancangan model dari “Analisis Perbandingan Node Centrality pada Jaringan

Manusia

Riil

terhadap

Jaringan

Teoritis

(Random Network dan Scale-Free Network)”. BAB IV

PENGUJIAN DAN ANALISIS Bab ini berisi tahap pengujian dan analisa data hasil pengujian.

BAB V

PENUTUP Bab ini berisi kesimpulan dan saran dari hasil pengujian berdasarkan hasil yang telah didapat.


BAB II LANDASAN TEORI 2.1

Social Network (Jaringan Sosial) Social network atau jejaring sosial adalah struktur sosial yang terbentuk dari himpunan terhingga dari individual (organisasi) dengan bentuk relasi / koneksi antaranya. Disebut 'nodes' yang terhubung oleh satu atau lebih ketergantungan yang spesifik , seperti pertemanan, kesamaan, gender ataupun lainnya. Penghubung nodes tersebut yang disebut connections. Connections ini dalam materi graph, disebut sisi. Social network analysis (SNA) atau analisis social network telah menjadi kunci utama dalam sosiologi modern. Dan telah menjadi topik populer

dalam

perkembangan

antropologi,

ekonomi,

geografi

dan

sosiolinguistik. Social Network Analysis (SNA) dapat dideskripsikan sebagai sebuah studi yang mempelajari tentang hubungan manusia dengan memanfaatkan teori graf. (Tsvetovat & Kouznetsov, 2011, hal 1). Dengan pemanfaatan teori graf ini membuat SNA mampu memeriksa struktur dari hubungan sosial dalam suatu kelompok untuk mengungkap hubungan informal antar individu. Pada social network, individu atau orang digambarkan sebagai nodes atau titik, sedangkan relasi yang terjadi antar individu disebut dengan edges atau links. Pada dasarnya sebuah jaringan sosial adalah sebuah peta yang terdiri atas banyak orang dimana di dalamnya terdapat relasi antar individunya. Berkenaan dengan teori jejaring sosidal. Nodes dalam graf itu dinamakan 'aktor' / individu dengan sisi / garis penghubung adalah relasi dari 2 individu tersebut (ties). Subgrup adalah istilah yang menggambarkan himpunan kecil dari suatu grup graf, yang berbentuk DYAD ataupun Triad. DYAD adalah hubungan sederhana yang terbentuk dari dua aktor dan penghubung antara mereka.

5


6

Gambar 2.1 Relasi DYAD

Triad adalah hubungan yang terbentuk dari 3 buah aktor, dengan berbagai macam kemungkinan hubungan diantaranya.

Gambar 2.2 Relasi Triad

SNA memiliki perluasan yang sangat kompleks. Dari sebuah nodes berupa individu, hingga skala negara. Hubungan sisi yang mengikat juga sangat banyak macamnya, dari hasil penelitian jejaring sosial ini bisa digunakan dalam berbagai tingkat relasi. Teori ini dapat digunakan untuk menyelesaikan beberapa masalah seperti bagaimana suatu organisasi berjalan, pengambilan keputusan maupun hubungan antar individu. Jejaring sosial juga digunakan untuk menganalisa bagaimana sebuah organisasi berinterkasi dengan relasi lainya. Apa yang menghubungkan antar individu, dan bagaimana kerapatan atau banyaknya. Ada beberapa jenis penggambaran jejaring sosial, yaitu:


7

1. Monomodal networks

Gambar 2.3 Penggambaran monomodal networks Setiap aktor dalam graf ini dapat terhubung dengan lainnya melalui relasi yang didefinisikan khusus.

2. Two Mode Networks

Gambar 2.4 Penggambaran Two Mode Networks

Dalam graf ini, tiap aktor tidak terhubung secara langsung oleh suatu relasi. Tetapi terhubungkan oleh suatu 'event' / kejadian yang sama yang berada dalam himpunan berbeda. Dalam bahasa sederhana, social network adalah graf dengan ikatan relasi spesifik . Hubungan antar nodes / individu, disebut sosial kontak.


8

Gambar 2.5 Social Network Dikutip dari : Kazienko, P. & Musial, K. (2005). Social Networks. 2.2

Social Network Analysis (SNA) Social Network Analysis (SNA) adalah sebuah studi yang mempelajari tentang hubungan manusia dengan memanfaatkan teori graf. Menurut Scott, SNA adalah sekumpulan metode yang digunakan untuk menginvestigasi aspek relasi pada struktur data. SNA merupakan metode yang digunakan untuk mengetahui hubungan informal antar individu dengan menganalisa struktur dari hubungan sosial dalam suatu kelompok. Pada social network, individu atau orang digambarkan sebagai node atau titik. Sedangkan relasi yang terjadi antar individu digambarkan dengan edge atau link. Pada dasarnya sebuah jaringan sosial adalah sebuah peta yang terdiri atas banyak orang dimana didalamnya terdapat relasi antar individunya. Network didefinisikan sebagai sekumpulan actors/nodes yang dihubungkan oleh ties/links. Actors/nodes adalah kita, individu yang terlibat dalam sebuah network dan ties/links adalah hubungan dan interaksi yang


9

terjadi antara kita dengan individu lainnya dalam sebuah network (jaringan). Nodes juga dapat berupa departemen atau organisasi lain. Tergantung bagaimana kita hendak melakukan analisis. Ties (hubungan) juga berbedabeda tergantung tujuan dan kebutuhan.

2.3

Algoritma Dijkstra Algortima ini ditemukan oleh Edsger W. Dikstra dan di publikasi pada tahun 1959 pada sebuah jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs”. Algoritma ini sering digambarkan sebagai algoritma greedy (tamak). Sebagai contoh, ada pada buku Algorithmics (Brassard and Bratley [1988, pp. 87-92]) Dijkstra merupakan salah satu varian bentuk algoritma popular dalam pemecahan persoalan terkait masalah optimasi pencarian lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (tak hingga). Pada algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute listasan terpendek. Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titk lainnya. Misalnya titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik. Berikut flowchart algoritma Dijkstra:


Gambar 2.6 Flowchart algoritma Dijkstra

’

Gambar 2.7 Contoh graf algoritma Dijkstra

10


11

Berikut ini adalah tahapan urutan logika algoritma Dijkstra. Pertamatama tentukan titik mana yang akan menjadikan node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu persatu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap inilah urutan logika dari algoritma Dijkstra : 1. Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi) 2. Set semua node “Belum Terjamah” dan set node awal sebagai “Node keberangkatan” 3. Dari no keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru. 4. Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya. 5. Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selajutnya dan lanjutkan dengan kembali ke step 3


2.4

12

Metrik Centrality Dalam teori graf dan network analysis, terdapat empat cara untuk mengukur centrality, yaitu dengan cara menghitung degree centrality, betweenness centrality, closeness centrality dan eigenvector centrality. Pada penelitian ini akan digunakan tiga cara perhitungan, yaitu degree centrality, betweeness centrality, dan closeness centrality.

2.4.1 Degree Centrality Degree centrality adalah jumlah koneksi yang dimiliki sebuah node. Degree Centrality akan menghitung bobot suatu node berdasar banyaknya edge yang terbentuk antara node i dengan node yang lainnya. Ada istilah indigree untuk relasi yang mengarah ke nodes tersebut, dan outdegree untuk relasi yang mengarah keluar node tersebut. Berikut adalah rumus untuk menghitung nilai degree centrality setiap node dalam jaringan.

CD = sum (adj) Gambar 2.8 Rumus Degree Centrality Keterangan:

CD

= Menghitung bobot suatu node

sum

= Perintah penjumlahan

adj

= Jumlah edge/link yang terbentuk pada node i dengan node lain pada matriks adjacency

2.4.2 Betweenness Centrality Betweenness centrality adalah salah satu cara untuk mengukur centrality dalam suatu jaringan sosial. Betweenness centrality yang akan menghitung bobot setiap node berdasar seberapa banyak node i dilalui oleh dua node lain dalam graf berdasar jalur terpendeknya (shortest path). Dimana (v) st s adalah banyaknya jalur terpendek dari s ke t yang melalui nodes v.


13

Yang st s adalah banyaknya jalur terpendek dari s ke t. Penjumlahan dari perhitungan tersebut yang disebut Betweenness. Berikut adalah rumus untuk menghitung nilai betweenness centrality setiap node dalam jaringan.

CB (i) =

Gambar 2.9 Rumus Betweenness Centrality Keterangan: σ_st (v) = jumlah shortest paths dari node s ke t yang melewati node v σ_st

= jumlah shortest paths dari node s ke t

2.4.3 Closeness Centrality Closeness centrality adalah salah satu cara untuk mengukur centrality dalam suatu jaringan sosial yang fokus terhadap seberapa dekat suatu aktor dengan semua aktor lainnya. Closeness centrality akan menghitung bobot centrality sebuah node berdasar jumlah jarak terpendek antara node i dengan node lainnya. Berikut adalah rumus untuk menghitung nilai closeness centrality setiap node dalam jaringan.

C(i) = 1/ sum (simple_dijkstra(adj,i)) Gambar 2.10 Rumus Closeness Centrality Keterangan: C(i)

= Menghitung bobot suatu node ke i

(simple_dijkstra(adj,i))= Jumlah jarak terpendek antara node i dengan node lainnya


2.5

14

Teori Graf Teori

graf atau teori

grafik dalam matematika dan ilmu

komputer adalah cabang kajian yang mempelajari sifat-sifat "graf" atau "grafik". Secara informal, suatu graf adalah himpunan benda-benda yang disebut "simpul" (vertex atau node) yang terhubung oleh "sisi" (edge) atau "busur" (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan "simpul") yang dihubungkan oleh garis-garis (melambangkan "sisi") atau garis berpanah (melambangkan "busur"). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan "gelang" (loop). Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna

jika

dan

hanya

jika

mereka

berteman.

Perkembangan

algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer. Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan. Jaringan

banyak

digunakan pada

cabang

praktis

teori graf

yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah). Suatu graph G dapat dinyatakan sebagai. Graph G terdiri atas himpunan V yang berisikan simpul pada graf tersebut dan himpunan dari E yang berisi sisi pada graf tersebut. Himpunan E dinyatakan sebagai pasangan dari simpul yang ada dalam V. Sebagai contoh definisi dari graf pada gambar


15

di atas adalah : dan Gambar dengan node yang sama dengan yang di atas, tapi merupakan digraf. Pada digraf maka pasangan-pasangan ini merupakan pasangan

terurut.

Untuk

menyatakan

digraf

(gambar

kedua

yang

menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut: Dalam

himpunan edge untuk

digraf,

urutan

pasangan

verteks

menentukan arah dari edge tersebut. Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf : 

Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.



Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path



Cycle siklus ? path yang kembali melalui titik asal 2 kembali ke 2.



Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf di atas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex



Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (vi,vj)=(vj,vi)



Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.


16

2.5.1 Definisi Graf Graf adalah kumpulan dari minimal satu atau lebih simpul (vertex) yang dihubungkan oleh sisi atau busur (edge). Dalam kehidupan sehari-hari, graf banyak diaplikasikan (Suryanaga, 2003) seperti untuk pengaturan arus lalu lintas, jaringan komputer, pembuatan chip, jaringan sosial dan sebagainya.

Simpul didalam graf biasanya dilambangkan dengan titik

sedangkan busur dilambangkan dengan garis. Contohnya : kota-kota di lambangkan dengan titik dan garis melambangkan jalan yang menghubungkan antar kota.

Gambar 2.11 Gambar graf setiap titik mewakili kota dan garis mewakili jalan.

Menurut Diestel (2000), sebuah graf G dapat diartikan sebagai himpunan berhingga dan tak kosong dari v dan e yang merupakan himpunan pasangan tak berurut dari unsur-unsur di v, dimana v=Vertex dan e=edge.

G=(v,e)

e1 1

3 e3

e5 4

e2

e4 2

Gambar 2.12 Gambar graf sederhana (G) pada gambar 2.2, G memiliki v={1,2,3,4} dan e={(1,3), (1,2), (1,4), (2,4), (3,4)} atau {e1,e2,e3,e4,e5}.


17

2.5.2 Jenis-jenis Graf Menurut Scheinerman dan Ullman (2008), berdasarkan ada atau tidaknya gelang (loop), graf digolongkan menjadi dua, yaitu : a. Graf sederhana (simple graph) Graf yang tidak memiliki loops dan sisi paralel. b. Graf tak-sederhana (unsimple graph/multigraph) Graf yang memiliki loops dan sisi paralel. Menurut Munir (2008), Berdasarkan ada atau tidaknya arah, graf digolongkan menjadi dua, yaitu : a. Graf berarah (directed graph) Graf yang memiliki orientasi arah pada sisinya. (va,vb) ≠ (vb,va). Pada simpul (va,vb), va adalah simpul asal sedangkan vb adalah simpul tujuan. b. Graf tak berarah (undirected graph) Graf yang tidak memiliki orientasi arah pada sisinya. (va,vb) = (vb,va). Dalam hal ini tidak terdapat simpul asal maupun simpul tujuan karena bukan merupakan hal yang terlalu diperhatikan.


18

2.5.3 Macam-macam Graf a. Graf Berdasarkan Bobot Berdasarkan bobot, graf dapat dikelompokan menjadi dua macam, yaitu graf berbobot dan graf tidak berbobot. Bobot disini dapat direpresentasikan sebagai jumlah interaksi, kekuatan hubungan, jarak suatu node, atau yang lainnya. Sedangkan graf tidak berbobot hanya merepresentasikan suatu hubungan antar node-nya saja.

Gambar 2.13 Graf tidak berbobot

Gambar 2.14 Graf berbobot


19

b. Graf Berdasarkan Arah Graf berdasarkan arah dapat di kelompokan menjadi 2 macam, yaitu graf berarah dan graf tidak berarah. Graf berarah tersebut merepresentasikan arah relasi yang terjadi antar node.

Gambar 2.15 Graf tidak berarah

Gambar 2.16 Graf berarah


20

2.5.4 Representasi Graf Ada dua cara merepresentasikan sebuah graf (Adamchik, 2005) 1. Adjacency lists Representasi ini secara visual lebih mudah dimengerti, akan tetapi kurang bagus untuk dioperasikan bila vertex yang dimiliki terlalu banyak. Biasanya adjacency lists direpresentasikan seperti bentuk array.

Gambar 2.17 Gambar kiri merupakan graf (G), gambar kanan merupakan adjacency lists. Kerugian potensial dari representasi adjacency-daftar adalah bahwa tidak ada cara cepat untuk menentukan apakah ada edge diantara dua simpul. 2. Adjacency matrix Representasi ini baik digunakan untuk representasi graf didalam komputer. Kekurangan dari adjacency lists dapat ditutupi dengan adjacency matrix. Adjacency matrix adalah matriks dari v x v dimana, Mi,j{ 1,jika ada 𝑒𝑑𝑔𝑒 diantara 𝑖 dan j; 0,jika tidak ada 𝑒𝑑𝑔𝑒 diantara 𝑖 dan 𝑗

Gambar 2.18 Gambar kiri merupakan graf (G), gambar kanan merupakan matriks


21

2.5.5 Random Graph Dalam matematika, random graph adalah istilah umum untuk menyebut distribusi probabilitas lebih grafik. Random graph dapat digambarkan hanya dengan distribusi probabilitas, atau dengan proses acak yang menghasilkan graf tersebut.

Teori random graph terletak di

persimpangan antara teori graf dan teori probabilitas. Dari perspektif matematika, random graph digunakan untuk menjawab pertanyaan tentang sifat-sifat grafik khas. Aplikasi praktis ditemukan di semua daerah di mana jaringan yang kompleks perlu dimodelkan - sejumlah besar model random graph sehingga diketahui, mencerminkan beragam jenis jaringan yang kompleks yang dihadapi di daerah yang berbeda. Dalam konteks matematika, random graph mengacu hampir secara eksklusif pada Erdös-Rényi model random graph. Dalam konteks lain, model grafik dapat disebut sebagai random graph. Sebuah random graph diperoleh dengan memulai dengan satu set n simpul terisolasi dan menambahkan tepi berturut-turut antara mereka secara acak. Tujuan dari penelitian di bidang ini adalah untuk menentukan pada tahap apa properti tertentu dari grafik cenderung timbul. [2] model grafik acak yang berbeda menghasilkan distribusi probabilitas yang berbeda pada grafik. Paling sering dipelajari adalah yang diusulkan oleh Edgar Gilbert, dinotasikan G (n, p), di mana setiap kemungkinan tepi terjadi secara independen dengan probabilitas 0

dengan notasi

. Sebuah

model terkait erat, model Erdös-Rényi dilambangkan G (n, M), memberikan probabilitas yang sama untuk semua grafik dengan tepat M tepi. Dengan 0 ≤ M ≤ N, G (n, M) memiliki probabilitas

.

elemen dan setiap elemen terjadi dengan


22

Model terakhir dapat dilihat sebagai snapshot pada waktu tertentu (M) dari proses grafik acak

, yang merupakan proses stokastik yang dimulai

dengan n simpul dan tidak ada ujungnya, dan di setiap langkah menambahkan satu keunggulan baru yang dipilih seragam dari set hilang tepi. Jika bukan kita mulai dengan set tak terbatas simpul, dan lagi biarkan setiap kemungkinan tepi terjadi secara independen dengan probabilitas 0

properti

berikut:

Mengingat

setiap

n

+

elemen

m

, ada c titik di V yang berdekatan dengan masing-masing

dan tidak berdekatan dengan

.

Ternyata bahwa jika set titik dapat dihitung maka ada, hingga isomorfisma, hanya satu grafik dengan properti ini, yaitu grafik Rado. Jadi setiap grafik acak tak terbatas hampir pasti grafik Rado, yang untuk alasan ini kadangkadang disebut hanya grafik acak. Namun, hasil analog tidak berlaku untuk grafik terhitung, dari yang ada banyak (nonisomorphic) grafik memuaskan properti di atas. Model lain, yang generalisasi model grafik acak Gilbert, adalah model dot-produk acak. Sebuah dot-produk acak rekan grafik dengan masing-masing simpul vektor nyata. Probabilitas suatu uv tepi antara setiap simpul u dan v adalah beberapa fungsi dari titik produk u • v vektor masingmasing. Model probabilitas jaringan matriks grafik acak melalui tepi probabilitas, yang mewakili probabilitas p_ {i, j} bahwa keunggulan e_ diberikan {i, j} ada untuk jangka waktu tertentu. Model ini dapat dikembangkan untuk diarahkan dan diarahkan; tertimbang dan tertimbang; dan grafik statis atau dinamis struktur. Untuk M ≃ pN, di mana N adalah jumlah maksimal tepi mungkin, dua model yang paling banyak digunakan, G (n, M) dan G (n, p), hampir dipertukarkan.Grafik biasa acak membentuk kasus khusus, dengan sifat yang mungkin berbeda dari grafik acak pada umumnya.


23

Setelah kita memiliki model grafik acak, setiap fungsi pada grafik, menjadi variabel acak. Studi tentang model ini adalah untuk menentukan apakah, atau setidaknya memperkirakan probabilitas bahwa, properti mungkin terjadi. Dalam teori grafik, model Erdös-Rényi adalah salah satu dari dua model terkait erat untuk menghasilkan grafik acak. Mereka diberi nama oleh Paul Erdös dan Alfred Rényi, yang pertama kali memperkenalkan salah satu model ini pada tahun 1959. Model lainnya diperkenalkan secara independen dan serentak oleh Edgar Gilbert. Dalam model yang diperkenalkan oleh Erdös dan Rényi, semua grafik pada titik tetap diatur dengan jumlah tetap tepi. Dalam model yang diperkenalkan oleh Gilbert, setiap tepi memiliki probabilitas tetap hadir atau tidak, secara independen dari tepi lainnya. Model ini dapat digunakan dalam metode probabilistik untuk membuktikan keberadaan grafik memuaskan berbagai properti, atau untuk memberikan definisi yang ketat tentang apa artinya untuk properti untuk menahan untuk hampir semua grafik. Ada dua varian terkait erat dari Erdös-Rényi (ER) model random graph. Sebuah grafik yang dihasilkan oleh model binomial dari Erdös dan Rényi (p=0,01). Dalam G (n, M) model, grafik yang dipilih seragam secara acak dari koleksi semua grafik yang memiliki node n dan M tepi. Misalnya, dalam G (3, 2) model, masing-masing dari tiga kemungkinan grafik pada tiga titik dan dua sisi disertakan dengan probabilitas 1/3. Dalam G (n, p) model, grafik dibangun dengan menghubungkan node secara acak. Setiap sisi disertakan dalam grafik dengan probabilitas p independen dari setiap tepi lainnya. Ekuivalen, semua grafik dengan node n dan M tepi memiliki probabilitas yang sama Parameter p dalam model ini dapat dianggap sebagai fungsi pembobotan; sebagai p meningkat dari 0 ke 1, model menjadi lebih dan lebih mungkin untuk memasukkan grafik dengan lebih tepi dan kurang dan kurang kemungkinan untuk memasukkan grafik dengan tepi yang lebih sedikit.


Secara khusus, kasus p = 0,5 sesuai dengan kasus di mana semua

24

grafik

pada n simpul yang dipilih dengan probabilitas yang sama. Perilaku grafik acak sering dipelajari dalam kasus di mana n, jumlah simpul, cenderung tak terhingga. Meskipun p dan M bisa diperbaiki dalam kasus ini, mereka juga dapat berfungsi tergantung pada n. Sebagai contoh, pernyataan. Hampir setiap grafik di G (n,2ln(n)/n) terhubung. cara N cenderung tak terbatas, probabilitas bahwa grafik pada n simpul dengan probabilitas tepi 2ln (n) / n terhubung, cenderung 1 2.5.6 Scale-Free Network Graph (SFNG) Scale free network graph adalah jaringan yang mempunyai jumlah distribusi power-law, yaitu asimtotik. Artinya, fraksi P(k) dari node dalam jaringan memiliki koneksi k ke node lain berlaku untuk nilai-nilai besar k sebagai

dimana

adalah parameter yang nilainya biasanya dalam kisaran 2 <

< 3,

meskipun kadang-kadang mungkin berada di luar batas-batas tersebut. Preferential Attachment dan fitness model telah diusulkan sebagai mekanisme untuk menjelaskan jumlah distribusi power-law dalam jaringan nyata. Dalam studi tentang jaringan kutipan antara karya ilmiah, Derek de Solla Price menunjukkan pada tahun 1965 bahwa jumlah link ke kertas yaitu, jumlah kutipan yang mereka terima-memiliki distribusi heavy-tailed menyusul distribusi Pareto atau power-law, dan dengan demikian bahwa jaringan kutipan adalah skala bebas. Dia tidak masalah menggunakan istilah "jaringan skala bebas", yang tidak diciptakan sampai beberapa decade kemudian. Dalam sebuah makalah selanjutnya pada tahun 1976, Price juga mengusulkan mekanisme untuk menjelaskan terjadinya hukum kekuasaan di jaringan kutipan, yang ia sebut "keuntungan kumulatif" tapi yang sekarang lebih dikenal dengan nama lampiran preferensial. Baru-baru ini dalam jaringan skala bebas dimulai pada tahun 1999 dengan karya Albert-László Barabasi


25

dan rekan-rekannya di University of Notre Dame yang memetakan topologi sebagian dari World Wide Web, menemukan bahwa beberapa node, yang mereka sebut "hub", memiliki lebih banyak koneksi dari yang lain dan bahwa jaringan secara keseluruhan memiliki distribusi power-law dari jumlah link yang menghubungkan ke node. Setelah menemukan beberapa jaringan lain, termasuk beberapa jaringan sosial dan biologis, juga memiliki jumlah distribusi heavy-tailed, Barabasi dan kolaborator menciptakan istilah "jaringan skala bebas" untuk menggambarkan kelas jaringan yang menunjukkan distribusi power-law. Amaral et al. menunjukkan bahwa sebagian besar jaringan dunia nyata dapat diklasifikasikan ke dalam dua kategori besar berdasarkan jumlah distribusi derajat P (k) untuk k besar. Barabasi dan Albert mengusulkan mekanisme generatif untuk menjelaskan

penampilan

distribusi

power-law,

yang

mereka

sebut

"preferential attachment" dan yang pada dasarnya sama dengan yang diusulkan oleh Price. Solusi analitik untuk mekanisme ini (juga mirip dengan solusi Price) diadakan pada tahun 2000 oleh Dorogovtsev, Mendes dan Samukhin dan secara independen oleh Krapivsky, Redner, dan Leyvraz, dan kemudian dibuktikan dengan matematika Béla Bollobás. Namun, mekanisme ini hanya menghasilkan subset spesifik jaringan di kelas skala bebas, dan banyak mekanisme alternatif telah ditemukan. Sejarah

jaringan

skala

bebas

juga

mencakup

beberapa

ketidaksepakatan. Pada tingkat empiris, sifat skala bebas dari beberapa jaringan telah dipertanyakan. Misalnya, tiga bersaudara Faloutsos percaya bahwa Internet memiliki distribusi power-law atas dasar data traceroute; Namun, telah menyarankan bahwa ini adalah lapisan 3 ilusi yang diciptakan oleh router, yang mana muncul sebagai node-tingkat tinggi selama menyembunyikan layer 2 struktur internal dari ASes interkoneksi mereka. Pada tingkat teoritis, perbaikan untuk definisi abstrak skala bebas telah diusulkan. Misalnya, Li et al. (2005) baru-baru ini menawarkan "metrics skala bebas" yang berpotensi lebih tepat. Secara singkat, biarkan G adalah graf


26

dengan tepi set E, dan menunjukkan tingkat simpul v (yaitu, jumlah tepi kejadian untuk v) oleh \ deg (v). Menetapkan

Ini dimaksimalkan ketika node-tingkat tinggi yang terhubung ke nodetingkat tinggi lainnya.Sekarang mendefinisikan

Dimana Smax adalah nilai maksimum s (H) untuk H dalam himpunan semua grafik dengan distribusi gelar identik dengan G. Ini memberikan metric antara 0 dan 1, di mana grafik G dengan S kecil (G) adalah "skala-kaya", dan grafik G dengan S (G) mendekati 1 adalah "skala-bebas". Definisi ini diambil dari kesamaan diri yang tersirat dalam nama "skala-bebas". 2.5.6.1 Barabasi-Albert Model Barabasi-Albert

(BA) Model adalah sebuah algoritma untuk

membangkitkan jaringan skala bebas dengan menggunakan mekanisme Preferential Attachment. Jaringan skala bebas secara luas diamati dalam sistem alam dan buatan manusia, termasuk internet, world wide web, jaringan kutipan, dan beberapa jaringan sosial. Algoritma ini dinamakan oleh penemunya yaitu Albert-László Barabasi dan Reka Albert. Banyak jaringan diamati masuk ke dalam kelas jaringan skala bebas, yang berarti bahwa mereka memiliki power-law (skala bebas) distribusi derajat, sementara model grafik acak seperti (ER) Model Erdös-Rényi dan Watts-Strogatz (WS) tidak menunjukkan power-law. Barabasi-Albert model adalah salah satu dari beberapa model yang diusulkan yang menghasilkan jaringan skala bebas. Algoritma ini menggabungkan dua konsep umum yang penting: pertumbuhan dan preferential attachment. Baik pertumbuhan dan preferential attachment ada secara luas di jaringan nyata. Pertumbuhan berarti bahwa


27

jumlah node dalam jaringan meningkat dari waktu ke waktu. Preferential attachment berarti bahwa lebih banyak node yang terhubung, maka semakin besar kemungkinan untuk menerima link baru. Preferential attachment adalah contoh dari siklus umpan balik positif di mana variasi awalnya acak (satu simpul awalnya memiliki banyak link atau telah mulai mengumpulkan link lebih awal dari yang lain) secara otomatis diperkuat, sehingga sangat besar perbedaannya. Ini juga kadang-kadang disebut efek Matthew, "yang kaya semakin kaya", dan dalam kimia autocatalysis. Jaringan dimulai dengan jaringan terhubung awal node m0. Node baru ditambahkan ke jaringan satu per satu. Setiap node baru terhubung ke m ≤ m0 node yang ada dengan probabilitas yang sebanding terhadap jumlah link yang sudah memiliki node. Secara formal, probabilitas Pi terhadap node baru yang terhubung ke node i adalah:

Dimana ki adalah derajat simpul dari node i dan jumlah ini dibuat atas semua node yang sudah ada j (yaitu hasil denominator dua kali jumlah edges dalam jaringan). Node yang terhubung ("hub") cenderung cepat menumpuk ketika lebih banyak link, ketika node dengan hanya beberapa link yang mungkin untuk dipilih sebagai tujuan untuk link baru. Node baru memiliki "preferensi" untuk melampirkan diri untuk node yang terhubung.


28

Algoritma: Masukan: Jumlah Nodes N; Inisialisasi jumlah nodes m0; Offset Eksponen a; Minimum degree 1<= d <=m0. Keluaran: scale-free multigraph G=({0,….,N-1}, E). 1) Tambahkan nodes m0 ke G. 2) Hubungkan setiap node dalam G ke setiap node lain dalam G, buat grafik lengkap. 3) Buat node baru i. 4) Ambil node j seragam secara acak dari grafik G. Set P = (k (j) / k_tot) ^ a. 5) Ambil bilangan real R seragam secara acak antara 0 dan 1. 6) Jika P > R kemudian tambahkan j ke i daftar adjacency. 7) Ulangi langkah 4 - 6 sampai i memiliki node m dalam daftar adjacencynya. 8) Tambahkan i ke daftar adjacency dari setiap node dalam daftar adjacencynya. 9) Tambahkan i ke grafik. 10) Ulangi langkah 3-9 sampai ada N node dalam grafik.

2.6 Matriks Adjacency Jenis matriks yang biasa digunakan dalam analisa jaringan sosial adalah matriks adjacency. Nilai yang ada di tiap cell menunjukkan informasi atas hubungan atau relasi antar aktor atau individu. Matriks adjacency sangat berguna untuk melihat kedekatan antar aktor atau individu berdasarkan nilai yang ada di tiap cell. Pada penelitian ini skala pengukuran akan menggunakan binary yang hanya memiliki nilai 0 dan 1. Nilai 0 akan merepresentasikan tidak adanya hubungan, sedangkan nilai 1 merepresentasikan adanya hubungan antar aktor atau individu tertentu. Ada 2 tipe matriks adjacency, yaitu symmetric dan asymmetric. Sebuah jaringan sosial dapat terdiri dari 2 tipe ini. Jika terdapat relasi pertemanan antara Bob, Carol, Alice dan Ted, digambarkan bahwa Bob menjalin relasi dengan Carol, tetapi Carol tidak. Maka dari itu, matriks Xij tidak mungkin sama dengan matriks Xji, inilah yang disebut dengan asymmetric.


29

BAB III PERANCANGAN MODEL Pada bab ini akan dijelaskan perancangan model dan algoritma dalam mengubah graf ke dalam bentuk adjacency matriks. 3.1

Sumber Data Dalam penelitian ini, sumber data yang digunakan adalah data berupa graf yang diubah menjadi matriks adjacency, jika memiliki relasi maka bernilai 1, jika tidak maka bernilai 0. Data diambil dari social network facebook penulis dengan menggunakan bantuan aplikasi touchgraph. Touchgraph adalah software manipulasi dan grafik visualisasi yang digunakan untuk mempelajari jaringan aktor (sosial media). Perangkat lunak ini menampilkan hubungan antar individu. Individu akan diwakili oleh "node", kemudian hubungan antara individu akan menjadi sebuah "link". Aplikasi ini dapat memvisualisasikan jaringan pertemanan di facebook, sedangkan untuk random graph dan scale-free network graph didapat dengan menggunakan algoritma Erdos Renyi dan Barabassi-Albert.

3.2

Perancangan Model Perancangan model untuk merepresentasikan centrality pada jaringan manusia, random graph, dan scale-free network graph secara umum dapat digambarkan sebagai berikut:

Data Facebook, Random Graph, SFNG

Preprocessing

Perhitungan betweenness, closeness, degree centrality

Hasil

Gambar 3.1 Perancangan Model Data yang dipakai untuk melakukan perhitungan centrality pada jaringan manusia riil adalah dataset yang diperoleh dari facebook dengan menggunakan aplikasi touchgraph yaitu berupa graf yang diubah menjadi


30

matriks adjacency. Dataset yang diambil terdiri dari nama-nama pengguna facebook dan relasi antara pengguna. Untuk data random graph dan scale-free network graph menggunakan dataset yang dibangkitkan dengan algoritma Erdos Renyi dan Barabassi-Albert. Setelah dataset diperoleh, selanjutnya akan dilakukan

preprocessing

terhadap

data

tersebut.

Data

set

tersebut

direpresentasikan ke dalam bentuk matriks nxn, dengan n merupakan jumlah node yang terambil. Pada tugas akhir ini akan dilakukan perhitungan centrality yang meliputi betweenness centrality, closeness centrality, dan degree centrality pada jaringan manusia riil (nyata), random graph, dan scalefree network graph yang bertujuan untuk mengetahui individu yang paling penting

(popular)

dalam

sebuah

jaringan

relasi

manusia,

serta

membandingkan ketiga jaringan tersebut. Hasil perhitungan tersebut akan menampilkan nilai dari betweenness, closeness, dan degree centrality dari setiap graf. 3.3

Preprocessing Data yang digunakan merupakan dataset yang diperoleh dari social network facebook yang diambil menggunakan aplikasi touchgraph. Dataset terdiri dari nama-nama pengguna facebook dan relasi antar pengguna, sedangkan random graph dan scale-free network graph merupakan dataset yang diperoleh dengan menggunakan algoritma Erdos Renyi dan BarabassiAlbert. Data Facebook, Random Graph, SFNG

Pembuatan matriks

Gambar 3.2 Proses Preprocessing

Matriks nxn


31

Preprocessing dilakukan sebelum dataset memasuki proses inti. Berdasarkan Gambar 3.2 dapat dilihat alur yang terjadi saat preprocessing. Preprocessing yang dilakukan adalah pembuatan matriks dari dataset tersebut dengan cara merepresentasikannya ke dalam matriks nxn dengan n adalah jumlah node yang terambil. 3.3.1 Pembuatan Matriks Dari dataset tersebut kemudian direpresentasikan ke dalam bentuk matriks nxn dengan n adalah jumlah node yang terambil untuk dianalisis. Gambar 3.4 menunjukkan tabel berisi daftar pengguna yang terambil serta relasi yang terjadi. Relasi dipresentasikan dengan bilangan biner, yang artinya apabila memiliki relasi maka kolom tersebut bernilai 1, sedangkan jika tidak maka bernilai 0.

Gambar 3.3 Real Graf Facebook


Gambar 3.4 Representasi Matriks nxn Social Network Facebook dengan n=50

32


Gambar 3.5 Random Graph

Gambar 3.6 Representasi Matriks nxn Random Graph

33


Gambar 3.7 Scale-free graph

Gambar 3.8 Representasi Matriks nxn Scale-Free Graph

34


3.4

35

Parameter Simulasi Pada penelitian ini menggunakan beberapa parameter yang akan digunakan pada skenario simulasi pembentukan matriks di random graph dan scale-free graph. Parameter Random Graph Parameter

Nilai

Jumlah node

50

Probabilitas

0.1

Tabel 3.1 Parameter simulasi random graph Parameter Scale-free Graph Parameter

Nilai

Jumlah node

50

mlinks

4

Seed

[1 0 0 1 ; 1 1 0 0 ; 1 0 1 0 ; 0 0 0 1]

Tabel 3.2 Parameter simulasi scale-free graph 3.5

Skenario Simulasi Percobaan dilakukan terhadap 50 node dari jaringan manusia riil(facebook), random network, dan scale free-network. Node tersebut diubah ke dalam bentuk matriks adjacency yang bernilai 0 dan 1 yang kemudian dianalisis dengan menggunakan metrik centrality. Pada random graph menggunakan parameter seperti tabel 3.1 di atas yaitu jumlah node dan probabilitas untuk menghasilkan sebuah matriks nxn, sedangkan pada scalefree graph menggunakan parameter mlinks dan seed. Berikut adalah tahaptahap pembentukan matriks adjacency pada jaringan manusia riil (nyata), random network, dan scale-free network.


36

3.5.1 Real Human Network Algoritma: 1. Masukkan data facebook ke dalam touchgraph. 2. Ubah graf secara manual menjadi bilangan biner 0 dan 1, yang artinya jika berteman maka 1, jika tidak maka 0. 3. Selesai 3.5.2 Random Graph Algoritma: 1. Buat variabel A=erdos_reyni(n,p) 2. Nilai n diisi dengan jumlah node yang akan dimasukkan yaitu 50 dan nilai p diisi dengan probabilitas dari setiap node yaitu 0.1 3. Kemudian buat variabel x=full(A) 4. Selesai 3.5.3 Scale-free Graph Algoritma: 1. Buat variabel seed= [1 0 0 1 ; 1 1 0 0 ; 1 0 1 0 ; 0 0 0 1] 2. Buat variabel SFNet=SFNG(Nodes,mlinks,seed) 3. Nilai Nodes diisi dengan jumlah node yang akan dimasukkan yaitu 50, nilai mlinks diisi dengan jumlah link setiap node yaitu 4, dan seed merupakan variabel yang berisi bilangan biner 0 dan 1. 4. Selesai


BAB IV PENGUJIAN DAN ANALISIS 4.1

Perhitungan Centrality Pada bagian ini dilakukan perhitungan dengan menggunakan metrik centrality pada jaringan manusia riil, random network, dan scale-free network.. Dari hasil perhitungan kemudian akan dianalisis hasil dari proses perhitungan yang dilakukan. Setidaknya terdapat 3 buah metode dasar untuk dapat menghitung bobot centrality dari setiap node dalam suatu graf, yaitu: betweenness centrality, closeness centrality, dan degree centrality. Betweenness centrality adalah cara untuk menentukan bobot setiap node berdasar jalur terpendek yang dilewati oleh node lainnya. Closeness centrality adalah cara untuk mengukur kedekatan satu individu dengan individu lainnya, dan degree centrality adalah cara untuk mengukur popularitas individu dalam sebuah jaringan sosial. Adapun rumus untuk menghitung betweenness centrality, closeness centrality, dan degree centrality adalah: Betweenness Centrality: CB (i) =

Keterangan: σ_st (v) = jumlah shortest paths dari node s ke t yang melewati node v σ_st

= jumlah shortest paths dari node s ke t Closeness Centrality: C(i) = 1 / sum (simple_dijkstra(adj,i))

Keterangan: C(i) = Menghitung bobot suatu node ke i (simple_dijkstra(adj,i)) = Jumlah jarak terpendek antara node i dengan node lainnya 37


38

Degree Centrality: CD = sum (adj) Keterangan:

CD = Menghitung bobot suatu node sum = Perintah penjumlahan adj = Jumlah edge/link yang terbentuk pada node i dengan node lain pada matriks adjacency

4.2

Real Human Network

4.2.1 Betweenness Centrality 600

Nilai Betweenness Centrality

500

400

300

200

100

0

0

10

20

30

40

50

60

Node ID

Gambar 4.1 Grafik hasil betweenness centrality pada Real Human Network

Berdasarkan rumus, betweenness centrality adalah metode untuk menghitung bobot setiap node berdasar seberapa banyak node i dilalui oleh dua node lain dalam graf berdasar jalur terpendeknya. Nilai betweenness centrality 0-600 pada gambar 4.1 grafik di atas merupakan jarak terpendek suatu node yang dilalui oleh node lainnya. Berdasarkan grafik betweenness


39

centrality real graph (facebook) di atas nilai betweenness tertinggi ada di node 1, karena node 1 merupakan pusat (central) dalam real human network. Node 1 memiliki nilai betweenness sebesar 595,3566 yang artinya node tersebut berperan sebagai jembatan (penghubung) antara satu node dengan node yang lainnya ketika node tersebut ingin bertemu dan node 1 juga terhubung dengan semua node yang ada. Jika dibandingkan dengan yang lainnya node 1 memiliki hasil yang paling signifikan, karena node 2-50 memiliki hasil yang lebih rendah dan memiliki nilai betweenness yang hampir sama. Jika dilihat dari grafik di atas, maka node 1 merupakan node yang menghubungkan satu node dengan node lainnya, karena semakin besar nilai betweenness suatu node maka semakin besar pula node tersebut dilewati oleh node lainnya berdasarkan jarak terpendek. 4.2.2 Closeness Centrality 0.025

Nilai Closeness Centrality

0.02

0.015

0.01

0.005

0

0

10

20

30

40

50

60

Node ID

Gambar 4.2 Grafik hasil closeness centrality pada Real Human Network

Berdasarkan rumus, closeness centrality adalah salah satu cara untuk mengukur centrality dalam suatu jaringan sosial yang fokus terhadap seberapa dekat suatu aktor dengan semua aktor lainnya. Closeness centrality akan menghitung bobot centrality sebuah node berdasar jumlah jarak terpendek


40

antara node i dengan node lainnya. Angka 0-0.025 pada gambar 4.2 grafik di atas adalah nilai kedekatan sebuah node terhadap node lainnya. Dari hasil grafik di atas node 1 memiliki nilai closeness 0.0204. Jika diamati ada beberapa node yang memiliki hubungan yang relatif dekat dengan node lainnya seperti node 15, 20, 24, 28, 29, 32, 34, 40, dan 46, namun hubungan individu yang terjalin tidak sedekat (sepopuler) node 1 yang memiliki hasil paling signifikan dibandingkan dengan node lainnya. Dapat dikatakan demikian karena semakin besar nilai closeness sebuah node, maka semakin besar juga kedekatan node tersebut dengan node yang lainnya. 4.2.3 Degree Centrality y 50 45

Nilai Degree Centrality

40 35 30 25 20 15 10 5 0

0

10

20

30

40

50

Node ID

Gambar 4.3 Grafik hasil degree centrality pada Real Human Network

Berdasarkan rumus, degree centrality adalah cara untuk mengukur popularitas individu berdasarkan jumlah relasi yang dimiliki. Angka 0-50 pada sumbu y gambar 4.3 grafik di atas merupakan relasi/hubungan yang dimiliki suatu node dengan node lainnya. Pada degree centrality node 1 memiliki jumlah hubungan/relasi sebanyak 49. Jika dilihat dari grafik di atas ada beberapa node yang populer seperti node 15, 20, 24, 28, 32, 34, 40, dan

60


41

46, namun relasi yang dimiliki tidak sebanyak (sepopuler) node 1. Dapat dikatakan node 1 adalah individu yang paling populer, karena node 1 merupakan pusat diantara node yang lainnya dan memiliki hubungan langsung dengan semua node yang ada. Jadi semakin besar nilai degree suatu node maka semakin penting (populer) pula node tersebut dalam real human network. 4.2.4 Hubungan Betweenness, Closeness, dan Degree Centrality Dari ketiga grafik real human network di atas dapat dilihat bahwa node 1 merupakan node yang populer (penting) yang diukur dengan betweenness, closeness, dan degree centality. Nilai betweenness dari node 1 sebesar 595,3566 yang mana node 1 menjadi jalur terpendek antar node. Pada closeness node 1 memiliki nilai sebesar 0,0204 yang berarti node 1 memiliki hubungan yang dekat dengan node lainnya. Kemudian pada degree node 1 memiliki hasil sebesar 49 yang menunjukkan jumlah hubungan/relasi langsung dengan node lainnya. Dari hasil analisis tersebut dapat dikatakan bahwa hubungan node 1 terhadap betweenness, closeness, dan degree adalah node 1 memberikan pengaruh lebih besar kepada node lainnya dan menjadi node yang paling penting dalam sebuah jaringan relasi manusia dilihat dari ketiga metrik centrality. Analoginya adalah tipe orang populer yang kenal dengan semua orang akan memiliki pengaruh yang lebih besar karena dapat menyebarkan informasi lebih cepat tanpa perlu perantara pihak ketiga. Ini menunjukkan bahwa sifat karakteristik hubungan manusia itu terjadi berdasarkan hubungan sekitarnya.


4.3

42

Random Graph (Erdos Reyni)



300

250

200

150

100

50

0

0

10

20

30

40

50

60

Node ID

Gambar 4.4 Grafik hasil betweenness centrality pada Random Graph

Berdasarkan rumus yang ada, betweenness centrality adalah cara untuk mengukur bobot node berdasarkan jalur terpendek (shortest path). Angka 0400 pada gambar 4.4 grafik di atas merupakan jarak terpendek sebuah node ketika dilewati oleh node lainnya. Pada betweenness centrality random graph, node yang memiliki nilai betweenness tertinggi adalah node 25 yaitu 325,6295. Jika melihat grafik di atas, ada beberapa node yang memiliki nilai betweenness yang cukup tinggi seperti node 7, 9, 10, 33, 44, 45, dan 46, sedangkan di real human network hanya ada satu node yang memiliki nilai betweenness paling tinggi. Perbedaan yang sangat mencolok terlihat dari grafik real human network dan random graph, karena nilai betweenness di random graph lebih kecil jika dibandingkan dengan nilai betweenness di real human

network.

Ini

menunjukkan

bahwa

ketika

betweenness

direpresentasikan pada setiap node di random graph hampir setiap node


43

mempunyai kecenderungan sebagai penghubung antar satu node dengan node lainnya. 4.3.2 Closeness Centrality 0.01 0.009


0.008 0.007 0.006 0.005 0.004 0.003 0.002 0.001 0

0

10

20

30

40

50

60

Node ID

Gambar 4.5 Grafik hasil closeness centrality pada Random Graph

Berdasarkan gambar 4.5 grafik di atas, closeness centrality merupakan cara untuk mengukur kedekatan sebuah individu dengan individu lainnya. Angka 0-0.01 pada grafik di atas adalah nilai kedekatan dari sebuah node terhadap node lainnya. Pada closeness centrality di random graph, setiap node memiliki nilai kedekatan yang hampir sama contohnya seperti node 3, 7, 9, 10, 13, 14, 16, 17, 23, 28, 30, 31, 33, 34, 36, 41, 44, 45, 46, dan 48, namun ada satu node yang memiliki nilai closeness tertinggi sebesar 0.0096 yaitu node 25. Beberapa node tersebut pun memiliki perbedaan hasil yang tidak jauh dengan node 25. Ini menunjukkan bahwa setiap node di random graph memiliki hubungan/relasi kedekatan yang sama kuat.


44

4.3.3 Degree Centrality 9 8


7 6 5 4 3 2 1 0

0

10

20

30

40

50

60

Node ID

Gambar 4.6 Grafik hasil degree centrality pada Random Graph

Berdasarkan gambar 4.6 grafik di atas, degree centrality adalah cara untuk menentukan individu yang paling populer (penting) dalam sebuah jaringan sosial. Angka 0-10 pada gambar 4.6 grafik di atas merupakan jumlah koneksi suatu node terhadap node lainnya. Jika dibandingkan dengan real human network, pada random graph node yang paling populer adalah node 25 dan 46, hal ini dikarenakan kedua node ini memiliki jumlah koneksi yang sama yaitu 9. Jika diamati ada beberapa node juga yang memiliki hasil hampir sama seperti node 3, 7, 9, 10, 16, 17, 23, 28, 30, 33, dan 44. Dari grafik di atas terlihat jelas perbedaan degree centrality yaitu di real human network hanya ada satu node yang populer dan memiliki hubungan langsung dengan node lainnya, sedangkan di random graph ada dua node yang memiliki jumlah koneksi yang sama dengan node lainnya. Ini menunjukkan bahwa ketika degree centrality direpresentasikan di random graph maka penyebarannya juga secara acak.


45

4.3.4 Hubungan Betweenness, Closeness, dan Degree Centrality Pada random graph terdapat lebih dari satu node yang populer. Jika dilihat dari nilai betweenness, node 25 memiliki nilai sebesar 325,6295 yang mana merupakan node yang berperan sebagai penghubung antara node satu dengan node lainnya. Namun nilai betweenness di random graph lebih kecil jika dibandingkan dengan nilai betweenness di real human network. Pada closeness node 25 memiliki nilai sebesar 0,0096 yang berarti node 25 memiliki hubungan kedekatan dengan node lainnya. Kemudian pada degree centrality, nilai dari node 25 sebesar 9 yang mana node 25 memiliki jumlah hubungan/relasi sebanyak 9. Jika dilihat dengan seksama pada degree centrality node yang memiliki hasil tertinggi tidak hanya pada node 25, tetapi juga node 46 memiliki nilai degree yang sama dengan node 25 yaitu 9. Dari hasil analisis tersebut, hubungan setiap node terhadap betweenness, closeness, dan degree adalah bersifat acak. 4.4

Scale-Free Network Graph (SFNG)



500

400

300

200

100

0

0

10

20

30

40

50

Node ID

Gambar 4.7 Grafik hasil betweenness centrality pada Scale-free graph

60


46

Gambar 4.7 grafik di atas menunjukkan bahwa node 1 memiliki nilai betweenness yang paling tinggi di antara node yang lainnya yaitu sebesar 575,3217 yang artinya node 1 merupakan node yang menghubungkan satu node ketika ingin bertemu dengan node lainnya. Jika dibandingkan dengan grafik di real human network dan random graph, scale-free graph memiliki hasil yang hampir sama dengan real human network. Dapat dilihat dari grafik di atas bahwa hanya ada satu node yang memiliki hasil signifikan. Hal ini menunjukkan bahwa karakteristik scale-free graph mirip dengan real human network. Analoginya, anggap persimpangan sebagai node. Semakin banyak jalan yang harus melewati persimpangan itu (misal tidak ada jalan alternatif), maka semakin penting arti persimpangan tersebut. 4.4.2 Closeness Centrality 0.014


0.012

0.01

0.008

0.006

0.004

0.002

0

0

10

20

30

40

50

Node ID

Gambar 4.8 Grafik hasil closeness centrality pada Scale-free graph

Gambar 4.8 grafik di atas menunjukkan bahwa node 1 memiliki nilai kedekatan yang tinggi. Dapat dikatakan bahwa node 1 merupakan node yang memiliki hubungan/relasi yang dekat dengan semua node. Node 1 memiliki

60


47

nilai closeness sebesar 0.0125. Kemudian node yang memiliki nilai yang hampir sama dengan node 1 adalah node 5 dengan nilai kedekatan 0.0118. Jika dibandingkan dengan closeness di real human network, nilai setiap node di scale-free graph hampir sama, namun tetap node 1 yang memiliki nilai kedekatan yang paling tinggi dengan node lainnya. 4.4.3 Degree Centrality 45 40


35 30 25 20 15 10 5 0

0

10

20

30

40

50

60

Node ID

Gambar 4.9 Grafik hasil degree centrality pada Scale-free graph

Gambar 4.9 grafik di atas menunjukkan bahwa node 1 memiliki nilai degree paling tinggi yaitu sebesar 45. Node 1 berarti menjadi node yang populer (penting) dibandingkan dengan node lainnya. Sama seperti degree di real human network node 1 menjadi node yang memiliki jumlah hubungan paling banyak dengan node lainnya. Hal ini menunjukkan scale-free graph mempunyai karakteristik yang sama dengan real human network. Jadi, semakin besar nilai degree suatu node maka semakin penting (populer) pula node tersebut.


48

4.4.4 Hubungan Betweenness, Closeness, dan Degree Centrality Pada Scale-free graph, node yang memiliki nilai yang paling tinggi adalah node 1. Nilai betweenness dari node 1 sebesar 575,3217, nilai closeness sebesar 0,0125 dan nilai degree sebesar 45. Node 1 menjadi jalur terpendek/jembatan yang yang menghubungkan node satu dengan node lainnya. Node 1 juga memiliki hubungan yang dekat dengan semua node, dan menjadi node yang paling populer dikarenakan memiliki hubungan/relasi yang paling banyak. Dari hasil analisis tersebut, hubungan node 1 terhadap betweenness, closeness, dan degree yaitu node 1 menjadi individu yang paling populer, karena node 1 memberikan pengaruh yang besar daripada node lainnya. 4.5

Rekap Perbandingan Real Human Network dengan Random Graph Dari hasil analisis dengan menggunakan metrik centrality pada real human network dan random graph, keduanya memiliki perbedaan yang cukup mencolok. Dapat dilihat dari perhitungan betweenness centrality pada real human network hanya ada satu node yang menjadi penghubung antara satu node dengan node lainnya dan juga memiliki nilai tertinggi, sedangkan pada random graph ada beberapa node yang menjadi jembatan antar node. Jadi ketika betweenness direpresentasikan pada random graph nilai betweenness lebih kecil dibandingkan dengan real human network. Dari sisi closeness real human network hanya ada satu node yang memiliki hubungan yang dekat dengan node lainnya. Jika dibandingkan di random graph semua node memiliki kedekatan yang sama kuat karena setiap node memiliki perbedaan nilai yang tidak jauh. Kemudian pada degree real human network, tetap hanya ada satu node yang menjadi node yang paling populer (penting) karena memiliki jumlah relasi yang banyak terhadap node lainnya, tetapi ketika melihat di random graph ada dua node yang memiliki jumlah relasi yang sama dan menjadi node yang populer

dalam

jaringan tersebut.

Dari perbandingan tersebut


49

menunjukkan bahwa jaringan manusia riil hanya memiliki satu node yang populer, node tersebut menjadi penghubung antar node dan memiliki kedekatan dengan node lainnya dalam jaringan tersebut, sedangkan random graph sebaliknya memiliki lebih dari satu node yang populer hal ini dikarenakan random graph memiliki karakteristik acak. 4.6

Rekap Perbandingan Real Human Network dengan Scale-free Network Graph Dari hasil analisis yang telah dilakukan pada real human network dan scale-free network graph dengan menggunakan metrik centrality yaitu keduanya memiliki nilai yang hampir sama. Kita dapat melihat dari perhitungan betweenness, pada real human network ada satu node yang menjadi jembatan (hub node) antara satu node dengan node lainnya yaitu node 1 karena node 1 merupakan pusat (central) dalam jaringan tersebut, sedangkan pada scale-free graph node 1 juga menjadi jalur terpendek antar node. Dari sisi closeness, node 1 di real human network memiliki hubungan yang dekat dengan semua node yang ada. Jika dibandingkan dengan real human network, nilai setiap node di scale-free graph hampir sama, namun tetap node 1 yang memiliki kedekatan yang paling tinggi dengan node lainnya. Kemudian pada degree, di real human network node yang memiliki relasi yang kuat dengan node lainnya adalah node 1, demikian pula pada scale-free graph node 1 pun menjadi node yang paling populer karena memiliki relasi hampir maksimum. Jadi dari perbandingan tersebut menunjukkan bahwa node 1 menjadi pusat dari semua node yang ada, node 1 merupakan penghubung antar node. Node 1 juga memiliki kedekatan dengan node lainnya, serta memiliki hubungan relasi paling banyak dibanding node lainnya. Jadi, ketika melihat hasil analisis yang dilakukan, jaringan manusia riil memiliki karakteristik yang sama dengan scale-free network

graph.


BAB V PENUTUP 5.1

Kesimpulan Adapun beberapa kesimpulan yang diperoleh dari perhitungan dan análisis yang dilakukan dengan menggunakan metrik centrality terhadap Jaringan Manusia Rill, Random Network, dan Scale-free Network adalah: 1) Perhitungan centrality di Jaringan Manusia Riil dilihat dari betweenness, closeness, dan degree centrality dalam penentuan central dari suatu jaringan. Dimana hanya ada satu node yang menjadi jembatan (hub node) antar satu node dengan node lainnya dilihat dari betweenness centrality, memiliki hubungan yang dekat dengan node lainnya dilihat dari closeness centrality, dan memiliki relasi/hubungan langsung dengan node lainnya dilihat dari degree centrality. 2) Setiap node di random graph mempunyai kecenderungan sebagai penghubung antar satu node dengan node lainnya berdasarkan perhitungan yang dilakukan dengan betweenness centrality. Setiap node memiliki hubungan kedekatan yang sama kuat karena random graph memiliki karakteristik acak dilihat dari perhitungan closeness centrality dan degree centrality. 3) Sebagian orang menganggap bahwa hubungan/relasi manusia di dunia ini adalah random/acak, namun dari penelitian yang telah dilakukan dengan menggunakan

betweenness,

closeness,

dan

degree

centrality

dapat

disimpulkan bahwa hubungan manusia tidak acak. Hal ini dapat dilihat dari perhitungan metrik centrality pada real human network, random graph, dan scale-free graph. Scale-free graph sendiri memiliki karakteristik yang sama dengan real human network dilihat berdasarkan parameter yang ada yaitu jumlah node, mlinks, dan

seed.

50


51

DAFTAR PUSTAKA 1. Bonacich, P., 2005. “Centrality and network flow”. Journal of Social Networks. 27, 55-71. 2. Freeman, L. C. (1978). Centrality in social networks: Conceptual clarification. Social Networks 1, 215-239. 3. Freeman, L.C., Borgatti, S.P., White, D.R., 1991. Centrality in valued graphs: a measure of betweenness based on network flow. Social Networks 13, 141– 154. 4. John, Paul Hatala.2006.Social Network Analysis in Human Resource Development : A New Methodology, Louisana State University. Loisana : SagePublications 5. Kretschmer, Hildrun. Kretschmer Theo. 2010. A New Centrality Measure for Social Network Analysis Applicable to Bibliometric and Webometric Data. Humboldt-University Berlin : Department of Library and Information Science, 26-D-10117 6. Opsahl, T., Agneessens, F., Skvoretz, J., (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks 32 (3), 245-251,

dari

http://toreopsahl.com/2010/04/21/article-node-centrality-in

weighted-networks-generalizing-degree and-shortestpaths/ 7. Scott John. "Social Network Analysis Theory and Application". 2011. 8.

Susanto Budi, et al. “Penerapan Social Network Analysis dalam Penentuan Centrality”. Fakultas Teknologi Informasi. Universitas Kristen Duta Wacana. Yogyakarta.

9. Tsevetovat Maksim and Kouznetsov Alexander."Social Network Analysis for Startups". O'Reilly. 2011. 10. Yunita Diska, et al. “Analisis dan Implementasi Betweenness Centrality pada Social Network Twitter dengan Metode Linear Scaling Berbasis Pengguna”. Fakultas Informatika. Universitas Telkom. Bandung


LAMPIRAN Tabel Data Hasil Pengujian Real Human Network Hasil Pengujian Node ID

Betweenness

Closeness

Degree

1

595.3566

0.0204

49

2

96.3403

0.0135

24

3

10.7971

0.0132

22

4

6.2471

0.0133

23

5

23.6805

0.0137

25

6

22.5422

0.0119

14

7

0

0.0105

3

8

33.3432

0.0137

25

9

2.1667

0.0106

4

10

6.3516

0.0112

9

11

19.6873

0.013

21

12

1.1107

0.0109

6

13

15.762

0.0139

26

14

8.1845

0.0114

10

15

29.0098

0.0149

31

16

7.45

0.0112

9

17

43.1148

0.0133

23

52


18

15.1344

0.0139

26

19

14.3871

0.0139

26

20

46.5276

0.0149

31

21

1.5683

0.0114

10

22

3.1934

0.0127

19

23

9.376

0.012

15

24

22.8019

0.0149

31

25

14.2127

0.0137

25

26

1.3012

0.011

7

27

6.6236

0.0125

18

28

22.1238

0.0149

31

29

46.1703

0.0164

37

30

1.229

0.0116

12

31

8.8464

0.0114

10

32

30.983

0.0159

35

33

4.9863

0.0128

20

34

32.0449

0.0152

32

35

13.3354

0.0139

26

36

4.6603

0.0132

22

37

7.5076

0.0109

6

38

20.5001

0.0128

20

39

10.1952

0.0132

22

40

42.0056

0.0152

32

53


41

2.9386

0.0108

5

42

10.7861

0.0137

25

43

7.5845

0.0114

10

44

1.3679

0.0112

9

45

25.9195

0.0141

27

46

23.4793

0.0152

32

47

22.9402

0.013

21

48

10.7908

0.0133

23

49

10.9293

0.0132

22

50

2.4052

0.0127

19

Random Graph Hasil Pengujian Node ID

Betweenness

Closeness

Degree

1

40.2183

0.0077

3

2

110.9913

0.0076

4

3

113.1001

0.0086

6

4

50.2286

0.0072

4

5

16.3333

0.0066

3

6

41.2214

0.007

4

7

174.1603

0.0088

7

8

28.239

0.0074

3

9

214.1476

0.0084

6

54


10

199.1525

0.0077

6

11

38.819

0.0071

4

12

0

0.0061

2

13

93.7778

0.0085

5

14

48.5568

0.0076

4

15

40.9786

0.0071

4

16

123.3976

0.0081

6

17

126.5739

0.0087

6

18

69.027

0.0076

4

19

86.7017

0.0074

5

20

0

0.0056

1

21

106.4397

0.0067

3

22

33.9714

0.007

4

23

133.5149

0.0082

6

24

34.3889

0.0067

3

25

325.6295

0.0096

9

26

0

0.0051

1

27

17.4371

0.0072

3

28

116.3098

0.0081

6

29

22.4443

0.0071

4

30

113.5603

0.0082

6

31

70.802

0.0081

5

32

5.5833

0.006

2

55


33

196.896

0.0083

7

34

96.5492

0.0083

5

35

32.2952

0.0068

3

36

85.8965

0.0082

5

37

37.846

0.0075

5

38

16.3767

0.007

3

39

37.4714

0.0075

3

40

59.9191

0.0074

4

41

102.2004

0.0082

5

42

29.9667

0.0075

3

43

93.5535

0.0077

6

44

168.7384

0.0088

7

45

186.1144

0.0085

6

46

261.9137

0.0092

9

47

0

0.0063

2

48

90.524

0.0079

5

49

74.2366

0.0076

5

50

81.796

0.0074

4

56


Scale-free Network Graph Hasil Pengujian Node ID

Betweenness

Closeness

Degree

1

575.3217

0.0125

45

2

97.3899

0.01

17

3

66.2375

0.01

15

4

26.9468

0.009

13

5

455.1541

0.0118

38

6

257.0518

0.011

28

7

235.1694

0.0112

26

8

62.6133

0.0102

12

9

14.7413

0.0093

10

10

177.9569

0.0102

20

11

218.1983

0.011

20

12

66.7739

0.0094

14

13

9.0869

0.0085

6

14

11.5599

0.0081

8

15

10.0235

0.009

8

16

7.8415

0.0091

8

17

247.1911

0.0108

24

18

45.7215

0.0085

14

19

66.8155

0.0098

14

20

4.3397

0.0083

6

57


21

33.0199

0.009

10

22

14.2621

0.0094

8

23

49.5013

0.0088

10

24

1.3333

0.0074

6

25

20.5911

0.0094

8

26

3.9206

0.0083

6

27

11.5512

0.0089

8

28

4.6667

0.0084

6

29

2.2595

0.0081

6

30

5.2185

0.0083

6

31

0

0.0081

6

32

74.1156

0.0092

14

33

10.0027

0.0088

6

34

9.627

0.0083

8

35

11.9702

0.0088

6

36

17.9302

0.0088

8

37

28.5113

0.0093

8

38

22.8297

0.0083

8

39

7.8345

0.008

6

40

10.9425

0.0085

6

41

34.4029

0.0088

8

42

10.7333

0.0076

6

43

18.7474

0.0088

6

58


44

3.4696

0.0094

6

45

5.7512

0.0081

6

46

2.3598

0.0093

6

47

9.5687

0.0083

6

48

17.7979

0.0088

8

49

3.7679

0.0083

6

50

2.179

0.0081

6

59

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents