×

TIFIM: a two-stage iterative framework for influence maximization in social networks. (English) Zbl 1429.91262

Summary: Influence maximization is an important problem in social networks, and its main goal is to select some most influential initial nodes (i.e., seed nodes) to obtain the maximal influence spread. The existing studies primarily concentrate on the corresponding methods for influence maximization, including greedy algorithms, heuristic algorithms and their extensions to determine the most influential nodes. However, there is little work to ensure efficiency and accuracy of the proposed schemes at the same time. In this paper, a two-stage iterative framework for the Influence Maximization in social networks, (i.e., TIFIM) is proposed. In order to exclude less influential nodes and decrease the computation complexity of TIFIM, in the first stage, an iterative framework in descending order is proposed to select the candidate nodes. In particular, based on the results of the last iteration and the two-hop measure, the First-Last Allocating Strategy (FLAS) is presented to compute the spread benefit of each node. We prove that TIFIM converges to a stable order within the finite iterations. In the second stage, we define the apical dominance to calculate the overlapping phenomenon of spread benefit among nodes and further propose Removal of the Apical Dominance (RAD) to determine seed nodes from the candidate nodes. Moreover, we also prove that the influence spread of TIFIM according to RAD converges to a specific value within finite computations. Finally, simulation results show that the proposed scheme has superior influence spread and running time than other existing ones.

MSC:

91D30 Social networks; opinion dynamics

Software:

