Densest Diverse Subgraphs: How to Plan a Successful Cocktail Party with Diversity

Abstract

Dense subgraph discovery methods are routinely used in a variety of applications including the identification of a team of skilled individuals for collaboration from a social network. However, when the network's node set is associated with a sensitive attribute such as race, gender, religion, or political opinion, the lack of diversity can lead to lawsuits. In this work, we focus on the problem of finding a densest diverse subgraph in a graph whose nodes have different attribute values/types that we refer to as colors. We propose two novel formulations motivated by different realistic scenarios. Our first formulation, called the densest diverse subgraph problem (DDSP), guarantees that no color represents more than some fraction of the nodes in the output subgraph, which generalizes the state-of-the-art due to Anagnostopoulos et al. (CIKM 2020). By varying the fraction we can range the diversity constraint and interpolate from a diverse dense subgraph where all colors have to be equally represented to an unconstrained dense subgraph. We design a scalable $\Omega (1/\sqrt{n})$-approximation algorithm, where $n$ is the number of nodes. Our second formulation is motivated by the setting where any specified color should not be overlooked. We propose the densest at-least-$\vec{k}$-subgraph problem (Dal$\vec{k}$S), a novel generalization of the classic Dal$k$S, where instead of a single value $k$, we have a vector $\mathbf{k}$ of cardinality demands with one coordinate per color class. We design a $1/3$-approximation algorithm using linear programming together with an acceleration technique. Computational experiments using synthetic and real-world datasets demonstrate that our proposed algorithms are effective in extracting dense diverse clusters.

arXiv commentAccepted to KDD 2023

References in corpus (12)

• DeepWalk: Online Learning of Social Representations
• Social Structure of Facebook Networks
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• Learning and Forecasting Opinion Dynamics in Social Networks
• A Survey on the Densest Subgraph Problem and Its Variants
• The Densest Subgraph Problem with a Convex/Concave Size Function
• Information content of colored motifs in complex networks
• Fair Hierarchical Clustering
• Node Embeddings and Exact Low-Rank Representations of Complex Networks
• Parallelizing the dual revised simplex method
• Online Dense Subgraph Discovery via Blurred-Graph Feedback
• On the Power of Edge Independent Graph Models

Cited by in corpus (2)

• A Survey on the Densest Subgraph Problem and Its Variants
• Fair densest subgraph across multiple graphs