A Graph Clustering Algorithm Based on Adaptive Neighbors Connectivity


  • Israa Hadi Faculty of Information Technology, University of Babylon, Iraq
  • Firas Sabar Miften Faculty of Information Technology, University of Babylon, Iraq


Automatic Clustering, Connectivity, Graph Clustering, Jaccard Similarity,


This paper deals with graph clustering algorithm which partitions a set of vertices in graphs into smaller sets (clusters). Such vertices of the same set are related to each other rather than to those in the other sets. This means that most graph clustering algorithms are based on the topological shape or feature similarity. Nevertheless, these algorithms suffered from scalability because of the height computation requirements for similarity estimation. This paper represents a stimulus for the current study to introduce an algorithm that automatically finds the number of clusters based on shared neighbours among vertices. The study is based on the hypothesis that the proposed algorithm is able to efficiently find the graph clustering partitions for the whole graphs.


O. Maimon and L. Rokach, Data mining and knowledge discovery handbook vol. 2: Springer, 2005.

J. Kleinberg and E. Tardos, "Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields," Journal of the ACM (JACM), vol. 49, pp. 616-639, 2002.

S. E. Schaeffer, "Graph clustering," Computer science review, vol. 1, pp. 27-64, 2007.

R. Andersen and K. J. Lang, "Communities from seed sets," in Proceedings of the 15th international conference on World Wide Web, 2006, pp. 223-232.

X. Xu, N. Yuruk, Z. Feng, and T. A. Schweiger, "Scan: a structural clustering algorithm for networks," in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, pp. 824-833.

J. Shi and J. Malik, "Normalized cuts and image segmentation," IEEE Transactions on pattern analysis and machine intelligence, vol. 22, pp. 888-905, 2000.

H. Ino, M. Kudo, and A. Nakamura, "Partitioning of web graphs by community topology," in Proceedings of the 14th international conference on World Wide Web, 2005, pp. 661-669.

M. E. Newman, "Detecting community structure in networks," The European Physical Journal B-Condensed Matter and Complex Systems, vol. 38, pp. 321-330, 2004.

W. Nawaz, K.-U. Khan, Y.-K. Lee, and S. Lee, "Intra graph clustering using collaborative similarity measure," Distributed and Parallel Databases, vol. 33, pp. 583-603, 2015.

[10] W. Ren, G. Li, and D. Tu, "Graph clustering by congruency approximation," IET Computer Vision, vol. 9, pp. 841-849, 2015.

S. M. Van Dongen, "Graph clustering by flow simulation," 2001.

P. Jaccard, Etude comparative de la distribution florale dans une portion des Alpes et du Jura: Impr. Corbaz, 1901.

B. Everitt, S. Landau, and M. Leese, "Cluster analysis. 4th," Arnold, London, 2001.

A. Lancichinetti and S. Fortunato, "Community detection algorithms: a comparative analysis," Physical review E, vol. 80, p. 056117, 2009.

M. E. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical review E, vol. 69, p. 026113, 2004.

M. E. Newman, "Fast algorithm for detecting community structure in networks," Physical review E, vol. 69, p. 066133, 2004.

S. Fortunato and M. Barthelemy, "Resolution limit in community detection," Proceedings of the National Academy of Sciences, vol. 104, pp. 36-41, 2007.

V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," Journal of statistical mechanics: theory and experiment, vol. 2008, p. P10008, 2008.

L. Waltman and N. J. van Eck, "A smart local moving algorithm for large-scale modularity-based community detection," The European Physical Journal B, vol. 86, pp. 1-14, 2013.

S. G. Kobourov, S. Pupyrev, and P. Simonetto, "Visualizing graphs as maps with contiguous regions," EuroVis14, Accepted to appear, vol. 4, 2014.

J. J. McAuley and J. Leskovec, "Learning to Discover Social Circles in Ego Networks," in NIPS, 2012, pp. 548-56.

J. Leskovec, J. Kleinberg, and C. Faloutsos, "Graph evolution: Densification and shrinking diameters," ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 1, p. 2, 2007.

J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, "Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters," Internet Mathematics, vol. 6, pp. 29-123, 2009.

B. Klimt and Y. Yang, "Introducing the Enron Corpus," in CEAS, 2004.




How to Cite

Hadi, I., & Miften, F. S. (2017). A Graph Clustering Algorithm Based on Adaptive Neighbors Connectivity. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(2-11), 19–22. Retrieved from https://jtec.utem.edu.my/jtec/article/view/2731