 Award ID(s):
 1934884
 NSFPAR ID:
 10288394
 Editor(s):
 He, Jing; Purohit, Hemant; Huang, Guangyan; Gao, Xiaoying; Deng, Ke
 Date Published:
 Journal Name:
 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI/IAT 2020,
 Page Range / eLocation ID:
 397404
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)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 \emph{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 submodular, and the attitude maximization problem is NPHard. We present a greedy algorithm for maximization with an approximation guarantee of $(11/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 \emph{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 nonsubmodular and however is \emph{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 \emph{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.more » « less

Atzmuller, Martin ; Coscia, Michele ; Missaoui, Rokia (Ed.)Influence diffusion has been central to the study of the propagation of information in social networks, where influence is typically modeled as a binary property of entities: influenced or not influenced. We introduce the notion of attitude, which, as described in social psychology, is the degree by which an entity is influenced by the information. We present an information diffusion model that quantifies the degree of influence, i.e., attitude of individuals, in a social network. With this model, we formulate and study the attitude maximization problem. We prove that the function for computing attitude is monotonic and submodular, and the attitude maximization problem is NPHard. We present a greedy algorithm for maximization with an approximation guarantee of $(11/e)$. Using the same model, we also introduce the notion of ``actionable'' attitude with the aim to study the scenarios where attaining individuals with high attitude is objectively more important than maximizing the attitude of the entire network. We show that the function for computing actionable attitude, unlike that for computing attitude, is nonsubmodular but is approximately submodular. We present an approximation algorithm for maximizing actionable attitude in a network. We experimentally evaluated our algorithms and studied empirical properties of the attitude of nodes in the network such as spatial and value distribution of high attitude nodes.more » « less

Due to the significance of its various applications, source localization has garnered considerable attention as one of the most important means to confront diffusion hazards. Multisource localization from a singlesnapshot observation is especially relevant due to its prevalence. However, the inherent complexities of this problem, such as limited information, interactions among sources, and dependence on diffusion models, pose challenges to resolution. Current methods typically utilize heuristics and greedy selection, and they are usually bonded with one diffusion model. Consequently, their effectiveness is constrained.To address these limitations, we propose a simulationbased method termed BOSouL. Bayesian optimization (BO) is adopted to approximate the results for its sample efficiency. A surrogate function models uncertainty from the limited information. It takes sets of nodes as the input instead of individual nodes. BOSouL can incorporate any diffusion model in the data acquisition process through simulations. Empirical studies demonstrate that its performance is robust across graph structures and diffusion models. The code is available at https://github.com/XGraphTeam/BOSouL.more » « less

Influence maximization problem attempts to find a small subset of nodes that makes the expected influence spread maximized, which has been researched intensively before. They all assumed that each user in the seed set we select is activated successfully and then spread the influence. However, in the real scenario, not all users in the seed set are willing to be an influencer. Based on that, we consider each user associated with a probability with which we can activate her as a seed, and we can attempt to activate her many times. In this article, we study the adaptive influence maximization with multiple activations (AdaptiveIMMA) problem, where we select a node in each iteration, observe whether she accepts to be a seed, if yes, wait to observe the influence diffusion process; if no, we can attempt to activate her again with a higher cost or select another node as a seed. We model the multiple activations mathematically and define it on the domain of integer lattice. We propose a new concept, adaptive drsubmodularity, and show our AdaptiveIMMA is the problem that maximizing an adaptive monotone and drsubmodular function under the expected knapsack constraint. Adaptive drsubmodular maximization problem is never covered by any existing studies. Thus, we summarize its properties and study its approximability comprehensively, which is a nontrivial generalization of existing analysis about adaptive submodularity. Besides, to overcome the difficulty to estimate the expected influence spread, we combine our adaptive greedy policy with sampling techniques without losing the approximation ratio but reducing the time complexity. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed policies.more » « less

Abstract Design heuristics are traditionally used as qualitative principles to guide the design process, but they have also been used to improve the efficiency of design optimization. Using design heuristics as soft constraints or search operators has been shown for some problems to reduce the number of function evaluations needed to achieve a certain level of convergence. However, in other cases, enforcing heuristics can reduce diversity and slow down convergence. This paper studies the question of when and how a given set of design heuristics represented in different forms (soft constraints, repair operators, and biased sampling) can be utilized in an automated way to improve efficiency for a given design problem. An approach is presented for identifying promising heuristics for a given problem by estimating the overall impact of a heuristic based on an exploratory screening study. Two impact indices are formulated: weighted influence index and hypervolume difference index. Using this approach, the promising heuristics for four design problems are identified and the efficacy of selectively enforcing only these promising heuristics over both enforcement of all available heuristics and not enforcing any heuristics is benchmarked. In all problems, it is found that enforcing only the promising heuristics as repair operators enables finding good designs faster than by enforcing all available heuristics or not enforcing any heuristics. Enforcing heuristics as soft constraints or biased sampling functions results in improvements in efficiency for some of the problems. Based on these results, guidelines for designers to leverage heuristics effectively in design optimization are presented.