图的相似性 (图的连接相似性)
Baseline (Connectivisimilarity)
Edge Overlap Coefficient
重叠系数，也称Szymkiewicz–Simpson系数，为集合A和B的交集大小比A和B间较小集合大小。
重叠系数出自上述论文，修正Community Structure Similarity based Weighted GMS中的EOL。
$$ \begin{equation}sim(G,G’)=oc(E,E’)={|E\cap E’|\over \min(|E|,|E’|)} \end{equation} $$
Graph Edit Distance
如果节点$v_i$和$v_j$存在边，在$G$中其权重标记为$w_{ij}^1$，在$G’$中其权重标记为$w_{ij}^2$。
$$ \begin{equation}\begin{split} d(G,G’)&=\sum_{(v_i,v_j)\in E\cap E’}{(w_{ij}-w_{ij}’)^2\over (\min(w_{ij}, w_{ij}’)+\epsilon)^2} \\&+\sum_{(v_i,v_j)\in E \backslash( E\cap E’)} (w_{ij}+\epsilon)^2\\&+\sum_{(v_i,v_j)\in E’ \backslash( E\cap E’)} (w_{ij}’+\epsilon)^2\end{split} \end{equation} $$
$$ \begin{equation}sim(G,G’)=1-{d(G,G’)\over \sum_{(v_i,v_j)\in E\cap E’}(\min(w_{ij}, w_{ij}’)+\epsilon)^2} \end{equation} $$
DeltaCon: A Principled Massive-Graph Similarity Function
参考上述论文，考虑$G$和$G’$各只有一条边$w_{ij}=10$，$w_{ij}’=0.01$；$d(G,G’)={(10-0.01)^2\over (0.01+\epsilon)^2}$，$sim(G,G’)=1-{9.99^2\over(0.01+\epsilon)^4}<0$，显然不合理。