An official website of the United States government
We consider the problem of Influence Maximization (IM), the task of selecting k seed nodes in a social network such that the expected number of nodes influenced is maximized. We propose a community-aware divide-and-conquer framework that involves (i) learning the inherent community structure of the social network, (ii) generating candidate solutions by solving the influence maximization problem for each community, and (iii ) selecting the final set of seed nodes using a novel progressiv e budgeting scheme. Our experiments on real-world social networks show that the proposed framework outperforms the standard methods in terms of run-time and the heuristic methods in terms of influence. We also study the effect of the community structure on the performance of the proposed framework. Our experiments sho w that the community structures with higher modularity lead the proposed framework to perform better in terms of run-time an d influence.
more »
« less
Approximate Expected Utility Rationalization
Abstract We propose a new measure of deviations from expected utility theory. For any positive number e, we give a characterization of the datasets with a rationalization that is within e (in beliefs, utility, or perceived prices) of expected utility (EU) theory, under the assumption of risk aversion. The number e can then be used as a measure of how far the data is to EU theory. We apply our methodology to data from three large-scale experiments. Many subjects in these experiments are consistent with utility maximization, but not with EU maximization. Our measure of distance to expected utility is correlated with the subjects’ demographic characteristics.
more »
« less
- Award ID(s):
- 1919263
- PAR ID:
- 10468380
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- Journal of the European Economic Association
- Volume:
- 21
- Issue:
- 5
- ISSN:
- 1542-4766
- Format(s):
- Medium: X Size: p. 1821-1864
- Size(s):
- p. 1821-1864
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Engineering design involves information acquisition decisions such as selecting designs in the design space for testing, selecting information sources, and deciding when to stop design exploration. Existing literature has established normative models for these decisions, but there is lack of knowledge about how human designers make these decisions and which strategies they use. This knowledge is important for accurately modeling design decisions, identifying sources of inefficiencies, and improving the design process. Therefore, the primary objective in this study is to identify models that provide the best description of a designer’s information acquisition decisions when multiple information sources are present and the total budget is limited. We conduct a controlled human subject experiment with two independent variables: the amount of fixed budget and the monetary incentive proportional to the saved budget. By using the experimental observations, we perform Bayesian model comparison on various simple heuristic models and expected utility (EU)-based models. As expected, the subjects’ decisions are better represented by the heuristic models than the EU-based models. While the EU-based models result in better net payoff, the heuristic models used by the subjects generate better design performance. The net payoff using heuristic models is closer to the EU-based models in experimental treatments where the budget is low and there is incentive for saving the budget. This indicates the potential for nudging designers’ decisions toward maximizing the net payoff by setting the fixed budget at low values and providing monetary incentives proportional to saved budget.more » « less
-
Abstract We propose a model-based clustering method for high-dimensional longitudinal data via regularization in this paper. This study was motivated by the Trial of Activity in Adolescent Girls (TAAG), which aimed to examine multilevel factors related to the change of physical activity by following up a cohort of 783 girls over 10 years from adolescence to early adulthood. Our goal is to identify the intrinsic grouping of subjects with similar patterns of physical activity trajectories and the most relevant predictors within each group. The previous analyses conducted clustering and variable selection in two steps, while our new method can perform the tasks simultaneously. Within each cluster, a linear mixed-effects model (LMM) is fitted with a doubly penalized likelihood to induce sparsity for parameter estimation and effect selection. The large-sample joint properties are established, allowing the dimensions of both fixed and random effects to increase at an exponential rate of the sample size, with a general class of penalty functions. Assuming subjects are drawn from a Gaussian mixture distribution, model effects and cluster labels are estimated via a coordinate descent algorithm nested inside the Expectation-Maximization (EM) algorithm. Bayesian Information Criterion (BIC) is used to determine the optimal number of clusters and the values of tuning parameters. Our numerical studies show that the new method has satisfactory performance and is able to accommodate complex data with multilevel and/or longitudinal effects.more » « less
-
Abstract Neutron star mergers (NSMs) producer-process elements after a time-delayed inspiral process. Once a significant number of NSMs are present in a galaxy,r-process elements, such as Eu, are expected to significantly increase with time. Yet, there have been limited observational data in support of Eu increasing within Local Group galaxies. We have obtained high-resolution Magellan/MIKE observations of 43 metal-poor stars in the Gaia-Sausage/Enceladus (GSE) tidally disrupted galaxy with −2.5 < [Fe/H] < −1. For the first time, we find a clear rise in [Eu/Mg] with increasing [Mg/H] within one galaxy. We use a simple chemical evolution model to study how such a rise can result from the interplay of prompt and delayedr-process enrichment events. Delayedr-process sources are required to explain the rise and subsequent leveling off of [Eu/Mg] in this disrupted galaxy. However, the rise may be explained by delayedr-process sources with either short (∼10 Myr) or long (∼500 Myr) minimum delay times. Future studies on the nature ofr-process sources and their enrichment processes in the GSE will require additional stars in the GSE at even lower metallicities than the present study.more » « less
-
In many real-world applications such as social network analysis and online advertising/marketing, one of the most important and popular problems is called influence maximization (IM), which finds a set of k seed users that maximize the expected number of influenced user nodes. In practice, however, maximizing the number of influenced nodes may be far from satisfactory for real applications such as opinion promotion and collective buying. In this paper, we explore the importance of stability and triangles in social networks, and formulate a novel problem in the influence spread scenario, named triangular stability maximization , over social networks, and generalize it to a general triangle influence maximization problem, which is proved to be NP-hard. We develop an efficient reverse influence sampling (RIS) based framework for the triangle IM with theoretical guarantees. To enable unbiased estimators, it demands probabilistic sampling of triangles, that is, sampling triangles according to their probabilities. We propose an edge-based triple sampling approach, which is exactly equivalent to probabilistic sampling and avoids costly triangle enumeration and materialization. We also design several pruning and reduction techniques, as well as a cost-model-guided heuristic algorithm. Extensive experiments and a case study over real-world graphs confirm the effectiveness of our proposed algorithms and the superiority of triangular stability maximization and triangle influence maximization.more » « less
