Details

Autor(en) / Beteiligte

• Guo, Jianxiong
• Ni, Qiufen
• Wu, Weili
• Du, Ding-Zhu

Titel

Composite Community-Aware Diversified Influence Maximization With Efficient Approximation

Ist Teil von

• IEEE/ACM transactions on networking, 2024-04, Vol.32 (2), p.1-16

Ort / Verlag

New York: IEEE

Erscheinungsjahr

2024

Quelle

IEEE Electronic Library Online

Beschreibungen/Notizen

• Influence Maximization (IM) is a well-known topic in mobile networks and social computing that aims to find a small subset of users that maximize the influence spread through an online information cascade. Recently, some cautious researchers have paid attention to the diversity of information dissemination, especially community-aware diversity, and formulated the diversified IM problem. Diversity is ubiquitous in many real-world applications, but these applications are all based on a given community structure. In social networks, we can form heterogeneous community structures for the same group of users according to different metrics. Therefore, how to quantify diversity based on multiple community structures is an interesting question. In this paper, we propose a Composite Community-Aware Diversified IM (CC-DIM) problem, which aims to select a seed set to maximize the influence spread and the composite diversity over all possible community structures under consideration. To address the NP-hardness of the CC-DIM problem, we adopt the technique of reverse influence sampling and design a random Generalized Reverse Reachable (G-RR) set to estimate the objective function. The composition of a random G-RR set is much more complex than the RR set used for the IM problem, which will lead to the inefficiency of traditional sampling-based approximation algorithms. Because of this, we further propose a two-stage algorithm, Generalized HIST (G-HIST). It can not only return a <inline-formula> <tex-math notation="LaTeX">(1-1/e-\varepsilon)</tex-math> </inline-formula> approximate solution with at least <inline-formula> <tex-math notation="LaTeX">(1-\delta)</tex-math> </inline-formula> probability but also improve the efficiency of sampling and ease the difficulty of searching by significantly reducing the average size of G-RR sets. Finally, we evaluate our proposed G-HIST on real datasets against existing algorithms. The experimental results show the effectiveness of our proposed algorithm and its superiority over other baseline algorithms.