A hybrid Cat Optimization and K-median for Solving Community Detection Problem
Keywords:
Community Detection, Social Network, K-median Clustering, Cat Swarm Optimization, ModularityAbstract
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.
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.
Downloads
Published
Issue
Section
License
- Papers must be submitted on the understanding that they have not been published elsewhere (except in the form of an abstract or as part of a published lecture, review, or thesis) and are not currently under consideration by another journal published by any other publisher.
- It is also the authors responsibility to ensure that the articles emanating from a particular source are submitted with the necessary approval.
- The authors warrant that the paper is original and that he/she is the author of the paper, except for material that is clearly identified as to its original source, with permission notices from the copyright owners where required.
- The authors ensure that all the references carefully and they are accurate in the text as well as in the list of references (and vice versa).
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Attribution-NonCommercial 4.0 International that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
- The journal/publisher is not responsible for subsequent uses of the work. It is the author's responsibility to bring an infringement action if so desired by the author.
