×

Finding top-\(k\) influential users in social networks under the structural diversity model. (English) Zbl 1427.68369

Summary: The influence maximization problem in a large-scale social network is to identify a few influential users such that their influence on the other users in the network is maximized, under a given influence propagation model. One common assumption adopted by two popular influence propagation models is that a user is more likely to be influenced if more his/her friends have already been influenced. This assumption recently however was challenged to be over simplified and inaccurate, as influence propagation process typically is much more complex than that, and the social decision of a user depends more subtly on the network structure, rather than how many his/her influenced friends. Instead, it has been shown that a user is very likely to be influenced by structural diversities of his/her friends. In this paper, we first formulate a novel influence maximization problem under this new structural diversity model. We then propose a constant approximation algorithm for the problem. We finally evaluate the effectiveness of the proposed algorithm by extensive experimental simulations, using different real datasets. Experimental results show that the users identified from a social network by the proposed algorithm have much larger influence than that found by existing algorithms.

MSC:

68W25 Approximation algorithms
05C82 Small world graphs, complex networks (graph-theoretic aspects)
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, N.; Liu, H.; Tang, L.; Yu, P. S., Identifying the influential bloggers in a community, Proceedings of the 2008 ACM International Conference on Web Search and Data mining (WSDM) (2008)
[2] Bakshy, E.; Hofman, J. M.; Mason, W. A.; Watts, D. J., Everyone’s an influencer: quantifying influence on twitter, Proceedings of the Fourth ACM International Conference on Web Search and Data Mining (WSDM) (2011)
[3] Borgs, C.; Brautbar, M.; Chayes, J.; Lucier, B., Maximizing social influence in nearly optimal time, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2014) · Zbl 1420.68248
[4] Borodin, A.; Braverman, M.; Lucier, B.; Oren, J., Strategy proof mechanisms for competitive influence in networks, Proceedings of the 22nd International Conference on World Wide Web (WWW) (2013)
[5] Budak, C.; Agrawal, D.; Abbadi, A. E., Limiting the spread of misinformation in social networks, Proceedings of the 20th International Conference on World Wide Web (WWW) (2011)
[6] Budak, C.; Agrawal, D.; Abbadi, A. E., Diffusion of information in social networks: is it all local?, Proceedings of the IEEE 12th International Conference on Data Mining (ICDM) (2012)
[7] Chaoji, V.; Ranu, S.; Rastogi, R.; Bhatt, R., Recommendations to boost content spread in social networks, Proceedings of the 21st International Conference on World Wide Web (WWW) (2012)
[8] Chen, W.; Lakshmanan, L. V.S.; Castillo, C., Information and Influence Propagation in Social Networks (2013), Morgan & Claypool Publishers
[9] Chen, W.; Lu, W.; Zhang, N., Time-critical influence maximization in social networks with time-delayed diffusion process, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI) (2012)
[10] Chen, W.; Wang, Y.; Yang, S., Efficient influence maximization in social networks, Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD) (2009)
[11] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), The MIT Press · Zbl 1187.68679
[12] Dinh, T. N.; Zhang, H.; Nguyen, D. T.; Thai, M. T., Cost-effective viral marketing for time-critical campaigns in large-scale social networks, IEEE/ACM Trans. Netw., 22, 6, 2001-2011 (2013)
[13] Domingos, P.; Richardson, M., Mining the network value of customers, Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2001)
[15] Gomez-Rodriguez, M.; Leskovec, J.; Krause, A., Inferring networks of diffusion and influence, ACM Trans. Knowl. Discov. Data (TKDD), 5, 4 (2012)
[16] Goyal, A.; Bonchi, F.; Lakshmanan, L., A data-based approach to social influence maximization, Proceedings of the VLDB Endowment (2011)
[17] Goyal, A.; Bonchi, F.; Lakshmanan, L.; Venkatasubramanian, S., On minimizing budget and time in influence propagation over social networks, Social Netw. Anal. Mining, 3, 2, 179-192 (2013)
[18] He, X.; Song, G.; Chen, W.; Jiang, Q., Influence blocking maximization in social networks under the competitive linear threshold model, Proceedings of the Twelfth SIAM International Conference on Data Mining (SDM) (2012)
[19] Hugo, O.; Garnsey, E., The emergence of electronic messaging and the growth of four entrepreneurial entrants, New Tech. Based Firms New Millenn., 2, 97-124 (2002)
[20] Jin, L.; Chen, Y.; Wang, T.; Hui, P.; Vasilakos, A. V., Understanding user behavior in online social networks: a survey, IEEE Commun. Mag., 51, 9, 144-150 (2013)
[21] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD) (2003)
[22] Li, H.; Bhowmick, S. S.; Sun, A., CINEMA: conformity-aware greedy algorithm for influence maximization in online social Networks, Proceedings of the 16th International Conference on Extending Database Technology (EDBT) (2013)
[23] Li, Y.; Qian, M.; Jin, D.; Hui, P.; Vasilakos, A. V., Revealing the efficiency of information diffusion in online social networks of microblog, Inf. Sci., 293, 383-389 (2015)
[24] Nemhauser, G.; Wolsey, L.; Fisher, M., An analysis of the approximations for maximizing submodular set functions-i, Math. Program., 14, 265-294 (1978) · Zbl 0374.90045
[25] Rezvani, M.; Liang, W.; Xu, W.; Liu, C., Identifying top-\(k\) structural hole spanners in large-scale social networks, Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM) (2015)
[26] Richardson, M.; Domingos, P., Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2002)
[27] Tang, Y.; Xiao, X.; Shi, Y., Influence maximization: near-optimal time complexity meets practical efficiency, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD) (2014)
[28] Ugander, J.; Backstrom, L.; Marlow, C.; Kleinberg, J., Structural diversity in social contagion, Proc. Nat. Acad. Sci. (PNAS), 109, 5962-5966 (2012)
[29] Wang, C.; Chen, W.; Wang, Y., Scalable influence maximization for independent cascade model in large-scale social networks, Data Mining Knowl. Discov., 25, 545-576 (2012) · Zbl 1260.91219
[30] Wang, Y.; Cong, G.; Song, G.; Xie, K., Community-based greedy algorithm for mining top-\(k\) influential nodes in mobile social networks, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD) (2010)
[31] Wang, Y.; Vasilakos, A. V.; Ma, J.; Xiong, N., On studying the impact of uncertainty on behavior diffusion in social networks, IEEE Trans. Syst. Man Cybern. Syst., 45, 2, 185-197 (2015)
[32] Wang, Y.; Vasilakos, A. V.; Ma, J., VPEF: a simple and effective incentive mechanism in community-based autonomous networks, IEEE Trans. Netw. Serv. Manage., 12, 1, 75-86 (2015)
[33] Wang, Y.; Vasilakos, A. V.; Jin, Q.; Ma, J., PPRank: economically selecting initial users for influence maximization in social networks, IEEE Syst. J., 1-12 (2015)
[34] Wei, G.; Zhu, P.; Vasilakos, A. V.; Mao, Y.; Luo, J.; Ling, Y., Cooperation dynamics on collaborative social networks of heterogeneous population, IEEE J. Select. Areas Commun., 31, 6, 1135-1146 (2013)
[35] Zhang, Y.; Li, X.; Xu, J.; Vasilakos, A. V., Human interactive patterns in temporal networks, IEEE Trans. Syst. Man Cybern. Syst., 45, 2, 214-222 (2015)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.