Aplikasi Graf dalam Situs Jejaring Sosial

Aplikasi Graf dalam Situs Jejaring Sosial Muhammad Aodyra Khaidir 13513063 Program Magister Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia [email protected]

Abstrak— Pada situs jejaring sosial, setiap orang yang memiliki akun pada situs tersebut pasti terhubung dengan teman – temannya. Keterhubungan orang yang satu dengan yang lain memiliki banyak informasi atau data. Graf merupakan gambaran yang tepat untuk menginterpretasikan informasi atau data dari keterhubungan ini. Misalnya, penggunaan graf untuk mengetahui hubungan sosial antara orang lain, menemukan teman lama, dan mengetahui karakteristik orang tersebut. Hal ini dapat dilakukan, karena graf dapat menggambarkan keterhubungan orang yang satu dengan lainnya dengan syarat – syarat tertentu. Keywords—Graf, keterhubungan, karakter, informasi.

masyarakat bisa diketahui apa yang masyarakat minati, ketertarikan masyarakat kepada hal tertentu, masalah sosial masyarakat tertentu, dan solusi – solusi untuk permasalahan tersebut. Banyak sekali penggunaan graf dalam suatu situs jejaring sosial, seperti yang sudah disebutkan diatas. Situs jejaring sosial memudahkan kita untuk mencari relasi, menemukan relasi, lebih jauh lagi, graf juga dapat membantu kita mengetahui musik kesukaan orang tertentu, tempat berlibur yang paling digemari, dan buku yang digemari dari relasi antara orang yang satu dengan yang lain.

II. TEORI

I. Pendahuluan Manusia sebagai makhluk sosial pasti berhubungan dengan orang lain. Baik berhubungan langsung maupun tidak langsung. Manusia juga sebagai makhluk sosial pasti membutuhkan orang lain, baik dia menyadari atau tidak setiap manusia saling membutuhkan. Hubungan manusia dengan yang lain bisa dimasukkan kebeberapa kategori, seperti keluarga, teman, suami, istri, saudara, sepupu. Hubungan orang yang satu dengan yang lain bisa dihubungkan oleh beberapa orang atau langsung, misalnya hubungan A dan X yaitu sepupu dihubungkan oleh kakek dan nenek yang sama. Sehingga dengan keterhubungan ini, bisa didapatkan keterhubungan lain dari orang tersebut. Perkembangan teknologi , terutama situs jejaring sosial memudahkan kita untuk berhubungan dengan orang lain. Seperti situs jejaring sosial yang banyak kita gunakan, Facebook, Twitter, Path, dan lain – lain. Situs – situs itu menyimpan informasi atau data dari keterhubungan orang lain ini, dari teman – teman masa kecilnya sampai teman kerjanya bisa digambarkan dalam graf yang terhubung dan mungkin terhubung dengan kita juga. Dari data pribadi yang disimpan pada situs jejaring sosial ini juga dapat diketahui hobi dan kesukaan dari orang tersebut, yang bisa digambarkan graf untuk keterhubungan orang yang satu dengan lainnya dengan kesamaan hobi dan karakter – karakter lainnya. Pemanfaatan graf pada hubungan sosial ini bisa sangat membantu, misalnya untuk mencari teman baru dengan hobi tertentu, menemukan teman lama, mengetahui karakter orang tersebut, dan untuk suatu lingkungan

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2014/2015

1. Teori Dasar Graf A. Defini Graf Dalam buku Matematika Diskrit[1], didefinisikan graf G sebagai pasangan himpunan (V,E), dimana V merupakan himpunan simpul dan E himpunan sisi. Notasi G = (V,E) V tidak kosong, dan E himpunan sisi yang menguhubungkan sepasang simpul. V = {V1, V2, V3,…, Vn} E = {e1,e2,e3,…,en} Jika graf mempunyai satu simpul tanpa adanya sisi, dinamakan graf trivial. Dua buah sisi yang meghubungkan dua simpul yang sama dimakan sisi ganda. Sisi yang menghubukan simpul yang sama dinamakan gelang atau kalang(loop). 1

1 e1

2

3

e2

2 e5

4

e3

1 e4

e1 3

e6 e7 4

(a)

(b) Gambar 1 Contoh graf

e2

2 e5

e3

e4

e6

3 e7

4

(c)

Dari gambar diatas e3 dan e4 dimanakan sisi ganda, karena menghubungkan dua simpul yang sama , yaitu simpul(node) 1 dan simpul(node) 3. Sisi e5 disebut

e8

