Fair dense subgraph discovery: algorithms and analysis

Abstract Recent years have seen a great deal of effort in the area of developing fair machine learning algorithms. The definition of ‘fair’ varies, but often, the focus is along the lines of ensuring that algorithms do not systematically discriminate against individuals on the basis of their protected attributes -e.g., those describing race or gender. However, although there are numerous important network applications, comparatively little attention has been paid to fairness in network algorithms. Here, we focus on the problem of fair dense subgraph discovery in networks. Dense subgraph discovery is often used as a first step in applications like community detection or influence maximization. However, as we show, unfairness in the structure of the dense subgraphs may propagate to those downstream applications, magnifying any unfairness in those subsequent algorithmic processes. We propose properties by which one may quantify the fairness of a subgraph, introduce algorithms connected to these fairness objectives, analyze the properties of the resulting subgraphs, and demonstrate their use with respect to applications.