Improving the Walktrap Algorithm Using K-Means Clustering

Area of Science:

• Psychological research
• Network analysis
• Computational methods

Background:

• The walktrap algorithm is a widely used community-detection method in psychology.
• It relies on hierarchical clustering, which may not be optimal for typical psychological network sizes.
• Existing methods can struggle with sum-of-squares optimization in community detection.

Purpose of the Study:

• To present a computationally simpler alternative to the walktrap algorithm.
• To demonstrate that K-means clustering can provide superior solutions to the sum-of-squares optimization problem.
• To evaluate the impact of improved sum-of-squares solutions on community detection.

Main Methods:

• Developed a computational alternative to hierarchical clustering for community detection.
• Applied exact and approximate K-means clustering methods to solve the sum-of-squares optimization problem.
• Conducted three simulation studies and analyzed empirical networks.

Main Results:

• The K-means clustering approach provides better solutions to the sum-of-squares optimization problem compared to hierarchical clustering used in walktrap.
• The alternative method is conceptually easier to understand.
• Empirical analyses and simulations confirm the benefits of the proposed approach.

Conclusions:

• K-means clustering offers a more effective computational alternative for community detection in psychological research.
• The proposed method improves upon the walktrap algorithm by providing better optimization solutions.
• This work facilitates more accurate community detection in psychological networks.