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 $\leq 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 \leq 2$ the tight upper-bound $O(|V| \min\{ \alpha(G^-)$, $\sqrt{|V|} \})$ and, when $G^-$ is the empty graph, the exact value of order $\frac{(2|V|)^{3/2}}{3}$. The time of convergence, for any fixed k \geq 4, was conjectured to be polynomial. In this paper we disprove this. Specifically, we prove that for any k \geq 4, the maximum time of convergence is an $\Omega(|V|^{\Theta(\log{|V|})})$.
Type de document :
Communication dans un congrès
9th International Conference on Fun with Algorithms (FUN 2018), 2018, La Maddalena, Italy
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01780627
Contributeur : Dorian Mazauric <>
Soumis le : vendredi 27 avril 2018 - 16:57:30
Dernière modification le : mardi 1 mai 2018 - 01:22:44

Fichier

article-funrapport.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01780627, version 1

Collections

Citation

Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, Dorian Mazauric. How long does it take for all users in a social network to choose their communities?. 9th International Conference on Fun with Algorithms (FUN 2018), 2018, La Maddalena, Italy. 〈hal-01780627〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

53