什么是图？这个图不是我们平时说的图形或者图像，这个图是点和边。点代表事物，边表示他们之间的关系。
我们最早知道图是欧拉定理和格尼斯堡七桥问题，然后翻山越岭，经过历史的长河，我们来到了本世纪初的图数据库和大图计算。
现在各行各业都需要图，比如：Web Graph, Social Network、Protein Interaction Network等等。下图是一个图的应用场景，左边是各种各样的应用，应用可以分解出基本算子，然后基本算子再分解出最基本算子，所以做系统就要把最基本算子处理好。
一、子图罗列Subgraph Enumeration
左边P是模式图，中间G是数据图，通常模式图比较小，可能就是几个点，数据图有可能非常大。下面是从G中找到所有和P同构的子图实例的三个样例。所以能想象，在实际应用中这种映射有可能会有成千上万，甚至上亿的量。
下面来分享一下子图罗列在各行各业中的应用。
1. 实时周期检测
下图是几年前和阿里合作的实时周期检测项目，主要用于欺诈检测和洗钱检测。
2. 检测指定社区
3. 单CPU解决方案
4. 分布式技术
在分布式技术中没有哪一个算法是最好的，需要我们根据数据分布选择适合的算法。
二、内聚子图Cohesive Subgraphs
下图是曾经和阿里合作的一个项目，目的是抓住刷单的水军。这个问题我们是怎么解决的呢？其实就是将问题转化成抓Bi-Clique就可以了。
所谓的Clique就是每两个点之间都有一条边，那么如何把所有的Clique或者最大的Clique找出来呢？这里就会有一个很大的难点。因为Clique和Clique之间是可以重叠的，这样就会使数目变得非常大。
在数据库他们会做各种各样的变种，比如Quasi-Clique，那么如何定义他们呢？
比如clique的边数是| v | ( | v | )-1，那么Quasi-Clique就是γ | v | ( | v | )-1。
K-Plex在Clique里它的度数等于n-1，那么K-Plex每个点的度数就会大于等于n-k。
K-clique是子图中任意两个顶点之间的距离小于等于k，K-club同样也是任意两个顶点之间的距离小于等于k，但是它的两点是指子群中两点的距离。
K-Core是指子图中每个点的度数大于等于k。这个就比较简单，比如现在这个图里找一度数最小的点，如果度数等于或者大于k就finish了。小于k的，我们就把它除掉，再update度数。
K-Truss是K-Core的加强版，每条边上三角形的个数要大于等于k-2。那么为什么说K-Truss是加强版呢？你能想象一个K-Truss一定是k-1 Core，就是度数值一定是大于等于k-1的。
K-Truss的算法实际上和K-Core的差不多。算法复杂性就是把每条边上的三角形个数全部罗列出来，这也是一个多项式算法。
子图里的度数如果大于等于p乘以全局的度数就叫P-Cohesion。
K-edge Connected是指一个图里去掉任意k减一条边，它仍然是联通的。所以K-edge Connected Component就是找最大的子图。这是一个分解算法，最坏的情形是N的三次方。
还有一个是K-vertex Connected Component，这个我们暂时没有找到非常快的算法。如果你们对这个话题感兴趣，可以来一起提高它的性能。
三、网络弹性Network Resilience
Friendster曾经是一家比较大的社交网站，但在2005年突然就collapse了。这到底是为什么呢，其实原因非常不好找。
就比如你去了一个party，好吃的东西和一个聊得来的人并不会让你留很久。如果想要长时间呆留在party，就需要很多这样的人才可以。
假如我是K-Core，给你的budget是b，也就是让你想办法留下b个人。这个b不用满足K-Core条件，那么b要怎么选才能让network最大呢？
最终我们没有找出非常快速的精确算法，所以就找了个近似算法。 这个论文发表在了VLDB 2017上。
四、二分图Bipartite Graph
所谓的Bipartite Graph就是把图分成两层，上面一层，下面一层。它们都没有边只有cross两层。
实际上它有很多应用，比如下图最左边的就是一个非常典型的academic的例子，上面是演员，下面是电影。
