.png){kind=icon}
.png){kind=icon}
Return
Partitioning Graph Clustering With User-Specified Density
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2023.3329429.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Graph clustering has attracted many interests in recent years, with numerous applications ranging from the clustering of computer networks to the detection of social communities. It presents a challenging NP-class problem, and as a result, numerous algorithms have been developed, each tailored to specific objectives and quality metrics for evaluation. This research commences by categorizing existing graph clustering algorithms based on two distinct perspectives: parameter-free algorithms and user-defined or adjustable parametric algorithms. Quality metrics are further categorized into three distinct groups: internal connectivity, external connectivity, and a combination of both. If a task can be represented by a simple undirected and unweighted graph, from a management and deployment of resources perspective, having clusters of some kind of similar density is advantageous as it allows efficient management. This research introduces a partitioning graph clustering algorithm that allows users to specify the desired density of a cluster by means of 'relative density'. Clustering process involves the determination of all triangles (i.e., smallest cliques) and selecting a clique as an initial cluster. The expansion of a cluster is done by adding adjacent cliques while the required relative density is monitored. Existing metrics are found unsuitable for evaluating the proposed method; therefore, a suitable new metric, the Mean Relative Density Deviation Coefficient (MRDDC), is introduced.
Keywords:
Clustering algorithms
Measurement
Partitioning algorithms
Tuning
Taxonomy
Task analysis
Monitoring
Quality assurance
Graph clustering
mean relative density deviation coefficient (MDRCC)
NP problem
partitioning graph clustering
quality metric
relative density
Journal
IF:
3.6
Papers:
9.7W
Citations:
29.4W