106
个编辑
更改
跳到导航
跳到搜索
第21行：
第21行： − {|class="10种基于节点局部信息的相似性指标" − |+ mfinder − |- − !rowspan="1"|名称 || 定义 || 名称 || 定义 − |- − |rowspan="1"|(1)共同邻居（CN）|| <math>s_{xy}^{CN} = |Γ(x)| \cap |Γ(y)|</math> || (6)大度节点不利指标（HDI）|| <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{max\{k_x,k_y\}}</math> − |- − |} + + + + + + + + + + + + + + +
→基于相似性的链路预测
[[File:Table1.png|600px|thumb|10种基于节点局部信息的相似性指标|center]]
[[File:Table1.png|600px|thumb|10种基于节点局部信息的相似性指标|center]]
第2个指标Salton又称余弦相似性，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{\sqrt{k(x)k(y)}}</math>
第3个指标Jaccard指标是于100多年前由Jaccard提出的，其定义为 <math>s_{xy}=\frac{|Γ(x)| \cap |Γ(y)|}{|Γ(x)| \bigcup |Γ(y)|}</math>
第4个指标Sorensen指标常用于生态学研究，其定义为 <math>s{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{kx + ky}</math>
第5个指标大度节点有利指标（Hub promoted index，HPI）被用来定量刻画新陈代谢网络中每对反应物的拓扑相似程度，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{min\{k_x,k_y\}}</math>，由于分母只由度较小的节点决定，在此定义下可知大度节点（hub）与其他节点之间更容易具有高的相似性。
第6个指标大度节点不利指标（hub depressed index, HDI）定义与HPI相似，只是分母取两端节点度的最大值，即 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{max\{k_x,k_y\}}</math>。
第7个指标LHN-I指标是由Leicht，Holme和Newman提出，其定义为 <math>s_{xy}=\frac{2 x |Γ(x)| \cap |Γ(y)|}{{k_xk_y}}</math>，其中分母<math>k_xk_y</math> 正比于节点<math>v_x</math>和节点<math>v_y</math>共同邻居数的期望值，即 <math>E( |Γ(x)| \cap |Γ(y)|)</math>。在下面这篇文献中，Leicht等人同时提出了另一个基于路径的指标，为了有所区别，将此局部指标命名为LHN-I指标，将基于路径的指标命名为LHN-II指标：
第8个指标PA（preferential attachment）是基于BA无标度网络模型中新加入节点倾向于和度大的节点相连的优先连接机制而提出的，在这种机制的链路预测中，每一步首先去除一条链接，然后再添加一条链接，新链接连接节点<math>v_x</math>和<math>v_y</math>的概率就正比于两节点度的乘积，由此可以定义两节点间的优先连接相似性：<math>s_{xy}= k_xk_y</math>
第9个指标AA（Adamic-Adar）的基本思想是度小的共同邻居节点的贡献大于度大的共同邻居节点，因此根据共同邻居节点的度为每个节点赋予一个权重值。这一点很容易理解，例如在微博中受关注较多的人往往是某个领域的专家或名人，因此共同关注他们的人之间可能并不拥有特别相似的兴趣——一个中学生和一个企业家都有可能是姚晨的粉丝。相反，如果两个人共同关注了一个粉丝很少的人（非名人），那么说明这两个人确实具有相同的兴趣爱好或者重叠的社交圈，因此有更高概率相连。又如在推荐系统中，共同购买冷门产品的两个用户往往比共同购买热门产品的用户更相似。AA指标根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点的度的对数分之一，即AA指标的定义为：<math>s_{xy}=\sum _{z\in \Gamma (x)\bigcap \Gamma (y)}\frac{1}{logk_z}</math>。
第10种指标RA是受网络资源分配过程的启发，周涛等人提出的“'''资源分配指标 Resource allocation'''”，其与AA指标有异曲同工之妙。RA和AA指标最大的区别就在于赋予共同邻居节点权重的方式不同，前者是以 1/k 的形式递减，后者是以 1/logk 的形式递减。可见，当网络的平均度较小时，RA和AA差别不大；但是当平均度较大时，就有很大的区别了。研究显示，RA指标在刻画加权网络和社区挖掘应用中的表现胜过AA指标，图灵奖得主Hopdroft的一篇论文也显示，可以利用社区等中观结构信息改进局部指标，其中RA指标改进后的效果最佳。
第10种指标RA是受网络资源分配过程的启发，周涛等人提出的“'''资源分配指标 Resource allocation'''”，其与AA指标有异曲同工之妙。RA和AA指标最大的区别就在于赋予共同邻居节点权重的方式不同，前者是以 1/k 的形式递减，后者是以 1/logk 的形式递减。可见，当网络的平均度较小时，RA和AA差别不大；但是当平均度较大时，就有很大的区别了。研究显示，RA指标在刻画加权网络和社区挖掘应用中的表现胜过AA指标，图灵奖得主Hopdroft的一篇论文也显示，可以利用社区等中观结构信息改进局部指标，其中RA指标改进后的效果最佳。