人活三十多，什么都存脑子里，不写点什么，实在有点对不起自己，对不起这社会。于是决定从今天开始写blog。
搞数据挖掘是个很死脑细胞的活儿，最近研究图结构的相似度比较，过目了不少论文，脑门子都看得有点儿发热了，先做一下总结，免得短路烧了。
图这东西应该算是数据结构里面终极难搞的结构了，单一个同构问题，就已经触及了目前人类能搞的极限了。图同构问题即判断两图是否同构已经被认为是NP，而子图同构问题即判断一图是否与另一图的子图同构已经被证明是NP-Compete，这倆座山摆在这，决定了在图的研究领域，想走的远点，必须学会一招：绕行。想了解图的传统处理算法朋友，可以参考这本书：Algorithms on Trees and Graphs, 作者是西班牙加泰罗尼亚(卧槽，这不是梅西的地盘儿？！)理工大学的Gabriel Valiente 教授。 书很厚，将近500页，亚马逊上要价76美金，算成RMB，几乎一页要一块大洋了！我等穷人实在买不起，看两页都够我上班来回一天的公交费了。还是看看网友分享版吧：http://www.doc88.com/p-7572045225030.html。该书详细讲解了图的相关算法和应用，如遍历问题，最大集问题，同构自构问题，子图问题等，另外还有不少树相关的基础算法，并有代码实现。
除此之外，学术界还有一些其他研究，侧重于解决效率问题。
总结一下，如果要想比较两图的相似度，大体上有如下三类主要方法：1 暴力比较
思想基于： 两图相似，仅当他们完全一致（图同构），或其一被另外包含（子图同构）。
这类属于精确比较算法，主要涉及图同构，子图同构等。有各种优化，如：
1.1 通过限制图的种类
代表如：
X. Y. Jiang, H. Bunke Including: geometry in graph representations: A quadratic-time graph isomorphism algorithm and its applications
J. Hopcroft, J. Wong, Linear time algorithm for isomorphism of planar graphs
E. M. Luks, Isomorphism of Graphs of bounded valence can be tested in polynomial time
这类算法只是针对特定的图特定的应用场景优化，达到多项式时间解，但并未从根本解决图比较的复杂度问题
1.2 通过精减搜索空间
典型的以回溯法为代表：
Ullmann：
J.R. Ullmann, An Algorithm for Subgraph Isomorphism
SD:
D.C. Schmidt, L.E. Druffel, A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
VF2：
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, An improved algorithm for matching large graphs.
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs
Nauty:
B.D. McKay, Practical Graph Isomorphism
这类算法各有应用场合：
对于无规则的图， 如果足够稠密并且规模比较大，Nauty比较适合；如果很稀疏并且规模较小，VF2性能更好。
对于有一定规则的图，VF2性能较好，
但这些并未解决时间复杂度问题，最差情况下仍为指数或阶乘级。
python的graph-tool用的是VF2，空间复杂度为O(V)，时间复杂度最好为O(V^2)， 最差为O(V!)
1.3 面向集合比较
这类算法规避了一对一比较，考虑面向集合的比较，降低整体计算代价。算法时间复杂度是输入样本图大小的二次方并且与集合大小无关。
如：
H. Bunke, B.T. Messmer, Efficient Attributed Graph Matching and its Application toImage Analysis
但算法的空间复杂度却是集合大小的指数级，因此只能适用于小规模的计算。
2 特征抽取
思想基于：两图相似，很大程度上一些属性也相似， 如度的分布，直径，特征值等。
算法通过抽取图的特征属性进行相似度计算，简化了问题的复杂度。
Sung-Hyuk Cha. Comprehensive survey on distance similarity measures between probability density functions
显而易见，这是个取巧的方法，精确性有很大问题。3 顶点迭代
思想基于：若各自邻节点相似，则两顶点相似；若所有顶点相似，则两图相似。
算法主要基于不动点计算，通过每一次迭代计算，在顶点之间交换或传播相似度分值，直到算法收敛。
想法有点借鉴于Pagerank。
典型的如：
V. Blondel, A. Gajardo, M. Heymans, P. Senellart, and P. V. Dooren. A measure of similarity between graph vertices: Applications to synonym extraction and web searching
Sergey Melnik, Hector Garcia-Molina, and Erhard Rahm. Similarity flooding: A versatile graph matching algorithm and its application to schema matching
Glen Jeh and Jennifer Widom. SimRank: a measure of structural-context similarity
L Zager and G Verghese. Graph similarity scoring and matching
Mohsen Bayati, David F. Gleich, Amin Saberi, and YingWang. Message passing algorithms for sparse network alignment
这类算法在时间复杂度上有明显提升，以SimRank为例，每次迭代最坏情况时间复杂度为 O(V^3), 空间复杂度为O(V^2), 适合大图计算。 但这类方法本质上属于近似比较，以牺牲一定程度的精确性为代价，不适合应用于严格拓扑结构比较，但在社交网络等非严格拓扑结构中却应用广泛，因为对于社交网络，相比较于结构的拓扑性，更关心结构的聚合度。另外， 由于是近似比较，算法精确度的衡量也是个问题， Similarity flooding 就是靠人工来验证的。
以上3类方法中只有方法1属于精确比较，其他属于近似比较，在不同的场合有不同的应用。本人最近结合1.1，1.2的思想，在图的一对一精确比较上做了一些改进， 目前我们的改进算法时间复杂度为 O(V^3)，并在实际应用环境中展现了不错的精度和性能，后面会详细介绍。
先写这么多吧，开篇之作，不严谨之处，望斧正！