A hybrid Cat Optimization and K-median for Solving Community Detection Problem

Abstract

Detecting the hidden community structure, which is conclusive to understanding the features of networks, is an important topic in Social Network Analysis (SNA). Community detection problem is the process of network clustering into similar clusters. K-median clustering is one of the popular techniques that has been applied in clustering as a substitute of K-means algorithm but it attempts to minimize the 1-norm distance between each point and its closest cluster center. The problem of clustering network can be formalized as an optimization problem where a qualitatively objective function that captures the intuition of a cluster as a set of nodes with better internal connectivity than external connectivity is selected to be optimized. Cat Swarm Optimization (CSO) is one of the latest population based optimization methods used for global optimization. In this paper, a hybrid cat optimization and K-median for solving the community detection problem is proposed and named as K-median Modularity CSO. Experimental results which are applied on real life networks show the ability of the hybrid cat optimization and K-median to detect successfully an optimized community structure based on putting the modularity as an objective function.