图分析是知识图谱（Knowledge Graph）图结构消费的重要组成部分，基于图分析算法的应用近年来层出不穷，比如：Palantir利用关联分析指导复杂战场环境下的军事行动、天眼查发现企业关联关系、拓尔思水晶球、宜信金融反欺诈等等。
本文首先对图分析算法进行归纳总结，后期将结合现有的工具，详细介绍图分析每个算法的实现以及应用案例。
图度量
节点度量
| 节点度量 | 描述 | 参考资料 |
|---|---|---|
| 度中心性 Degree centrality |
与节点连接的数据量，如果是有向图，则分为入度和出度 | lecture |
| 介数中心性 Betweenness centrality |
指其它两个节点的所有最短路径都经过这个节点， 则这些所有最短路径数即为此节点的介数中心性。 可用来鉴别网络中的“信息中间人”或者聚类后的联结点 |
|
| 紧密中心性 Closeness centrality |
指节点到网络中所有其他节点的平均距离的倒数 | Sabidussi |
| 特征向量中心性 Eigenvector centrality |
指节点在网络中的重要程度，比PageRank更泛 | Newman |
| HITS Hpyerlink - Induced Topic Search |
使用(Hub, Authority)描述节点重要性- Hub 枢纽性，指包含了很多指向高质量 Authority页面链接的页面，如 hao123- Authority权威性，指与某个领域或者某个话题相关的 高质量网页，比如视频领域 youtobe- 两个假设： 1. 一个好的 Authority会被很多好的Hub指向2. 一个好的 Hub页面会指向很多好的Authority |
Kleinberg |
| Neighbordhood Connectivity | 给定节点的邻居的平均连通性（度中心性） | Maslov |
| Vertex Embeddedness | 给定节点的邻居的平均嵌入度 | Dong |
| Local Clustering Coefficient | 给定节点的邻居的现有连接数量除以邻居节点集合全部 可能的连接数量，用于衡量邻居节点的紧密程度 |
Watts |
边度量
| 边度量 | 描述 | 参考资料 |
|---|---|---|
| Adamic/Adar | 给定两个顶点的公共邻居中心度的倒数和 | Adamic |
| Common Neighbours | 给定两个顶点的公共邻居节点数量 | Newman |
图度量
| 图度量 | 描述 | 参考资料 |
|---|---|---|
| Freeman’s network centrality | 描述网络中节点度中心性的不均匀程度 | Freeman |
| Modularity | 网络分成社区（模块、集群）的强度 | lecture Newman |
社区发现
同一社区内的节点与节点之间的连接很紧密，而社区与社区之间的连接比较稀疏
社区发现主要面向非重叠社团发现和重叠社团发现两类问题。所谓重叠性，是指单个顶点并非仅仅属于一个社团，而是可以属于多个社团。社团与社团由这些有重叠归属的顶点相连。
- 非重叠社团发现算法
| 方法 | 描述 | 参考资料 |
|---|---|---|
| 基于模块度优化的社团发现 | 优化模块度Q值的算法 | - 采用聚合思想 FN CNM MSGMV - 采用分裂思想 GN 谱方法 - 直接寻优法 EO |
| 基于谱分析的社团发现 | 将节点对应的矩阵特征分量看 成空间坐标，将网络节点映射 到多维向量空间，运用传统的 聚类算法将他们聚集成社团 |
- |
| 基于信息论的社团发现 | 模拟退火优化算法和随机游走 | Rosvall Random Walks |
| 基于标签传播的社团发现 | 网络的边很多时候代表信息的传播 | LPA |
- 重叠社团发现算法
| 方法 | 描述 | 资料 |
|---|---|---|
| 基于团渗透改进的社团发现 | 以团为基本单元来发现重叠，这对于很多真 实网络尤其是稀疏网络而言，限制条件过于严 格，只能发现少量的重叠社团 |
CPM SCP |
| 基于种子扩散思想的社团发现 | 基本思想是以具有某种特征的子网络为种子， 通过合并、扩展等操作向邻接节点扩展，直至 获得评价函数最大的社团 |
LFM |
| 基于混合概率模型的社团发现 | 以概率方法对复杂网络的社团结构进行探索， 以求得期望最大的社团结构，从而避开社团定义的问题 |
Newman |
| 基于边聚类的社团发现 | 以边为研究对象 | Line Graphs, Link Partitions Yong-Yeol Ahn |
频繁子图挖掘
Frequent sub graph discovery is a process of identifying frequently occuring sub graphs from a set of graphs or a single large graph with frequency of occurrence is no less than a specified threshold.
频繁子图挖掘一般包含以下两种方法：Apriori-based 和 Pattern growth based
- Apriori-based
If a graph is frequent, all of its subgraphs are frequent.
| 方法 | 描述 | 参考资料 |
|---|---|---|
| AGM/AcGM | - | AGM |
| FSG | - | FSG |
| FFSM | - | FFSM1 FFSM2 |
- Pattern growth based
| 方法 | 描述 | 参考资料 |
|---|---|---|
| Subdue | 基于最小描述长度原则 MDL来发现子结构 - 定义：$S$是图$G$的一个子结构，$I(S)$表示子结构$S$的描述长度，$I(G|S)$表示在图$G$中使用单个顶点替换子结构$S$后得到的图的描述长度 - 寻找最优子结构：使得$I(S) = v\ bits + r\ bits + e\ bits$最小的子结构$S$，$S$即为频繁子图。 其中$v\ bits$表示表示编码图的顶点标签所需的$bit$位数： $$v\ bits = lg\ v + v\ lg\ l_u$$ $r\ bits$表示编码邻接矩阵$A$的各行所需的$bit$位数： $$r\ bits = lg(b+1) + \sum_{i=0}^v lg(b+1) \ +lg\ C(v,k_i)$$ 其中$b=max_ik_i$，$k_i$表示邻接矩阵$A$第$i$行中为$1$的个数 $e\ bits$表示编码邻接矩阵$A$中以$A[i,j]=1$所表示的边所需的$bit$位数： $$e\ bits=lg\ m\ +\ \sum_{i=1}^{v}\sum_{j=1}^{v} lg\ m + e(i,j)[1+lg\ l_u]$$ - 过程：初始枚举单节点最优子结构，然后由此进行迭代。在每次迭代中，算法选择最优子结构后，通过增加一个顶点扩展当前子结构，直到所有的最优子结构都被列出或者所需考虑的候选最优子结构数量达到一定限制 |
SUBDUE |
| gSpan | - | Xifeng Yan网站 |
| Gaston | - | Gaston网站 |
| CMTreeMiner | - | CMTreeMiner |
链接预测
通过已知的网络节点以及网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性 ，包括对未知链接的预测和未来链接的预测
- 基于相似性的链路预测 Similarity-based methods
假设两个节点之间相似性越大，它们之间存在链接的可能性就越大。如何定义节点之间的相似性成为基于节点相似性的链路预测方法的核心问题，根据不同的相似性度量方法，可将该类相似性指标分为基于局部信息的相似性指标、基于路径的相似性指标和基于随机游走的相似性指标
| 方法 | 描述 | 参考资料 |
|---|---|---|
| 基于局部信息的相似指标 | - 共同邻居 （CN） | - |
| 基于路径的相似性指标 | - | - |
| 基于随机游走的相似性指标 | - | - |
- 基于概率统计方法 Probabilistic and statistical method
基本思想是建立一个含有一组可调参数的模型，然后使用优化策略寻找最优的参数值，使得所得到的模型能够更好地再现真实网络的结构和关系特征，网络中两个未连边的节点对连边的概率就是等于在改组最优参数下它们之间产生连边的条件概率
| 方法 | 描述 | 参考资料 |
|---|---|---|
| 概率关系模型 PRMs | - | - |
| 有向无环概率实体关系模型 DAPER | - | - |
- 基于最大似然估计的链路预测
很多网络的连接可以看作某种内在的层次结构的反映
| 方法 | 描述 | 参考资料 |
|---|---|---|
| 层次结构模型 | - | - |
| 随机分块模型 | - | - |
