Reconciliation k-median

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorOrdozgoiti, Brunoen_US
dc.contributor.authorGionis, Aristidesen_US
dc.contributor.departmentTechnical University of Madriden_US
dc.contributor.departmentHelsinki Institute for Information Technology (HIIT)en_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.date.accessioned2019-07-30T07:18:41Z
dc.date.available2019-07-30T07:18:41Z
dc.date.issued2019-05-13en_US
dc.description| openaire: EC/H2020/654024/EU//SoBigData
dc.description.abstractWe 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.en
dc.description.versionPeer revieweden
dc.format.extent11
dc.format.extent1387-1397
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationOrdozgoiti , B & Gionis , A 2019 , Reconciliation k-median : Clustering with non-polarized representatives . in The Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019 . ACM , pp. 1387-1397 , The Web Conference , San Francisco , California , United States , 13/05/2019 . https://doi.org/10.1145/3308558.3313475en
dc.identifier.doi10.1145/3308558.3313475en_US
dc.identifier.isbn9781450366748
dc.identifier.otherPURE UUID: 9c3ed082-9557-41b2-b4c6-dc9a59a7c448en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/9c3ed082-9557-41b2-b4c6-dc9a59a7c448en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85066881161&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/35173766/p1387_ordozgoiti.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/39472
dc.identifier.urnURN:NBN:fi:aalto-201907304527
dc.language.isoenen
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/654024/EU//SoBigDataen_US
dc.relation.ispartofThe Web Conferenceen
dc.relation.ispartofseriesThe Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019en
dc.rightsopenAccessen
dc.subject.keywordApproximation algorithmsen_US
dc.subject.keywordClusteringen_US
dc.subject.keywordCommittee selectionen_US
dc.subject.keywordData miningen_US
dc.subject.keywordK-medianen_US
dc.subject.keywordPolarizationen_US
dc.titleReconciliation k-medianen
dc.typeConference article in proceedingsfi
dc.type.versionpublishedVersion
Files