Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.26579 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912860746022912 |
|---|---|
| author | Rui, Xiaobin Fang, Qiangpeng Peng, Chen Shi, Jilong Wang, Zhixiao Chen, Wei |
| author_facet | Rui, Xiaobin Fang, Qiangpeng Peng, Chen Shi, Jilong Wang, Zhixiao Chen, Wei |
| contents | Fair Influence Maximization (FIM) seeks to mitigate disparities in influence across different groups and has recently garnered increasing attention. A widely adopted notion of fairness in FIM is the maximin constraint, which directly requires maximizing the utility (influenced ratio within a group) of the worst-off group. Despite its intuitive formulation, designing efficient algorithms with strong theoretical guarantees remains challenging, as the maximin objective does not satisfy submodularity, a key property for designing approximate algorithms in traditional influence maximization settings. In this paper, we address this challenge by proposing a two-step optimization framework consisting of Inner-group Maximization (IGM) and Across-group Maximization (AGM). We first prove that the influence spread within any individual group remains submodular, enabling effective optimization within groups. Based on this, IGM applies a greedy approach to pick high-quality seeds for each group. In the second step, AGM coordinates seed selection across groups by introducing two strategies: Uniform Selection (US) and Greedy Selection (GS). We prove that AGM-GS holds a $(1-1/e-\varepsilon)$ approximation to the optimal solution when groups are completely disconnected, while AGM-US guarantees a roughly $\frac{1}{m}(1-1/e-\varepsilon)$ lower bound regardless of the group structure, with $m$ denoting the number of groups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26579 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint Rui, Xiaobin Fang, Qiangpeng Peng, Chen Shi, Jilong Wang, Zhixiao Chen, Wei Data Structures and Algorithms Fair Influence Maximization (FIM) seeks to mitigate disparities in influence across different groups and has recently garnered increasing attention. A widely adopted notion of fairness in FIM is the maximin constraint, which directly requires maximizing the utility (influenced ratio within a group) of the worst-off group. Despite its intuitive formulation, designing efficient algorithms with strong theoretical guarantees remains challenging, as the maximin objective does not satisfy submodularity, a key property for designing approximate algorithms in traditional influence maximization settings. In this paper, we address this challenge by proposing a two-step optimization framework consisting of Inner-group Maximization (IGM) and Across-group Maximization (AGM). We first prove that the influence spread within any individual group remains submodular, enabling effective optimization within groups. Based on this, IGM applies a greedy approach to pick high-quality seeds for each group. In the second step, AGM coordinates seed selection across groups by introducing two strategies: Uniform Selection (US) and Greedy Selection (GS). We prove that AGM-GS holds a $(1-1/e-\varepsilon)$ approximation to the optimal solution when groups are completely disconnected, while AGM-US guarantees a roughly $\frac{1}{m}(1-1/e-\varepsilon)$ lower bound regardless of the group structure, with $m$ denoting the number of groups. |
| title | Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.26579 |