How long does it take for all users in a social network to choose their communities? - Archive ouverte HAL Access content directly
Journal Articles Discrete Applied Mathematics Year : 2019

How long does it take for all users in a social network to choose their communities?

(1) , (2) , (3) , (4)
1
2
3
4

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 in $\Omega(|V|^{\Theta(\log{|V|})})$.
Fichier principal
Vignette du fichier
no-format-01-08-19.pdf (591.6 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02264327 , version 1 (06-08-2019)

Identifiers

Cite

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?. Discrete Applied Mathematics, 2019, 270, pp.37-57. ⟨10.1016/j.dam.2019.07.023⟩. ⟨hal-02264327⟩
90 View
164 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More