TL;DR
This paper tackles the challenge of ensuring fair information spread in social networks, even when the spreading entity is purely efficiency-driven. They propose modifying the network structure by adding links to automatically enforce fairness, rather than relying on the spreader's good intentions. Their work introduces novel theoretical problems and practical algorithms, demonstrating that even a few added links can significantly improve fairness compared to existing methods.
What Problem Does This Paper Address?
Influence maximization (IM) in social networks aims to select a set of "seed" nodes to maximize the spread of information. A recent extension, fairness in IM, focuses on ensuring that different communities or groups within the network receive a fair share of the information. However, existing fairness-aware IM approaches typically assume that the entity spreading information wants to be fair. This paper argues this assumption is often unrealistic, as real-world agents are usually driven by efficiency (maximizing overall spread). The core problem addressed is: How can we make information spread automatically fair, even if the spreader only cares about maximizing reach? The authors propose to achieve this by strategically adding links to the network, thereby altering its structure to guide the spread towards fairness.
Methods
The paper introduces two main theoretical problems:
- FIMAL (Fair Influence Maximization by Adding Links): This problem aims to find a set of at most b new links to add to a network such that if an efficiency-driven entity then selects k seed nodes to maximize overall spread, the minimum community coverage is maximized. They analyze the computational complexity of FIMAL, showing it's generally hard to solve exactly or even approximate.
- FIMAAL (Fair Influence Maximization by Adding Links - Approximate): Recognizing the intractability of FIMAL, this problem shifts focus. Instead of assuming the spreader uses an optimal seed set, it assumes they use the greedy algorithm for influence maximization (a common and practical approach). The goal is to add at most b links to maximize the expected minimum community coverage when the greedy algorithm is used. This problem is shown to be polynomial-time approximable when b is a constant.
For practical solutions to FIMAAL, the authors propose several heuristic algorithms:
- grdy_al: A greedy approach that iteratively adds non-edges to improve the minimum community coverage.
- to_minC_infl: Adds non-edges that connect a potential seed node to a node in the currently least-covered community, considering edge weights and seed probabilities.
- to_minC_min: Focuses on adding edges to nodes that are least likely to be reached in the most under-covered community.
Datasets
The paper uses a combination of datasets for evaluation:
- Random Instances: Generated using the Barabasi-Albert model.
- Synthetic Instances: From Tsang et al. (2019).
- Real-World Instances: Similar to those used by Fish et al. (2019), including
ca-GrQc,ca-HepTh,email-Eu-core, andyoutube.
The authors also mention using different community structures for evaluation, including singleton communities, BFS-generated communities, and community structures provided with the synthetic/real-world datasets.
Key Insights and Ideas
- Shifting the Fairness Mechanism: The most significant insight is moving away from relying on the "goodwill" of information spreaders. By modifying the network structure itself, fairness becomes an emergent property of the system, even for purely self-interested agents.
- The Power of a Few Links: The experiments reveal that adding a surprisingly small number of links can dramatically improve fairness, often surpassing dedicated fairness-oriented seeding algorithms. This suggests that network structure is a powerful lever for achieving fairness.
- FIMAL vs. FIMAAL Trade-off: The theoretical analysis highlights a crucial trade-off. FIMAL (assuming optimal spreaders) is computationally intractable, while FIMAAL (assuming practical greedy spreaders) becomes more tractable, especially when the number of added links (b) is small. This distinction is vital for designing practical solutions.
- Greedy Algorithm's Role: The paper leverages the fact that the greedy algorithm for IM is widely used and theoretically well-founded. By making the network fair for the greedy algorithm, they achieve practical fairness improvements.
Key Results
- Theoretical Hardness: The decision version of FIMAL is proven to be $\Sigma_2$-hard, even in deterministic cases and when b or k are small. Approximating FIMAL is also shown to be NP-hard.
- Approximability for Constant b: FIMAAL (with greedy spreaders) is polynomial-time $\epsilon$-approximable when b is a constant.
- Heuristic Performance: In experiments, the
to_minC_inflheuristic consistently performed well, achieving better fairness than other proposed heuristics and baseline methods. - Significant Fairness Gains: Adding as few as 50 links to real-world networks resulted in fairness levels comparable to or even better than existing ex-ante fairness-optimized algorithms, and significantly better than ex-post fairness algorithms. This was observed even when the added links were chosen by simple heuristics.
Limitations and Future Work
- Computational Complexity: While FIMAAL is approximable for constant b, the general problem remains hard. The theoretical hardness results for FIMAL suggest that finding optimal solutions is likely infeasible for large networks.
- Heuristic Nature: The practical algorithms for FIMAAL are heuristics. While they show strong empirical performance, theoretical guarantees for their optimality are limited.
- Future Work: The authors suggest exploring fairness with multiple implementations of the greedy algorithm or even multiple different algorithms. They also point to the potential for extending their approach to other diffusion models beyond the Independent Cascade model. The paper also hints at the possibility of using other network modification techniques besides adding links.
Summary updated