Graph Clustering
Mohammad Asadpour; Shahin Pourbahrami
Abstract
Background and Objectives: One of the most important clustering methods is density-based clustering. This technique operates on the idea that clusters are regions of higher data density, separated by areas of lower density. Density Peak Clustering (DPC) is a modern density-based algorithm designed to ...
Read More
Background and Objectives: One of the most important clustering methods is density-based clustering. This technique operates on the idea that clusters are regions of higher data density, separated by areas of lower density. Density Peak Clustering (DPC) is a modern density-based algorithm designed to efficiently identify cluster centers by constructing a decision graph. In this graph, points with high local density and a large distance from other high-density points are selected as cluster centers. Once these centers are determined, the remaining non-central points are assigned to clusters based on their proximity to the nearest center. However, DPC performs poorly on manifold datasets with varying densities and is highly sensitive to the selection of the cut-off distance parameter. Methods: To address these limitations and improve clustering performance, this study introduces an approach that employs the radial distribution function to quantify the relationship between data points and high-density regions. This method enables the estimation of the probability of finding neighboring points around a central or dense point, and a histogram is generated to represent these relationships. Results: Unlike traditional DPC, the proposed method eliminates the need for a distance cut-off parameter. The approach was implemented using the natural neighbor algorithm and the radial distribution function in a MATLAB environment. Conclusion: Experimental results demonstrated significant improvements in clustering accuracy and reductions in execution time compared to existing methods.
Graph Clustering
M. Ghadirian; N. Bigdeli
Abstract
Background and Objectives: Community detection is a critical problem in investigating complex networks. Community detection based on modularity/general modularity density are the popular methods with the advantage of using complex network features and the disadvantage of being NP-hard ...
Read More
Background and Objectives: Community detection is a critical problem in investigating complex networks. Community detection based on modularity/general modularity density are the popular methods with the advantage of using complex network features and the disadvantage of being NP-hard problem for clustering. Moreover, Non-negative matrix factorization (NMF)-based community detection methods are a family of community detection tools that utilize network topology; but most of them cannot thoroughly exploit network features. In this paper, a hybrid NMF-based community detection infrastructure is developed, including modularity/ general modularity density as more comprehensive indices of networks. The proposed infrastructure enables to solve the challenges of combining the NMF method with modularity/general modularity density criteria and improves the community detection methods for complex networks.Methods: First, new representations, similar to the model of symmetric NMF, are derived for the model of community detection based on modularity/general modularity density. Next, these indices are innovatively augmented to the proposed hybrid NMF-based model as two novel models called ‘general modularity density NMF (GMDNMF) and mixed modularity NMF (MMNMF)’. In order to solve these two NP-hard problems, two iterative optimization algorithms are developed.Results: it is proved that the modularity/general modularity density-based community detection can be consistently represented in the form of SNMF-based community detection. The performances of the proposed models are verified on various artificial and real-world networks of different sizes. It is shown that MMNMF and GMDNMF models outperform other community detection methods. Moreover, the GMDNMF model has better performance with higher computational complexity compared to the MMNMF model.Conclusion: The results show that the proposed MMNMF model improves the performance of community detection based on NMF by employing the modularity index as a network feature for the NMF model, and the proposed GMDNMF model enhances NMF-based community detection by using the general modularity density index.
