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: https://drops.dagstuhl.de/opus/volltexte/2018/8797/
Go to the corresponding LIPIcs Volume Portal


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?

pdf-format:
LIPIcs-FUN-2018-6.pdf (0.7 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI