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

This paper studies the dynamics of formation of groups in social networks. In a friendship graph \(G^+\), the vertices are the users and an edge represents a friendship relation. The complementary graph is called the conflict graph and denoted by \(G^-\). Let \(L(k,G^-)\) be the size of a longest sequence of \(k\)-deviations on a conflict graph \(G^-\). The maximum value is denoted by \(L(k,n)\) of \(L(k,G^-)\) over all the graphs with \(n\) vertices. Let \(m\) and \(r\) be the unique non-negative integers such that \(n=\frac{m(m+1)}{2}+r\) and \(0\le r\le m\). It is shown \(L(1,n)=2\frac{m+1}{3}+mr\). Moreover, \(L(2,n)=L(1,n)\). For \(n=\frac{m+1}{2}\), there exist a conflict graph \(G^-\) with \(\alpha(G^-)=m=\Theta(\sqrt{n})\) and a sequence of \(\frac{m+1}{3}\) valid 1-deviations, namely, a sequence of \(\Omega(n^{3/2})=\Omega(n\alpha(G^-))\) 1-deviations.