Enhancing Community Detection in Complex Networks Using the Definition of Membership Degree for each nod

  • Aniseh Taheri Islamic Azad University, Khorasgan (Isfahan) Branch, Isfahan
Keywords: Societies` recognition, Clustering Based on density, Complex networks, reduction of nonlinear

Abstract

To recognize the societies in complex networks, Iso Fdp algorithm has used the combination of IsoMap algorithm so as to reduce the linear dimensions and clustering algorithm based on FDP density. One of the problems of this method is selecting the clusters’ centers or societies using the decision graph. The reason is that it would face problems in overlapped societies. Hence, the current study has investigated a method to overcome the problem. To this end, non-parametric clustering algorithm of Meanshift was used for clustering. Unlike the FDP algorithm, the suggested algorithm does not need to determine the cluster`s centers. Moreover, this algorithm has tried to solve the problem of cluster overlapping and membership problem of nods in each cluster through defining the vector of nods membership degree. Additionally, it has tried to choose the maximum difference to determine the clusters` centers and different weighing to their neighbors through defining different kernel functions. In this research for investigating the suggested method and the previous methods, 5 graphs of real networks of Football, Dolphins, Les Miserable and artificial ones like LFR and GN were used. In addition, for evaluating the results, NMI and Modularity criteria were used. The results of experiments using the above criteria on real and artificial networks indicated that the suggested method of recognizing the societies in comparison to the previous methods had remarkably improved.

References

(1) M. E. Newman, "Complex systems: A survey," arXiv preprint arXiv:1112.1440, 2011.A. Author 1 and B. Author 2, “Title of the conference paper,” Proc. Int. Conf. on Power System Reliability. Singapore, pp. 100-105, 1999.
(2) M. E. Newman, "Communities, modules and large-scale structure in networks," Nature Physics, vol. 8, pp. 25-31, 2012.
(3) S. Wang, D. Wang, C. Li, and Y. Li, "Comment on" Clustering by fast search and find of density peaks"," arXiv preprint arXiv:1501.04267, 2015.
(4) K. Fukunaga and L. Hostetler, "The estimation of the gradient of a density function, with applications in pattern recognition," IEEE Transactions on information theory, vol. 21, pp. 32-40, 1975.
(5) Y. Cheng, "Mean shift, mode seeking, and clustering," IEEE transactions on pattern analysis and machine intelligence, vol. 17, pp. 790-799, 1995.
(6) D. Comaniciu and P. Meer, "Mean shift: A robust approach toward feature space analysis," IEEE Transactions on pattern analysis and machine intelligence, vol. 24, pp. 603-619, 2002.
(7) S. Anand, S. Mittal, O. Tuzel, and P. Meer, "Semi-supervised kernel mean shift clustering," IEEE transactions on pattern analysis and machine intelligence, vol. 36, pp. 1201-1215, 2014.
(8) O. Tuzel, F. Porikli, and P. Meer, "Kernel methods for weakly supervised mean shift clustering," in Computer Vision, 2009 IEEE 12th International Conference on, 2009, pp. 48-55.
(9) K. G. Derpanis, "Mean shift clustering," Lecture Notes, 2005.
(10) M. A. Carreira-Perpinán, "A review of mean-shift algorithms for clustering," arXiv preprint arXiv:1503.00687, 2015.
(11) M. Rosenblatt, "Remarks on some nonparametric estimates of a density function," The Annals of Mathematical Statistics, vol. 27, pp. 832-837, 1956.
(12) 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.
(13) S. Emmons, S. Kobourov, M. Gallant, and K. Börner, "Analysis of network clustering algorithms and cluster quality metrics at scale," PloS one, vol. 11, p. e0159161, 2016
(14) W. M. Rand, "Objective criteria for the evaluation of clustering methods," Journal of the American Statistical association, vol. 66, pp. 846-850, 1971.
(15) L. Hubert and P. Arabie, "Comparing partitions," Journal of classification, vol. 2, pp. 193-218, 1985.
(16) N. X. Vinh, J. Epps, and J. Bailey, "Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance," Journal of Machine Learning Research, vol. 11, pp. 2837-2854, 2010.
(17) A. Strehl and J. Ghosh, "Cluster ensembles---a knowledge reuse framework for combining multiple partitions," Journal of machine learning research, vol. 3, pp. 583-617, 2002.
(18) 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.
(19) 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, p. 471, 2013.
(20) T. You, H.-M. Cheng, Y.-Z. Ning, B.-C. Shia, and Z.-Y. Zhang, "Community detection in complex networks using density-based clustering algorithm and manifold learning," Physica A: Statistical Mechanics and its Applications, vol. 464, pp. 221-230, 2016.
(21) M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise," in Kdd, 1996, pp. 226-231.
(22) A. Rodriguez and A. Laio, "Clustering by fast search and find of density peaks," Science, vol. 344, pp. 1492-1496, 2014.
(23) J. Han, J. Pei, and M. Kamber, Data mining: concepts and techniques: Elsevier, 2011.
Published
2019-01-16
Section
Articles