gelang/kalang karena menghubungkan simpul yang sama, yaitu simpul(node) 3. Sisi e dapat ditulis juga dalam (v1,v2), yang berarti sisi e menghubungkan simpul v1 dan v2.



Graf Kosong Graf yang himpunan sisinya merupakan graf kosong. 1

B. Jenis – Jenis Graf Graf dapat digolongkan berdasarkan ada tidaknya sisi ganda atau gelang pada graf tersebut[1].  Graf sederhana(simple graph) Graf yang tidak mengandung gelang dan sisi ganda dinamakan graf sederhana. Contoh Gambar 1 (a) merupakan graf sederhana.  Graf tak-sederhana Graf yang mengandung sisi ganda atau gelang dimakan graf tak sederhana. 1. Graf ganda (multigraph), graf yang mengandung sisi ganda. Contoh Gambar 1 (b) merupakan graf ganda, karena memiliki sisi ganda. 2. Graf semu (pseudograph), graf yang mengandung gelang (loop). Contoh Gambar 1 (c) merupakan graf semu, karena memiliki gelang. Penggolongan graf berdasarkan orientasi arah pada sisi, graf dibedakan menjadi 2 jenis [1]:  Graf tak-berarah Graf yang sisinya tdak mempunyai orientasi arah disebut graf tak berarah. Contoh Gambar 1  Graf Berarah Graf yang sisinya diberikan orientasi arah dinamakan graf berarah. 1

4

3





1

 2

3

4

2

3

4

Gambar 2 contoh graf berarah dan graf ganda berarah 

2 5



Graf ganda berarah (director multigraph) Pada graf ganda berarah, gelang dan sisi ganda dapat ada dan setiap sisinya berarah.

Gambar 3 Graf kosong Derajat(Degree) Derajat (Degree) suatu simpul pada graf tak-berarah adalah jumlah sisi yang beririsan dengan dengan simpul tersebut. Simpul – simpul yang berederajat satu disebut anting – anting. Contoh pada Gambar 1 (a) derajat simpul 1 adalah dua. Lintasan(Path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn dalam graf G adalah barisan selangseling antara simpul-simpul dan sisi-si yang berbentuk v0,e1,v1,...,vn-1,en,vn. e1 = {v0,v1}, en = {vn-1,vn}. lintasan dimana hanya melewati satu kali setiap simpul dan sisi dinamakan lintasan sederhana. Lintasan yang berakhir dan berawal pada simpul yang sama dikatakan lintasan tertutup, sedangkan litasan yang tidak berakhir dan berawal dari simpul yang sama dikatakan lintasan tebuka. Panjang lintasan adalah jumlah sisi yang dilewati dari satu simpul ke simpul yang dituju. Siklus atau Sirkuit Sirkuit atau siklus adalan lintasan tertutup, yaitu lintasan yang berawal dan berakhir di simpul yang sama. Terhubung Dua buah pasang simpul dikatakan terhubung, jika terdapat lintasan antara kedua simpul tersebut. Graf G dikatakan terhubung jika setiap pasang simpul pada V terhubung. Jika tidak, maka G disebut graf takterhubung. Contoh graf terhubung Gambar 1 (a).

C. Termonilogi Dasar Istilah – istilah atau terminologi yang berkaitan dengan graf [1]:  Bertetangga Dua buah simpul pada graf tak-berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Contoh pada Gambar 1 (a) simpul 1 dan 3 bertetangga.  Beririsan Sisi e dikatan beririsan dengan kedua simpul yang dihubungkan olehnya. Contohnya pada Gambar 1 (b) e1 beririsan dengan simpul 1 dan 2.  Simpul Terpencil Simpul yang tidak mempunyai sisi beririsa dengannya. Cohtoh jika semua sisi yang beririsan dengan simpul 3 pada Gambar 1 (a) dihilangkan, maka simpul 3 menjadi simpul terpencil.

2 5

1

4 6 3

8

7

Gambar 4 contoh graf tak-terhubung Pada graf berarah G, dikatakan terhubung jika graf tak-berarahnya terhubung. Dua simpul pada graf berarah G dikatakan terhubung kuat jika terdapat lintsan berarah dari u ke v dan v ke u. Sedangkan, graf berarah G dikatakan terhubung lemah jika terdapat lintasan berarah hanya dari u ke v atau sebaliknya. 1 1 2


2 3

4

3



Gambar 5 contoh graf berarah terhubung lemah dan graf berarah terhubung kuat Upagraf Sebuah graf G1 dikatakan upagraf dari graf G, jika himpunan simpulnya V1` merupakan himpunan bagian himpunan simpul graf awal G, dan himpunan sisinya juga merupakan himpunan bagian himpunan sisi graf awal G. 2

2

1

1

1

3

3

3 6

4



6 2

5

1





5

5

(a) (b) (c) Gambar 6 (a)graf awal, (b) upagraf, (c)upagraf yang komplemen dengan (b) Upagraf Merentang Graf G1 dikatakan upagraf merentang dari upagraf G, jika upagraf G1 mengandung semua simpul graf G, dan himpunan sisinya merupakan himpunan bagian dari himpunan sisi graf G. 1

2

3

4

5

Jaringan sosial adalah struktur sosial yang dibuat oleh beberapa agen sosial, seperti individu atau organisasi, dan setiap agen sosial mempunyai hubungan satu sama lain[2]. Situs jejaring sosial adalah alat untuk membuat jaringan sosial antara seseorang dengan orang lain, yang memiliki latar belakang, aktifitas, ketertarikan pada hal tertentu, atau membagikan cerita tentang dirinya. Situs jejaring sosial adalah aplikasi berbasis web yang membolehkan invidu untuk membuat profil, membuat koneksi dengan orang lain, pada suatu sistem tertentu[3]. Situs jejaring sosial memudahkan seseorang unutk berhubungan dengan orang lain tanpa harus kontak fisik. Selain itu, kelebihan situs jejaring sosial adalah kita dapat mencari teman baru yang memili ketertarikan pada hal tertentu, teman dari luar negeri yang mempunya budaya yang khas, mencari kerabat jauh, dan seterusnya.

1

2

3

4

E. Situs Jejaring Sosial

2

3

5

(a) (b) (c) Gambar 7 (a) graf awal, (b) upagraf merentang, (c) bukan upagraf merentang Cut-Set Cut-Set adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen terhubung. Graf Berbobot Graf yang setiap sisinya diberi sebuah harga (bobot).

D. Graf Sederhana Khusus Bedasarkan refrensi[1] ada beberapa graf sederhana khusus yang dijumpai pada banyak aplikasi.  Graf Lengkap Graf lengkap adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.  Graf Lingkaran Graf sederhanan yang setiap simpulnya berderajat dua.  Graf Teratur Graf yang setiap simpulnya mempunyai derajat yang sama  Graf Bipartit Graf G yang himpunan setiap simpunya dapat dikelompokkan menjadi dua himpunan bagian V1 dan V2,sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2. Sehingga, setiap pasang simpul di V1 dan setiap pasang simpul di V2 tidak bertetangga.

Gambar 8 statistik penggunaan situs jejaring sosial di internet dalam juta[4] Dari data diatas bisa dilihat banyak sekali pengguna situs jejaring sosial di internet. Pertama dipimpin oleh Facebook dengan total user 1 milyar lebih. Disusul dengan situs – situs lain dengan total user masing – masing situs kurang dari 1 milyar. Dengan banyak pengguna situs jejaring sosial seperti ini, memudahkan kita untuk membuat koneksi dengan orang lain, walaupun beda negara.

III. Pemanfaatan Graf dalam Situs Jejaring Sosial A. Penggambaran Relasi antar Individu Pada penggambaran relasi antar orang di situs jejaring sosial. Simpul (node) pada graf tersebut adalah pengguna atau individu. Lalu, sisi menggambar hubungan apa yang ada antara orang yang satu dengan lainnya. sehinnga, simpul – simpul yang ada pada graf tersebut dihubungkan oleh sisi – sisi tersebut. Graf pada pemanfaatannya di situs jejaring sosial, dapat digunakan untuk banyak kondisi yang menghubungkan oang yang satu dengan lainnya. Ada graf yang


menghubungka seseorang dengan orang lain, karena hubungan keluarga. Selain itu, ada graf yang menghubungkan seseorang dengan orang lain, karena hubungan pertemanan. Ada juga graf yang menghubungkan seseorang dengan orang lain, karena hubungan selera musik, graf yang menghubungkan seseorang dengan orang lain dari persamaan hobi, olahraga, makanan kesukaan dan seterusnya.

Sama seperti Gambar 9, disini pengguna situs jejaring sosial, bisa membuat sisi baru yang beririsan antara pengguna dengan orang yang dia kenal, dengan opsi Add Friend atau follow pada situs jejaring sosial tersebut. Misalnya B adalah keluarga jauh dari G, B tidak mengetahui G mempunyai akun di situs tersebut, namun karena ada keluarga lain yang sudah mempunyai sisi berhubungan dengan G, sehingga ada lintasan antara B dengan G. Dengan adanya lintasan ini, B bisa mendapatkan opsi untuk menambah sisi dengan G.

Gambar 9 graf pertemenan Pada Gambar 9 dapat dilihat bagaimana graf menggambarkan hubungan kekeluargaan anatar seseorang dengan orang lain. Pada Gambar 8, simpul A, B, C, D, E menujukkan individu, sisi – sisinya menujukkan hubungan pertemanan. A berteman dengan B, A berteman dengan C, B berteman dengan D, dan D berteman dengan E. Graf ini sangat berguna untuk situs jejaring sosial, karena bisa diketahui adanya hubungan antar A dengan D dan E, atau hubungan B dengan C. sehingga pengguna dari situs jejaring sosial itu dapat diberikan opsi intuk menambah teman dari teman kita yang mungkin kita kenal. Misalnya, A diberikan opsi untuk menambahkan D dan E menjadi teman di situs jejaring sosial tersebut. Hal ini sangat berguna untuk pengguna situs tersebut. Pengguna dapat menambahkan teman yang sebelumnya dia tidak tahu bahwa temannya juga memiliki akun di situs jejaring sosial tersebut. Misalnya, A awalnya tidak mengetahui E memiliki akun di situs tersebut, namun karena ada hubungan pertemanan atau lintasan dari A menuju E, A mendapat opsi untuk menambahkan E menjadi teman.

Gambar 10 Graf hubungan kekeluargaan Pada Gambar 10, digambar hubungan kekeluargaan seseorang dengan graf. Simpul, A, B, C, D, E, F, G menujukkan individu yang berada pada keluarga tersebut, dan sisi yang menghubungkan simpul – simpul menujukkan adanya hubungan kekeluargaan antara simpul tersebut.

Gambar 11 graf dengan sisi baru antara B dengan G Pada Gambar 10, terbentuk sisi baru antara B dengan G, karena pengguna B memilih opsi Add Friend atau Follow pengguna G. Dengan tambahan sisi baru ini B dan G dapat berhubungan secara langsung, dan dari penambahan sisi baru ini pengguna B mendapatkan lebih banyak opsi keluarga yang dia kenal yang sudah mempunya sisi dengan E. Akibat dari pemilihan opsi – opsi ini untuk membuat sisi langsung menuju teman atau keluarga yang pengguna situs pilih, makin banyak data dan informasi yang tersimpan. Struktur data yang cocok untuk merepresentasikan data ini adalah graf, karena memudahkan pembuat situs tersebut untuk menyimpan data relasi antara satu orang dengan orang lain. Untuk menggambar hubungan atau relasi antar satu individu dengan individu lain, tidak bisa digabungkan manjadi satu graf, karena pengertiannya nanti akan berbeda. Seperti Gambar 9 dan 10 tidak bisa digabungkan, karena pengertinnya nanti akan berbeda. Sehingga untuk menggambar graf dengan relasi yang berbeda perlu digambarkan graf baru yang merepresentasikan graf tersebut. Situs jejaring sosial juga menawarkan opsi seperti mencari orang di lingkungakan sekitar kita dengan kriteria tertentu. Krteria – kriteria yang sama anatara orang yang satu dengan lainnya bisa didapatkan dari data/informasi yang pengguna simpan di situs tersebut, seperti hobi, tempat makan yang disukai, dan lain – lain. Situs jejaring tersebut menambah fitur search untuk mencari kriteria tersebut, sehingga pengguna dapat mencari masyrakat sekita yang mempunya kriteria tertentu. Misalnya pengguna memasukkan query pada fitur search untuk menemukan orang dengan hobi tertentu. Awalnya hubungan antara seseorang dengan orang tertentu tidak ada dan menghasilkan graf kosong.


Gambar 12 graf kosong hasil pencarian orang dengan hobi tertentu Selanjutnya, dari yang sebelumnya orang tersebut tidak kenal, mereka menambah sisi atau relasi sehingga terbentuklah suatu komunitas dengan kesamaan hobi atau ketertarikan dengan sesuatu.

Gambar 14 graf berbobot Graf ini juga bisa digunakan untuk memasarkan suatu produk. Seorang marketer harus mampu menganalisis graf atau hubungan sosial untuk memasarkan produknya. Misalnya, target utama pemasaran adalah orang yang mempunya banyak relasi dan hubungan dekat dengan orang lain. Sehingga, orang yang seperti ini dapat berpengaruh atau secara tidak lansgung ikut membantu memasarkan produk tersebut ke orang yang dia kenal. Pada graf diatas A merupakan target pemasaran yang cocok untuk memasarkan produk, karena A mempunya relasi yang banyak dan hubungan dekat ke orang lain. Namun, tidak hanya itu target pemasaran juga harus pada orang yang suka dengan produk tersebut.

Gambar 13 graf dengan keterhubungan antara setiap individu Dari gambar diatas juga dapat diketahui apa yang sedang masyrakat minati, mulai dari makanan yang sedang banyak diminati, film yang sedang banyak diminati, permainan yang sedang diminati, tempat – tempat yang ramai pengunjung, tempat wisaya yang biasa dikunjungi oleh masyrakat, keadaan trasportasi yanga da di masyrakat tersebut, dan seterusnya.

B. Kegunaan dari Aplikasi Graf pada Situs Jejaring Sosial Banyak sekali manfaat yang bisa digunakan dengan graf yang ada di situs jejaring sosial, seperti bagian pemasaran suatu perusahaan untuk menganalisis produk unggulan, bagian kedokteran untuk menganalisis penyebab penyakit yang banyak diderita di lingkungan masyrakat tertentu, mencari tahu tujuan penggunaan situs jejaring sosial. Pada graf dibawah ini menggambarkan hubungan antar individu dengan bobot yang menandakan seberapa dekat hubungan tersebut.

Gambar 15 graf menggambar orang yang suka terhadap suatu produk Pada Gambar 15 ditunjukkan orang – orang yang suka terhadap suatu produk, yaitu F, I, G, ketiga orang itu merupakan potensi menjadi terger pemasaran produk. Namun, untuk memasarkan produk juga harus diperhitungkan apakah orang bersangkutan mempunyai relasi yang banyak dan banyak hubungan dekat orang lain, atau mempunyai hubungan dengan orang yang punya banyak relasi. Dari gambar diatas, orang yang cocok adalah I, karena ini mempunya hubunungan yang cukup dekat dengan A yang punya banyak relasi. Orang yang mempunya kriteria atau umur yang sama dengan I juga termasuk target pemasaran. Berdasarkan refrensi[5], marketing di situs jejaring sosial adalah proses untuk mendapatkan perhatian pengguna atau lalu lintas di situs jejaring sosial tersebut. Sehingga, banyak pengguna tertarik menggunakan produk yang dipasarkan.

IV. Kesimpulan Aplikasi graf pada situs jejaring sosial banyak sekali, mulai dari membuat koneksi baru dengan orang lain, mencari teman baru dengan kesamaan hobi atau kertarikan pada hal tertentu, mecari kerabat jauh. Pemanfaatan graf


juga dapat digunakan untuk menentukan target pemasaran, mengetahui masalah disuatu masyrakat, dan seterusnya. Merepresentasikan hubungan seseorang dengan orang lain dengan graf sangat baik, karena data – data yang didapat pengguna situs jejaring sosial mudah direpresentasikan dengan graf.

V. Ucapan Terimakasih Puji syukur penulis panjatkan kepada tuhan YME, berkat rahmat dan izin-nya makalah ini dapat diselesaikan tepat waktu. Rasa terima kasih juga penulis ucapkan kepada Dr. Ir. Rinaldi Munir, MT, dan Harlili S., M.Sc. atas bimbingannya selaku dosen matematika diskrit. Penulis juga mengucapkan terima kasih kepada orang tua penulis, dan teman – teman atas segala doa, bantuan, masukan, sehingga masalah ini dapat selesai.

REFERENCES [1] [2]

[3]

Munir, Rinaldi. MATEMATIKA DISKRIT Revisi Kelima. Bandung: Penerbit Informatika. 2012 Wasserman, Stanley; Faust, Katherine (1994). "Social Network Analysis in the Social and Behavioral Sciences". Social Network Analysis: Methods and Applications. Cambridge University Press. pp. 1–27.

Boyd, Danah; Ellison, Nicole (2008). "Social Network Sites: Definition, History, and Scholarship". Journal of Computer-Mediated Communication 13: 210–230.

[4]

http://www.statista.com/statistics/272014/global-social-networksranked-by-number-of-users/ Tanggal akses : 12 Desember 2014 [5] TRATTNER, C., KAPPE, F. (2013). "SOCIAL STREAM MARKETING ON FACEBOOK: A CASE STUDY". INTERNATIONAL JOURNAL OF SOCIAL AND HUMANISTIC COMPUTING (IJSHC) 2 (1/2).

PERNYATAAN Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain, dan bukan plagiasi. Bandung, 10 Desember 2014

Muhammad Aodyra Khaidir 13513063


Aplikasi Graf dalam Situs Jejaring Sosial

Recommend Documents