Maximizing fair content spread via edge suggestion in social networks

IP Swift, S Ebrahimi, A Nova, A Asudeh - arXiv preprint arXiv:2207.07704, 2022 - arxiv.org
arXiv preprint arXiv:2207.07704, 2022arxiv.org
Content spread inequity is a potential unfairness issue in online social networks, disparately
impacting minority groups. In this paper, we view friendship suggestion, a common feature in
social network platforms, as an opportunity to achieve an equitable spread of content. In
particular, we propose to suggest a subset of potential edges (currently not existing in the
network but likely to be accepted) that maximizes content spread while achieving fairness.
Instead of re-engineering the existing systems, our proposal builds a fairness wrapper on …
Content spread inequity is a potential unfairness issue in online social networks, disparately impacting minority groups. In this paper, we view friendship suggestion, a common feature in social network platforms, as an opportunity to achieve an equitable spread of content. In particular, we propose to suggest a subset of potential edges (currently not existing in the network but likely to be accepted) that maximizes content spread while achieving fairness. Instead of re-engineering the existing systems, our proposal builds a fairness wrapper on top of the existing friendship suggestion components. We prove the problem is NP-hard and inapproximable in polynomial time unless P = NP. Therefore, allowing relaxation of the fairness constraint, we propose an algorithm based on LP-relaxation and randomized rounding with fixed approximation ratios on fairness and content spread. We provide multiple optimizations, further improving the performance of our algorithm in practice. Besides, we propose a scalable algorithm that dynamically adds subsets of nodes, chosen via iterative sampling, and solves smaller problems corresponding to these nodes. Besides theoretical analysis, we conduct comprehensive experiments on real and synthetic data sets. Across different settings, our algorithms found solutions with nearzero unfairness while significantly increasing the content spread. Our scalable algorithm could process a graph with half a million nodes on a single machine, reducing the unfairness to around 0.0004 while lifting content spread by 43%.
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果