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|})}).