Clustering Graf dengan Algoritma Rantai Markov

  • Theophilus Wellem Fakultas Teknologi Informasi, Universitas Kristen Satya Wacana Jl. Diponegoro 52-60 Salatiga 50711, Jawa Tengah
  • Yessica Nataliani Fakultas Teknologi Informasi, Universitas Kristen Satya Wacana Jl. Diponegoro 52-60 Salatiga 50711, Jawa Tengah
Keywords: Clustering, clustering graph, algoritma rantai Markov, Traffic Dispersion Graph

Abstract

Graph clustering is the task of grouping the vertices of the graph into clusters taking into consideration the edge structure of the graph in such a way that there should be many edges within each cluster and relatively few between the clusters. The objective of this paper is to apply Markov clustering algorithm. Two examples are used to demonstrate the algorithm. In the first example, simple graph is presented to illustrate the computation of this algorithm. While the second example is to study the hosts’ interaction behavior using graph clustering algorithm. The Markov clustering algorithm is used to group (cluster) hosts which have interaction using the HTTP protocol. Using real network traces, the clustering results show that the algorithm successfully group the hosts to their corresponding clusters.

Downloads

Download data is not yet available.

References

[1] Manongga, D., Nataliani, Y. (2015). Matematika Diskrit cetakan ke-2. Prenada Media (Kencana).

[2] Schaeffer, S. (2007). Graph clustering. Computer Science Review, 1, 27--64.

[3] Xu, X., Yuruk, N., Feng, Z. & Schweiger, T. A. J. (2007). SCAN: A Structural Clustering Algorithm for Networks. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (p./pp. 824-833).

[4] Wilkinson, D. J. (2006). Stochastic modelling for systems biology. Boca Raton, Fla. [u.a.]: Chapman & Hall/CRC. ISBN: 978-1-584-88540-5.

[5] M. Iliofotou, P. Pappu, M. Faloutsos, M. Mitzenmacher, S. Singh, and G. Varghese, “Network monitoring using tra_c dispersion graphs (TDGs)," in Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, IMC '07, (New York, NY, USA), pp. 315-320, ACM, 2007.

[6] M. Iliofotou, “Exploring graph-based network traffic monitoring," in IEEE INFOCOM Workshops 2009, pp. 1-2, 2009.

[7] van Dongen, S. (2000). Graph Clustering by Flow Simulation. Unpublished doctoral dissertation, University of Utrecht.

[8] MAWI Working Group, “MAWI Working Group Traffic Archive."
http://mawi.wide.ad.jp.

[9] “Graphviz: Open source graph visualization software."
http://www.graphviz.org/.

[10] Nataliani, Y., Wellem, T. (2014) HTTP Traffic Graph Clustering using Markov Clustering Algorithm. International Journal of Computer Applications 90(2):37-41.
Section
Articles