7,129
个编辑
更改
跳到导航
跳到搜索
第477行：
第477行： − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + − + − + − + − [[File:Pin_n.png|120px]]和[[File:Pppinot_N.png|140px]]+ − + − [[File:Cin_Cout.png|220px]]+
→可探测性
从某种意义上说，社团本身仍然存在，因为边的存在和缺失仍然与其节点的社团成员关系密切；但是，从理论上讲，如果没有社团结构，就不可能更好地标记节点，甚至不可能将图与由'''Erdos-Renyi模型 Erdos–Renyi model '''等空模型生成的图区分开来。这种转换与用于检测社团的算法类型无关，这意味着我们在网络中检测社团的能力存在根本的限制，即使我们使用最优的贝叶斯推理（而不考虑我们的计算资源）。
从某种意义上说，社团本身仍然存在，因为边的存在和缺失仍然与其节点的社团成员关系密切；但是，从理论上讲，如果没有社团结构，就不可能更好地标记节点，甚至不可能将图与由'''Erdos-Renyi模型 Erdos–Renyi model '''等空模型生成的图区分开来。这种转换与用于检测社团的算法类型无关，这意味着我们在网络中检测社团的能力存在根本的限制，即使我们使用最优的贝叶斯推理（而不考虑我们的计算资源）。<ref name=reichardt>
{{cite journal
| first1 = J. | last1 = Reichardt | first2 = M. | last2 = Leone
| year = 2008
| title = (Un)detectable Cluster Structure in Sparse Networks
| journal = Phys. Rev. Lett.
| volume = 101
| issue = 78701
| pages = 1–4
| doi = 10.1103/PhysRevLett.101.078701
| bibcode=2008PhRvL.101g8701R
| arxiv = 0711.1452}}
</ref><ref name=Decelle>
{{cite journal
| first1 = A. | last1 = Decelle | first2 = F. | last2 = Krzakala | first3 = C. | last3 = Moore | first4 = L. | last4 = Zdeborová|author4-link= Lenka Zdeborová
| year = 2011
| title = Inference and Phase Transitions in the Detection of Modules in Sparse Networks
| journal = Phys. Rev. Lett.
| volume = 107
| issue = 65701
| pages = 1–5
| doi = 10.1103/PhysRevLett.107.065701 | pmid = 21902340 | bibcode=2011PhRvL.107f5701D
| arxiv = 1102.1182}}
</ref><ref name=rajrao>
{{cite journal
| first1 = R.R | last1 = Nadakuditi | first2 = M.E.J. | last2 = Newman | author2-link = Mark Newman
| year = 2012
| title = Graph Spectra and the Detectability of Community Structure in Networks
| journal = Phys. Rev. Lett.
| volume = 108
| issue = 188701
| pages = 1–5
| doi = 10.1103/PhysRevLett.108.188701 | pmid = 22681123 | bibcode=2012PhRvL.108r8701N
| arxiv = 1205.1813}}
</ref>
考虑一个具有 ''n'' 个节点，''q''=2 的相同组的随机块模型，并且设[[File:Putin_(1).png|30px]][[File:putout.png|40px]]分别是组内和组间的连接概率。
考虑一个具有 <math>n</math> 个节点，<math> q=2 </math> 的相同组的随机块模型，并且设<math> p_\text{in} </math>和<math>p_\text{out}</math>分别是组内和组间的连接概率。
如果[[File:ppppinpout.png|90px]]，由于社团内部的链接密度大于群体之间的链接密度，网络将具有群体结构。
如果<math>p_\text{in}>p_\text{out}</math>，由于社团内部的链接密度大于群体之间的链接密度，网络将具有群体结构。
在稀疏情况下,[[File:Putin_(1).png|30px]]和[[File:putout.png|40px]]都以[[File:O_n.png|50px]]为比例，所以平均温度是恒定的，则有:
在稀疏情况下, <math> p_\text{in} </math> 和 <math>p_\text{out}</math> 都以 <math>O(1/n)</math> 为比例，所以平均温度是恒定的，则有:
<math>p_\text{in}=c_\text{in}/n</math> 和 <math>p_\text{out}=c_\text{out}/n</math>
然后就不可能在下列情况检测到这些社团:
然后就不可能在下列情况检测到这些社团<ref name=Decelle/>:
<math>c_\text{in}-c_\text{out}=\sqrt{2(c_\text{in}+c_\text{out})}</math>
==进一步阅读==
==进一步阅读==