2013网络科学论坛 4月24-26日 Exploring adaptive proximities to detect possible link and rich club phenomenon 丁义明 ding@wipm.ac.cn 中国科学院武汉物理与数学研究所

目 录 六度分离 节点相似性：局部方法 适应性三度相似：拟局部方法 链路预测：相似度高的结点对连边的可能性大 富人俱乐部 总结

六度分离 Six Degrees of Separation：你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。 1950s，Manfred Kochen（数学） 、和 Ithiel de Sola Pool（政治）写了数学文章 “Contacts and Influences”,1978年发表. 20世纪60年代，耶鲁大学的社会心理学家米尔格兰姆(Stanley Milgram)就设计了一个连锁信件实验。 1985，电影 Six Degrees：这个世界真是太小了，随便五个人就能永远改变你的未来 In 1998, Duncan J. Watts 、 Steven Strogatz 发表了第一个小世界网络模型. 爱尔兰手创乐队(The Script)： Six Degrees of Separation

节点相似性（Node Proximity) 六度之内，都是朋友，哪些是真朋友？ 关键：衡量两个节点的相互接近的程度 节点相似度：每对节点都给出一个数来衡量它们的接近程度 两者越接近，该数值越大 在链路预测、社团、富人俱乐部等方面有广泛应用

Why Node Proximity？ 衡量一对未连接的节点通过中间结点信息交换的潜力 衡量一对节点接近的程度 发现可能存在的边——链路预测 在社会网络中，有助于预测和跟踪思想、疾病和产品的传播 探测网络中的意外结构

局部相似性和基于路径的相似性 吕琳媛、周涛：2011综述文章 公共邻居： （1）局部相似性指标中表现最好的三种指标 Adamic-Adar指标 ： 资源分配指标： （2）基于路径的相似性指标 局部路径指标： Katz指标： LHN指标： 吕琳媛、周涛：2011综述文章

适应的三度相似 Extended RA(ERA) Extended AA(EAA) Extended CN(ECN) 各有一个调节参数

链路预测（Link Prediction） 复杂网络中的链路预测是指基于网络已知的连边结构信以及节点的属性来预测两个节点之间产生连边的可能性。我们给定一种连边预测的算法，每对不存在连边的节点对赋予一个分值，然后将比较分值大小。 AUC：随机从测试集中抽出一条边的分数比随机从不存在连边集合中抽出一条边大的概率 AUC越大，预测效率越高 全集图 训练集 吕琳媛、周涛：2011综述文章

优化链路预测效率得到最优调节参数 链路预测：预测两个节点之间是否存在连边 节点相似性：相似性值大的两个节点存在连边的可能性大 预测效果评价：选训练集和测试集，判断预测效果 给定调节参数——节点相似性指标——链路预测效率 选择效率最好者作为调节参数

采用三度相似进行链路预测 实际网络数据和基本拓扑性质

我们给出的三个“三度相似”指标的预测效率在16个相似性指标中排前三 三度相似在七个网络链路预测效率领先 三度相似性指标ERA在以上所有指标表现得最好，EAA指标表现得第二好，ECN指标和LP指标有着不相上下的预测连边效果。Email和PPI网络的最优参数比其它网络的最优参数相对要大些，而且他们预测精确度AUC被提高得也更多些，因为这两个网络的密度相对更为稀疏些。 我们给出的三个“三度相似”指标的预测效率在16个相似性指标中排前三

为什么三度?? 二度邻居——三度邻居：覆盖率增加29.1% 三度邻居——四度邻居：覆盖率增加13.9% 11.30 11.24 4.92 0.0487 0.0085 0.1399 0.0127 0.0224 0.0041 0.0386 0.5503 0.0955 0.6883 0.056 0.3979 0.0286 0.4057 0.9474 0.4516 0.9468 0.1352 0.8575 0.1267 0.8481 0.9998 0.8559 0.9915 0.2657 0.9869 0.3642 0.9728 1 0.9993 0.6016 0.9999 0.8383 0.7577 0.9357 0.86 0.9763 11.30 11.24 4.92 4.41 17.76 6.98 10.51 1.72 4.73 1.375 2.41 2.155 4.43 2.09 1.055 1.895 1.05 1.965 1.15 2.87 1.00 1.17 1.01 2.26 2.30 1.03 1 1.26 1.12 1.135 1.04 二度邻居——三度邻居：覆盖率增加29.1% 三度邻居——四度邻居：覆盖率增加13.9%

