Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Evans, Robin ; Shpitser, Ilya (Ed.)We consider the problem of maximizing submodular functions under submodular constraints by formulating the problem in two ways: \SCSKC and \DiffC. Given two submodular functions $f$ and $g$ where $f$ is monotone, the objective of \SCSKC problem is to find a set $S$ of size at most $k$ that maximizes $f(S)$ under the constraint that $g(S)\leq \theta$, for a given value of $\theta$. The problem of \DiffC focuses on finding a set $S$ of size at most $k$ such that $h(S) = f(S)g(S)$ is maximized. It is known that these problems are highly inapproximable and do not admit any constant factor multiplicative approximation algorithms unless NP is easy. Known approximation algorithms involve datadependent approximation factors that are not efficiently computable. We initiate a study of the design of approximation algorithms where the approximation factors are efficiently computable. For the problem of \SCSKC, we prove that the greedy algorithm produces a solution whose value is at least $(11/e)f(\OPT)  A$, where $A$ is the datadependent additive error. For the \DiffC problem, we design an algorithm that uses the \SCSKC greedy algorithm as a subroutine. This algorithm produces a solution whose value is at least $(11/e)h(\OPT)B$, where $B$ is also a datadependent additive error. A salient feature of our approach is that the additive error terms can be computed efficiently, thus enabling us to ascertain the quality of the solutions produced.more » « less

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