Measuring the impact of influence on individuals: roadmap to quantifying attitude
Tóm tắt
Diffusion of information in social network has been the focus of intense research in the recent past decades due to its significant impact in shaping public discourse through group/individual influence. Existing research primarily models influence as a binary property of entities: influenced or not influenced. While this is a useful abstraction, it discards the notion of degree of influence, i.e., certain individuals may be influenced “more” than others. We introduce the notion of attitude, which, as described in social psychology, is the degree by which an entity is influenced by the information. Intuitively, attitude captures the number of distinct neighbors of an entity influencing the latter. We present an information diffusion model (AIC model) that quantifies the degree of influence, i.e., attitude of individuals, in a social network. With this model, we formulate and study attitude maximization problem. We prove that the function for computing attitude is monotonic and sub-modular, and the attitude maximization problem is NP-Hard. We present a greedy algorithm for maximization with an approximation guarantee of
$$(1-1/e)$$
. In the context of AIC model, we study two problems, with the aim to investigate the scenarios where attaining individuals with high attitude is objectively more important than maximizing the attitude of the entire network. In the first problem, we introduce the notion of actionable attitude; intuitively, individuals with actionable attitude are likely to “act” on their attained attitude. We show that the function for computing actionable attitude, unlike that for computing attitude, is non-submodular and however is approximately submodular. We present approximation algorithm for maximizing actionable attitude in a network. In the second problem, we consider identifying the number of individuals in the network with attitude above a certain value, a threshold. In this context, the function for computing the number of individuals with attitude above a given threshold induced by a seed set is neither submodular nor supermodular. We present heuristics for realizing the solution to the problem. We experimentally evaluated our algorithms and studied empirical properties of the attitude of nodes in network such as spatial and value distribution of high attitude nodes.
Tài liệu tham khảo
Aggarwal CC, Khan A, Yan X (2011) On flow authority discovery in social networks. In: Proceedings of SIAM international conference on data mining, pp 522–533
Ajzen I (2001) Nature and operation of attitudes. Annu Rev Psychol 52:27–58
Aral S, Walker D (2012) Identifying influential and susceptible members of social networks. Science 337(6092):337–341
Arora A, Galhotra S, Ranu S (2017) Debunking the myths of influence maximization: An in-depth benchmarking study. In: SIGMOD, pp 651–666
Barbieri N, Bonchi F, Manco G (2012) Topic-aware social influence propagation models. In: ICDM, pp 81–90
Bastian Mathieu, Heymann Sebastien (2009) and Mathieu Jacomy. An open source software for exploring and manipulating networks, Gephi
Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech: Theory Exp 2008(10):P10008
Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. In: SODA, pp 946–957
Chen S, Fan J, Li G, Feng J, Tan K-L, Tang J (2015) Online topic-aware influence maximization. Proc VLDB Endow 8(6):666–677
Chen W, Collins A, Cummings R, Ke T, Liu Z, Rincón D, Sun X, Wang Y, Wei W, Yuan Y (2011) Influence maximization in social networks when negative opinions may emerge and propagate. In: SDM, pp 379–390
Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: SIGKDD, pp 1029–1038
Domingos P, Richardson M (2001) Mining the network value of customers. In: KDD, pp 57–56
Duane A, Scott J (1996) Understanding Change in Social Attitudes
Fishbein M, Ajzen I (1975) Belief, attitude, intention, and behavior: an introduction to theory and research. Addison-Wesley, Boston
Fowler James H, Christakis Nicholas A (2011) Connected: The surprising power of our social networks and how they shape our lives. Little, Brown Spark
Fu X, Padmanabhan M, Gaurav R, Basu S, Dorius S, Pavan A (2020) Measuring the impact of influence on individuals: Roadmap to quantifying attitude. In: IEEE/ACM 2020 international conference on advances in social networks analysis and mining, ASONAM, pp 227–231. IEEE Computer Society
Galhotra S, Arora A, Roy S (2016) Holistic influence maximization: combining scalability and efficiency with opinion-aware models. In: SIGMOD, pages 743–758
Guo J, Zhang P, Zhou C, Cao Y, Guo L (2013) Personalized influence maximization on social networks. CIKM 13:199–208
Huang K, Wang S, Bevilacqua G, Xiao X, Lakshmanan LVS (2017) Revisiting the stop-and-stare algorithms for influence maximization. Proc VLDB Endow 10(9):913–924
Jung K, Heo W, Chen W (2012) IRIE: scalable and robust influence maximization in social networks. ICDM 2012:918–923
Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: KDD, pp 137–146
Krause A, Singh A, Guestrin C (2008) Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J Mach Learn Res 9(8):235–284
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: KDD, pp 420–429
Li FH, Li CT, Shan MK (2011) Labeled influence maximization in social networks for target marketing. PASSAT/SocialCom 2011:560–563
Li Y, Zhang D, Tan K-L (2015) Real-time targeted influence maximization for online advertisements. VLDB 8(10):1070–1081
Liu Q, Xiang B, Zhang L, Chen E, Tan C, Chen J (2013) Linear computation for independent social influence. In: IEEE 13th international conference on data mining, pp 468–477
Liu Q, Xiang B, Yuan NJ, Chen E, Xiong H, Zheng Y, Yang Y (2017) An influence propagation view of pagerank. ACM Trans Know Dis Data 11(3)
Lu W, Lakshmanan LVS (2012) Profit maximization over social networks. In: ICDM, pp 479–488
Martin Shawn, Brown W Michael, Klavans Richard, Boyack Kevin (01 2011) Openord: An open-source toolbox for large graph layout. Proc SPIE, 7868:786806
Nemhauser George, Wolsey Laurence, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions. 14:265–294
Nguyen H, Thai M, Dinh T (2016) Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In: Proceedings SIGMOD, pp 695–710
Padmanabhan M, Somisetty N, Basu S, Pavan A (2018) Influence maximization in social networks with non-target constraints. IEEE International Conference on Big Data, Big Data 2018:771–780
Rokeach M (1970) Beliefs. Jossey-Bass, Attitudes and Values
Song C, Hsu W, Lee ML (2016) Targeted influence maximization in social networks. Proc CIKM 16:1683–1692
Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: A martingale approach. In: SIGMOD, pages 1539–1554
Tang Y, Xiao X, Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: SIGMOD, pp 75–86
Vosoughi S, Roy D, Aral S (2018) The spread of true and false news online. Science 359(6380):1146–1151
Zajonc R (1968) Attitudinal effects of mere exposure. J Pers Soc Psychol 9(2):1–27
Zhang H, Dinh TN, Thai MT (2013) Maximizing the spread of positive influence in online social networks. In: ICDCS, pp 317–326
Zhou C, Zhang P, Zang W, Guo L (2014) Maximizing the cumulative influence through a social network when repeat activation exists. In: International Conference on Computational Science, pp 422 – 431