<  Back to the Polytechnique Montréal portal

A unifying framework for fairness-aware influence maximization

Golnoosh Farnadi, Behrouz Babaki and Michel Gendreau

Conference or Workshop Item - Paper (2020)

[img]
Preview
Published Version
Terms of Use: Creative Commons Attribution .
Download (1MB)
Cite this document: Farnadi, G., Babaki, B. & Gendreau, M. (2020, April). A unifying framework for fairness-aware influence maximization. Paper presented at WWW '20: The Web Conference 2020, Taipei, Taiwan. doi:10.1145/3366424.3383555
Show abstract Hide abstract

Abstract

The problem of selecting a subset of nodes with greatest influence in a graph, commonly known as influence maximization, has been well studied over the past decade. This problem has real world applications which can potentially affect lives of individuals. Algorithmic decision making in such domains raises concerns about their societal implications. One of these concerns, which surprisingly has only received limited attention so far, is algorithmic bias and fairness. We propose a flexible framework that extends and unifies the existing works in fairness-aware influence maximization. This framework is based on an integer programming formulation of the influence maximization problem. The fairness requirements are enforced by adding linear constraints or modifying the objective function. Contrary to the previous work which designs specific algorithms for each variant, we develop a formalism which is general enough for specifying different notions of fairness. A problem defined in this formalism can be then solved using efficient mixed integer programming solvers. The experimental evaluation indicates that our framework not only is general but also is competitive with existing algorithms.

Uncontrolled Keywords

Group Fairness; Influence Maximization; Mixed Integer Programming

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2713 Algorithmes
2700 Technologie de l'information > 2717 Études de modélisation et de simulation
Department: Département de génie informatique et génie logiciel
Research Center: Autre
Funders: Canada First Research Excellence Fund (CFREF), Calcul Québec, Compute Canada
Date Deposited: 22 Nov 2021 14:00
Last Modified: 23 Nov 2021 09:57
PolyPublie URL: https://publications.polymtl.ca/9245/
Document issued by the official publisher
Conference Title: WWW '20: The Web Conference 2020
Conference Location: Taipei, Taiwan
Conference Date(s): 2020-04-20 - 2020-04-24
Publisher: Association for Computing Machinery
Official URL: https://doi.org/10.1145/3366424.3383555

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only