一篇文章带你认识“高大上”的图数据挖掘

互联网发展至今，数据规模越来越大，数据结构越来越复杂，而且对系统的需求越来越高。如果学习过数据结构，那么都知道图是放在最后一个结构，当你学习了图，那么应该感知到前面的链表，队列，树都是在图上面加了一些约束而派生出来的结构。所以图是一个一般性的结构，可以适应于任何结构类型的数据。那么图数据挖掘是干什么的呢？难道是开着挖掘机来进行挖掘？还是扛着锄头？下面讲讲什么是图数据挖掘。

一、什么是图数据挖掘

这个话题感觉比较沉重，以至于我敲打每个字都要犹豫半天，这里我说说我对图数据挖掘的理解。数据是一个不可数名字，那么说明数据是一个没有边界的东西。而挖掘是一个很形象化的动词，一般意义上，挖掘是挖掘出对我们有用的东西，不然也不会闲着没事刨个坑把自己放进去，肯定是里面有宝贝，我们才挖掘。那么不难理解，数据挖掘就是挖掘数据里面的“宝贝”，图数据挖掘，就是以图的结构来存储、展示、思考数据，以达到挖掘出其中的“宝贝”。那这个“宝贝”是什么？这个有点主观意识来理解了，“宝贝”这个词本身就带有主观色彩，而没有一个客观的答案，不像是美女大胸、翘臀、高挑、皮肤白皙、脸蛋好看等一系列标准。那么如何理解图数据里面的“宝贝”呢？举个例子吧，例如：当今互联网产生了很多社交数据，某某关注了某某，那么某某和某某就有了关系，某某评论过某某，那么这又产生了关系，在这个里面某某就是图中的节点，而评论过，关注了则是节点之间的关系，如果某某再多点，这就形成了一个无边界的图了。那么对这个图进行关系挖掘，那么会产生很多有用的数据，比如可以推荐你可能认识的人，那就是朋友的朋友，甚至更深，这就形成了某空间好友推荐的功能。比如某宝的你可能喜欢的宝贝，可以通过图数据挖掘来实现。这就是我认为的图数据挖掘。

从学术上讲，图数据挖掘分为数据图，模式图两种。至于这两个类型的区别，由于很久没有关注这块，所以只能给出一个字面意义上的区别。数据图：则是以数据节点为基础来进行分析图，模式图：则是以数据整个关系模型来进行分析数据。可能解释存在错误，望指正。我之前主要是接触数据图一块的东西，模式图没有太多了解。关于数据图和模式图在学术界存在几个比较有参考意义的实现以及算法。数据图有：BANKS,BLINKS,Object rank；模式图有：DBXplorer（微软）,DISCOVER(加利福尼亚大学)，S-CBR（人民大学，就是在大学学数据库都会知道的人：王珊）。下面主要对数据图的几种实现进行简单介绍，模式图，可以找上面相关论文进行了解。

二、数据图典型实现介绍

1、BANK（Browsing and Keyword Searching in Relational Databases）

整体上说一下它的思想是通过关系数据库进行存储图结构的数据加上Dijkstra算法来进行数据的存储和图数据的搜索。该算法第一步先是先是匹配所有关键词的关键节点，并且以每个关键节点为源节点进行一次Dijkstra算法对图进行遍历，因此可以形成和每个关键节点可达的节点堆，该堆是进行了按照到关键节点距离进行堆排序的堆。因此可以想想每个关键节点的节点堆的第一个元素则是到该关键节点最近的节点。利用这个，那么对每个节点堆一次遍历，每次遍历只取堆的第一个节点，可以得知，这个取出的节点和节点对对应的关键词是可达的，如果这个节点和所有关键节点可达，那么就可以这个节点为根节点形成一个结果树，所以需要对这个取出的节点进行标记，标记的目的就是说我这个关键节点来过这里了（有点类似到此一游的感觉）。这就是BANK的大体上的算法思想。下面提出一个流程图，帮助大家理解一下。

这种方式存在几个缺点：由于它的这个算法是需要把整个图结构加载到内存中，所以当节点数一大，那么可能会收到内存的限制。第二个缺点是，它的搜索是单向的，这样在效率上面存在一定的缺陷。这个算法也是我研究图数据挖掘主要研究的对象，因为比较简单，容易理解。下面针对上面两个缺陷介绍另外两个算法。

2、Bidirectional Expansion For Keyword Search on Graph Databases

这个算法则是在第一个基础上面进行了扩展，支持双向搜索。从而解决了上麦年的第二个缺陷。具体算法实现，很久没接触了，而且当时也没关注这方面的实现，所以我也不是很清楚，只是知道它实现了双向遍历。具体的可以点击标题，看它的论文。

3、BLINK BLINKS Ranked keyword searches on graphs

这个实现是解决了大图问题，通过对图进行分割，形成超图的概念，加载内存只需要把超图进来，当需要遍历这个超图节点的时候，再将超图节点里面的明细节点加载到内存，基于这个概念可以很好的解决节点数量大而受内存的限制，这个算法有点类似地图的放大镜，当需要展示某一块（超图节点）的时候，则加载当前块的内容，用户就会看到更加明细的地图信息。具体算法，可以点击标题，看看它的论文。

既然说道图，那么不得不提一下在图数据库方面最流行的neo4j.neo4j是在09年过年的时候接触的，当时是调研以何种方式来存储图数据，所以当时弄了一下，后没就没关注了。当时看neo4j真的很小，不像现在这么成熟。

三、NEO4J预览

在NEO4J官方文档里面会看到下面几点介绍图数据库。

“A Graph —records data in→ Nodes —which have→ Properties”

上面很简单明了的介绍了图是什么，图是以节点存储记录数据，而节点数据是以属性形式关联节点。

“Nodes —are organized by→ Relationships —which also have→ Properties”

这句话说明了关系在图中的作用，可以理解节点是通过关系来进行组织和管理，并且关系也可以包裹属性信息。

“Nodes —are grouped by→ Labels —into→ Sets”

在图中标签的作用就是对节点进行分组，并且同一个标签的节点会放到一个集合中，这个有点类似上面说的对图进行分割。比如：给节点贴上一个“人”的标签，那么当对图进行搜索的时候，当指定“人”这个标签的时候，那么只会找到所有人的节点，而不会找到猫，狗等节点。这样可以提高图的遍历速度，而且可以更好的管理图的节点。

“A Traversal —navigates→ a Graph; it —identifies→ Paths —which order→ Nodes”

一个路径的遍历，它可以正确的导航整个图的结构遍历，并且它可以对应一系列路径，这些路径则是将所有节点串联起来。这个解释了搜索在图中的定位，一条搜索可以对应多条路径，也就是多条结果，而每个结果包含一系列节点。

“An Index —maps from→ Properties —to either→ Nodes or Relationships”

图中的建立索引的数据来自于节点和关系的属性，并且索引会直接映射到节点和关系。这样可以通过索引遍历图中的节点和关系，以得到结果。

“A Graph Database —manages a→ Graph and —also manages related→ Indexes”

这里明确的表示了图数据是干什么的，同时也表达了NEO4J是干什么的。他是管理和维护图数据CRUD，并且维护图数据的索引建立和更新。是对图数据操作的一个对外接口。