Transactions on Data Analysis in Social Science

Transactions on Data Analysis in Social Science

HNoF: A Neighbors-of-Friends Heuristic for Influence Maximization in Social Networks

Author
P. Nair
Department of Computer Science, Faculty of Engineering, Indian Institute of Science (IISc), Bengaluru, India
10.22034/tdas.2025.255648
Abstract
Influence maximization (IM) seeks a set of k seed users that maximizes the expected spread of influence in a social network. Because IM is NP-hard and computing the spread is #P-hard, simulation-based greedy algorithms achieve near-optimal spread but scale poorly, whereas fast heuristics often sacrifice much of the achievable spread. This paper proposes HNoF (Heuristic based on Neighbors of Friends), a greedy heuristic that restricts candidates to the two-hop neighbors of the current seed that are not its direct friends and ranks them by their marginal gain in the Expected Diffusion Value (EDV), a closed-form one-hop approximation of spread under the Independent Cascade (IC) model. This restriction prunes most of the graph at each iteration, and the EDV score replaces Monte Carlo simulation during seed selection. A derived closed-form expression for the EDV marginal gain shows how HNoF penalizes overlapping neighborhoods. HNoF was compared with General Greedy, LIR, SAEDV and DDSE on four real-world networks (NetHEPT, NetPHY, Epinions1 and Slashdot0902) under the IC model (p = 0.01, k = 5–50). On the two collaboration networks, it came within about 1–4% of the spread of General Greedy at k = 50 while running roughly four orders of magnitude faster. On all four networks, it achieved the largest spread among the scalable methods, exceeding DDSE by about 1–6%, although at a higher running time than DDSE and SAEDV on the largest networks. Combining a locality-constrained candidate set with an analytical spread estimate thus offers a favorable balance between spread and efficiency.
Keywords
Influence Maximization
Social Networks
Viral Marketing
Independent Cascade Model
Expected Diffusion Value
Information Diffusion
Greedy Heuristics
[1]      Talukder, A., et al. (2019). Knapsack-based reverse influence maximization for target marketing in social networks. IEEE Access, 7, 44182–44198. https://doi.org/10.1109/ACCESS.2019.2908412
[2]      He, Q., et al. (2019). TIFIM: A two-stage iterative framework for influence maximization in social networks. Applied Mathematics and Computation, 354, 338–352. https://doi.org/10.1016/j.amc.2019.02.056
[3]      Li, X., Smith, J. D., Dinh, T. N., & Thai, M. T. (2019). TipTop: (Almost) exact solutions for influence maximization in billion-scale networks. IEEE/ACM Transactions on Networking, 27(2), 649–661. https://doi.org/10.1109/TNET.2019.2898413
[4]      Domingos, P., & Richardson, M. (2001). Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 57–66). Association for Computing Machinery. https://doi.org/10.1145/502512.502525
[5]      Wu, K. (2015). Influence maximization in social networks [Master’s thesis, Concordia University].
[6]      Banerjee, S., Jenamani, M., & Pratihar, D. K. (2019). ComBIM: A community-based solution approach for the budgeted influence maximization problem. Expert Systems with Applications, 125, 1–13. https://doi.org/10.1016/j.eswa.2019.01.070
[7]      Chang, T.-C., et al. (2019). Seed selection and social coupon allocation for redemption maximization in online social networks. 2019 IEEE 35th International Conference on Data Engineering (ICDE). https://doi.org/10.1109/ICDE.2019.00044
[8]      Cui, L., Hu, H., Yu, S., Yan, Q., Ming, Z., Wen, Z., & Lu, N. (2018). DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks. Journal of Network and Computer Applications, 103, 119–130. https://doi.org/10.1016/j.jnca.2017.12.003
[9]      Shang, J., Zhou, S., Li, X., Liu, L., & Wu, H. (2017). CoFIM: A community-based framework for influence maximization on large-scale networks. Knowledge-Based Systems, 117, 88–100. https://doi.org/10.1016/j.knosys.2016.09.029
[10]   Shang, J., et al. (2018). IMPC: Influence maximization based on multi-neighbor potential in community networks. Physica A: Statistical Mechanics and Its Applications, 512, 1085–1103. https://doi.org/10.1016/j.physa.2018.08.045
[11]   Singh, S. S., et al. (2019). MIM2: Multiple influence maximization across multiple social networks. Physica A: Statistical Mechanics and Its Applications, 526, Article 120902. https://doi.org/10.1016/j.physa.2019.04.138
[12]   Wang, W., & Street, W. N. (2018). Modeling and maximizing influence diffusion in social networks for viral marketing. Applied Network Science, 3, Article 6. https://doi.org/10.1007/s41109-018-0062-7
[13]   Wu, H., et al. (2018). LAIM: A linear time iterative approach for efficient influence maximization in large-scale networks. IEEE Access, 6, 44221–44234. https://doi.org/10.1109/ACCESS.2018.2864240
[14]   Zhu, W., et al. (2019). Location-based seeds selection for influence blocking maximization in social networks. IEEE Access, 7. https://doi.org/10.1109/ACCESS.2019.2900708
[15]   Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 137–146). Association for Computing Machinery. https://doi.org/10.1145/956750.956769
[16]   Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1), 265–294. https://doi.org/10.1007/BF01588971
[17]   Li, Y., Fan, J., Wang, Y., & Tan, K.-L. (2018). Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 30(10), 1852–1872. https://doi.org/10.1109/TKDE.2018.2807843
[18]   Peng, S., Zhou, Y., Cao, L., Yu, S., Niu, J., & Jia, W. (2018). Influence analysis in social networks: A survey. Journal of Network and Computer Applications, 106, 17–32. https://doi.org/10.1016/j.jnca.2018.01.005
[19]   Jiang, Q., Song, G., Cong, G., Wang, Y., Si, W., & Xie, K. (2011). Simulated annealing based influence maximization in social networks. In Proceedings of the twenty-fifth AAAI conference on artificial intelligence (pp. 127–132). AAAI Press. https://doi.org/10.1609/aaai.v25i1.7838
[20]   Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007). Cost-effective outbreak detection in networks. In Proceedings of the thirteenth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 420–429). Association for Computing Machinery. https://doi.org/10.1145/1281192.1281239
[21]   Goyal, A., Lu, W., & Lakshmanan, L. V. S. (2011). CELF++: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the twentieth international conference companion on World Wide Web (pp. 47–48). Association for Computing Machinery. https://doi.org/10.1145/1963192.1963217
[22]   Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. In Proceedings of the fifteenth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 199–208). Association for Computing Machinery. https://doi.org/10.1145/1557019.1557047
[23]   Chen, W., Lakshmanan, L. V. S., & Castillo, C. (2013). Information and influence propagation in social networks. Morgan & Claypool Publishers.
[24]   Cheng, S., Shen, H., Huang, J., Zhang, G., & Cheng, X. (2013). StaticGreedy: Solving the scalability-accuracy dilemma in influence maximization. In Proceedings of the 22nd ACM international conference on Information and knowledge management (pp. 509–518). Association for Computing Machinery. https://doi.org/10.1145/2505515.2505541
[25]   Borgs, C., Brautbar, M., Chayes, J., & Lucier, B. (2014). Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (pp. 946–957). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973402.70
[26]   Tang, Y., Xiao, X., & Shi, Y. (2014). Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data (pp. 75–86). Association for Computing Machinery. https://doi.org/10.1145/2588555.2593670
[27]   Tang, Y., Shi, Y., & Xiao, X. (2015). Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD international conference on Management of data (pp. 1539–1554). Association for Computing Machinery. https://doi.org/10.1145/2723372.2723734
[28]   Narayanam, R., & Narahari, Y. (2011). A Shapley value-based approach to discover influential nodes in social networks. IEEE Transactions on Automation Science and Engineering, 8(1), 130–147. https://doi.org/10.1109/TASE.2010.2052042
[29]   Wang, C., Chen, W., & Wang, Y. (2012). Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 25(3), 545–576. https://doi.org/10.1007/s10618-012-0262-1
[30]   Goyal, A., Lu, W., & Lakshmanan, L. V. S. (2011). SIMPATH: An efficient algorithm for influence maximization under the linear threshold model. In Proceedings of the 2011 IEEE 11th international conference on Data mining (pp. 211–220). IEEE. https://doi.org/10.1109/ICDM.2011.132
[31]   Morone, F., Min, B., Bo, L., Mari, R., & Makse, H. A. (2016). Collective influence algorithm to find influencers via optimal percolation in massively large social media. Scientific Reports, 6, Article 30062. https://doi.org/10.1038/srep30062
[32]   Liu, D., Jing, Y., Zhao, J., Wang, W., & Song, G. (2017). A fast and efficient algorithm for mining top-k nodes in complex networks. Scientific Reports, 7, Article 43330. https://doi.org/10.1038/srep43330
[33]   Rui, X., et al. (2019). A reversed node ranking approach for influence maximization in social networks. Applied Intelligence, 49(7), 2684–2698. https://doi.org/10.1007/s10489-018-01398-w
[34]   Ahajjam, S., & Badir, H. (2018). Identification of influential spreaders in complex networks using HybridRank algorithm. Scientific Reports, 8, Article 11932. https://doi.org/10.1038/s41598-018-30310-2
[35]   Chen, W., Lin, T., Tan, Z., Zhao, M., & Zhou, X. (2016). Robust influence maximization. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 795–804). Association for Computing Machinery. https://doi.org/10.1145/2939672.2939745
[36]   Xie, G., et al. (2019). MBIC: A novel influence propagation model for membership-based influence maximization in social networks. IEEE Access, 7, 75696–75707. https://doi.org/10.1109/ACCESS.2019.2922474
[37]   Chen, Y.-C., Zhu, W.-Y., Peng, W.-C., Lee, W.-C., & Lee, S.-Y. (2014). CIM: Community-based influence maximization in social networks. ACM Transactions on Intelligent Systems and Technology, 5(2), Article 25. https://doi.org/10.1145/2532549
[38]   Qiu, L., et al. (2019). PHG: A three-phase algorithm for influence maximization based on community structure. IEEE Access, 7, 62511–62522. https://doi.org/10.1109/ACCESS.2019.2912628
[39]   Zhu, R., et al. (2018). QuickIM: Efficient, accurate and robust influence maximization algorithm on billion-scale networks [Preprint]. arXiv. arXiv:1805.12320.
[40]   Centola, D., & Macy, M. (2007). Complex contagions and the weakness of long ties. American Journal of Sociology, 113(3), 702–734. https://doi.org/10.1086/521848
[41]   Richardson, M., Agrawal, R., & Domingos, P. (2003). Trust management for the semantic web. In The Semantic Web—ISWC 2003 (Lecture Notes in Computer Science, Vol. 2870, pp. 351–368). Springer. https://doi.org/10.1007/978-3-540-39718-2_23
[42]   Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009). Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1), 29–123. https://doi.org/10.1080/15427951.2009.10129177
[43]   Leskovec, J., & Krevl, A. (2014). SNAP datasets: Stanford large network dataset collection [Data set]. Stanford University. http://snap.stanford.edu/data
Transactions on Data Analysis in Social Science
Volume 7, Issue 3
Summer 2025
Pages 166-182

  • Receive Date 13 January 2025
  • Revise Date 04 March 2025
  • Accept Date 11 April 2025