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

Amany A. Naim, Lamiaa M. El Bakrawy, Neveen I. Ghali

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.


Keywords


Community Detection, Social Network, K-median Clustering, Cat Swarm Optimization, Modularity

Full Text:

PDF

References


D. Boyd, and N. Ellison, ”Social Network Sites: Definition, History, and Scholarship.”,

Journal of Computer-Mediated Communication, vol. 13, pp. 210-230, 2008.

Y. Chen, and X. Qiu, ”Detecting Community Structures in Social Networks with

Particle Swarm Optimization.”, Springer Berlin Heidelberg, pp. 266-275, 2013.

l. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, ”Comparing community structure

identification.”, Journal of Statistical Mechanics, vol. 9, pp. 1-10, 2005.

T. Alzahrani, and K. Horadam, ”Community Detection in Bipartite Networks: Algorithms

and Case studies.”, Complex Systems and Networks, Springer Berlin Heidelberg,

pp. 25-50, 2016.

M. Girvan, and M. Newman, ”Community structure in social and biological networks.”,

Proceedings of the National Academy of Sciences, vol. 99, pp. 7821-7826,

M. Newman, ”Detecting community structure in networks.”, The European Physical

Journal B - Condensed Matter and Complex Systems, vol. 38, pp. 321-330, 2004.

S. Nomura, S. Oyama, T. Hayamizu, and T. Ishida, ”Analysis and improvement of

HITS algorithm for detecting Web communities”, Journal of Systems and Computers

in Japan, vol. 35, pp. 32-42, 2004.

M. Newman, ”Spectral methods for network community detection and graph partitioning.”,

Journal of Physical Review E, vol. 88, pp. 1-11, 2013.

M. Newman, and M. Girvan, ”Finding and evaluating community structure in networks.”,

Physical Review, vol. 69, pp. 1-16, 2004.

C. Pizzuti, ”GA-Net: A Genetic Algorithm for Community Detection in Social Networks.”,

Springer Berlin Heidelberg, pp. 1081-1090, 2008.

C. Honghao, F. Zuren, and R. Zhigang, ”Community Detection Using Ant Colony

Optimization.”, IEEE Congress on Evolutionary Computation, pp. 3072-3078, 2013.

Z. Masdarolomoor, R. Azmi, S. Aliakbary, and N. Riahi, ”Finding Community Structure

in Complex Networks Using Parallel Approach.”, Embedded and Ubiquitous

Computing (EUC), 2011 IFIP 9th International Conference, IEEE, vol. 10, pp. 474-

, 2011.

A. Song, M. Li, X. Ding, w. Cao, and K. Pu, ”Community Detection Using Discrete

Bat Algorithm.”, IAENG International Journal of Computer Science, vol. 43, pp. 1-7,

Y. EL Barawy, L. EL Bakrawy, and N. Ghali, ”K-means Clustering With Swarm Optimization For Social Network Community Detection.”, Asian Journal of Mathematics

and Computer Research, vol. 3, pp. 220-230, 2013.

J. Yang, J. McAuley, and J. Leskovec, ”Community Detection in Networks with Node

Attributes.”, Published in the proceedings of IEEE ICDM ’13, vol. 10, pp. 1-10, 2014.

N. Yahia, N. Saoud, and H. Ghezala, ”Evaluating Community Detection Using

a Bi-objective Optimization.”, International Conference on Intelligent Computing,

Springer Berlin Heidelberg, pp. 61-70, 2013.

S. Chu, P. Tsai, and J. Pan, ”Cat Swarm Optimization”, Springer Berlin Heidelberg,

pp. 854-858, 2006.

S. Yousef, M. Khanesar, and M. Teshnehlab, ”Discrete binary cat swarm optimization

algorithm.”, Control and Communication (IC4), 2013 3rd International Conference on.

IEEE, pp. 1-6, 2013.

K. Yugal, and G. Sahoo, ”A hybrid data clustering approach based on improved cat

swarm optimization and K-harmonic mean algorithm.”, Journal of Information and

Computing Science, vol. 9, pp. 196-209, 2014.

S. Budi, and M. Ningrum, ”Cat swarm optimization for clustering.”, Soft Computing

and Pattern Recognition, International Conference of. IEEE, pp. 54-59, 2009.

P. Dalatu, ”Time Complexity of K-Means and K-Medians Clustering Algorithms in

Outliers Detection.”, Global Journal of Pure and Applied Mathematics, vol. 12, pp.

-4418, 2016.

H. Zhu, and Y. Shi, ”Brain storm optimization algorithms with k-medians clustering

algorithms.”, Advanced Computational Intelligence (ICACI), 2015 Seventh International

Conference on, IEEE, pp. 107-110, 2015.

C. Whelan, G. Harrell, and J. Wang, ”Understanding the K-Medians Problem.”, Proceedings

of the International Conference on Scientific Computing (CSC), The Steering

Committee of The World Congress in Computer Science, Computer Engineering and

Applied Computing (WorldComp), pp. 219-222, 2015.

http://konect.uni-koblenz.de/networks/ucidata-zachary, Accessed Novamber 2016.

http://konect.uni-koblenz.de/networks/dolphins, Accessed Novamber 2016.

http://www-personal.umich.edu/mejn/netdata, Accessed Novamber 2016.

Y. Wang, J. Fang, and F. Wu, ”Application of Community Detection Algorithm with

Link Clustering in Inhibition of Social Network Worms.”, International Journal of

Network Security, vol. 19, pp. 458-468, 2017.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.