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图包含其顶点之间紧密联系的特性,在模拟成对交互建模为二人博弈的顶点中的智能体时,有益于快速传播和学习信息。最后,我们将我们的发现推广到任何简洁表示的有组织结构。我们的工作可在辨识使足够大的内部子网络形成、其共同目标是占领网络或导致其操作受到破坏的条件时进行部署,尤其适用于网络安全问题的研究。

0
下载
关闭预览

相关内容

数据科学导论,54页ppt,Introduction to Data Science
专知会员服务
41+阅读 · 2020年7月27日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
可达鸭为什么这么火?
ZEALER订阅号
0+阅读 · 2022年5月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
82+阅读 · 2022年7月16日
VIP会员
相关VIP内容
数据科学导论,54页ppt,Introduction to Data Science
专知会员服务
41+阅读 · 2020年7月27日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
相关资讯
可达鸭为什么这么火?
ZEALER订阅号
0+阅读 · 2022年5月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
相关基金
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员