Community Partitioning over Feature-Rich Networks Using an Extended K-Means Method

Area of Science:

• Network analysis
• Machine learning
• Data mining

Background:

• Community detection is crucial for understanding network structures.
• Traditional K-means is limited in handling feature-rich networks.
• The curse of dimensionality affects clustering performance in high-dimensional data.

Purpose of the Study:

• To extend the K-means algorithm for community detection in feature-rich networks.
• To introduce a novel metric combining network and feature spaces.
• To evaluate different distance metrics for improved clustering.

Main Methods:

• Least-squares approximation of inter-node links and feature matrices.
• Alternating minimization strategy for clustering criterion.
• Development of K-means extensions using Euclidean, cosine, and Manhattan distances.

Main Results:

• The extended K-means effectively detects communities in feature-rich networks.
• Cosine-based K-means excels in high-dimensional, real-world datasets.
• Manhattan-based K-means demonstrates superior performance on synthetic datasets.

Conclusions:

• The proposed K-means extension offers a flexible approach to community detection.
• The choice of distance metric is critical and data-dependent.
• This method provides a robust framework for analyzing complex network data.