2.2.6　图计算

1. 图计算的概念

图（graph）可以是一个网络、一棵树、一个RDBMS或一个系数矩阵，它将数据信息中的实体抽象标示为各个顶点，顶点间的关系用以描述实体间的存在关系。像微信和微博这类社交软件所携带的数据，天生就适合于用图的方式表示。图计算就是主要针对图结构数据进行处理和针对性优化的技术（见图2-10）。

2. 图计算的实现方式

（1）网页排名

网页排名（PageRank）是Google公司提出的对搜索引擎显示的搜索结果中的网页进行排序的一种算法。它是一种以网页质量和网页间的超链接个数作为衡量标准，粗略分析网页重要性的算法。其理念就是，通常重要程度更高的网页会更多地被其他网页所引用，也就意味着会有更多的超链接存在。通过网页排名的方式，用户最需要的网页会拥有最高的优先级，在网页中优先被展示。

（2）最短路径

最短路径就是拥有最小权重的路径。根据不同的问题，可以选取不同的算法进行解决。例如，确定起点的最短路径问题，即已知起始节点，适合使用Dijkstra算法；全局最短路径问题，即求图中所有的最短路径，适合使用Floyd-Warshall算法。

（3）推荐算法（ALS）

推荐算法（ALS）是一种矩阵分解算法。例如，如果一个社交网站想要向用户推荐文章，它就需要知道哪些用户对哪些标题感兴趣。在这种情况下，如果用户阅读过的分类是1，而用户从未浏览过的分类是0，就可以通过ALS构造矩阵图。此种方法需要我们计算推理出哪些0是有可能变成1的。

（4）HCGraph算法

HCGraph（异构共识图）让临近的具备TEE（Trusted Execution Environment，可信执行环境）运行环境的节点互相验证对方的可信度，并将所收集到的可信节点信息在已获得其信任的其他节点间传播。HCGraph算法可以应用在区块链技术当中，帮助降低TEE的使用难度。它让邻近的节点相互验证信任度，利用不同的TEE协议收集逻辑相邻节点的可信状态信息，之后使用Gossip协议传递可信状态信息，即建立信誉关系网络，最后利用本地TEE环境执行合约代码。一旦存在某个节点要发出错误信息，其周围节点都会及时指正信息错误，若此节点周围还存在恶意节点向辅助节点发送错误信息，则必须连同此节点周围的所有节点一同辅助，否则错误信息必定会被指正。HCGraph算法可以遍历并寻找网络中“难撒谎点”的位置信息，并为这些点分发智能合约程序，从而创造理想的智能合约运行环境。

3. 图计算的应用

在许多实际场合中，我们都能找到图计算的应用。图计算是用于挖掘人、物和数据信息中所包含的实体之间不易被观察到的潜在关系的，可以根据每个节点的传播影响力PageRank分析得到相应结果。

图计算应用领域十分广泛，尤其在金融、电子商务、社交软件等热门领域都扮演着重要角色。图2-11显示了图计算分别在上述3个领域的应用实例。例如，在手机社交游戏领域实现基于用户数据的运营商精准推荐功能；在电子商务领域实现基于用户浏览记录的商品实时推荐功能；在金融领域实现基于交易记录的金融关系图的欺诈检测、风险排名等功能。

（1）运营商精准推荐

新注册账号的用户，可以以快速更新的朋友圈作为数据源，以用户为节点，相同tag为节点间连线，从而构建兴趣图结构，通过图计算分析邻居节点的兴趣点，从而向用户推荐符合其兴趣和需求的数据内容。

（2）商品实时推荐

用户的浏览记录中，以快速更新的兴趣和商品图作为数据源，通过图计算分析邻居节点，从而实现针对用户的商品实时推荐。

（3）金融业的实时监测

在金融行业中，多种变量（如交易账号、交易内容、交易金额）之间的关系可以通过图直观地表示出来，通过对图结构的分析和计算，推算其结果对金融安全的影响，典型的金融异构系统如洗钱交易、庞氏骗局等，都能在图结构中有所反映。

在新交易记录产生时，快速更新金融关系网，通过转账记录组成图结构，从而构建各个节点的关系网络，分析得到节点的风险排序和网络体系的欺诈检测结果。