Reconciliation k-median: Clustering with non-polarized representatives

Bruno Ordozgoiti, Aristides Gionis

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

3 Citations (Scopus)
222 Downloads (Pure)


We propose a new variant of the k-median problem, where the objective function models not only the cost of assigning data points to cluster representatives, but also a penalty term for disagreement among the representatives. We motivate this novel problem by applications where we are interested in clustering data while avoiding selecting representatives that are too far from each other. For example, we may want to summarize a set of news sources, but avoid selecting ideologically-extreme articles in order to reduce polarization. To solve the proposed k-median formulation we adopt the local-search algorithm of Arya et al. [2], We show that the algorithm provides a provable approximation guarantee, which becomes constant under a mild assumption on the minimum number of points for each cluster. We experimentally evaluate our problem formulation and proposed algorithm on datasets inspired by the motivating applications. In particular, we experiment with data extracted from Twitter, the US Congress voting records, and popular news sources. The results show that our objective can lead to choosing less polarized groups of representatives without significant loss in representation fidelity.

Original languageEnglish
Title of host publicationThe Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019
Number of pages11
ISBN (Electronic)9781450366748
Publication statusPublished - 13 May 2019
MoE publication typeA4 Conference publication
EventThe Web Conference - San Francisco, United States
Duration: 13 May 201917 May 2019


ConferenceThe Web Conference
Abbreviated titleWWW
Country/TerritoryUnited States
CitySan Francisco
Internet address


  • Approximation algorithms
  • Clustering
  • Committee selection
  • Data mining
  • K-median
  • Polarization


Dive into the research topics of 'Reconciliation k-median: Clustering with non-polarized representatives'. Together they form a unique fingerprint.
  • Active knowledge discovery in graphs

    Gionis, A., Aslay, C., Zhang, G., Ordozgoiti Rubio, B. & Xiao, H.


    Project: Academy of Finland: Other research funding

  • Adaptive and intelligent data

    Gionis, A., Ordozgoiti Rubio, B., Zhang, G. & Muniyappa, S.


    Project: Academy of Finland: Other research funding

  • Network structure from group response

    Xiao, H., Gionis, A., Garimella, K., Vitale, F., Parotsidis, N., Zhang, G., Rozenshtein, P., Galbrun, E., Tatti, N., Scepanovic, S., Matakos, A. & Muniyappa, S.


    Project: Academy of Finland: Other research funding

Cite this