Fairness-Aware PageRank
Fairness-Aware PageRank
复制标题
公平感知 PageRank
DOI：
10.1145/3442381.3450065
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
N. Mamoulis
中科院分区：
文献类型：
--
作者：
Sotiris Tsioutsiouliklis;E. Pitoura;Panayiotis Tsaparas;Ilias Kleftakis;N. Mamoulis
算法公平性在过去几年里引起了人们的极大关注。在本文中，我们考虑链接分析的公平性，特别是著名的Pagerank算法。假设网络中的节点属于组（例如，基于人口统计或其他特征），我们提供了基于对等的公平性定义，该定义对分配给每个组成员的Pagerank比例施加了约束。我们提出了两类公平的Pagerank算法：第一类（公平敏感型Pagerank）通过修改Pagerank算法的跳转向量来增强公平性；第二种（本地公平Pagerank）对每个节点施加公平的行为。然后，我们定义了一个更强的公平性要求，称为通用个性化公平性，它要求所有节点的派生个性化页面排名都是公平的。我们证明了局部公平算法也实现了普遍的个性化公平，并进一步证明了这是唯一具有这种性质的算法族，从而建立了普遍个性化公平与局部公平之间的等价关系。我们还考虑了实现公平性的问题，同时最小化相对于原始Pagerank算法的效用损失。我们展示了真实和合成网络的实验，这些实验检查了原始Pagerank的公平性，并定性和定量地展示了我们算法的特性。
Algorithmic fairness has attracted significant attention in the past years. In this paper, we consider fairness for link analysis and in particular for the celebrated Pagerank algorithm. Given that the nodes in a network belong to groups (for example, based on demographic or other characteristics), we provide a parity-based definition of fairness that imposes constraints on the proportion of Pagerank allocated to the members of each group. We propose two families of fair Pagerank algorithms: the first (Fairness-Sensitive Pagerank) modifies the jump vector of the Pagerank algorithm to enforce fairness; the second (Locally Fair Pagerank) imposes a fair behavior per node. We then define a stronger fairness requirement, termed universal personalized fairness, that asks that the derived personalized pageranks of all nodes are fair. We prove that the locally fair algorithms achieve also universal personalized fairness, and furthermore, we prove that this is the only family of algorithms with this property, establishing an equivalence between universal personalized fairness and local fairness. We also consider the problem of achieving fairness while minimizing the utility loss with respect to the original Pagerank algorithm. We present experiments with real and synthetic networks that examine the fairness of the original Pagerank and demonstrate qualitatively and quantitatively the properties of our algorithms.
DOI：
10.1609/aaai.v34i01.5429
发表时间：
2020-04
期刊：
--
影响因子：
--
作者：
Farzan Masrour;T. Wilson;Heng Yan;P. Tan;A. Esfahanian
通讯作者：
Farzan Masrour;T. Wilson;Heng Yan;P. Tan;A. Esfahanian