2.1.2　图计算的适用场景

图计算的适用场景非常广泛。在早期阶段，图计算仅限于学术界以及工业界资深的研究机构内部，随着计算机体系架构的发展，图计算在更广泛的行业和场景中得到应用。按照时间维度大体可以把图计算的发展及适用范围分为如下几个阶段。

·20世纪50—60年代：最短路径算法、随机图理论研究、早期交易系统IBM IMS。

·20世纪80—90年代：图标签、逻辑数据模型、对象数据库、关系型数据库的关系模型等。

·20世纪90年代中叶至21世纪前10年：互联网索引技术、网页搜索引擎。

·21世纪第2个10年：最早的图数据库出现、大数据与NoSQL的蓬勃发展、各类图计算框架及多模式数据库的涌现、社交网络的爆发及社交网络分析。

·21世纪第3个10年：更广泛的业务场景、创新场景对于图计算及高性能图数据库的应用。

图计算在过去半个多世纪的发展是伴随着其他主流技术的发展而不断迭代的。以最著名的Dijkstra最短路径算法为例，它是位于荷兰阿姆斯特丹的数学中心于1955—1956年间构造的第三代计算机ARMAC，而该机构唯一的计算机程序员迪杰斯特拉在思考荷兰的两座城市鹿特丹与格罗宁根之间的最短路径问题时仅用了20min就想到了解决方案（一种典型的带权重的有向图中的广度优先算法），并在ARMAC上编程验证其算法的准确性（见图2-13）。该最短路径算法在寻路、交通、导航、路径及资源规划等场景中广泛应用。

事实上，解决最短路径问题不仅仅局限于Dijkstra算法，还有如Bellman-Ford算法（1955—1959年）、A*算法（著名的A星算法，1968年）、Floyd-Warshall算法（1962年）、Johnson's算法（1977年）等。

以A*算法为例，它是1968年国际斯坦福研究所（SRI International）在研制世界上第一个“通用”移动机器人（the shakey project）时发明的“寻路”算法，属于Dijkstra算法的延展算法。而这些算法所解决的都属于典型的动态规划（Dynamic Programming,DP）问题。在管理科学、经济学、信息生物学、航空航天等领域大量使用动态规划来解决问题，简而言之就是把原始、复杂的问题拆分为较为简单的问题，以某种“递归”的方式解决，在这个过程中找到“最优解”，例如旅行时间最小化、利润最大化、效用最大化等。在动态规划中最核心的是动态规划方程或称贝尔曼方程（bellman equation），有兴趣的读者可以深入研究。

图标号（graph labeling）源自Alexander Rosa在1967年发表的一篇论文。我们可以简单理解为对图中的点、边进行了标识赋值，例如对顶点、边进行具有唯一性的整数赋值，如图2-14所示。

这种整型赋值的方式对于人类而言显然是不友好的，因为我们很快就会无法区分到底1～5指的是顶点还是边，所以图上的标号被扩展为支持字符串（在存储数据结构上依然可以对应整数值以获得更高的存储、索引与计算效率），如图2-15所示。

图标号的应用场景随着图计算与图数据库的发展变得随处可见。在早期，它最知名的应用场景是地图上色。当我们把地图中的不同国家抽象为点或边的时候，相邻的顶点采用不同的颜色，相邻的边也采用不同的颜色以示区分。另外一个典型的应用场景是使用标签来参与计算的图算法，例如标签传播算法（LPA）、鲁汶社区识别算法以及带权重（标签）的全图出入度计算等。在第4章中会更详细地介绍图标号的应用。

图论的一个重要分支是网络理论，在第1章中提到的欧拉对于哥尼斯堡七桥的证伪问题就是网络理论最早的证明。网络理论的应用场景非常广泛，从各种网络分析到网络优化场景，例如社会网络分析、生物网络分析、鲁棒性分析、中心性分析、链接性分析等。网页排名算法就是典型的网络链接分析，例如谷歌搜索引擎中核心算法之一的网页排序PageRank（PR）算法、社交及金融反欺诈中的SybilRank排序算法等。

谷歌的PageRank算法把Web上所有网页作为顶点，把网页间的超链接作为边，通过计算每个节点的权重值来表达每个网页的重要性，权重值大小通过当前节点的入边及入边所关联的顶点的权重递归计算而得出。PR算法公式如下：

其中，d为阻尼系数，取值范围为0.1～0.15；n为所有页面数；L(j)为页面的出链数。在有的PR算法公式中，d也可能被设为0.85（相当于对d=0.15取余）。为了方便计算，所有网页的初始PR值为1且每次迭代中全部的网页节点都参与计算，在经过足够多次的迭代后（例如5次），PR值会稳定（收敛）下来，也就是说更多次的迭代并没有意义。很多图算法都有类似的特点，例如社区识别中的鲁汶算法，虽然比PR算法的计算复杂度要大得多，但也可以经过一定次数的迭代后让模块化度（louvain modularity）产生收敛。在满足业务需求的精度条件下运行最少次数的迭代来获得图算法结果（输出参数）是图计算的一个重要特点。

在图计算逐步融入图数据库后，其应用场景得到了大范围的增加，本节简要罗列一下不同行业的应用（图2-16），在后面的章节中会详细地介绍其中一些应用场景和实现原理。

·反欺诈：金融行业为主、全行业适用。

·反洗钱：金融监管、银行、大型企业。

·风控：全行业适用。

·金融风险管理：信用风险、交易风险、操作风险、风险偏好、量化、科技风险、风险战略、合规与审计、风险穿透与预警等，多行业适用（以金融行业最为显著）。

·资债管理、流动性管理等：银行、财务公司等。

·商务智能、实时决策系统等：全行业适用。

·基于多源数据的图谱分析系统等：全行业适用。

·智能营销、推荐系统、客服机器人：全行业适用。

·药物研制分析：生物制药。

·潮流分析：电力行业。

·网络监控：运营商与公有云服务商等。

以上面提到的金融风险为例，有学者已经把风险管理在管理理论层面进行了归类与划分。中国人民大学财政金融学院的陈忠阳教授把金融行业的风险管理分为如图2-17所示的12个子类。

风险的本质是与（收入、回报）预期的偏离和不确定性，而这种偏离和不确定性是需要尽可能地进行量化穿透、精准计量，以及场景模拟和压力测试的。这也是图计算相较于之前的传统风险管理技术手段更具有优势的地方。 KdYA8Ax+07GkqfNhGkaaHUkOrE1uYtO+pIEJn/KTjt4A5bIWFm++QBCIPAMb6Chu