有哪些指标可以描述两个图（graph）的相似度？ 第1页

作为纯数出身的人，从数学角度思考题主的问题。如果是喜欢图论又关注数学的人，应该听说过近几年的热点方向：“graph limit”。数学界三大奖之一沃尔夫奖获得者，L. Lovasz[1]对这个方向做出了很大贡献，并且graph limit无论是在数论，分析，概率这些纯数方向，还是CS，算法这些应数方项都有很多应用。

极限的定义大家都知道，不严谨的说极限是描述一种无限接近的状态，那graph limit不可避免的要定义不同的图之间的距离。从几何上考虑，如果要定义两个图G和H距离很近，那么他们应该在局部足够相似。也就是说如果我从G上面撕下来一块相对大的碎片，那我应该能从H上找到一个局部和我刚撕下来的那块graph很“几乎同构”。用数学的语言描述，首先定义 图F到G同构的个数，然后定义同构密度，于是 ，。

如果稍微思考几秒钟我上面说的话，你就会发现..我说的是废话。因为这个定义只是直观的几何描述，对解决问题没有任何帮助。..接下来是正经的定义（虽然实际上和上面的直观定义是一回事）。首先对于两个定义在同一个点集上的图，直观的看，如果我们从中找任意两个子集，这两个子集之间的边的数量在上差不多，我们就可以认为这两个图很相似。也就是说，定义是图中之间的边的数量，我们用描述两个图的距离。我们把这种距离叫做cut distance。注意的是这个定义也在adjacency matrix上有良好的表示。

有了这个定义，那么对于拥有相同vertex数但是不同点集的两个图，我们可以对其中一个图重新编号；对于vertex数不同的两个图，我们可以blow-up。比较令人惊讶的是，这样得来的距离定义和我们一开始的直观定义相同。

接下来，这个距离的定义有什么用？

我注意到题主貌似是cs的，那我着重说一下我了解的cs方向的应用。作为背景，Szemeredi's regularity lemma目前是图论中最重要的定理之一，同时在数论，分析，概率，理论CS中有非常多的应用。粗略的说，这个引理描述的是每个很大的图都可以被划分为几部分，使得几乎任意两部分形成的二部图“random-like”。大概在95年左右，Friez和Kannan做出了一个regularity lemma的弱化版本，目前称为FK-regularity lemma（或者weak regularity lemma）：他们构造了一个的算法，input任意一个非常大的图（有个点 ），output一个非常regular的图，使得。

有了这个定理，我们可以快速（ ）的找到很多NP问题的近似解。这个方向的研究现在非常活跃。举个例子，判定一个图是否包含子图是至少NP-complete的，但是我们可以快速找出图中子图的近似数量[2]。找到一个图的rectilinear crossing number是NP-hard的，但是我们可以快速找出他的近似值，甚至可以给出一个构造[3]。大致思路很简单，给定一个大图，先作用FK算法找到一个划分，我们先遍历小图（constant time），然后再blow-up，利用两个图cut-distance相近来近似得到的结果。

强调一下这个方法我认为应该只对dense graph有效。对于稀疏图，我们的近似太粗暴了。L. Lovasz[1]最近倒是有研究graphs with bounded degree这种相对稀疏的图，不过具体方法不是很了解，大家有兴趣可以看参考资料。

Reference

[1]. L. Lovasz, Large networks and graph limits, American Mathematical Society, 2012.

[2]. J. Fox, L.M. Lovasz and Y. Zhao, On regularity lemmas and their algorithmic applications, arXiv[math.CO] 1604:0733.

[3]. J. Fox, J. Pach and A. Suk, Approximating the rectilinear crossing number, arXiv[cs.CG] 1606:3752