Quantum-PSO based unsupervised clustering of users in social networks using attributes
Abstract
Unsupervised cluster detection in social network analysis involves grouping social actors into distinct groups, each distinct from the others. Users in the clusters are semantically very similar to those in the same cluster and dissimilar to those in different clusters. Social network clustering reveals a wide range of useful information about users and has many applications in daily life. Various approaches are developed to find social network users’ clusters, using only links or attributes and links. This work proposes a method for detecting social network users’ clusters based solely on their attributes. In this case, users’ attributes are considered categorical values. The most popular clustering algorithm used for categorical data is the K-mode algorithm. However, it may suffer from local optimum due to its random initialization of centroids. To overcome this issue, this manuscript proposes a methodology named the Quantum PSO approach based on user similarity maximization. In the proposed approach, firstly, dimensionality reduction is conducted by performing the relevant attribute set selection followed by redundant attribute removal. Secondly, the QPSO technique is used to maximize the similarity score between users to get clusters. Three different similarity measures are used separately to perform the dimensionality reduction and similarity maximization processes. Experiments are conducted on two popular social network datasets; ego-Twitter, and ego-Facebook. The results show that the proposed approach performs better clustering results in terms of three different performance metrics than K-Mode and K-Mean algorithms.
References
[1]
Fiedler M Algebraic connectivity of graphs Czechoslov. Math. J. 1973 23 2 298-305
[2]
Pothen A, Simon HD, and Liou KP Partitioning sparse matrices with eigenvectors of graphs SIAM J. Matrix Anal. Appl. 1990 11 3 430-452
[3]
Kernighan BW and Lin S An efficient heuristic procedure for partitioning graphs Bell Syst. Tech. J. 1970 49 2 291-307
[4]
Au WH, Chan KC, Wong AK, and Wang Y Attribute clustering for grouping, selection, and classification of gene expression data IEEE/ACM Trans. Comput. Biol. Bioinf. 2005 2 2 83-101
[5]
Akbas, E., Zhao, P.: Graph clustering based on attribute-aware graph embedding. In: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 109–131. Springer (2017)
[6]
Aranganayagi, S., Thangavel, K.: Clustering categorical data using silhouette coefficient as a relocating measure. In: International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007), vol. 2, pp. 13–17. IEEE (2007)
[7]
He Z, Xu X, and Deng S A cluster ensemble method for clustering categorical data Inf. Fusion 2005 6 2 143-151
[8]
Dabeeru, V.A.: User profile relationships using string similarity metrics in social networks (2014). arxiv:1408.3154
[9]
Hajarian M, Bastanfard A, Mohammadzadeh J, and Khalilian M Introducing fuzzy like in social networks and its effects on advertising profits and human behavior Comput. Hum. Behav. 2017 77 282-293
[10]
Martínez-López B, Perez A, and Sánchez-Vizcaíno J Combined application of social network and cluster detection analyses for temporal-spatial characterization of animal movements in salamanca, spain Prev. Vet. Med. 2009 91 1 29-38
[11]
Liu B, Meng Q, Zhang H, Xu K, and Cao J Vgmf: visual contents and geographical influence enhanced point-of-interest recommendation in location-based social network Trans. Emerg. Telecommun. Technol. 2022 33 6 e3889
[12]
Neves TTdAT, Martins RM, Coimbra DB, Kucher K, Kerren A, and Paulovich FV Fast and reliable incremental dimensionality reduction for streaming data Comput. Gr. 2022 102 233-244
[13]
Fayyad UM, Piatetsky-Shapiro G, Smyth P, et al. Knowledge discovery and data mining: towards a unifying framework KDD 1996 96 82-88
[14]
Giglio S, Bertacchini F, Bilotta E, and Pantano P Using social media to identify tourism attractiveness in six Italian cities Tour. Manage. 2019 72 306-312
[15]
Xiao, C., Freeman, D.M., Hwa, T.: Detecting clusters of fake accounts in online social networks. In: Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security, pp. 91–101 (2015)
[16]
John, S.A., Keikhosrokiani, P.: Covid-19 fake news analytics from social media using topic modeling and clustering. In: Big Data Analytics for Healthcare, pp. 221–232. Elsevier (2022)
[17]
Toujani R and Akaichi J Event news detection and citizens community structure for disaster management in social networks Online Inf. Rev. 2019 43 1 113-132
[18]
Hajarian M, Bastanfard A, Mohammadzadeh J, and Khalilian M Snefl: social network explicit fuzzy like dataset and its application for Incel detection Multimedia Tools Appl. 2019 78 33457-33486
[19]
Takbiri Y, Bastanfard A, and Amini A A gamified approach for improving the learning performance of k-6 students using easter eggs Multimedia Tools Appl. 2023
[20]
Cai Q, Gong M, Ma L, Ruan S, Yuan F, and Jiao L Greedy discrete particle swarm optimization for large-scale social network clustering Inf. Sci. 2015 316 503-516
[21]
Frawley WJ, Piatetsky-Shapiro G, and Matheus CJ Knowledge discovery in databases: an overview AI Mag. 1992 13 3 57-57
[22]
Verma M, Srivastava M, Chack N, Diswar AK, and Gupta N A comparative study of various clustering algorithms in data mining Int. J. Eng. Res. Appl. (IJERA) 2012 2 3 1379-1384
[23]
Ng RT and Han J Clarans: a method for clustering objects for spatial data mining IEEE Trans. Knowl. Data Eng. 2002 14 5 1003-1016
[24]
Guha S, Rastogi R, and Shim K Cure: an efficient clustering algorithm for large databases ACM SIGMOD Rec. 1998 27 2 73-84
[25]
Huang Z A fast clustering algorithm to cluster very large categorical data sets in data mining Dmkd 1997 3 8 34-39
[26]
Huang Z Extensions to the k-means algorithm for clustering large data sets with categorical values Data Min. Knowl. Discovery 1998 2 3 283-304
[27]
Tian, F., Gao, B., Cui, Q., Chen, E., Liu, T.Y.: Learning deep representations for graph clustering. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol 28 (2014)
[28]
Xie, J., Girshick, R., Farhadi, A.: Unsupervised deep embedding for clustering analysis. In: International Conference on Machine Learning, PMLR, pp. 478–487 (2016)
[29]
Guo, X., Gao, L., Liu, X., Yin, J.: Improved deep embedded clustering with local structure preservation. In: Ijcai, pp. 1753–1759 (2017)
[30]
Gibson D, Kleinberg J, and Raghavan P Clustering categorical data: an approach based on dynamical systems VLDB J. 2000 8 3 222-236
[31]
Bai L, Liang J, Dang C, and Cao F A novel attribute weighting algorithm for clustering high-dimensional categorical data Pattern Recogn. 2011 44 12 2843-2861
[32]
Rashidi R, Khamforoosh K, and Sheikhahmadi A Proposing improved meta-heuristic algorithms for clustering and separating users in the recommender systems Electron. Commer. Res. 2022 22 2 623-648
[33]
Guha S, Rastogi R, and Shim K Rock: a robust clustering algorithm for categorical attributes Inf. Syst. 2000 25 5 345-366
[34]
Bock HH and Diday E Analysis of Symbolic Data: Exploratory Methods for Extracting Statistical Information from Complex Data 1999 Berlin Springer
[35]
Cheetham AH and Hazel JE Binary (presence-absence) similarity coefficients J. Paleontol. 1969 43 1130-1136
[36]
Niwattanakul S, Singthongchai J, Naenudorn E, and Wanapu S Using of Jaccard coefficient for keywords similarity Proc. Int. Multiconf. Eng. Comput. Sci. 2013 1 380-384
[37]
Jia H, Ym Cheung, and Liu J A new distance metric for unsupervised learning of categorical data IEEE Trans. Neural Netw. Learn. Syst. 2015 27 5 1065-1079
[38]
Blum AL and Langley P Selection of relevant features and examples in machine learning Artif. Intell. 1997 97 1–2 245-271
[39]
Devijver PA and Kittler J Pattern Recognition: A Statistical Approach 1982 Hoboken Prentice Hall
[40]
Shannon CE A mathematical theory of communication Bell Syst. Tech. J. 1948 27 3 379-423
[41]
Alam S, Dobbie G, Koh YS, Riddle P, and Rehman SU Research on particle swarm optimization based clustering: a systematic review of literature and techniques Swarm Evol. Comput. 2014 17 1-13
[42]
Li L, Jiao L, Zhao J, Shang R, and Gong M Quantum-behaved discrete multi-objective particle swarm optimization for complex network clustering Pattern Recogn. 2017 63 1-14
[43]
Sun, J., Xu, W., Feng, B.: Adaptive parameter control for quantum-behaved particle swarm optimization on individual level. In: 2005 IEEE International Conference on Systems, Man and Cybernetics, vol. 4, pp. 3049–3054. IEEE (2005)
[44]
Pat, A., Hota, A.R.: An improved quantum-behaved particle swarm optimization using fitness-weighted preferential recombination. In: 2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC), pp. 709–714. IEEE (2010)
[45]
Leskovec, J., Mcauley, J.: Learning to discover social circles in ego networks. Adv. Neural Inf. Process. Syst. 25 (2012)
[46]
Rousseeuw PJ Silhouettes: a graphical aid to the interpretation and validation of cluster analysis J. Comput. Appl. Math. 1987 20 53-65
[47]
Davies, D., Bouldin, D.: A cluster separation measure: IEEE transactions on pattern analysis and machine intelligence. itpidj 0162-8828, pami-1, 2 224–227. Crossref Web of Science (1979)
[48]
Caliński T and Harabasz J A dendrite method for cluster analysis Commun. Stat.-Theory Methods 1974 3 1 1-27
Recommendations
Application of metaheuristic based fuzzy K-modes algorithm to supplier clustering
Highlights- Proposes a clustering method using a metaheuristics-based fuzzy K-modes algorithms.
AbstractMany companies find difficulty in choosing right suppliers. Organizing suppliers based on their characteristics might help the company solve this problem. This study proposes an approach for supplier selection by organizing suppliers ...
Clustering for high dimensional categorical data based on text similarity
ICCIP '16: Proceedings of the 2nd International Conference on Communication and Information ProcessingIt is a well-known fact that a variety of cluster analysis techniques exist to group objects which have characteristics related to one another. But the fact of the matter is the implementation of many of these techniques poses a great challenge because ...
Unsupervised fuzzy clustering with multi-center clusters
Clustering and modelingA new unsupervised fuzzy clustering algorithm is provided in this paper to cluster the data patterns without a priori information about the number of clusters. The initial guesses of the locations of the cluster centers or the initial guesses of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 13 April 2023
Accepted: 18 March 2023
Revision received: 22 February 2023
Received: 19 January 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in