Fairness in influence maximization has been a very active research topic recently. Most works in this context study the question of how to find seeding strategies (deterministic or probabilistic) such that nodes or communities in the network get their fair share of coverage. Different fairness criteria have been used in this context. All these works assume that the entity that is spreading the information has an inherent interest in spreading the information fairly, otherwise why would they want to use the developed fair algorithms? This assumption may however be flawed in reality -- the spreading entity may be purely \emph{efficiency-oriented}. In this paper we propose to study two optimization problems with the goal to modify the network structure by adding links in such a way that efficiency-oriented information spreading becomes \emph{automatically fair}. We study the proposed optimization problems both from a theoretical and experimental perspective, that is, we give several hardness and hardness of approximation results, provide efficient algorithms for some special cases, and more importantly provide heuristics for solving one of the problems in practice. In our experimental study we then first compare the proposed heuristics against each other and establish the most successful one. In a second experiment, we then show that our approach can be very successful in practice. That is, we show that already after adding a few edges to the networks the greedy algorithm that purely maximizes spread surpasses all fairness-tailored algorithms in terms of ex-post fairness. Maybe surprisingly, we even show that our approach achieves ex-post fairness values that are comparable or even better than the ex-ante fairness values of the currently most efficient algorithms that optimize ex-ante fairness.
翻译:影响最大化的公平性是最近一个非常积极的研究课题。 多数在本文中研究如何找到种子战略( 确定性或概率性), 使网络中的节点或社区获得公平的覆盖比例。 不同的公平标准在此背景下被使用。 所有这些工作都假设传播信息的实体对公平传播信息有着内在的兴趣, 否则他们为什么想要使用发达的公平算法? 然而,这种假设在现实中可能是有缺陷的 -- 扩张实体可能纯粹是公平性或效率导向性。 在本文中,我们提议研究两个优化问题,以改变网络结构的目标为优化,方法是增加链接,使面向效率的信息传播成为外部公平。 我们从理论和实验的角度来研究拟议的优化问题,就是说,我们给某些特殊案例提供有效的算法,更重要的是,为解决实际中的问题提供超文本性的方法。 在我们的实验研究中,我们首先比较了两个目标的优化问题,即改变网络结构,使面向前端的信息传播变得公平性成为了一种成功的。 也就是说,我们从理论上看, 最接近的算法可以显示, 最成功的是, 最成功的算法是,我们后来的比前端的更成功的是更成功的。</s>