Influence Maximization in Social Network using Community Detection and Node Modularity

doi:10.23940/ijpe.24.09.p3.552562

Abstract

Abstract: Research in the area of identifying the most influential users in social networks is currently regarded to be one of the most important areas of study. Through the examination of the most influential users on social networks, it is possible to analyze and, in some cases, manage the dissemination of information. A technique that is both quick and scalable is proposed in this research as a means of identifying the users with maximum diffusion capabilities in online social networks. This approach is suited for directed networks as well as undirected networks. The approach that has been suggested is comprised of four stages: (1) community detection, which involves the partial partitioning of the whole social network into communities that are connected to one another by the use of the Louvain algorithm; (2) the removal of communities that are not suitable; (3) selection of prominent nodes within the particular community; and (4) selection of the top k seed nodes. Experimental research was carried out on a number of datasets, each of which was of a different complexity. Using imperfect social networks, it has been demonstrated that the findings generate better outcomes for the diffusion of influence than the current related work models, and they do so with a much less amount of processing time being required.

Key words: osn, community detection, influence maximization, deep learning

Aditya Dayal Tyagi, and Krishna Asawa. Influence Maximization in Social Network using Community Detection and Node Modularity [J]. Int J Performability Eng, 2024, 20(9): 552-562.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

[1] Rice S.A.,1927. The identification of blocs in small political bodies. American Political Science Review,21(3), pp.619-627.
[2] Newman, M.E. and Girvan, M., 2004. Finding and evaluating community structure in networks.Physical review E, 69(2), p.026113.
[3] Girvan, M. and Newman, M.E., 2002. Community structure in social and biological networks. Proceedings of the national academy of sciences,99(12), pp.7821-7826.
[4] Liu F., Xue S., Wu J., Zhou C., Hu W., Paris C., Nepal S., Yang J. and Yu P.S., 2020. Deep learning for community detection: progress, challenges and opportunities.arXiv preprint arXiv:2005.08225.
[5] Yang C., Liu Z., Zhao D., Sun M. and Chang E.Y., 2015, July. Network representation learning with rich text information. In IJCAI (Vol. 2015, pp. 2111-2117).
[6] Chunaev P.,2020. Community detection in node-attributed social networks: a survey. Computer Science Review, 37, p.100286.
[7] Jin D., Liu Z., Li W., He D. and Zhang W., 2019, July. Graph convolutional networks meet markov random fields: Semi-supervised community detection in attribute networks. In Proceedings of the AAAI conference on artificial intelligence (Vol. 33, No. 01, pp. 152-159).
[8] Huang X., Chen D., Ren T. and Wang D., 2021. A survey of community detection methods in multilayer networks.Data Mining and Knowledge Discovery, 35, pp.1-45.
[9] Xie J., Kelley S. and Szymanski B.K., 2013. Overlapping community detection in networks: The state-of-the-art and comparative study. Acm computing surveys (csur),45(4), pp.1-35.
[10] Javed M.A., Younis M.S., Latif S., Qadir J. and Baig A., 2018. Community detection in networks: A multidisciplinary review.Journal of Network and Computer Applications, 108, pp.87-111.
[11] Xin X., Wang C., Ying X. and Wang B., 2017. Deep community detection in topologically incomplete networks.Physica A: Statistical Mechanics and its Applications, 469, pp.342-352.
[12] Rossetti, G. and Cazabet, R., 2018. Community discovery in dynamic networks: a survey. ACM computing surveys (CSUR),51(2), pp.1-37.
[13] Pizzuti C.,2017. Evolutionary computation for community detection in networks: A review. IEEE Transactions on Evolutionary Computation,22(3), pp.464-483.
[14] Cai Q., Ma L., Gong M. and Tian D., 2016. A survey on network community detection based on evolutionary computation. International Journal of Bio-Inspired Computation,8(2), pp.84-98.
[15] Zachary W.W.,1977. An information flow model for conflict and fission in small groups. Journal of anthropological research,33(4), pp.452-473.
[16] Lusseau D.,2003. The emergent properties of a dolphin social network. Proceedings of the Royal Society of London. Series B: Biological Sciences,270(suppl_2), pp.S186-S188.
[17] Clauset A., Newman M.E. and Moore C., 2004. Finding community structure in very large networks.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 70(6), p.066111.
[18] Bhatia, V. and Rani, R., 2018. Dfuzzy: a deep learning-based fuzzy clustering model for large graphs.Knowledge and Information Systems, 57, pp.159-181.
[19] Leskovec, J. and Mcauley, J., 2012. Learning to discover social circles in ego networks.Advances in neural information processing systems, 25.
[20] Nicolini C., Bordier C. and Bifone A., 2017. Community detection in weighted brain connectivity networks beyond the resolution limit.Neuroimage, 146, pp.28-39.
[21] Xie, J. and Szymanski, B.K., 2012. Towards linear time overlapping community detection in social networks. In Advances in Knowledge Discovery and Data Mining: 16th Pacific-Asia Conference, PAKDD 2012, Kuala Lumpur, Malaysia, May 29-June 1, 2012, Proceedings, Part II 16(pp. 25-36). Springer Berlin Heidelberg.
[22] Yang J., McAuley J. and Leskovec J., 2013, December. Community detection in networks with node attributes. In 2013 IEEE 13th international conference on data mining(pp. 1151-1156). IEEE.
[23] Chen, P. and Redner, S., 2010. Community structure of the physical review citation network. Journal of Informetrics,4(3), pp.278-290.
[24] Namata G., London B., Getoor L., Huang B. and Edu U., 2012, July. Query-driven active surveying for collective classification. In 10th international workshop on mining and learning with graphs(Vol. 8, p. 1).
[25] Ravasz E., Somera A.L., Mongru D.A., Oltvai Z.N. and Barabási A.L., 2002. Hierarchical organization of modularity in metabolic networks. science,297(5586), pp.1551-1555.
[26] Guimera, R. and Nunes Amaral, L.A., 2005. Functional cartography of complex metabolic networks. nature,433(7028), pp.895-900.
[27] Chen, J. and Yuan, B., 2006. Detecting functional modules in the yeast protein-protein interaction network. Bioinformatics,22(18), pp.2283-2290.
[28] Sporns, O. and Betzel, R.F., 2016. Modular brain networks. Annual review of psychology,67(1), pp.613-640.
[29] Holland P.W., Laskey K.B. and Leinhardt S., 1983. Stochastic blockmodels: First steps. Social networks,5(2), pp.109-137.
[30] Karrer, B. and Newman, M.E., 2011. Stochastic blockmodels and community structure in networks.Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 83(1), p.016107.
[31] Airoldi E.M., Blei D., Fienberg S. and Xing E., 2008. Mixed membership stochastic blockmodels.Advances in neural information processing systems, 21.
[32] Amini A.A., Chen A., Bickel P.J. and Levina E., 2013. Pseudo-likelihood methods for community detection in large sparse networks.
[33] de Lange S.C., de Reus M.A. and van den Heuvel M.P., 2014. The Laplacian spectrum of neural networks. Frontiers in computational neuroscience, 7, p.189.
[34] Shu K., Sliva A., Wang S., Tang J. and Liu H., 2017. Fake news detection on social media: A data mining perspective. ACM SIGKDD explorations newsletter,19(1), pp.22-36.
[35] LeCun Y., Bengio Y. and Hinton G., 2015. Deep learning. nature,521(7553), pp.436-444.
[36] Park C., Kim D., Han J. and Yu H., 2020, April. Unsupervised attributed multiplex network embedding. In Proceedings of the AAAI conference on artificial intelligence (Vol. 34, No. 04, pp. 5371-5378).
[37] Yang L., Wang Y., Gu J., Wang C., Cao X. and Guo Y., 2020, July. JANE: Jointly Adversarial Network Embedding. InIJCAI(pp. 1381-1387).
[38] Yang L., Cao X., He D., Wang C., Wang X. and Zhang W., 2016, July. Modularity based community detection with deep learning. In IJCAI (Vol. 16, No. 2016, pp. 2252-2258).
[39] Zhang X., Liu H., Li Q. and Wu X.M., 2019. Attributed graph clustering via adaptive graph convolution.arXiv preprint arXiv:1906.01210.
[40] Jing B., Park C. and Tong H., 2021, April. Hdmi: High-order deep multiplex infomax. InProceedings of the Web Conference 2021(pp. 2414-2424).
[41] Gao H., Pei J. and Huang H., 2019, July. Progan: Network embedding via proximity generative adversarial network. InProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining(pp. 1308-1316).
[42] Sperlí G.,2019, April. A deep learning based community detection approach. InProceedings of the 34th ACM/SIGAPP symposium on applied computing(pp. 1107-1110).
[43] Wang Z., Wang C., Gao C., Li X. and Li X., 2020. An evolutionary autoencoder for dynamic community detection.Science China Information Sciences, 63(11), p.212205.
[44] Du L., Lu Z., Wang Y., Song G., Wang Y. and Chen W., 2018, July. Galaxy network embedding: a hierarchical community structure preserving approach. InIJCAI(pp. 2079-2085).
[45] Fu X., Zhang J., Meng Z. and King I., 2020, April. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. InProceedings of the web conference 2020(pp. 2331-2341).
[46] Blondel V.D., Guillaume J.L., Lambiotte R. and Lefebvre E., 2008. Fast unfolding of communities in large networks.Journal of statistical mechanics: theory and experiment, 2008(10), p.P10008.
[47] Liu W., Li Y., Chen X. and He J., 2020. Maximum likelihood-based influence maximization in social networks.Applied Intelligence, 50, pp.3487-3502.
[48] Nguyen H.T., Thai M.T. and Dinh T.N., 2016, June. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. InProceedings of the 2016 international conference on management of data(pp. 695-710).
[49] Goyal A., Lu W. and Lakshmanan L.V., 2011, March. Celf++ optimizing the greedy algorithm for influence maximization in social networks. InProceedings of the 20th international conference companion on World wide web(pp. 47-48).