发帖
雷达卡
从学术上讲，图数据挖掘分为数据图，模式图两种。至于这两个类型的区别，由于很久没有关注这块，所以只能给出一个字面意义上的区别。数据图：则是以数据节点为基础来进行分析图，模式图：则是以数据整个关系模型来进行分析数据。可能解释存在错误，望指正。我之前主要是接触数据图一块的东西，模式图没有太多了解。关于数据图和模式图在学术界存在几个比较有参考意义的实现以及算法。数据图有：BANKS,BLINKS,Object rank;模式图有：DBXplorer(微软),DISCOVER(加利福尼亚大学)，S-CBR(人民大学，就是在大学学数据库都会知道的人：王珊)。下面主要对数据图的几种实现进行简单介绍，模式图，可以找上面相关论文进行了解。
二、数据图典型实现介绍 1、BANK
整体上说一下它的思想是通过关系数据库进行存储图结构的数据加上Dijkstra算法来进行数据的存储和图数据的搜索。该算法第一步先是先是匹配所有关键词的关键节点，并且以每个关键节点为源节点进行一次Dijkstra算法对图进行遍历，因此可以形成和每个关键节点可达的节点堆，该堆是进行了按照到关键节点距离进行堆排序的堆。因此可以想想每个关键节点的节点堆的第一个元素则是到该关键节点最近的节点。利用这个，那么对每个节点堆一次遍历，每次遍历只取堆的第一个节点，可以得知，这个取出的节点和节点对对应的关键词是可达的，如果这个节点和所有关键节点可达，那么就可以这个节点为根节点形成一个结果树，所以需要对这个取出的节点进行标记，标记的目的就是说我这个关键节点来过这里了(有点类似到此一游的感觉)。这就是BANK的大体上的算法思想。下面提出一个流程图，帮助大家理解一下。
2、算法
这个算法则是在第一个基础上面进行了扩展，支持双向搜索。从而解决了上麦年的第二个缺陷。具体算法实现，很久没接触了，而且当时也没关注这方面的实现，所以我也不是很清楚，只是知道它实现了双向遍历。具体的可以点击标题，看它的论文。
3、BLINK
这个实现是解决了大图问题，通过对图进行分割，形成超图的概念，加载内存只需要把超图进来，当需要遍历这个超图节点的时候，再将超图节点里面的明细节点加载到内存，基于这个概念可以很好的解决节点数量大而受内存的限制，这个算法有点类似地图的放大镜，当需要展示某一块(超图节点)的时候，则加载当前块的内容，用户就会看到更加明细的地图信息。具体算法，可以点击标题，看看它的论文。
既然说道图，那么不得不提一下在图数据库方面最流行的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”
京公网安备 11010802022788号