CoFIM; CELF++; IIMOF; TIFIM
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Zhang, H.; Mishra, S.; Thai, M. T., Recent advances in information diffusion and influence maximization in complex social networks, Opportun. Mob. Soc. Netw., 1-37 (2014)
[2] Tan, W.; Blake, M. B.; Saleh, I.; Dustdar, S., Social-network-sourced big data analytics, IEEE Int. Comput., 17, 5, 62-69 (2013)
[3] Zhang, H.; Zhang, H.; Kuhnle, A.; Thai, M. T., Profit maximization for multiple products in online social networks, Proceedings of the IEEE International Conference on Computer Communications, 1-9 (2016)
[4] Kundu, S.; Murthy, C.; Pal, S. K., A new centrality measure for influence maximization in social networks, Proceedings of the International Conference on Pattern Recognition and Machine Intelligence, 242-247 (2011)
[5] Kim, J.; Kim, S. K.; Yu, H., Scalable and parallelizable processing of influence maximization for large-scale social networks, Proceedings of the IEEE International Conference on Data Engineering (ICDE), 266-277 (2013)
[6] He, Q.; Wang, X.; Huang, M.; Lv, J.; Ma, L., Heuristics-based influence maximization for opinion formation in social networks, Appl. Soft Comput., 66, 360-369 (2018)
[7] Sichani, O. A.; Jalili, M., Influence maximization of informed agents in social networks, Appl. Math. Comput., 254, 1, 229-239 (2015) · Zbl 1410.91389
[8] Martinčić-Ipšić, S.; Močibob, E.; Perc, M., Link prediction on twitter, PloS One., 12, 7, 1-21 (2017)
[9] Jalili, M.; Orouskhani, Y.; Asgari, M.; Alipourfard, N.; Perc, M., Link prediction in multiplex online social networks, R. Soc. Open Sci., 4, 2, 160863 (2017)
[10] Cai, J. L.Z.; Yan, M.; Li, Y., Using crowdsourced data in location-based social networks to explore influence maximization, Proceedings of the IEEE International Conference on Computer Communications, 1-9 (2016)
[11] Zhuang, H.; Sun, Y.; Tang, J.; Zhang, J.; Sun, X., Influence maximization in dynamic social networks, Proceedings of the IEEE International Conference on Data Mining (ICDM), 1313-1318 (2013)
[12] Li, S.; Zhu, Y.; Li, D.; Kim, D.; Ma, H.; Huang, H., Influence maximization in social networks with user attitude modification, Proceedings of the IEEE International Conference on Communications, 3913-3918 (2014)
[13] Chen, D.; Lü, L.; Shang, M. S.; Zhang, Y. C.; Zhou, T., Identifying influential nodes in complex networks, Phys. A Stat. Mech. Appl., 391, 4, 1777-1787 (2012)
[14] Bozorgi, A.; Samet, S.; Kwisthout, J.; Wareham, T., Community-based influence maximization in social networks under a competitive linear threshold model, Knowl. Based Syst., 134, 149-158 (2017)
[15] Rahimkhani, K.; Aleahmad, A.; Rahgozar, M.; Moeini, A., A fast algorithm for finding most influential people based on the linear threshold model, Expert Syst. Appl., 42, 3, 1353-1361 (2015)
[16] Ganesh, A.; Massoulié, L.; Towsley, D., The effect of network topology on the spread of epidemics, Proceedings of the IEEE International Conference on Computer Communications, 1455-1466 (2005)
[17] Woo, J.; Chen, H., Epidemic Model for Information Diffusion In Web forums: Experiments in Marketing Exchange and Political Dialog, 5, 1-19 (2016), SpringerPlus
[18] Tzoumas, V.; Amanatidis, C.; Markakis, E., A game-theoretic analysis of a competitive diffusion process over social networks, Proceedings of the International Conference on Internet and Network Economics, 1-14 (2012)
[19] He, Q.; Wang, X.; Huang, M.; Cai, Y.; Ma, L., An adaptive approach for handling two-dimension influence maximization in social networks, Int. J. Commun. Syst., 31, 15, 1-14 (2018)
[20] Jalili, M.; Perc, M., Information cascades in complex networks, J. Complex Netw., 5, 5, 665-693 (2017)
[21] Domingos, P.; Richardson, M., Mining the network value of customers, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 57-66 (2001)
[22] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 137-146 (2003)
[23] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Theory Comput., 11, 4, 105-147 (2015) · Zbl 1337.91069
[24] Chen, W.; Wang, Y.; Yang, S., Efficient influence maximization in social networks, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 199-208 (2009)
[25] Chen, W.; Wang, C.; Wang, Y., Scalable influence maximization for prevalent viral marketing in large-scale social networks, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1029-1038 (2010)
[26] Chen, Y. C.; Zhu, W. Y.; Peng, W. C.; Lee, W. C.; Lee, S. Y., CIM: community-based influence maximization in social networks, ACM Trans. Intell. Syst. Technol. (TIST)., 5, 2, 1-31 (2014)
[27] He, Q.; Wang, X.; Zhang, C.; Huang, M.; Zhao, Y., IIMOF: an iterative framework to settle influence maximization for opinion formation in social networks, IEEE Access., 6, 49654-49663 (2018)
[28] Liu, B.; Cong, G.; Zeng, Y.; Xu, D.; Chee, Y. M., Influence spreading path and its application to the time constrained social influence maximization problem and beyond, IEEE Trans. Knowl. Data Eng., 26, 8, 1904-1917 (2014)
[29] Lee, J. R.; Chung, C. W., A query approach for influence maximization on specific users in social networks, IEEE Trans. Knowl. Data Eng., 27, 2, 340-353 (2015)
[30] Song, G.; Zhou, X.; Wang, Y.; Xie, K., Influence maximization on large-scale mobile social network: a divide-and-conquer method, IEEE Trans. Parallel Distr. Syst., 26, 5, 1379-1392 (2015)
[31] Song, G.; Li, Y.; Chen, X.; He, X.; Tang, J., Influential node tracking on dynamic social network: an interchange greedy approach, IEEE Trans. Knowl. Data Eng., 29, 2, 359-372 (2017)
[32] Goyal, A.; Lu, W.; Lakshmanan, L. V.S., CELF++: optimizing the greedy algorithm for influence maximization in social networks, Proceedings of the International Conference Companion on World Wide Web, 47-48 (2011)
[33] Jung, K.; Heo, W.; Chen, W., IRIE: scalable and robust influence maximization in social networks, Proceedings of the IEEE International Conference on Data Mining (ICDM), 918-923 (2012)
[34] Nguyen, H.; Zheng, R., On budgeted influence maximization in social networks, IEEE J. Selected Areas Commun., 31, 6, 1084-1094 (2013)
[35] Tong, G.; Wu, W.; Tang, S.; Du, D. Z., Adaptive influence maximization in dynamic social networks, IEEE/ACM Trans. Netw., 25, 1, 112-125 (2017)
[36] Shang, J.; Zhou, S.; Li, X.; Liu, L.; Wu, H., CoFIM: a community-based framework for influence maximization on large-scale networks, Knowl Based Syst., 117, 1, 88-100 (2017)
[37] Gong, M.; Song, C.; Duan, C.; Ma, L.; Shen, B., An efficient memetic algorithm for influence maximization in social networks, IEEE Comput. Intell. Mag., 11, 3, 22-33 (2016)
[38] Walker, S. K., Connected: the surprising power of our social networks and how they shape our lives, J. Family Theory Review., 3, 3, 220-224 (2011)
[39] Pei, S.; Muchnik, L.; Andrade, J. S.; Zheng, Z.; Makse, H. A., Searching for superspreaders of information in real-world social media, Sci. Rep., 4, 1-12 (2014)
[40] Sanders, R., On convergence of monotone finite difference schemes with variable spatial differencing, Math. Comput., 40, 161, 91-106 (1983) · Zbl 0533.65061
[41] Wade, W. R., The bounded convergence theorem, Ame. Math. Monthly., 81, 4, 387-389 (1974) · Zbl 0294.28003
[42] Lusseau, D.; Schneider, K.; Boisseau, O. J.; Haase, P.; Slooten, E.; Dawson, S. M., The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol., 54, 4, 396-405 (2003)
[43] Newman, M. E.J., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E., 74, 3, 036104 (2006)
[44] Opsahl, T.; Panzarasa, P., Clustering in weighted networks, Soc. Netw., 31, 2, 155-163 (2009)
[45] McAuley, J.; Leskovec, J., Learning to discover social circles in ego networks, Adv. Neural Inf. Process. Syst. (NIPS), 1-12 (2012)
[47] Kumar, S.; Spezzano, F.; Subrahmanian, V. S.; Faloutsos, C., Edge weight prediction in weighted signed networks, Proceedings of the IEEE International Conference on Data Mining (ICDM), 221-230 (2016)
[48] Paolo, M.; Martino, S.; Danilo, T., Bowling alone and trust decline in social network sites, Proceedings of the IEEE International Conference on Dependable, Autonomic and Secure Computing, 658-663 (2009)
[49] Flache, A.; Macy, M. W., Local convergence and global diversity from interpersonal to social influence, J. Conflict Resolut., 55, 6, 970-995 (2011)
[50] Borgs, C.; Brautbar, M.; Chayes, J.; Lucier, B., Maximizing social influence in nearly optimal time, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 946-957 (2014) · Zbl 1420.68248
[51] Tang, Y.; Shi, Y.; Xiao, X., Influence maximization in near-linear time: a martingale approach, Proceedings of the ACM SIGMOD International Conference on Management of Data, 1539-1554 (2015)
[52] Brin, S.; Page, L., Reprint of: the anatomy of a large-scale hypertextual web search engine, Comput. Netw., 56, 18, 3825-3833 (2012)
[53] Williams, D., Probability with Martingales (1991), Cambridge University Press · Zbl 0722.60001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.