In this paper we investigate phenomena of spontaneous emergence or purposeful formation of highly organized structures in networks of related agents. We show that the formation of large organized structures requires exponentially large, in the size of the structures, networks. Our approach is based on Kolmogorov, or descriptional, complexity of networks viewed as finite size strings. We apply this approach to the study of the emergence or formation of simple organized, hierarchical, structures based on Sierpinski Graphs and we prove a Ramsey type theorem that bounds the number of vertices in Kolmogorov random graphs that contain Sierpinski Graphs as subgraphs. Moreover, we show that Sierpinski Graphs encompass close-knit relationships among their vertices that facilitate fast spread and learning of information when agents in their vertices are engaged in pairwise interactions modelled as two person games. Finally, we generalize our findings for any organized structure with succinct representations. Our work can be deployed, in particular, to study problems related to the security of networks by identifying conditions which enable or forbid the formation of sufficiently large insider subnetworks with malicious common goal to overtake the network or cause disruption of its operation.
翻译:在本文中,我们研究了与相关智能体网络中高度有序结构的自发出现或有目的形成现象。我们证明了形成大型有序结构需要指数级的网络规模。我们的方法是基于将网络视为有限大小的字符串时的Kolmogorov(描述性)复杂度。我们将这种方法应用于对基于Sierpinski图的简单有序层次结构的出现或形成的研究,并证明了一个Ramsey类型的定理,它限制了包含Sierpinski图作为子图的Kolmogorov随机图中顶点数量的上限。此外,我们展示了Sierpinski图包含其顶点之间紧密联系的特性,在模拟成对交互建模为二人博弈的顶点中的智能体时,有益于快速传播和学习信息。最后,我们将我们的发现推广到任何简洁表示的有组织结构。我们的工作可在辨识使足够大的内部子网络形成、其共同目标是占领网络或导致其操作受到破坏的条件时进行部署,尤其适用于网络安全问题的研究。