二度邻居——三度邻居：邻居个数的中位数增加28.7% 三度邻居——四度邻居：邻居个数的中位数增加12.6% 三度?????? 13 8 26 5 14 6 171 79 148 17 519 41 120 290 512 193 48 1120 223 309 297 1035 197 91 1217 874 331 1129 198 157 1221 1723 332 1133 244 1222 2166 318 2313 339 2356 359 2368 13.15 9.875 5.69 3.4 37.1 8.2 20 1.696 6.481 1.3 2.82 2.16 5.4 2.58 1.024 2.021 1.02 1.9 1.09 3.9 1.07 1 1.091 1.01 1.73 2 1.004 1.55 1.1 1.06 二度邻居——三度邻居：邻居个数的中位数增加28.7% 三度邻居——四度邻居：邻居个数的中位数增加12.6%

四度相似?? 两个参数

四度相似链路预测AUC随着参数 而变化的趋势 最优参数 都接近于零，四度邻居的贡献可以忽略

小结：为什么采用三度相似 二度邻域中的点的覆盖度不够，导致很多节点对的相似度为0 三度邻域具有较好的覆盖度，信息较充分 从二度到三度扩充的效率高 从三度到四度扩充的效率不到前者的一半 从链路预测的角度来看，三度相似的预测效果优于二度，且计算上可行 而四度邻居太多，计算较复杂，链路预测效率提高不大（除非非常稀疏的网络） 李幼平院士：loglogN~~3

Rich club现象 rich club现象：富人俱乐部是复杂网络中的一种特殊现象，一些度较大的节点(富节点)相对于度小的节点往往更趋向于紧密联系在一起，从而形成一个俱乐部 富人俱乐部现象没有明确的定义，导致很难判别 富人俱乐部现象的出现，表明网络有较高效率，且稳健；网络调控的关键 判断一个网络是否有Rich Club是一个有挑战性的问题，已经有大量文献

三度相似调节参数

USAir,JAZZ网络的三度相似调节参数小于0 对ECN,EAA,ERA,LP都小于0

Rich Club ？？ 判断富人俱乐部现象的方法比较多，往往需要与大量度分布相同的随机模型进行对比，判断富人俱乐部现象过程相对比较繁琐，这些方法之间也存在一定的误差，容易引起争论。 参考网络 Colizza等2006 统计检验 江、周 2008 判别 许, 张，Small 2010

三度相似——Rich Club现象 用现有的方法，难以判断右边的网络有Rich Club现象 三度相似指标ERA的最优调节参数为 -0.886，根据我们的方法可知该网络表现出非常明显的富人俱乐部现象

总 结 6度分离 相似性度量 适应性3度相似：拟局部方法——调节参数 链路预测：相似的结点对连边的可能性大——调节参数 总 结 6度分离 相似性度量 适应性3度相似：拟局部方法——调节参数 链路预测：相似的结点对连边的可能性大——调节参数 富人俱乐部探测：——调节参数小于0

致 谢 武汉理工大学：郑汉彬、余旌胡等 中科院武汉物数所：崔鸿飞、蒋杭进、雷皓等 致 谢 武汉理工大学：郑汉彬、余旌胡等 中科院武汉物数所：崔鸿飞、蒋杭进、雷皓等 科技部973计划、 国家数学交叉研究中心、 中科院生物磁共振分析重点实验室 …

谢谢大家！

由随机分块模型生成400个节点，4个类的网络模型： Figure 1(optimal alpha)： 左1：lambda=0.6 2 3

LFR benchmark N=500; <k>=20; maxk=40; minc=30; maxc=100 混合参数mu值越小,代表产生的网络社团结构越清晰。 The mixing parameter mu~[0.1, 0.4] 1 2 3 mu=0.1, 0.2时，分类结果完全准确； mu=0.3, 0.4时，分类结果错1~3个节点。

实际网络 Dolphin social network DB_ERA=2.1384; DB_ECN=2.0163; Alpha_ERA=0.036; Alpha_ECN=0.056; Alpha_EAA=0.014; 分类结果一致，较为准确。 实际网络 DB_ERA=0.6531; DB_ECN=0.7305; DB_ERA=0.6845; Alpha_ERA=0.15; Alpha_ECN=0.15; Alpha_EAA=0.15; ECN对应的聚类方法分类结果比另外两种准确。 The karate club network