Motivated by biological processes, we introduce here the model of growing graphs, a new model of highly dynamic networks. Such networks have as nodes entities that can self-replicate and thus can expand the size of the network. This gives rise to the problem of creating a target network $G$ starting from a single entity (node). To properly model this, we assume that every node $u$ can generate at most one node $v$ at every round (or time slot), and every generated node $v$ can activate edges with other nodes only at the time of its birth, provided that these nodes are up to a small distance $d$ away from $v$. We show that the most interesting case is when the distance is $d=2$. Edge deletions are allowed at any time slot. This creates a natural balance between how fast (time) and how efficiently (number of deleted edges) a target network can be generated. A central question here is, given a target network $G$ of $n$ nodes, can $G$ be constructed in the model of growing graphs in at most $k$ time slots and with at most $\ell$ excess edges (i.e., auxiliary edges $\notin E(G)$ that are activated and later deleted)? We consider here both centralized and distributed algorithms for such questions (and also their computational complexity). Our results include lower bounds based on properties of the target network and algorithms for general graph classes that try to balance speed and efficiency. We then show that the optimal number of time slots to construct an input target graph with zero-waste (i.e., no edge deletions allowed), is hard even to approximate within $n^{1-\varepsilon}$, for any $\varepsilon>0$, unless P=NP. On the contrary, the question of the feasibility of constructing a given target graph in $\log n$ time slots and zero-waste, can be answered in polynomial time. Finally, we initiate a discussion on possible extensions for this model for a distributed setting.


翻译:由生物进程驱动, 我们在此引入了增长图形模型, 这是一种高动态网络的新模式。 这些网络作为节点实体, 可以自我复制, 从而可以扩大网络的大小。 这就产生了创建目标网络的问题 $G$, 从单个实体( 节点) 开始 。 为了正确模拟这一点, 我们假设每个节点$可以在每个回合( 或时空) 产生最多一个节点美元 。 每个节点 $v$ 的节点只有在诞生时才能激活其它节点的边缘 。 只要这些节点在离 $V$ 的短距离内, 节点的节点是 美元 。 我们显示最有趣的情况是当距离是 $=2$。 Edge的删除可以在任何时间档中创建目标网络的快速( 时间) 和 效率( 被删除的边缘数) 之间自然平衡。 鉴于目标网络以美元为基点, 以美元为节点的节点, 只要这些节点的节点为美元 。 节点的节点可以建成一个模型, 美元, 美元, 以正点的节点的节点的节点的节点的节点在最 美元 美元 的节点上, 。 。 平的节点的节点中, 将显示的节点的节点的节点的节点的节点的节点的节点的节点 。 。 。 。 。 将显示的节点的节点 。

0
下载
关闭预览

相关内容

专知会员服务
84+阅读 · 2020年12月5日
【阿尔托大学】图神经网络,Graph Neural Networks,附60页ppt
专知会员服务
181+阅读 · 2020年4月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【快讯】CVPR2020结果出炉,1470篇上榜, 你的paper中了吗?
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
BERT源码分析PART I
AINLP
38+阅读 · 2019年7月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Growing the Simulation Ecosystem
Arxiv
0+阅读 · 2021年9月29日
Arxiv
0+阅读 · 2021年9月27日
Arxiv
0+阅读 · 2021年9月26日
Arxiv
0+阅读 · 2021年9月24日
Arxiv
0+阅读 · 2021年9月24日
Arxiv
13+阅读 · 2021年6月14日
VIP会员
相关VIP内容
专知会员服务
84+阅读 · 2020年12月5日
【阿尔托大学】图神经网络,Graph Neural Networks,附60页ppt
专知会员服务
181+阅读 · 2020年4月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【快讯】CVPR2020结果出炉,1470篇上榜, 你的paper中了吗?
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
BERT源码分析PART I
AINLP
38+阅读 · 2019年7月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Growing the Simulation Ecosystem
Arxiv
0+阅读 · 2021年9月29日
Arxiv
0+阅读 · 2021年9月27日
Arxiv
0+阅读 · 2021年9月26日
Arxiv
0+阅读 · 2021年9月24日
Arxiv
0+阅读 · 2021年9月24日
Arxiv
13+阅读 · 2021年6月14日
Top
微信扫码咨询专知VIP会员