图算法—杰卡德相似度_杰卡德算法

图算法—杰卡德相似度

1.图算法

图是一种表示两两对象之间的抽象数据结构，使用顶点与边进行表示，图计算就是在基于图数据上进行有目的性和针对性的计算过程，指解决一系列问题和发现潜在的数据价值，而图算法是图计算中用于解决指定问题的核心。

2.相似度算法-杰卡德

杰卡德相似度使用杰卡德系数（Jaccard Index）进行衡量，用于比较有限样本集之间的相似性与差异性。杰卡德系数值越大，样本相似度越高。杰卡德系数的计算公式如下：

3.图数据应用

图数据中，顶点与顶点之间采用边的方式连接，那么任意一个顶点的邻接顶点可看为其可比较的有限样本集。

如图上所示，该图是一个有向图，可以按照方向来计算顶点之间的相似程度。
计算顶点1和顶点2的相似度：

1. out: V(1)={2,4,5,6}，V(2)={3,4}
   
2. in：V(1)={4}，V(2)={1,4}
   
3. both：V(1)={2,4,5,6}，V(2)={1,3,4}
   
   以上针对不同方向的邻接点，对指定两个顶点的相似度进行了度量。
   在图数据计算中，一般而言，只会针对某个标签下顶点进行相似度度量，此时，我们可以选择度量所有维度，也可以选择指定维度进行比较（即按照边类型进行筛选），达到我们所需要的业务场景要求。

4.总结

杰卡德相似度算法是图论相似度中一种简单，执行效率高，针对行为分析和推荐是一种精确度比较高的算法，该算法可单机实现，也非常容易扩展到分布式系统，对于超大图某类标签顶点的相似度度量，分布式实现可分为单源杰卡德相似度和all pairs-杰卡德相似度。