西安电子科技大学：《复杂网络与群体智能》课程教学课件（复杂网络）第四讲 节点相似性

历些毛子种拔大皇 第四讲：节点相似性 XIDIAN UNIVERSITY (1)节点相似性 (2)基于局部结构相似性指标 (3)全局路径特征 2

（1）节点相似性 （2）基于局部结构相似性指标 （3）全局路径特征 第四讲：节点相似性 2

历些毛子代枝大学 第四讲：节点相似性 XIDIAN UNIVERSITY ● 节点相似性指标用于评价节点之间的相似程度： ·用途：可作为链路预测、节点分类的依据。 ·依据：节点相似性度量的依据是局部结构特征或者全局 路径特征。 3

第四讲：节点相似性 3 • 节点相似性指标用于评价节点之间的相似程度; • 用途：可作为链路预测、节点分类的依据。 • 依据：节点相似性度量的依据是局部结构特征或者全局 路径特征

面些毛子种枝大票 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 ·用途：可作为链路预测、节点分类的依据。 依据：节点相似性度量的依据是局部结构特征或者全局 路径特征

第四讲：节点相似性 4 基于局部结构相似性指标 • 用途：可作为链路预测、节点分类的依据。 • 依据：节点相似性度量的依据是局部结构特征或者全局 路径特征

历些毛子代枝大学 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 1公共邻居 。顾名思义，共同邻居指标认为两个节点之间共同的邻居越多，这两 个节点的相似性越高。用T()表示节点v,邻居集合，则TΓ()∩「)表示 两个节点邻居集合的交集。用引表示集合中节点的数量，则共同邻居 相似性指标S如式(3-1)所示： S,=r(x)nF(y川 (3-1) ·该方法的有点是简单，但是考虑的因素较少。在共同邻居的基础上 ,考虑其它因素，比如节点度，可以得到其它几种指标。 5

第四讲：节点相似性 5 基于局部结构相似性指标 1 公共邻居 • 顾名思义，共同邻居指标认为两个节点之间共同的邻居越多，这两 个节点的相似性越高。用Г(i)表示节点vi邻居集合，则Г(i)∩Г(j)表示 两个节点邻居集合的交集。用|·|表示集合中节点的数量，则共同邻居 相似性指标Sij如式（3-1）所示： （3-1） • 该方法的有点是简单，但是考虑的因素较少。在共同邻居的基础上 ，考虑其它因素，比如节点度，可以得到其它几种指标。 ( ) ( ) ij S x y    

面些毛子代枝大票 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 2 Salton相似性指标 ·也称为余弦相似性指标，是由Salton等人提出的，定义如 下： s,-ronrun V压×K (3-2) 其中，k,表示节点y,的度。 ·把邻接矩阵的第行和第行视为两个向量a和a(元素为0和1)，并 使用两者夹角的余弦值作为相似度的计算。 6

第四讲：节点相似性 6 基于局部结构相似性指标 2 Salton相似性指标 • 也称为余弦相似性指标，是由Salton等人提出的，定义如 下： （3-2） 其中，ki表示节点vi的度。 • 把邻接矩阵的第i行和第j行视为两个向量ai和aj （元素为0和1），并 使用两者夹角的余弦值作为相似度的计算。 ( ) ( ) ij = i j i j S k k    

历些毛子代枝大学 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 3 Jaccard相似性指标 这个指标是由Jaccard提出的，定义如下： r(ior() (3-3) r(or() 可见，Jaccard相似性指标是两个节点邻居集合的交集与并 集的比值。 7

第四讲：节点相似性 7 基于局部结构相似性指标 3 Jaccard相似性指标 这个指标是由Jaccard提出的，定义如下： (3-3) 可见，Jaccard相似性指标是两个节点邻居集合的交集与并 集的比值。 ( ) ( ) = ( ) ( ) ij i j S i j      

面些毛子种枝大票 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 ·4 Sorenson指标 是由S0 renson在处理植物生态数据时提出的，定义如下 s,-2r0orl k +kj (3-4) ·5大度节点有利指标(HPI) s,-rooro min(kk,) (3-5) 8

第四讲：节点相似性 8 基于局部结构相似性指标 • 4 Sorenson指标 是由Sθrenson在处理植物生态数据时提出的，定义如下 (3-4) • 5 大度节点有利指标（HPI） （3-5） 2 ( ) ( ) ij = i j i j S k k     ( ) ( ) = min{ , } ij i j i i S k k   

历些毛子代枝大学 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 ·6大度节点不利指标(HDI) s,-ooro max(ki,k (3-6) ·7优先连接指标(PA) S,=k×k (3-7) 9

第四讲：节点相似性 9 基于局部结构相似性指标 • 6 大度节点不利指标（HDI） (3-6) • 7 优先连接指标 (PA) （3-7） ( ) ( ) = max{ , } ij i j i i S k k    S k k ij i j = 

面些毛子种枝大票 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 ·8AA指标 = ser(r()logk. 该指标主要考虑了两节点共同邻居的度的信息，主要考虑到共同 邻居中度小的节点的影响。这一点很容易理解，例如在新浪微博 上甲乙两个人都关注了一个名星，丙丁两个人共同关注了一个普 通的人，则丙和丁两个人认识的可能性大于甲和乙两个人认识的 可能性。 10

第四讲：节点相似性 10 基于局部结构相似性指标 • 8 AA指标 该指标主要考虑了两节点共同邻居的度的信息，主要考虑到共同 邻居中度小的节点的影响。这一点很容易理解，例如在新浪微博 上甲乙两个人都关注了一个名星，丙丁两个人共同关注了一个普 通的人，则丙和丁两个人认识的可能性大于甲和乙两个人认识的 可能性。 ( ) ( ) 1 logk ij z i j z s    

历些毛子代枝大学 第四讲：节点相似性 XIDIAN UNIVERSITY >基于局部结构相似性指标 ·9RA指标 ,=∑ 1 zer(r()k. 周涛等提出的，RA指标主要基于网络上资源传递的思想，例如在 网络中不存在连边的两个节点和y，要想从v传递一些资源到y ，就需要传递媒介，在网络中他们的共同邻居则充当着这种传递 的媒介。从节点传递一个单位的资源到，首先先平均分配传 递到v的邻居，每个邻居也说平均分配给它的邻居，则得到的 资源数则为这两个节点的相似度。 11

第四讲：节点相似性 11 基于局部结构相似性指标 • 9 RA指标 周涛等提出的，RA指标主要基于网络上资源传递的思想，例如在 网络中不存在连边的两个节点vi和vj ，要想从vi传递一些资源到vj ，就需要传递媒介，在网络中他们的共同邻居则充当着这种传递 的媒介。从节点 vi传递一个单位的资源到vj，首先先平均分配传 递到vi的邻居，每个邻居也说平均分配给它的邻居，则vj得到的 资源数则为这两个节点的相似度。 ( ) ( ) 1 k ij z i j z s    