Fair dense subgraph discovery: algorithms and analysis
Authors:
- Danylo HoncharovDHDanylo Honcharov
- Sucheta SoundarajanSSSucheta Soundarajan
Open Access
- 24 December 2025
- journal article
- Published by Springer Nature in Social Network Analysis and Mining
- Vol. 16 (1)
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.Keywords
Funding Information
- NSF (1908048)
- NSF (1908048)
This publication has 23 references indexed in Scilit:
- K-Core Based Temporal Graph Convolutional Network for Dynamic GraphsIEEE Transactions on Knowledge and Data Engineering, 2020
- Evaluating User Influence in Social Networks Using k-core2020
- A K-shell Decomposition Based Algorithm for Influence Maximization2015
- Identifying the node spreading influence with largest k -core valuesPhysics Letters A, 2014
- Measuring segregation in social networksSocial Networks, 2014
- Adaptive methods for the computation of PageRankLinear Algebra and its Applications, 2004
- Mixing patterns in networksPhysical Review E, 2003
- Greedy Approximation Algorithms for Finding Dense Components in a Graph2000
- Network structure and minimum degreeSocial Networks, 1983
- Gaussian elimination is not optimalNumerische Mathematik, 1969