去匿名化中的结构相似度

未分类

---

本文总结了所有已使用的结构相似度，并进行了基本的分类，后期会有相应的实验分析

只考虑无向无权图

首先可以分成两种方式，一种是先构造出特征向量，然后再使用常见的相似度或距离度量来计算，另一种是直接设计一个新的相似度度量方式
分为两大类，第一类是与种子节点无关的，第二类是与种子节点相关的

1.1 基于节点基本信息

1.1.1 节点自身的信息

（1）节点的度[1]
1）使用常见的距离度量来计算距离，然后使用高斯函数
2）RDD(Relative Degree Distance)：
（2）中心性[2]
1）closeness centrality
2）betweenness centrality

1.1.2 节点之间的信息

采出部分节点（如k个度最大的节点），然后计算其他每个节点和这些节点的距离
（1）最短路径长度（如Top-K Reference Distance[3]）
（2）中心性
1）closeness centrality(如Sampling Closeness Centrality[4])
2）betweenness centrality[5]
（3）eccentricity(衡量唯一性)[6][7]:

$$ecc(L)=\frac{s(v, u_1)-S(v, u_2)}{dev(L)}$$ ，L是其他节点与它的相似度（从大到小排列）

如果部分节点是种子节点：
（1）最短路径长度（如Relative Distance Similarity[8]、Landmark Reference Distance[9]）

1.2 基于图局部结构

（1）邻居的度信息
1）1阶度序列，前k个最大的度组成一个向量[10]
2）度分布（直接比较邻居的序列，只适用于噪声极少的情况[11]）
（2）k-clique+节点的度+两个节点的共同邻居[12][13][14]
（3）k-邻居度直方图统计[15]

1.3 基于图全局结构

（1）（标准化）拉普拉斯映射[16]

1.4 适用于不同网络上的两个节点的相似度计算（只能直接算，无法先得出特征向量再计算）

（1）度信息+种子节点
1）Inheritance Similarity[17]：

$$s(v, v^{'})=\frac{C}{|N_{} (v, v^{'})|} (1-\frac{|degree_v - degree_{v^{'}}|}{max\{v,v^{'}\}})$$
2）Dice coefficient[18]: $$dice(v, u)=1-\frac{2w(N_v \cap N_u)}{w(N_v)+w(N_u)}$$ ，传统的，无权重图的权重可以认为是1，在该论文中，给出了一种新的方式：$w(N_v)=\sum_{i \in N_v} \frac{1}{log d_i}$
3）Controversial UMP[19]: $$c-ump(v,u)=|N_v \cap N_u|+\frac{|N_v \cap N_u|}{min(|N_v|, |N_u|)}$$
4）Shared Identified Friends[20][21][22]:$sif(v,u)=|N_v \cap N_u|$
5）Subgraph Jacarrd Coefficient[23]: $$S_{sub}(u, v)=\frac{|N_{sub}(v) \cap N_{sub}(u)|}{|N_{sub}(v) \cup N_{sub}(u)|}$$
6）度信息+sif[24]：$s(u,v)=\frac{|N_v \cap N_u|}{\sqrt{d_v d_u}}$