{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T15:42:31Z","timestamp":1775144551527,"version":"3.50.1"},"reference-count":37,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2023,12,3]],"date-time":"2023-12-03T00:00:00Z","timestamp":1701561600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"STU Scientific Research Initiation Grant","award":["NTF23021T"],"award-info":[{"award-number":["NTF23021T"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>To address the problem that traditional spectral clustering algorithms cannot obtain the complete structural information of networks, this paper proposes a spectral clustering community detection algorithm, PMIK-SC, based on the point-wise mutual information (PMI) graph kernel. The kernel is constructed according to the point-wise mutual information between nodes, which is then used as a proximity matrix to reconstruct the network and obtain the symmetric normalized Laplacian matrix. Finally, the network is partitioned by the eigendecomposition and eigenvector clustering of the Laplacian matrix. In addition, to determine the number of clusters during spectral clustering, this paper proposes a fast algorithm, BI-CNE, for estimating the number of communities. For a specific network, the algorithm first reconstructs the original network and then runs Monte Carlo sampling to estimate the number of communities by Bayesian inference. Experimental results show that the detection speed and accuracy of the algorithm are superior to other existing algorithms for estimating the number of communities. On this basis, the spectral clustering community detection algorithm PMIK-SC also has high accuracy and stability compared with other community detection algorithms and spectral clustering algorithms.<\/jats:p>","DOI":"10.3390\/e25121617","type":"journal-article","created":{"date-parts":[[2023,12,4]],"date-time":"2023-12-04T03:40:58Z","timestamp":1701661258000},"page":"1617","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Spectral Clustering Community Detection Algorithm Based on Point-Wise Mutual Information Graph Kernel"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1596-6599","authenticated-orcid":false,"given":"Yinan","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science and Technology, Shantou University, Shantou 515821, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenbin","family":"Ye","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7313-4374","authenticated-orcid":false,"given":"Dong","family":"Li","sequence":"additional","affiliation":[{"name":"School of Software Engineering, South China University of Technology, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,12,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1126\/science.aal3856","article-title":"Prediction and explanation in social systems","volume":"355","author":"Hofman","year":"2017","journal-title":"Science"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1002\/prot.20348","article-title":"Small-world network approach to identify key residues in protein-protein interaction","volume":"58","year":"2005","journal-title":"Proteins"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of small-world networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Albert","year":"1999","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Chen, Y., Wang, C., and Li, D. (2022). MINC-NRL: An information-based approach for community detection. Algorithms, 15.","DOI":"10.3390\/a15010020"},{"key":"ref_7","first-page":"2749091","article-title":"A multi-label propagation algorithm for community detection based on average mutual information","volume":"2022","author":"Chen","year":"2022","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"078301","DOI":"10.1103\/PhysRevLett.117.078301","article-title":"Estimating the number of communities in a network","volume":"117","author":"Newman","year":"2016","journal-title":"Phys. Rev. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"066133","DOI":"10.1103\/PhysRevE.69.066133","article-title":"Fast algorithm for detecting community structure in networks","volume":"69","author":"Newman","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"8577","DOI":"10.1073\/pnas.0601602103","article-title":"Modularity and community structure in networks","volume":"103","author":"Newman","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1073\/pnas.0605965104","article-title":"Resolution limit in community detection","volume":"104","author":"Fortunato","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_12","first-page":"329325","article-title":"A community detection algorithm based on topology potential and spectral clustering","volume":"2014","author":"Wang","year":"2014","journal-title":"Sci. World J."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1177\/1471082X15577017","article-title":"Model selection and clustering in stochastic block models based on the exact integrated complete data likelihood","volume":"15","author":"Latouche","year":"2015","journal-title":"Stat. Model."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"016107","DOI":"10.1103\/PhysRevE.83.016107","article-title":"Stochastic blockmodels and community structure in networks","volume":"83","author":"Karrer","year":"2011","journal-title":"Phys. Rev. E"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Funke, T., and Becker, T. (2019). Stochastic block models: A comparison of variants and inference methods. PLoS ONE, 14.","DOI":"10.1371\/journal.pone.0215296"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"032310","DOI":"10.1103\/PhysRevE.96.032310","article-title":"Efficient method for estimating the number of communities in a network","volume":"96","author":"Riolo","year":"2017","journal-title":"Phys. Rev. E"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/j.patrec.2018.06.024","article-title":"Fast spectral clustering learning with hierarchical bipartite graph for large-scale data","volume":"130","author":"Yang","year":"2020","journal-title":"Pattern Recognit. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"036111","DOI":"10.1103\/PhysRevE.77.036111","article-title":"Communicability in complex networks","volume":"77","author":"Estrada","year":"2008","journal-title":"Phys. Rev. E"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ibrahim, R., and Gleich, D. (2019, January 13\u201317). Nonlinear diffusion for community detection and semi-supervised learning. Proceedings of the World Wide Web Conference, San Francisco, CA, USA.","DOI":"10.1145\/3308558.3313483"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kloster, K., and Gleich, D.F. (2014, January 24\u201327). Heat kernel based community detection. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/2623330.2623706"},{"key":"ref_21","unstructured":"Saerens, M., Fouss, F., Yen, L., and Dupont, P. (2004). European Conference on Machine Learning, Springer."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Blondel, V.D., Guillaume, J.L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp., P10008.","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ejc.2018.02.002","article-title":"Similarities on graphs: Kernels versus proximity measures","volume":"80","author":"Avrachenkov","year":"2019","journal-title":"Eur. J. Comb."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"046110","DOI":"10.1103\/PhysRevE.78.046110","article-title":"Benchmark graphs for testing community detection algorithms","volume":"78","author":"Lancichinetti","year":"2008","journal-title":"Phys. Rev. E"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"P09008","DOI":"10.1088\/1742-5468\/2005\/09\/P09008","article-title":"Comparing community structure identification","volume":"2005","author":"Danon","year":"2005","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B., and Bollobas, B. (1998). Modern Graph Theory, Springer Science & Business Media.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"ref_27","first-page":"1","article-title":"Hierarchical directed spectral graph partitioning","volume":"443","author":"Gleich","year":"2006","journal-title":"Inf. Netw."},{"key":"ref_28","unstructured":"Miasnikof, P., Pitsoulis, L., Bonner, A.J., Lawryshyn, Y., and Pardalos, P.M. (2018, January 8). Graph clustering via intra-cluster density maximization. Proceedings of the Network Algorithms, Data Mining, and Applications: NET, Moscow, Russia."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Williams, V.V. (2012, January 20\u201322). Multiplying matrices faster than Coppersmith-Winograd. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/2213977.2214056"},{"key":"ref_30","unstructured":"Ivashkin, V., and Chebotarev, P. (2016). International Conference on Network Analysis, Springer."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Kuikka, V., Aalto, H., Ij\u00e4s, M., and Kaski, K.K. (2022). Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks. Algorithms, 15.","DOI":"10.3390\/a15080262"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1016\/j.datak.2008.10.006","article-title":"Graph nodes clustering with the sigmoid commute-time kernel: A comparative study","volume":"68","author":"Yen","year":"2009","journal-title":"Data Knowl. Eng."},{"key":"ref_33","unstructured":"Avrachenkov, K., Gon\u00e7alves, P., and Sokol, M. (2013). International Workshop on Algorithms and Models for the Web-Graph, Springer."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Rozemberczki, B., Davies, R., Sarkar, R., and Sutton, C. (2019, January 27\u201330). Gemsec: Graph embedding with self clustering. Proceedings of the 2019 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, Vancouver, BC, Canada.","DOI":"10.1145\/3341161.3342890"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Coscia, M., Rossetti, G., Giannotti, F., and Pedreschi, D. (2012, January 12\u201316). Demon: A local-first discovery method for overlapping communities. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China.","DOI":"10.1145\/2339530.2339630"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Epasto, A., Lattanzi, S., and Paes Leme, R. (2017, January 13\u201317). Ego-splitting framework: From non-overlapping to overlapping clusters. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada.","DOI":"10.1145\/3097983.3098054"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Li, P.Z., Huang, L., Wang, C.D., and Lai, J.H. (2019, January 4\u20138). Edmot: An edge enhancement approach for motif-aware community detection. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA.","DOI":"10.1145\/3292500.3330882"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/12\/1617\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:37:04Z","timestamp":1760132224000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/12\/1617"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,3]]},"references-count":37,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["e25121617"],"URL":"https:\/\/doi.org\/10.3390\/e25121617","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,3]]}}}