Speaker:Xiaoyun Fu

Attitude Maximization Under Attitude-IC model, and Multi-Objective Submodular Optimization with Approximate Oracles

Diffusion of information in social networks 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.

While Attitude Maximization introduced new aspects and insight into the basic information diffusion models, it still focuses on maximizing the “influence” measure of the seed set over the whole network without differentiating the individuals by their affiliation to different groups. To take this into account, we study the group influence maximization problem which seeks to influence each group in the network fairly. We then generalize this problem to the multi-objective optimization problem with cardinality constraint in the context of δ-approximate oracle and show that it is possible to ensure (1 −1/e)2 −3δ-approximate guarantee. As group influence maximization in online social networks is an instance of this optimization problem with cardinality constraint and δ-oracle, we apply the results to it. We develop a prototype implementation of our solution strategy for group influence maximization problem for networks of different sizes and experimentally justify the effectiveness and scalability of our strategy.

Committee: Pavan Aduri (major professor), Samik Basu (major professor), Shawn Fletcher Dorius, Qi Li, and Kevin Liu

Join on WebEx: https://iastate.webex.com/iastate/j.php?MTID=m0ffa055fe51bd6ab817089270e3fc5e7