Search

Abstract Existing works on influence maximization (IM) aim at finding influential online users as seed nodes. Originated from these seed nodes, large online influence spread can be triggered. However, such user-driven perspective limits the IM problem within the purely online environment. Due to the increasing interactions between the cyber world and the physical world, offline events in real world are showing more impact on online information spread. Most IM methods are totally unaware of the cyber–physical interactions and thus their effectiveness is limited when offline events are taken into account. To address this issue, in this paper we consider influence maximization from an online–offline interactive setting and propose the location-driven influence maximization (LDIM) problem. The LDIM problem aims to find the optimal offline deployment of locations and durations to hold events, so as to maximize the online influence spread. We propose a location-driven propagation (LDP) model to describe the online influence spread process triggered by offline events. Under the LDP model, we prove the LDIM problem is NP-hard and computing the objective function is #P-hard. Thus we develop a greedy algorithm over integer lattice and prove its 1 − 1 ∕ e approximation. To overcome the expensive time complexity, we further develop two algorithms with time complexity reduced successively while ensuring provable approximation ratios of 1 − 1 ∕ e − ε and 1 − 1 ∕ e − ε − ε ′ respectively. Experimental results on real datasets show the effectiveness of the proposed algorithms and the significant improvement on scalability. [ABSTRACT FROM AUTHOR]

Influence maximization (IM) in social media aims at finding influential seed users to trigger large online cascading influence spread. Existing studies mainly focus on maximizing the number of the activated nodes, but the diversity of the activated nodes has been mostly ignored even though it is crucial in many real-world applications, e.g., diversity of the influenced crowd can reduce the risk of marketing campaigns, or diversity of recommended items can improve the recommendation quality. In this paper, we study the diversified influence maximization (DIM) problem which aims to select k nodes such that both the number of activated nodes and the diversity of the activated nodes can be maximized. By designing a practical diversity function to model the distribution of activated nodes among all communities, we model the DIM problem by maximizing a parameterized linear combination of the diversity and the active node number. To tackle the NP-hardness of the DIM problem, we propose an efficient diversified influence maximization algorithm, diversified influence maximization via martingale (DIMM), which returns a 1 − 1 ∕ e − ε -approximate solution with at least 1 − 2 ∕ n ℓ probability. Moreover, as the influence spread is highly stochastic and the DIM setting leaves no reserved measures for handling unforeseen events, we present an improved version of the algorithm named adaptive diversified influence maximization via martingale (ADIMM) with the adaptive setting. With the adaptive RI- π α policy, ADIMM is able to return an α (1 − e − 1 ∕ α) -approximate solution with at least 1 − 1 ∕ n ℓ probability. Finally, we experimentally evaluate our algorithm against existing algorithms on large-scale real-world datasets. The experimental results validate the effectiveness and efficiency of our proposed algorithms. [ABSTRACT FROM AUTHOR]

The gradient-based meta learning and its approximation algorithms have been widely used in the few-shot scenarios. In practice, it is common for the trained meta-model to employ uniform settings for gradient descent steps across different tasks. However, the meta-model may be biased toward some tasks. The convergence issue occurs that some tasks may see convergence in a few steps while others fail to approach the optimum in the whole inner loop. The bias problem may cause the trained meta-model works well in some tasks but has unexpected bad performance in other tasks, which hurts the generality of the meta-model. To address this issue, in this paper, we formally establish the approximation between the metric-based strategy and gradient descent in meta-test. By directly calculating similarity to classify data, the trained meta-model avoids the convergence issue. We point out that the metric-based methods can closely approximate the gradient descent in meta-test if the representation capability of the derived features and the convergence of the inner loop during meta-training are guaranteed. Based on such observation, we propose a new meta-learning model GMT2 (Gradient-based Meta-Train with Metric-based meta-Test) by combining gradient descent in meta-training with metric-based methods in meta-test. GMT2 employs a new first-order approximation scheme using the adversarial update strategy which not only enhances the feature representation of inner layers, but also allows enough inner gradient steps without calculating second-order derivatives. Experiments show that GMT2 achieves better efficiency and competitive accuracy comparing with popular meta-learning models. [ABSTRACT FROM AUTHOR]