网络重要结构特征识别

张海峰安徽大学2016.4.10网络的重要结构特征识别提纲链路预测——朋友推荐模型社团划分——weakclique识别重叠网络识别有影响力节点朋友推荐的链路预测

定义G（V，E）为一个无向网络，其中V为节点集合，E为边集合。网络总的节点数为N，边数为M。该网络共有

个节点对N（N-1）/2，即全集U。给定一种链路预测的方法，对每对没有连边的节点对

赋予一个分数值

，然后将所有未连接的节点对按照该分数值从大到小排序，排在最前面的节点对出现连边的概率最大。问题描述实验设计AUC精确度CN指标如果两个陌生人有很多的共同朋友，那么这两个人成为朋友的可能性就比较大。

则节点i与j的CN相似性指标可以定义为：AA指标与RA指标度小的共同邻居节点贡献要大于度大的共同邻居的节点。

例如：a图中A与B都认识一个导师，而b图中A与B都认识成龙。显然a中A，B认识的可能性最大。

在RA和AA指标中节点3会把自身以及他和节点1的共同邻居4以等概率介绍给节点1.实际上，节点3只会把2，5，7介绍给节点1。朋友推荐模型的动机通过节点3介绍邻居给节点1.FR相似性指标计算节点i通过l介绍给j的可能性为：分母减1表示不会把l自身介绍给j；

表示不会把l和j的共同邻居介绍给j.节点i介绍给j的可能性为：节点i和节点j的相似性指标为：f231=1/3,f241=1/2;f21=1/3+1/2=5/6;f132=1/2,f142=1/2;f12=1/2+1/2=1;则1与2的相似性指标为：11/12朋友推荐模型的优点1.两节点的共同邻居越多，相似性越高。2.度小的共同邻居节点的贡献大于度大的共同邻居节点。3.节点更倾向被推荐到具有“局部群落”结构的节点上。注:a,b,c三个图中节点1和节点3的CN，AA，RA指标都相同，但在朋友推荐模型中：从左到右可以发现随着{2,3}之间的“局部群落现象”越来越大，f_{123}的概率分别是1/3,1/2以及1.因此朋友推荐模型倾向把节点推荐给具有“局部群落结构”的节点上。4.具有更高的分辨率。节点偏向链接具有“局部群落特征”现象的验证Step1:网络中的边分成是否具有“局部群落结构”根据两个端点的共同邻居数是否大于一个给定的阈值。（文中取平均值）Step2:三个节点构成的三元组的所有7种构型：节点偏向连接具有“局部群落特征”现象的验证Step3:定义P_1,P_2,P_3如下：A,如果两条都是strong-tielinks，则相连的概率P_1为

（N_i表示第i种构型在网络中的数量）：B,如果两条边一个是strong-tielink一个是commonlink，则相连的概率P_2为：C,如果两条边一都是commonlink，则相连的概率P_3为：Step4:比较P_1,P_2,P_3之间的大小关系判断节点是否更偏向链接具有“局部群落特征”的现象。当P_1>P_2且P_1>P_3时，称这种现象存在，进一步，P_1>P_2>P_3,称这种现象是significant.基于真实网络对偏向连接“局部群落特征”现象的验证RN表示网络自身，NN表示原网络的零模型。蓝色表示此现象是significant，红色表示不具有此现象。结论：真实网络中普遍存在这种现象——节点更偏向连接到具有“局部群落结构”的节点。因此该算法的优越性。与RA算法的比较结论：RA相似性高的点对也会导致对应的FR相似性也高，但是FR高的不一定导致RA相似性指标高。如子图g,j所示。在Yeast网络中，点对{A,C}和{A,B}的共同邻居都很多，因此都具有“局部群落”结构，FR指标可以给出A,B连接的概率很高。而基于RA指标，由于C的度很大，所以A和B相连的概率很小。实际上A和B确实真实存在。其中0≤alpha≤1；当alpha=0时，为RA指标，方便比较；当alpha=1时，与FR指标有异曲同工之处。给出FR的更一般形式：问：当alpha逐渐增加时，链路预测的结果是什么样呢？偏向连接“局部群落结构”节点对链路预测的影响（1）如果P1>P2>P3，alpha越大，链路预测中的精度就越高。（2）如果P1<P3，P2<P3，alpha越大，朋友推荐模型在链路预测中的精度就越低。

正反两面都说明此现象在对链路预测起到起到重要作用。基于weak-clique方法识别具有重叠结构的社团网络背景与动机1，很多真实网络具有社团结构，且如何对社团进行准确划分具有很多应用；

2，网络中的有些节点往往属于不同的社团，即重叠结构的社团网络；3，著名的cliquepercolationmethod(CPM)缺点：时间复杂度很高；4，标签传播方法(labelpropagation)缺点：不能分出小的社团结构；5，Linkcommunity缺点：导致重叠度过高……如何发展一种有效的方法识别具有重叠结构的社团网络是值得思考的问题,我们在CPM的基础上发展一种weakcliquepercolationmethod(W-CPM).Weak-clique的定义Weak-clique:两个相邻的节点u和v，他们weak-clique定义为：即：u,v和他们的邻居以及他们之间连边构成的导出子图。节点a和c构成的weak-clique是a,b,c,e,f.（d不属于weak-clique）Weak-clique的选取首先根据一个指标选择一个节点u，再选择一个和u相似度最高的节点v,然后得到u和v构成的weak-clique.红色表示u和v构成的weak-clique.Weak-clique间的合并首先定义两个weak-clique的相似性，当相似性大于一个给定阈值T则合并。T的大小可以确定分成两个社团还是一个社团部分实验结果——运行时间无论是随着节点的增加还是网络平均度的增加，时间W-CPM复杂度都很低。部分实验结果——NMI精确度阈值T对结果的影响关键节点识别（单源和多源）单源——万有引力模型节点的重要性不仅仅与自身有关，且与邻居、次邻居、甚至次次邻居的重要性有关；距离越远，对中心节点的影响越小。因此定义节点i的影响力为：多传播源——着色方法核心思想：用着色图方法把网络节点分成不同的集合，同一个颜色的节点归为一个集合，同一个集合