A Graph Clustering Algorithm Based on Adaptive Neighbors Connectivity
Keywords:
Automatic Clustering, Connectivity, Graph Clustering, Jaccard Similarity,Abstract
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.References
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.
Downloads
Published
How to Cite
Issue
Section
License
TRANSFER OF COPYRIGHT AGREEMENT
The manuscript is herewith submitted for publication in the Journal of Telecommunication, Electronic and Computer Engineering (JTEC). It has not been published before, and it is not under consideration for publication in any other journals. It contains no material that is scandalous, obscene, libelous or otherwise contrary to law. When the manuscript is accepted for publication, I, as the author, hereby agree to transfer to JTEC, all rights including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the author(s) specifically retain(s):
- All proprietary right other than copyright, such as patent rights
- The right to make further copies of all or part of the published article for my use in classroom teaching
- The right to reuse all or part of this manuscript in a compilation of my own works or in a textbook of which I am the author; and
- The right to make copies of the published work for internal distribution within the institution that employs me
I agree that copies made under these circumstances will continue to carry the copyright notice that appears in the original published work. I agree to inform my co-authors, if any, of the above terms. I certify that I have obtained written permission for the use of text, tables, and/or illustrations from any copyrighted source(s), and I agree to supply such written permission(s) to JTEC upon request.
