Link injection for boosting information spread in social networks
Tóm tắt
Social media have become popular platforms for spreading information. Several applications, such as ‘viral marketing’, pause the requirement for attaining large-scale information spread in the form of word-of-mouth that reaches a large number of users. In this paper, we propose a novel method that predicts new social links that can be inserted among existing users of a social network, aiming directly at boosting information spread and increasing its reach. We refer to this task as ‘link injection’, because unlike most existing people-recommendation methods, it focuses directly on information spread. A set of candidate links for injection is first predicted in a collaborative-filtering fashion, which generates personalized candidate connections. We select among the candidate links a constrained number that will be finally injected based on a novel application of a score that measures the importance of nodes in a social graph, following the strategy of injecting links adjacent to the most important nodes. The proposed method is suitable for real-world applications, because the injected links manage to substantially increase the reach of information spread by controlling at the same time the number of injected links not to affect the user experience. We evaluate the performance of our proposed methodology by examining several real data sets from social networks under several distinct factors. The experimentation demonstrates the effectiveness of our proposed method, which increases the spread by more than a twofold factor by injecting as few as half of the existing number of links.
Tài liệu tham khảo
Anagnostopoulos A, Kumar R, Mahdian M (2008) Influence and correlation in social networks. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’08. ACM, New York, pp 7–15. doi:10.1145/1401890.1401897
Berry MW, Browne M, Langville AN, Pauca VP, Plemmons RJ (2003) Algorithms and applications for approximate nonnegative matrix factorization. Comput Stat Data Anal 52(1):155–173
Bhatt R, Chaoji V, Parekh R (2010) Predicting product adoption in large-scale social networks. In: Proceedings of the 19th ACM international conference on information and knowledge management, CIKM ’10. ACM, New York, pp 1039–1048. doi:10.1145/1871437.1871569
Boldi P, Rosa M, Vigna S (2013) Robustness of social and web graphs to node removal. Soc Netw Anal Min 3(4):829–842
Bonchi F, Castillo C, Gionis A, Jaimes A (2011) Social network analysis and mining for business applications. ACM Trans Intell Syst Technol 2(3):22:1–22:37
Borbora Z, Ahmad M, Oh J, Haigh K, Srivastava J, Wen Z (2013) Robust features of trust in social networks. Soc Netw Anal Min 3(4):981–999
Chaoji V, Ranu S, Rastogi R, Bhatt R (2012) Recommendations to boost content spread in social networks. In: Proceedings of the 21st international conference on World Wide Web, WWW ’12. ACM, New York, pp 529–538
Chen J, Geyer W, Dugan C, Muller M, Guy I (2009) Make new friends, but keep the old: recommending people on social networking sites. In: Proceedings of the SIGCHI conference on human factors in computing systems, CHI ’09. ACM, New York, pp 201–210
Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’09. ACM, New York, pp 199–208
Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: Proceedings of the 2010 IEEE international conference on data mining, ICDM ’10. IEEE Computer Society, Washington DC, pp 88–97. doi:10.1109/ICDM.2010.118
Chung F (2014) Spectral graph theory. No. 92 in CBMS Regional Conference Series. Conference Board of the Mathematical Sciences. http://books.google.gr/books?id=YUc38_MCuhAC
David E, Jon K (2010) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, New York
Dinev T, Hu Q, Yayla A (2008) Is there an on-line advertisers’ dilemma? A study of click fraud in the pay-per-click model. Int J Electron Commer 13(2):29–60
Goyal A, Bonchi F, Lakshmanan L, Venkatasubramanian S (2013) On minimizing budget and time in influence propagation over social networks. Soc Netw Anal Min 3(2):179–192
Goyal A, Bonchi F, Lakshmanan LV (2010) Learning influence probabilities in social networks. In: Proceedings of the third ACM international conference on web search and data mining, WSDM ’10. ACM, New York, pp 241–250. doi:10.1145/1718487.1718518
Guille A, Hacid H, Favre C, Zighed DA (2013) Information diffusion in online social networks: a survey. SIGMOD Rec 42(2):17–28. doi:10.1145/2503792.2503797
Guy I, Ronen I, Wilcox E (2009) Do you know?: Recommending people to invite into your social network. In: Proceedings of the 14th international conference on intelligent user interfaces, IUI ’09. ACM, New York, pp 77–86
Hannon J, Bennett M, Smyth B (2010) Recommending twitter users to follow using content and collaborative filtering approaches. In: Proceedings of the fourth ACM conference on recommender systems, RecSys ’10. ACM, New York, pp 199–206
Hinz O, Bernd S, Christian B, Becker JU (2011) Seeding strategies for viral marketing: an empirical comparison. J Mark 75(6):55–71
Jackson MO (2011) An overview of social networks and economic applications. In: Benhabib J, Bisin A, Jackson MO (eds) Handbook of Social Economics, vol 1A, Elsevier, Amsterdam, pp 511–585
Kempe D, Kleinberg J, Tardos E (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, KDD ’03. ACM, New York, pp 137–146
Kempe D, Kleinberg J, Tardos E (2005) Influential nodes in a diffusion model for social networks. In: Proceedings of the 32nd international conference on automata, languages and programming, ICALP’05. Springer, Berlin, pp 1127–1138. doi:10.1007/11523468_91
Kim YA, Srivastava J (2007) Impact of social influence in e-commerce decision making. In: Proceedings of the ninth international conference on electronic commerce, ICEC ’07. ACM, New York, pp 293–302
Kimura M, Saito K (2006) Tractable models for information diffusion in social networks. In: Proceedings of the 10th European conference on principle and practice of knowledge discovery in databases, PKDD’06. Springer, Berlin, pp 259–271. doi:10.1007/11871637_27.
Kiss C, Bichler M (2008) Identification of influencers—measuring influence in customer networks. Decis Support Syst 46(1):233–253
Lawton B, Gregor S (2003) Internet marketing communications: interactivity and integration. In: Seeking success in e-business. Kluwer Academic Publishers, Norwell, pp 239–257
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’07. ACM, New York, pp 420–429. doi:10.1145/1281192.1281239
Li YM, Shiu YL (2012) A diffusion mechanism for social advertising over microblogs. Decis Support Syst 54(1):9–22
Liben-Nowell D, Kleinberg J (2003) The link prediction problem for social networks. In: Proceedings of the twelfth international conference on information and knowledge management, CIKM ’03. ACM, New York, pp 556–559
Ling C, Huang J, Zhang H (2003) Auc: a better measure than accuracy in comparing learning algorithms. In: Xiang Y, Chaib-draa B (eds) Advances in artificial intelligence. Lecture notes in computer science, vol 2671. Springer, Berlin, pp 329–341
Liu H, Li X, Zheng X (2013) Solving non-negative matrix factorization by alternating least squares with a modified strategy. Data Min Knowl Discov 26(3):435–451
Mussweiler T, Strack F (2000) Numeric judgments under uncertainty: the role of knowledge in anchoring. J Exp Soc Psychol 36:495–518
Narayanam R, Narahari Y (2011) A shapley value-based approach to discover influential nodes in social networks. IEEE Trans Autom Sci Eng 8(1):130–147. doi:10.1109/TASE.2010.2052042
Papadopoulos S, Kompatsiaris Y, Vakali A, Spyridonos P (2012) Community detection in social media. Data Min Knowl Discov 24(3):515–554
Piraveenan M, Thedchanamoorthy G, Uddin S, Chung K (2013) Quantifying topological robustness of networks under sustained targeted attacks. Soc Netw Anal Min 3(4):939–952
Saito K, Kimura M, Ohara K, Motoda H (2010) Selecting information diffusion models over social networks for behavioral analysis. In: Proceedings of the 2010 European conference on machine learning and knowledge discovery in databases: part III, ECML PKDD’10. Springer, Berlin, pp 180–195. http://dl.acm.org/citation.cfm?id=1889788.1889801
Schifanella R, Barrat A, Cattuto C, Markines B, Menczer F (2010) Folks in folksonomies: social link prediction from shared metadata. In: Proceedings of the third ACM international conference on web search and data mining, WSDM ’10. ACM, New York, pp 271–280
Tang J, Sun J, Wang C, Yang Z (2009) Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’09. ACM, New York, pp 807–816. doi:10.1145/1557019.1557108
Tang L, Wang X, Liu H (2009) Uncovering groups via heterogeneous interaction analysis. In: Proceedings of the 9th international conference on data mining, ICDM ’09, pp 503–512
Tong H, Prakash BA, Tsourakakis C, Eliassi-Rad T, Faloutsos C, Chau DH (2010) On the vulnerability of large graphs. In: Proceedings of the 2010 IEEE international conference on data mining, ICDM ’10. IEEE Computer Society, Washington DC, pp 1091–1096