<  Back to the Polytechnique Montréal portal

A unifying framework for fairness-aware influence maximization

Golnoosh Farnadi, Behrouz Babaki and Michel Gendreau

Paper (2020)

Open Acess document in PolyPublie and at official publisher
[img]
Preview
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution
Download (348kB)
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

Subjects: 2700 Information technology > 2700 Information technology
2700 Information technology > 2713 Algorithms
2700 Information technology > 2717 Modelling and simulation studies
Department: Department of Computer Engineering and Software Engineering
Research Center: Other
Funders: Canada First Research Excellence Fund (CFREF), Calcul Québec, Compute Canada
PolyPublie URL: https://publications.polymtl.ca/9245/
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
DOI: 10.1145/3366424.3383555
Official URL: https://doi.org/10.1145/3366424.3383555
Date Deposited: 22 Nov 2021 14:00
Last Modified: 06 Apr 2024 06:21
Cite in APA 7: Farnadi, G., Babaki, B., & Gendreau, M. (2020, April). A unifying framework for fairness-aware influence maximization [Paper]. WWW '20: The Web Conference 2020, Taipei, Taiwan. https://doi.org/10.1145/3366424.3383555

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only

View Item View Item