Exploiting community and structural hole spanner for influence maximization in social networks
Corresponding Author
Xiao Li
School of Management, Capital Normal University, Beijing, China
Correspondence
Xiao Li, School of Management, Capital Normal University, 105 West Third Ring Road North, Haidian District, Beijing 100048, China.
Email: [email protected]
Search for more papers by this authorZiang Chen
School of Management, Capital Normal University, Beijing, China
Search for more papers by this authorCorresponding Author
Xiao Li
School of Management, Capital Normal University, Beijing, China
Correspondence
Xiao Li, School of Management, Capital Normal University, 105 West Third Ring Road North, Haidian District, Beijing 100048, China.
Email: [email protected]
Search for more papers by this authorZiang Chen
School of Management, Capital Normal University, Beijing, China
Search for more papers by this authorAbstract
Viral marketing is a frequently used social marketing strategy which aims to promote products on various social media. In order to devise an efficient viral marketing strategy, influence maximization problem is widely studied in social networks. Influence maximization problem tries to find a set of influential users who could influence social users maximally. However, existed influence maximization algorithms could not satisfy the needs of social marketers well. In social networks, community structure is an important feature where social users are closely connected together in groups, and structural hole spanners are those users who bridge different communities. In order to balance the effectiveness and efficiency of viral marketing in social networks, in this paper, we present to exploit the community structure and structural hole spanners in social networks for solving the influence maximization problem. Different to traditional algorithms, we devise a strategy to approximate social influences of social users to find seeds efficiently. In particular, for an internal user inside a community in social networks, we utilize his social influence to members inside this community to approximate his social influence in the whole social network. For a structural hole spanner who bridges multiple communities, we utilize his social influence to members in these communities to approximate his social influence in the whole network. Based on the approximate social influence, information diffusion model and greedy framework, we propose a Community and Structural Hole Spanner based Greedy (CSHS-G) algorithm which devises several influence lists to store social influences of users and fast computation scheme to find seeds. Besides, to further improve the efficiency, we propose a Community and Structural Hole Spanner based Heuristic (CSHS-H) algorithm which approximates social influences of structural hole spanners by utilizing their 2-hops influences. We conduct a comprehensive performance evaluation on the crawled real-world data set. Experimental results show that, compared to all of the baseline algorithms, our proposed algorithms not only have high efficiency, but also could guarantee larger influence spread.
CONFLICT OF INTEREST STATEMENT
The authors declare no conflict of interest.
Open Research
DATA AVAILABILITY STATEMENT
The data that support the findings of this study are available on request from the corresponding author. The data are not publicly available due to privacy or ethical restrictions.
REFERENCES
- AlFalahi, K., Atif, Y., & Abraham, A. (2014). Models of influence in online social networks. International Journal of Intelligent Systems, 29(2), 161–183.
- Arazkhani, N., Meybodi, M., & Rezvanian, A. (2019). An efficient algorithm for influence blocking maximization based on community detection. In 2019 5th international conference on web research (ICWR) (pp. 258–263). IEEE.
10.1109/ICWR.2019.8765277 Google Scholar
- Bagheri, E., Dastghaibyfard, G., & Hamzeh, A. (2021). FAIMCS: A fast and accurate influence maximization algorithm in social networks based on community structures. Computational Intelligence, 37, 1779–1802.
- 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.
- Bello-Orgaz, G., Mesas, R. M., Zarco, C., Rodriguez, V., Cordón, Ó., & Camacho, D. (2020). Marketing analysis of wineries using social collective behavior from users' temporal activity on Twitter. Information Processing and Management, 57(5), 102220.
- Beni, H. A., & Bouyer, A. (2020). TI-SC: Top-k influential nodes selection based on community detection and scoring criteria in social networks. Journal of Ambient Intelligence and Humanized Computing, 11, 1–20.
- Borgs, C., Brautbar, M., Chayes, J. T., & Lucier, B. (2012). Influence maximization in social networks: Towards an optimal algorithmic solution. CoRR.
- Boroujeni, R. J., & Soleimani, S. (2023). Classify nodes based on their degree distribution: A more scalable method for influence maximization. Expert Systems, 40(2), e13156.
- Bozorgi, A., Samet, S., Kwisthout, J., & Wareham, T. (2017). Community-based influence maximization in social networks under a competitive linear threshold model. Knowledge-Based Systems, 134, 149–158.
- Brin, S., & Page, L. (1998). The anatomy of a large-scale Hypertextual web search engine. Computer Networks, 30, 107–117.
- Buhai, I. S., & van der Leij, M. J. (2023). A social network analysis of occupational segregation. Journal of Economic Dynamics and Control, 147, 104593.
- Cha, M., Mislove, A., & Gummadi, K. P. (2009). A measurement-driven analysis of information propagation in the flickr social network. In Proceedings of the 18th international conference on World wide web (pp. 721–730). Association for Computing Machinery.
10.1145/1526709.1526806 Google Scholar
- Chatterjee, B., Bhattacharyya, T., Ghosh, K. K., Chatterjee, A., & Sarkar, R. (2021). A novel meta-heuristic approach for influence maximization in social networks. Expert Systems, 40, e12676.
- Chen, S., Fan, J., Li, G., Feng, J., Kl, T., & Tang, J. (2015). Online topic-aware influence maximization. VLDB Endowment, 8(6), 666–677.
- Chen, W., Wang, C., & Wang, Y. (2010). Scalable influence maximization for prevalent viral marketing in large-scale social networks (pp. 1029–1038). SIGKDD.
- Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks (pp. 199–208). SIGKDD.
- Chen, X., Zhang, F., Zhou, F., & Bonsangue, M. (2022). Multi-scale graph capsule with influence attention for information cascades prediction. International Journal of Intelligent Systems, 37(3), 2584–2611.
- Chen, Y., Wang, W., Feng, J., Lu, Y., & Gong, X. (2020). Maximizing multiple influences and fair seed allocation on multilayer social networks. PLoS One, 15(3), 1–19.
- 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 (TIST), 5(2), 25–31.
- Deng, X., Long, F., Li, B., Cao, D., & Pan, Y. (2020). An influence model based on heterogeneous online social network for influence maximization. IEEE Transactions on Network Science and Engineering, 7(2), 737–749.
- Domingos, P., & Richardson, M. (2001). Mining the network value of customers (pp. 57–66). SIGKDD.
- Fani, H., Jiang, E., Bagheri, E., Al-Obeidat, F., Du, W., & Kargar, M. (2020). User community detection via embedding of social network structure and temporal content. Information Processing and Management, 57, 102056.
- Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 75–174.
- Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1–44.
- Giráldez-Cru, J., Chica, M., Cordón, O., & Herrera, F. (2020). Modeling agent-based consumers decision-making with 2-tuple fuzzy linguistic perceptions. International Journal of Intelligent Systems, 35(2), 283–299.
- Gong, C., Du, Y., Li, X., Chen, X., Li, X., Wang, Y., & Zhou, Q. (2020). Structural hole-based approach to control public opinion in a social network. Engineering Applications of Artificial Intelligence, 93, 103690.
- Granovetter, M. (1978). Threshold models of collective behavior. American Journal of Sociology, 83, 1420–1443.
- Guo, J., Li, Y., & Wu, W. (2020). Targeted protection maximization in social networks. IEEE Transactions on Network Science and Engineering, 7(3), 1645–1655.
- He, L., Lu, C. T., Ma, J., Cao, J., Shen, L., & Yu, P. S. (2016). Joint community and structural hole spanner detection via harmonic modularity. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining (pp. 875–884). Association for Computing Machinery.
10.1145/2939672.2939807 Google Scholar
- He, Q., Wang, X., Lei, Z., Huang, M., Cai, Y., & Ma, L. (2019). TIFIM: A two-stage iterative framework for influence maximization in social networks. Applied Mathematics and Computation, 354, 338–352.
- He, Q., Wang, X., Mao, F., Lv, J., Cai, Y., Huang, M., & Xu, Q. (2020). CAOM: A community-based approach to tackle opinion maximization for social networks. Information Sciences, 513, 252–269.
- Horng, S., & Wu, C. L. (2020). How behaviors on social network sites and online social capital influence social commerce intentions. Information Management, 57, 103176.
10.1016/j.im.2019.103176 Google Scholar
- Hu, P., & Mei, T. (2018). Ranking influential nodes in complex networks with structural holes. Physica A: Statistical Mechanics and its Applications, 490, 624–631.
- Huang, H., Shen, H., & Meng, Z. (2019). Item diversified recommendation based on influence diffusion. Information Processing and Management, 56, 939–954.
- Jiang, Q., Song, G., Gao, C., Wang, Y., Si, W., & Xie, K. (2011). Simulated annealing based influence maximization in social networks. Association for the Advancement of Artificial Intelligence, 25, 127–132.
- Jokar, E., Mosleh, M., & Kheyrandish, M. (2022). Overlapping community detection in complex networks using fuzzy theory, balanced link density, and label propagation. Expert Systems, 39(5), e12921.
- Jurvetson, S., & Draper, T. (1997). Viral marketing: Viral marketing phenomenon explained. DFJ Network News.
- Kazemzadeh, F., Safaei, A. A., & Mirzarezaee, M. (2022). Influence maximization in social networks using effective community detection. Physica A: Statistical Mechanics and its Applications, 598, 127314.
- Kazemzadeh, F., Safaei, A. A., Mirzarezaee, M., Afsharian, S., & Kosarirad, H. (2023). Determination of influential nodes based on the Communities' structure to maximize influence in social networks. Neurocomputing, 534, 18–28.
- Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a social network (pp. 137–146). SIGKDD.
- Kim, J., Kim, S. K., & Yu, H. (2013). Scalable and parallelizable processing of influence maximization for large-scale social networks. In 2013 IEEE 29th international conference on data engineering (ICDE) (pp. 266–277). IEEE.
- Kumar, S., Singhla, L., Jindal, K., Grover, K., & Panda, B. (2021). IM-ELPR: Influence maximization in social networks using label propagation based community structure. Applied Intelligence, 51, 1–19.
- Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007). Cost-effective outbreak detection in networks (pp. 420–429). SIGKDD.
- Li, H., Zhang, R., & Liu, X. (2022). An efficient discrete differential evolution algorithm based on community structure for influence maximization. Applied Intelligence, 52, 12497–12515.
- Li, M., Lu, S., Zhang, L., Zhang, Y., & Zhang, B. (2021). A community detection method for social network based on community embedding. IEEE Transactions on Computational Social Systems, 8, 308–318.
- Li, X., Cheng, X., Su, S., & Sun, C. (2018). Community-based seeds selection algorithm for location aware influence maximization. Neurocomputing, 275, 1601–1613.
- Lin, Z., Zhang, Y., Gong, Q., Chen, Y., Oksanen, A., & Ding, A. Y. (2022). Structural hole theory in social network analysis: A review. IEEE Transactions on Computational Social Systems, 9, 724–739.
- Lou, T., & Tang, J. (2013). Mining structural hole spanners through information diffusion in social networks. In Proceedings of the 22nd international conference on World Wide Web (pp. 825–836). Association for Computing Machinery.
10.1145/2488388.2488461 Google Scholar
- Ma, L., & Liu, Y. (2019). Maximizing three-hop influence spread in social networks using discrete comprehensive learning artificial bee colony optimizer. Applied Soft Computing, 83, 105606.
- MacKay, D. J. (1998). Introduction to Monte Carlo methods. In Learning in graphical models (pp. 175–204). Springer.
- Mattke, J., Maier, C., Reis, L., & Weitzel, T. (2020). Herd behavior in social media: The role of Facebook likes, strength of ties, and expertise. Information Management, 57, 103370.
10.1016/j.im.2020.103370 Google Scholar
- Naoto, O. (2020). The solution distribution of influence maximization: A high-level experimental study on three algorithmic approaches. In SIGMOD/PODS ‘20: International conference on management of data (pp. 2151–2166). Association for Computing Machinery.
- Qiu, L., Jia, W., Yu, J., Fan, X., & Gao, W. (2019). PHG: A three-phase algorithm for influence maximization based on community structure. IEEE Access, 7, 62511–62522.
- Ramponi, G., Brambilla, M., Ceri, S., Daniel, F., & Giovanni, M. D. (2020). Content-based characterization of online social communities. Information Processing and Management, 57(6), 102133.
- Rezvani, M., Liang, W., Xu, W., & Liu, C. (2015). Identifying top-k structural hole spanners in large-scale social networks. In Proceedings of the 24th ACM international on conference on information and knowledge management (pp. 263–272). Association for Computing Machinery.
10.1145/2806416.2806431 Google Scholar
- Sakshi, A., & Mehta, S. (2020). Effective influence estimation in twitter using temporal, profile, structural and interaction characteristics. Information Processing and Management, 57, 102321.
- Samir, A. M., Rady, S., & Gharib, T. F. (2021). LKG: A fast scalable community-based approach for influence maximization problem in social networks. Physica A: Statistical Mechanics and its Applications, 582, 126258.
- Shang, C., Zhang, R., Zhu, X., & Liu, Y. (2023). An adaptive consensus method based on feedback mechanism and social interaction in social network group decision making. Information Sciences, 625, 430–456.
- 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.
- Tang, J., Tang, X., & Yuan, J. (2017). Influence maximization meets efficiency and effectiveness: A hop-based approach. In In proceedings of the 2017 IEEE/ACM international conference on advances in social networks analysis and mining 2017 (pp. 64–71). IEEE.
10.1145/3110025.3110041 Google Scholar
- Wang, X., Zhang, Y., Zhang, W., & Lin, X. (2016). Distance-aware influence maximization in geo-social network. In 2016 IEEE 32nd international conference on data engineering (ICDE) (pp. 1–12). IEEE.
- Wang, Y., Cong, G., Song, G., & Xie, K. (2010). Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1039–1048). Association for Computing Machinery.
10.1145/1835804.1835935 Google Scholar
- Wang, Z., Sun, C., Xi, J., & Li, X. (2021). Influence maximization in social graphs based on community structure and node coverage gain. Future Generation Computer Systems, 118, 327–338.
- Xiaoping, S., & Yurong, S. (2015). Leveraging neighborhood “structural holes” to identifying key spreaders in social networks. Acta Physica Sinica, 64, 020101.
- Xu, W., Rezvani, M., Liang, W., Yu, J. X., & Liu, C. (2017). Efficient algorithms for the identification of top-k structural hole spanners in large social networks. IEEE Transactions on Knowledge and Data Engineering, 29(5), 1017–1030.
- You, Y., He, Y., Chen, Q., & Hu, M. (2021). The interplay between brand relationship norms and ease of sharing on electronic word of-mouth and willingness to pay. Information Management, 58(2), 103410.
10.1016/j.im.2020.103410 Google Scholar
- Zhang, M., Wei, X., & Chen, G. (2018). Maximizing the influence in social networks via holistic probability maximization. International Journal of Intelligent Systems, 33(10), 2038–2057.
- Zhang, Z., Zhao, W., Yang, J., Paris, C., & Nepal, S. (2019). Learning influence probabilities and modeling influence diffusion in twitter. Companion Proceedings of the 2019 World Wide Web Conference, 2019, 1087–1094.
10.1145/3308560.3316701 Google Scholar
- Zhao, Y., Li, S., & Jin, F. (2016). Identification of influential nodes in social networks with community structure based on label propagation. Neurocomputing, 210, 34–44.
- Zhu, J., Liu, Y., & Yin, X. (2017). A new structure-hole-based algorithm for influence maximization in large online social networks. IEEE Access, 5, 23405–23412.
- Zhu, J., Yin, X., Wang, Y., Li, J., Zhong, Y., & Li, Y. (2017). Structural holes theory-based influence maximization in social network. In Lecture Notes in Computer Science. Springer.