第九章、图挖掘与网络分析

概述：分组、短信、约会及许多其他方式是社会交往或者社交网络中经典社交行为的主要形式。所有这些概念都用图来建模，即节点、边和其他属性。图挖掘用来挖掘此类信息，类似于其他类型的信息，比如生物信息等。

1.图挖掘

    1.1 图

        图G包含节点V和边E，图可用方程G=（V，E）表示。有两种类型的图：有向图和无向图

    1.2 图挖掘算法

        图挖掘算法包含了频繁模式（子图）挖掘、分类和聚类。

2.频繁子图模式挖掘

    子图模式或者图模式是数据挖掘的一个重要应用。它可以用于生物信息学和社交网络分析等。频繁子图模式是指频繁出现在一组图或者一幅大图中的模式。

    2.1 gPLS算法

        在图的数据集内应用偏最小二乘法PLS算法

        算法详细解析： https://www.cnblogs.com/duye/p/9031511.html

    2.2 GraphSig算法(网络上没有相关论述)

    2.3 gSpan算法

        基本思想：先生成频繁树，再在频繁树的基础上，生成频繁子图，满足最小支持度，满足最小DFS编码的所有频繁子图。

        讲的比较详细（可结合下面图解对此算法进行理解）： https://www.cnblogs.com/zhang293/p/9427988.html

        gSpan算法图解： https://blog.csdn.net/weidai00/article/details/85245217

    2.4 最右路径扩展和他们的支持(网络上没有相关论述)

    2.5 子图同构枚举算法

        算法详细解析（两篇）： ①.https://blog.csdn.net/chichoxian/article/details/52746232

                                              ② https://blog.csdn.net/chichoxian/article/details/52748456

3.社交网络挖掘

    社交网络中收集的数据实例有与图类似和时间的特征。社交网络，有两个主要策略可用于数据挖掘：一个是基于连接（linkage-based）或者基于结构的，另一个是基于内容的。社交网络中收集的数据实例也有两种类型：静态数据和动态或者时间序列数据。

    3.1 社区检测和Shingling算法

        shingling算法用于计算两个文档的相似度

        shingling算法是最常见的文档分割算法，说白了就是将一个文档分解成由短字符构成的字符串集合。分割后的文档就可以通过Jaccard相似度等简单的度量标准进行相似度检测了。

        Shingling算法详解： https://www.cnblogs.com/bonelee/p/6411167.html

    3.2 节点分类和迭代分类算法

4.总结

    图挖掘：频繁模式挖掘、分类和聚类的图数据的特征。

    挖掘模式子图是为了从一组图或者一个大图中找到频繁模式（规则）。

    社交网络分析包括具有宽泛定义的广泛的网络应用，比如说Facebook、LinkleIn、Google+等

下一章将主要研究网络挖掘和算法相关的主题，并基于他们讨论一些实例。