MKVI: Hybridization of k-shell Decomposition, Vertex Cover, and Independent Set for Influence Maximization in Multiplex Networks

doi:10.23940/ijpe.26.06.p2.309317

Abstract

Abstract: This paper proposes a novel hybrid approach called Multiplex k-shell and Vertex Cover Integrated Independent Set (MKVI) for influence maximization in a multiplex network. Here, the concepts of k-shell decomposition, vertex cover, and independent set are extended to multiplex networks and combined to select influential nodes (seed sets). The average influence spread of the selected seed set is computed by simulating the independent cascade model with three different influence probabilities (p), where the p values are set to 0.01, 0.05, and 0.1. The proposed MKVI reports a dominant average influence spread in comparison to six state-of-the-art approaches: Degree centrality (DC), Betweenness centrality (BC), Eigenvector centrality (EC), K-shell coefficient (KC), Cost-Effective Lazy Forward selection++ (CELF++), and Reverse random walk (RRW), across six datasets: CElegans, Drosophila, CKM-Physicians, CS-Aarhus, EUAir_Multiplex, and Padgett-Florence-Families_Multiplex_Social. MKVI also reports a closer average influence spread to that of multiplex networks using the learning automata (MISM-LA) method while requiring a much smaller seed set size.

Key words: influence maximization, multiplex k-shell decomposition, multiplex vertex cover, multiplex independent set, seed set selection

Sunita Mahapatra, Nilambar Sethi, and Debasis Mohapatra. MKVI: Hybridization of k-shell Decomposition, Vertex Cover, and Independent Set for Influence Maximization in Multiplex Networks [J]. Int J Performability Eng, 2026, 22(6): 309-317.

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

References

[1] Maharani W., andGozali A.A., 2014. Degree centrality and eigenvector centrality in Twitter. In2014 8th International Conference on Telecommunication Systems Services and Applications (TSSA), pp. 1-5.
[2] Freeman L.C.,1977. A set of measures of centrality based on betweenness.Sociometry, pp. 35-41.
[3] Bonacich P.,1972. Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology,2(1), pp. 113-120.
[4] Kitsak M., Gallos L.K., Havlin S., Liljeros F., Muchnik L., Stanley H.E., andMakse H.A., 2010. Identification of influential spreaders in complex networks. Nature Physics,6(11), pp. 888-893.
[5] Goyal A., Lu W., andLakshmanan L.V., 2011. 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.
[6] Zhang H., Zhang D., Wan Y., Pan R., andKou G., 2025. Multiplex network influence maximization based on representation learning method.Applied Soft Computing, 174, 112956.
[7] Daliri Khomami M.M., Rezvanian A., andMeybodi M.R., 2025. Maximum independent set in multiplex social networks and its application to influence maximization.Scientific Reports, 15(1), 16322.
[8] Datasets Released for Reproducibility, https://manliodedomenico.com/data.php, accessed on May 1, 2026.
[9] Kuhnle A., Alim M.A., Li X., Zhang H., andThai M.T., 2018. Multiplex influence maximization in online social networks with heterogeneous diffusion models. IEEE Transactions on Computational Social Systems,5(2), pp. 418-429.
[10] Zhong Y.D., Srivastava V., andLeonard N.E., 2021. Influence spread in the heterogeneous multiplex linear threshold model. IEEE Transactions on Control of Network Systems,9(3), pp. 1080-1091.
[11] Do N., Chowdhury T., Ling C., Zhao L., andThai M.T., 2024. MIM-reasoner: learning with theoretical guarantees for multiplex influence maximization.Arxiv Preprint Arxiv:2402.16898.
[12] Yuan Z., Shao M., andChen Z., 2024. Graph bayesian optimization for multiplex influence maximization. In Proceedings of the AAAI Conference on Artificial Intelligence,38(20), pp. 22475-22483.
[13] Nguyen H., Dam H., Do N.H.K., Tran C., andPham C., 2025. Rem: A scalable reinforced multi-expert framework for multiplex influence maximization. In Proceedings of the AAAI Conference on Artificial Intelligence,39(25), pp. 27099-27107.
[14] Tortosa L., Vicent J.F., andYeghikyan G., 2021. An algorithm for ranking the nodes of multiplex networks with data based on the PageRank concept.Applied Mathematics and Computation, 392, 125676.
[15] Zhao D., Li S., Wang Z., andPeng H., 2023. Cooperation and competition coupled diffusion of multi-feature on multiplex networks and its control. IEEE Transactions on Network Science and Engineering,10(4), pp. 2307-2318.
[16] Chen J., Deng Y., Su Z., Wang S., Gao C., andLi X., 2019. Identifying multiple influential users based on the overlapping influence in multiplex networks.IEEE Access, 7, pp. 156150-156159.
[17] Manino E., Romero Moreno G., Cai Z., andBrede M., 2020. Influencing the dynamics of correlated opinions in the voter model on multiplex networks.
[18] Gadár L., andAbonyi J., 2024. Finding multifaceted communities in multiplex networks.Scientific Reports, 14(1), 14521.
[19] Hu X.M., Zhao Y.Q., andYang Z., 2023. Nodes grouping genetic algorithm for influence maximization in multiplex social networks. In2023 26th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 1130-1135.
[20] Liu Y., Zeng Q., Pan L., andTang M., 2023. Identify influential spreaders in asymmetrically interacting multiplex networks. IEEE Transactions on Network Science and Engineering,10(4), pp. 2201-2211.
[21] Chen B.L., Hall D.H., andChklovskii D.B., 2006. Wiring optimization can relate neuronal structure and function. Proceedings of the National Academy of Sciences,103(12), pp. 4723-4728.
[22] De Domenico M., Porter M.A., andArenas A., 2015. MuxViz: a tool for multilayer analysis and visualization of networks. Journal of Complex Networks,3(2), pp. 159-176.
[23] Stark C., Breitkreutz B.J., Reguly T., Boucher L., Breitkreutz A., andTyers M., 2006. BioGRID: a general repository for interaction datasets. Nucleic Acids Research,34(suppl_1), pp. D535-D539.
[24] De Domenico M., Nicosia V., Arenas A., andLatora V., 2015. Structural reducibility of multilayer networks.Nature Communications, 6(1), 6864.
[25] Coleman J., Katz E., andMenzel H., 1957. The diffusion of an innovation among physicians. Sociometry,20(4), pp. 253-270.
[26] Magnani M., Micenkova B., andRossi L., 2013. Combinatorial analysis of multiple networks.Arxiv Preprint Arxiv:1303.4986.
[27] Cardillo A., Gómez-Gardenes J., Zanin M., Romance M., Papo D., Pozo F.D., andBoccaletti S., 2013. Emergence of network features from multiplexity.Scientific Reports, 3(1), 1344.
[28] Padgett J.F., andAnsell C.K., 1993. Robust action and the rise of the medici, 1400-1434. American Journal of Sociology,98(6), pp. 1259-1319.