算法说明
算法原理
- MCE算法
MCE（Maximal Clique Enumeration，极大团）算法是在大规模图数据中，精确求解所有的极大团，其中极大团的定义如下：团是图中一个两两之间有边的顶点集合。如果一个团不被其他任何一个团包含，那么这个团即为极大团。
- WCE算法
WCE （Weak Clique Enumeration，弱团）是一种重叠社区发现的算法，在社交网络中是一个很重要的研究。所谓的弱团挖掘，即利用检测到的三角形结果，如果两个三角形有一条边是重叠的，则将两个三角形合并在一起，并递归的合并下去，最终到不能合并为止。
- Modularity算法
Modularity，模块度算法针对带有社区划分信息的图而言，该社区划分不存在重叠，可支持有向/无向图。模块度计算的目的是衡量对应社区划分在指定图上的质量，本质是衡量图中的边在社区内的分布与在整个图中分布的差异，越多比例的边分布在社区内部，对应社区划分在图上的模块度值就越大，社区划分的质量也就越高。模块度的计算基于图中节点的社区信息对边进行聚合，然后针对不同社区统计边的分布信息，最后得出模块度的值。
- TC算法
TC（Triangle Count，三角形计数）算法在大规模图数据计算领域，是社交网络分析的基本算法，可以计算出图网络中每个节点与其余节点形成的三角形个数，支撑数千万及上亿节点、十亿边数的无向网络图的三角形计数。
- MSSP算法
MSSP（Multiple Sources Shortest Path，多源最短路径）算法，是最短路径领域的基础算法，是指给定图数据集和指定部分节点，计算图中所有节点到给定节点的最短路径距离。
- PageRank算法
PageRank，网页排名算法是Google公司所使用的对其搜索引擎搜索结果中的网页进行排名的一种算法，也是图计算及推荐领域的基础算法。PageRank本质上是一种以网页之间的超链接个数和质量作为主要因素粗略地分析网页的重要性的算法。其基本假设是：更重要的页面往往更多地被其他页面引用（或称其他页面中会更多地加入通向该页面的超链接）。
- SCC算法
SCC（Strongly Connected Components，强联通分量）算法是图计算领域的基础算法。在有向图中，强连通图是指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图，即对于图上的每一个点对(Va, Vb )，都有Va→Vb以及Vb→Va。强连通分量则是指有向图的极大强连通子图。
- Louvain算法
Louvain算法作为一种以最大化模块度（Modularity）数值为目标函数的一种社区检测方法，具有社区检测效果好、速度快等特点。其主要通过贪心算法的策略，从底层不断聚合节点，每一次节点的聚合都选择能够使当前模块度增益最大的操作，从而最终达到社区划分结果在模块度评价指标上的最优解。
- LPA算法
LPA（Label Propagation，标签传播）算法是图分析领域的经典算法，主要利用邻居的标签信息在网络图中传播而进行非重叠社团划分。
- Closeness算法
Closeness，紧密中心性算法计算图中紧密中心性值最大的K个结点，支持有向图（含有/无权图，有权图要求输入边权值大于0）。紧密中心性计算的目的是衡量图中每个结点的与其它结点之间的接近程度，结点与其它结点的平均距离越短，则结点的紧密中心性值越大，结点在图中的重要性也就越高。紧密中心性的计算基于图中每个结点到其它所有结点的平均距离计算，然后得出每个结点的紧密中心性的值，最后选取图中紧密中心性值最大的K个结点，输出这K个结点的编号和紧密中心性值。
- CD算法
CD（Cycle Detection，环路检测）算法是图分析领域的基础算法，通常是在有向图中枚举出满足需求的所有环路。而在现实网络中，无约束的环很多，同时很大一部分环路信息是无用的，所以在本算法中，通过指定的约束条件，如环路长度约束、环路中边权重的约束，求解对应的环路信息。
- CC算法
CC（Connected Components，连通分量）算法是图计算领域的基础算法，用于求解无向图的所有连通分量。其中连通分量的定义如下：连通分量是指无向图中的极大连通子图，即子图中的任意点都可以通过边互相抵达，且与子图外的任意点不能互相抵达。本算法基于Spark计算引擎，精确求解所有连通分量。
- KCore算法
KCore（K-Core Decomposition，k核算法）对用户输入的图数据，精确求解图中各个节点coreness值。其中coreness值的定义如下：一个顶点属于k-core subgraph，但不属于(k+1)-core subgraph，则这个顶点的core number = k。k-core subgraph的定义如下：图G中的极大子图Gk，Gk中的所有顶点的度deg(v) ≥ k。
- Degree算法
Degree（Degree Centrality，度中心性）算法用于计算图中每个节点的度中心性值，支持无向图和有向图。度中心性是衡量节点重要性的重要指标，节点与其它节点的边越多，则节点的度中心性值越大，节点在图中的重要性也就越高。在无向图中，度中心性的计算是基于边信息统计节点出现次数，得出节点的度中心性的值，在有向图中则基于边的方向进行筛选，基于输入边或输出边信息统计节点出现次数，得到节点的入度值或出度值。
- BFS算法
BFS（Breadth-First-Search，广度优先搜索）算法，是图分析领域的基础算法，通过广度优先的方式对图进行搜索遍历直到达到最大搜索深度或访问完所有可达节点。
- ClusteringCoefficient算法
ClusteringCoefficient（聚集系数）算法是用来描述一个图中的顶点之间结集成团程度的系数。聚集系数分为全局，局部，平均三种。全局聚集系数可以给出一个图中全局的集聚程度的评估，而局部聚集系数则可以测量图中每一个结点附近的集聚程度，平均聚集系数则在局部聚集系数基础上给出整张图的聚集平均值。
- TrustRank（信任指数）
TrustRank（信任指数）算法，是PageRank算法的变种，基于以下理论假设：优质网站很少会链接到垃圾网站，反之则不成立。选定高质量种子节点，那么由“种子”节点指向的节点也可能是高质量节点，即其TrustRank也高，与“种子”节点的链接越远，节点的TrustRank越低。
- PPR（PersonalizedPageRank，个性化网页排名）
PPR（PersonalizedPageRank）算法，是图计算及推荐领域的基础算法，是指给定一份关系型数据和源节点，计算该节点对网络中其他节点的影响性。
- Betweenness（介数中心性）
Betweenness（介数中心性）算法计算图中介数中心性值最大的K个结点，是网络中心性重要的度量参数之一，同时也是图计算领域的基础算法。介数中心性算法的目的是衡量图中每一个结点与其它结点之间的互动程度，经过结点的最短路径数越多，该结点的介数中心性值越大，结点在图中的重要性也就越高。结点的介数中心性值是基于图中最短路径经过该结点的次数计算，最后选取图中介数中心性值最大的K个结点，输出这K个结点的编号和介数中心性值。
- Node2Vec
Node2vec算法是一种图表示学习算法，目的是将图中每一个节点v映射成一个d维向量。Node2vec算法生成的节点向量描述了图中每个节点与其它节点的临近程度，即在图中相近的节点的向量更相似。
- SubgraphMatching（子图匹配）
SubgraphMatching（子图匹配）算法是图分析算法中相似性度量的关键算法之一，其主要的功能是根据查询图的结构在目标数据图中搜索和匹配与查询图结构相同的子图，被广泛应用在图模式挖掘、图数据库查询等研究领域，也能够支持社团挖掘、团伙识别、商品推荐等应用场景。
使用场景
算法分类 |
算法名称 |
应用行业 |
||
|---|---|---|---|---|
运营商 |
金融 |
交通 |
||
图算法 |
WCE |
营销类服务（业务推荐：集团客户识别/集团业务推送） |
精准营销类（客户群体画像、个性化理财产品推荐/手机银行产品推荐、社交媒体营销效果预测） 智能风控类（团体欺诈识别） 基础服务类（全网用户群体细分） |
智能服务类（物流仓位推荐） |
MCE |
营销类服务（业务推荐：家庭套餐推荐/亲情号推荐） |
精准营销类（潜在VIP客户群体推荐） 智能风控类（团体欺诈识别） |
信息惠民类（共享单车投放推荐） |
|
TC |
维系类服务（携转客户预测、用户离网预测） |
智能风控类（信贷风险识别、客户违约预测） |
指挥管控类（交通站点流量预测、公交地铁站点流量监测、重点路段流量监测、重点道路拥堵识别） |
|
Modularity |
营销类服务（潜在集团群体亲密度细分） |
精准营销类（社交媒体营销效果预测） |
智能服务类（物流仓位推荐、物流资源配置与优化、物流供需分析） |
|
MSSP |
营销类服务（迁徙客户识别拉新） 合营类服务（交通-公交枢纽调度） |
精准营销类（客源获取渠道挖掘） 智能风控类（最短路触黑、资产转移查控） |
信息惠民类（交通知乎图谱-最优路线查询） 智能服务类（无人驾驶道路推荐，出行方式推荐，停车场推荐） 指挥管控类（警力动态部署） |
|
PageRank |
营销类服务（用户价值模型：高价值客户细分） 营销类服务（生命周期模型：风险用户细分） |
精准营销类（VIP客户推荐、社交媒体营销策略制定、广告精准投放、客户精准画像、理财产品推荐/手机银行产品推荐） 智能风控类（反欺诈评分、潜在拒贷用户识别、欺诈团伙核心成员识别、客户偿贷能力评估、账户风险评估） |
信息惠民类（交通知乎图谱--景点热点指数排序） 路网规划类（关键节点选址：公交地铁站点选址，天桥地下通道选址，安防监测选址，警示路牌选址） |
|
SCC |
基础类服务（全用户/全业务/全渠道：细分用户群） |
精准营销类（客户群体画像） 智能风控类（团体欺诈识别） 基础服务类（全网用户群体细分、社交媒体营销效果预测） |
智能服务类（物流仓位推荐） 路网规划类（车道方向优化） |
|
Louvain |
基础类服务（全用户/全业务/全渠道：细分用户群） |
精准营销类（客户群体画像、个性化理财产品推荐/手机银行产品推荐、社交媒体营销效果预测） 智能风控类（团体欺诈识别） 基础服务类（全网用户群体细分） |
指挥管控类（交通碰瓷团伙挖掘） 智能服务类（出行方式推荐，停车场推荐，物流仓位推荐，物流资源配置与优化，物流供需分析） 信息惠民类（出行群体分析） |
|
LPA |
维系类服务（携转客户预测、用户离网预测） |
精准营销类（新客户画像、个性化理财产品推荐/手机银行产品推荐、社交媒体营销效果预测、广告精准投放） 智能风控类（反欺诈评分、团体欺诈识别） 基础服务类（全网用户群体细分） |
信息惠民类（出行群体分析） 路网规划类（关键节点选址：公交地铁站点选址，天桥地下通道选址，安防监测选址，警示路牌选址） |
|
Closeness |
营销类服务（生命周期模型：不限量潜客识别、高风险客户细分） |
精准营销类（VIP客户推荐、社交媒体营销策略制定、广告精准投放、客户精准画像、理财产品推荐/手机银行产品推荐） 智能风控类（反欺诈评分、潜在拒贷用户识别、欺诈团伙核心成员识别、客户偿贷能力评估、账户风险评估） |
路网规划类（关键节点选址：公交地铁站点选址，天桥地下通道选址，安防监测选址，警示路牌选址） 指挥管控类（拥堵事件预测） |
|
CD |
合营类服务（金融-互金风险识别） |
智能风控类（循环担保识别、异常资金流追溯、资产转移查控） |
智能服务类（路径导航，出行方式推荐，无人驾驶道路推荐） |
|
CC |
基础类服务（全用户/全业务/全渠道：大颗粒用户分群） |
精准营销类（客户群体画像、个性化理财产品推荐/手机银行产品推荐、社交媒体营销效果预测） 智能风控类（团体欺诈识别） 基础服务类（全网用户群体细分） |
智能服务类（物流仓位推荐） 路网规划类（车道方向优化） |
|
KCore |
营销类服务（王卡用户模型：王卡感染用户挖掘、异网主卡用户反挖） 维系类服务（携转客户预测、用户离网预测） |
精准营销类（VIP客户群体推荐、客户群体画像） 智能风控类 |
路网规划类（关键节点选址：公交地铁站点选址，天桥地下通道选址，安防监测选址，警示路牌选址） 指挥管控类（拥堵事件预测） |
|
Degree |
营销类服务（内容推荐：数字广告发放） |
精准营销类（VIP客户推荐、社交媒体营销策略制定、广告精准投放、客户精准画像、理财产品推荐/手机银行产品推荐） 智能风控类（潜在拒贷用户识别、客户偿贷能力评估、账户风险评估） |
信息惠民类（共享单车投放推荐） 智能服务类（物流仓位推荐，物流资源配置与优化） |
|
BFS |
合营类服务（交通-人群流量预测、敏感旅客识别） |
精准营销类（客源获取渠道挖掘） 智能风控类（一度/二度触黑、资产转移查控） |
信息惠民类（交通知乎图谱--可达路线查询） 指挥管控类（公交地铁线路组合优化，目标车辆识别） |
|
ClusteringCoefficient |
维系类服务（携转客户预测、用户离网预测） |
智能风控类（信贷风险识别、客户违约预测） |
指挥管控类（交通站点流量预测） 智能服务类（物流仓位推荐，物流资源配置与优化，物流供需分析） |
|
TrustRank |
维系类服务（携转客户预测、用户离网预测） |
精准营销类（VIP客户推荐、社交媒体营销策略制定、广告精准投放、客户精准画像） 智能风控类（欺诈账户识别、潜在拒贷用户识别、客户偿贷能力评估） |
指挥管控类（拥堵站点预测） |
|
PPR |
营销类服务（王卡用户模型：王卡感染用户挖掘、异网主卡用户反挖） |
精准营销类（VIP客户推荐、社交媒体营销策略制定、个性化广告投放、客户精准画像、个性化理财产品推荐/手机银行产品推荐） 智能风控类（欺诈账户识别、潜在拒贷用户识别、客户偿贷能力评估） |
信息惠民类（交通知乎图谱--热点景点推荐） 路网规划类（关键节点选址：公交地铁站点选址，天桥地下通道选址，安防监测选址，警示路牌选址） |
|
Betweenness |
营销类服务（用户价值模型：异网高价值客户识别） 合营类服务（交通-公交枢纽调度；新零售：热点选址） |
精准营销类（VIP客户推荐、社交媒体营销策略制定、广告精准投放、客户精准画像、理财产品推荐/手机银行产品推荐） 智能风控类（反欺诈评分、潜在拒贷用户识别、欺诈团伙核心成员识别、客户偿贷能力评估、账户风险评估） |
路网规划类（关键节点选址：公交地铁站点选址，天桥地下通道选址，安防监测选址，警示路牌选址） 指挥管控类（城市交通网拥堵关键节点识别） |
|
Node2Vec |
维系类服务（携转客户预测、用户离网预测、用户续约预测） 合营类服务（金融-信贷风险识别） |
精准营销类（VIP客户推荐、客户群体画像、社交媒体营销策略制定、个性化广告投放、客户精准画像、个性化理财产品推荐/手机银行产品推荐、潜在VIP客户群体推荐、社交媒体营销效果预测） 智能风控类（反欺诈评分、潜在拒贷用户识别、欺诈团伙核心成员识别、客户偿贷能力评估、账户风险评估） 基础服务类（全网用户群体细分） |
指挥管控类（拥堵事件预测） 指挥管控类（交通站点流量预测） |
|
SubgraphMarching |
合营类服务（金融-信贷风险识别） |
精准营销类（精准客户推荐、广告精准投放、客户精准画像、社交媒体营销效果预测、理财产品推荐） 智能风控类（欺诈团伙核心成员识别、高风险账户识别、循环担保识别、异常资金流追溯、资产转移查控、一度/二度触黑） |
指挥管控类（重点车辆行为模式匹配） 路网规划类（道路优化与改建：拥堵路段识别，拥堵时段识别，道路设施损毁识别与维护） |
|