On the Existence of Consensus Converging Organized Groups in Large Social Networks

In this paper we investigate the emergence of highly organized communities in graphs modeling social networks and interactions among their members. We show that the formation of large organized communities requires exponentially large social networks. Our approach is based on Kolmogorov complexity of graphs represented as finite size strings of bits. We apply this approach to the problem of existence of organized communities which have the structure of the Zig-Zag class of graphs, with information diffusion properties. We provide a lower bound for the number of nodes a social network must have to allow the formation of a large Zig-Zag like community and conditions upon which a large Zig-Zag graph can be located in sufficiently large social networks by providing a randomized linear algorithm which locates this structure.