License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.6
URN: urn:nbn:de:0030-drops-87972
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8797/
Bermond, Jean-Claude ;
Chaintreau, Augustin ;
Ducoffe, Guillaume ;
Mazauric, Dorian
How long does it take for all users in a social network to choose their communities?
Abstract
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|})}).
BibTeX - Entry
@InProceedings{bermond_et_al:LIPIcs:2018:8797,
author = {Jean-Claude Bermond and Augustin Chaintreau and Guillaume Ducoffe and Dorian Mazauric},
title = {{How long does it take for all users in a social network to choose their communitiesl}},
booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)},
pages = {6:1--6:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-067-5},
ISSN = {1868-8969},
year = {2018},
volume = {100},
editor = {Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8797},
URN = {urn:nbn:de:0030-drops-87972},
doi = {10.4230/LIPIcs.FUN.2018.6},
annote = {Keywords: communities, social networks, integer partitions, coloring games, graphs}
}
|
Keywords: |
|
communities, social networks, integer partitions, coloring games, graphs |
|
Collection: |
|
9th International Conference on Fun with Algorithms (FUN 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
