91
个编辑
更改
→涌现的渗流模型
在键渗流中，我们研究最大连通集群的规模如何随每条边（键）存在概率<math>p</math>的变化而变化。通常存在一个临界阈值<math>p_c</math>:当<math>p<p_c</math>时，图处于不连通相，大多数节点孤立或属于小集群；当<math>p>p_c</math>时，图转变为连通相，出现跨越大部分图的巨型连通簇。这种从主要不连通状态到存在宏观集群的转变是渗流过程的标志特征，且随着节点数的增加，这一转变会愈发陡峭。
在键渗流中，我们研究最大连通集群的规模如何随每条边（键）存在概率<math>p</math>的变化而变化。通常存在一个临界阈值<math>p_c</math>:当<math>p<p_c</math>时，图处于不连通相，大多数节点孤立或属于小集群；当<math>p>p_c</math>时，图转变为连通相，出现跨越大部分图的巨型连通簇。这种从主要不连通状态到存在宏观集群的转变是渗流过程的标志特征，且随着节点数的增加，这一转变会愈发陡峭。
[[文件:Percolation-二分图.png|无|缩略图|800x800px|将构成看不见的概念(例如,实体和属性)的能力投射为二分图上的渗流：(a)若概念类仅部分出现在训练集中，或实体-属性连接稀疏，图中节点将形成多个“孤立簇”（见左图，颜色不同表示不同连通区域）；随着更多概念类被加入（虚线边表示新增连接），这些小簇开始合并（中图）；随着更多概念类被加入（虚线边表示新增连接），这些小簇开始合并（中图）。(b)我们的理论将这种转变建立为二阶相变，其中最大团簇的大小随着连接节点对的比例非线性地增加。]]
[[文件:Percolation-二分图.png|无|缩略图|600x600px|将构成看不见的概念(例如,实体和属性)的能力投射为二分图上的渗流：(a)若概念类仅部分出现在训练集中，或实体-属性连接稀疏，图中节点将形成多个“孤立簇”（见左图，颜色不同表示不同连通区域）；随着更多概念类被加入（虚线边表示新增连接），这些小簇开始合并（中图）；随着更多概念类被加入（虚线边表示新增连接），这些小簇开始合并（中图）。(b)我们的理论将这种转变建立为二阶相变，其中最大团簇的大小随着连接节点对的比例非线性地增加。]]
在简单渗流场景中（图的连接边随机选择，概率为<math>p</math>），渗流阈值为<math>p_c\approx \sqrt{1/\left | E \right | \left | K \right | } </math>（当<math> \left | E \right | </math>和<math> \left | K \right | </math>较大时）。这意味着当约<math>\sqrt{\left | E \right | \left | K \right | } </math>条边被连接时（总可能边数为<math>\left | E \right | \left | K \right | </math>），系统的连通簇会出现质变。对于<math>p>p_c</math>，最大簇的节点数迅速增长，任取一对实体–属性，其在同一簇中的概率趋近于常数。
在简单渗流场景中（图的连接边随机选择，概率为<math>p</math>），渗流阈值为<math>p_c\approx \sqrt{1/\left | E \right | \left | K \right | } </math>（当<math> \left | E \right | </math>和<math> \left | K \right | </math>较大时）。这意味着当约<math>\sqrt{\left | E \right | \left | K \right | } </math>条边被连接时（总可能边数为<math>\left | E \right | \left | K \right | </math>），系统的连通簇会出现质变。对于<math>p>p_c</math>，最大簇的节点数迅速增长，任取一对实体–属性，其在同一簇中的概率趋近于常数。