2026-08-17T08:40:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8797 2024-03-06T10:42:40Z ddc:004 open_access

How long does it take for all users in a social network to choose their communities? Bermond, Jean-Claude Chaintreau, Augustin Ducoffe, Guillaume Mazauric, Dorian communities social networks integer partitions coloring games graphs We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (i.e., independent sets in the conflict graph G^- =(V,E) that represents the enmities between users). The dynamics goes on as long as there exists any set of at most k users, k being any fixed parameter, that can change their current groups in the partition simultaneously, in such a way that they all strictly increase their utilities (number of friends i.e., the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were O(|V|alpha(G^-)) for k <= 2 and O(|V|^3) for k=3, with alpha(G^-) being the independence number of G^-. Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for k <= 2 the tight upper-bound O(|V| min {alpha(G^-), sqrt{|V|}}) and, when G^- is the empty graph, the exact value of order ((2|V|)^{3/2})/3. The time of convergence, for any fixed k >= 4, was conjectured to be polynomial [Escoffier et al., 2012][Kleinberg and Ligett, 2013]. In this paper we disprove this. Specifically, we prove that for any k >= 4, the maximum time of convergence is an Omega(|V|^{Theta(log{|V|})}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jean-Claude Bermond and Augustin Chaintreau and Guillaume Ducoffe and Dorian Mazauric 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.6 urn:nbn:de:0030-drops-87972 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode