内置算法

此文档主要详细介绍了TuGraph内置的算法程序，社区版6种算法可参考基础算法报

简介

TuGraph目前包含以下6个基础算法28种扩展算法，共34个图算法：

基础算法包：

中文算法名	英文算法名	程序名
广度优先搜索	Breadth-First Search	bfs
网页排序	Pagerank	pagerank
单源最短路径	Single-Source Shortest Path	sssp
弱连通分量	Weakly Connected Components	wcc
平均集聚系数	Local Clustering Coefficient	lcc
标签传播	Label Propagation Algorithm	lpa

扩展算法包：

中文算法名	英文算法名	程序名
全对最短路径	All-Pair Shortest Path	apsp
介数中心度	Betweenness Centrality	bc
置信度传播	Belief Propagation	bp
距离中心度	Closeness Centrality	clce
共同邻居	Common Neighborhood	cn
度数关联度	Degree Correlation	dc
直径估计	Dimension Estimation	de
EgoNet算法	EgoNet	en
超链接主题搜索	Hyperlink-Induced Topic Search	hits
杰卡德系数	Jaccard Index	ji
K核算法	K-core	kcore
鲁汶社区发现	Louvain	louvain
多源最短路径	Multiple-source Shortest Paths	mssp
个性化网页排序	Personalized PageRank	ppr
强连通分量	Strongly Connected Components	scc
监听标签传播	Speaker-listener Label Propagation Algorithm	slpa
两点间最短路径	Single-Pair Shortest Path	spsp
三角计数	Triangle Counting	triangle
信任指数排名	Trustrank	trustrank
带权重的标签传播	Weighted Label Propagation Algorithm	wlpa
带权重的网页排序	Weighted Pagerank Algorithm	wpagerank
最大独立集算法	Maximal independent set	mis
sybil检测算法	Sybil Rank	sybilrank
子图匹配算法	Subgraph Isomorphism	subgraph_isomorphism
模式匹配算法	Motif	motif
k阶团计数算法	Kcliques	kcliques
k阶桁架计数算法	Ktruss	ktruss
莱顿算法	Leiden	leiden

基础算法包

广度优先搜索

广度优先搜索实现了Breadth-first Search算法，从根点开始，沿着图的宽度遍历所有可访问点。返回结果为遍历点个数。算法内容请参考 https://en.wikipedia.org/wiki/Breadth-first_search。

网页排序

网页排序程序实现了常用的Pagerank算法。该算法根据图中边和边权值计算所有点的重要性排名，PageRank值越高，表示该点在图中的重要性越高。计算时以点数量的倒数为各点初始Rank值，然后将点的Rank值按照出边平均传递到相邻点，重复该传递过程直到满足给定的收敛阈值或达到给定迭代轮数。每轮传递结束后，所有点的Rank值会有一定的的比例随机传递到任意点上。算法内容请参考 https://en.wikipedia.org/wiki/PageRank。

单源最短路径

单源最短路径实现了Single Source Shortest Path算法，根据给定的源点，计算从该源点出发到其他任意点的最短路径长度。算法内容请参考 https://en.wikipedia.org/wiki/Shortest_path_problem。

弱连通分量

弱连通分量程序实现了Weakly Connected Components算法，该算法会计算图中所有的弱连通分量。弱连通分量是图的一个子图，子图中任意两点之间均存在可达路径。算法内容请参考https://en.wikipedia.org/wiki/Connected_component_(graph_theory)。

平均集聚系数

平均集聚系数程序实现了Local Clustering Coefficient算法，计算图中点之间聚集程度的系数。返回结果包括整体集聚系数和点集聚系数。整体集聚系数反映了图中整体的集聚程度的评估，点集聚系数包括任意点的集聚系数，反映了该点附近的集聚程度。集聚系数越高，表示集聚程度越高。算法内容请参考https://en.wikipedia.org/wiki/Clustering_coefficient。

标签传播

标签传播算法程序实现了Label Propagation Algorithm算法。该算法是基于标签传播的社区发现算法，计算对象为无权图。在标签传递时，每个点对收到的所有标签进行次数累加，在累加和最高的标签中随机选择一个。迭代收敛或执行到给定轮数后算法终止。最终输出结果为每个点的标签，标签值相同的点视为在同一社区。算法内容请参考 https://en.wikipedia.org/wiki/Label_Propagation_Algorithm。

扩展算法包

全对最短路径

全对最短路径程序实现了All-Pair Shortest Path算法，计算图中任意两点间的最短路径。返回结果为任意存在路径的点对之间的最短路径长度。算法内容请参考https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm

介数中心度

介数中心度程序实现了Betweenness Centrality算法，估算图中所有点的介数中心度值。介数中心度值反映了图中任一最短路径经过该点的可能性，值越高表示有越多的最短路径经过了该点。计算时需给定抽样点个数，分别以这些抽样点为中心进行计算。算法内容请参考https://en.wikipedia.org/wiki/Betweenness_centrality。

置信度传播

置信度传播程序实现了Belief Propagation算法。该算法给定已观测点的边缘分布，利用点之间相互传递消息的机制来估算未观测点的边缘分布。算法内容请参考https://en.wikipedia.org/wiki/Belief_propagation。

距离中心度

距离中心度程序实现了Closeness Centrality算法，估算任意点到图中其他点的最短路径的平均长度。距离中心度越小，表示该点到其他点的平均最短距离最小，意味着该点从几何角度看更位于图的中心位置。计算时需要给定抽样点个数，分别以这些抽样点为中心进行计算。算法内容请参考https://en.wikipedia.org/wiki/Closeness_centrality。

共同邻居

共同邻居程序实现了Common Neighborhood算法，计算任意给定相邻点对之间的共同邻居数量。计算时给定待查询的若干个点对，返回结果为待查询的任意点对的共同邻居数量。

度数关联度

度数关联度程序实现了Degree Correlation算法，通过计算任意相邻点对之间的Pearson关联系数来计算图的度数关联度，可用来表征图中高度数点之间关联程度。度数关联度越高，表示图中高度数点之间的关联程度越高。算法内容请参考https://en.wikipedia.org/wiki/Pearson_correlation_coefficient

直径估计

直径估计程序实现了Dimension Estimation算法。该算法会计算图中最长的最短路径长度，用来表征图的直径大小。算法内容请参考http://mathworld.wolfram.com/GraphDiameter.html。

EgoNet算法

EgoNet算法需要给定根点和K值，以根点为源点进行宽度优先搜索，找出所有K度以内的邻居组成的子图。找到的子图称为根点的EgoNet。

超链接主题搜索

超链接主题搜索算法实现了Hyperlink-Induced Topic Search算法，该算法假定每个点具有权威性Authority和枢纽性Hub两个属性，一个好的枢纽点应该指向许多高权威性的点，而一个良好的权威点应该被许多高枢纽型的点指向。算法将返回每个点的权威性值和枢纽性值。算法内容请参考https://en.wikipedia.org/wiki/HITS_algorithm。

杰卡德系数

杰卡德系数程序实现了Jaccard Index算法。该算法计算了给定点对之间的Jaccard系数，可用来表示这两个点的相似度。Jaccard系数越高，表示点对之间的相似程度越高。计算时给定带查询的若干点对，返回结果为这些点对的Jaccard系数。算法内容请参考https://en.wikipedia.org/wiki/Jaccard_index。

k核算法

k核算法实现了k-core算法。该算法计算所有点的核数，或找出图中所有的K核子图。K核子图是一种特殊子图，子图中任意点度数都不小于给定K值。算法内容请参考 https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)。

鲁汶社区发现

鲁汶社区发现程序实现了Fast-unfolding算法。该算法是基于模块度的社区发现算法，通过不断合并点社区来最大化图的模块度，能够发现层次性的社区结构。算法内容请参考 https://en.wikipedia.org/wiki/Louvain_Modularity。

多源最短路径

多源最短路径程序实现了Multiple-source Shortest Paths算法，根据给定的多个源点，从这些源点出发，计算到达任意点的最短路径值。其中，多个源点到某一点的最短路径值为分别从每个源点出发到达该点的最短路径的最小值。算法内容请参考 https://en.wikipedia.org/wiki/Shortest_path_problem。

个性化网页排序

个性化网页排序程序实现了Personalized PageRank算法。该算法根据给定的源点，基于该源点个性化计算所有点对于源点的重要性排名。Rank值越高，表示该点对于源点越重要。与PageRank不同的是，初始化时源点Rank值为1，其余点Rank值为0；并且每轮传递结束后，Rank值会有一定的比例随即传递回源点。算法内容请参考 https://cs.stanford.edu/people/plofgren/Fast-PPR_KDD_Talk.pdf。

强连通分量

强连通分量程序实现了Strongly Connected Components算法。该算法计算了图中所有的强连通分量，强连通分量是图的一个子图，子图中可从任意点出发到达其他任意点。算法内容请参考https://en.wikipedia.org/wiki/Strongly_connected_component。

监听标签传播

监听标签传播算法程序实现了Speaker-listener Label Propagation Algorithm算法。该算法是基于标签传播和历史标签记录的社区发现算法，是对标签传播算法的扩展。与标签传播算法不同的是，本算法会对所有点记录其历史标签，在迭代中对标签进行累加时，会将历史标签也计算在内。最终输出结果为每个点的所有历史标签记录。算法内容请参考论文：“SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process”。

两点间最短路径

两点间最短路径程序实现了Bidirectional Breadth-First Search算法，在有向无权图上从起点沿着出边做正向宽度优先搜搜，从终点沿着入边做反向宽度优先搜索，通过起点和终点共同遍历到的点来确定从起点到终点的最短路径长度。算法内容请参考https://en.wikipedia.org/wiki/Bidirectional_search。

三角计数

三角计数实现了Triangle-counting算法，计算无向图中的三角形个数，可用来表征图中点的关联程度。三角形数越多，表示图中点的关联程度越高。算法内容请参考论文：“Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study” 。

信任指数排名

信任指数排名算法实现了Trustrank算法，可以根据给定的白名单，计算任意点的信任指数。信任指数越高，表示该点为非法点的可能性越小。算法内容请参考 https://en.wikipedia.org/wiki/TrustRank。

带权重的标签传播

带权重的标签传播算法程序实现了Weighted Label Propagation Algorithm算法。=与标签传播算法不同的是，标签的传递跟边的权重相关，在标签传递时，每个点会根据标签的入边进行权重累加，在累加和最高的标签中随机选择一个。算法内容请参考 https://en.wikipedia.org/wiki/Label_Propagation_Algorithm。

带权重的网页排序

带权重的网页排序算法程序实现了Weighted Pagerank算法。与PageRank算法不同的是，Rank值的传递跟边的权重有关，点的Rank值将按照边权重加权传递到相邻点。算法内容请参考https://en.wikipedia.org/wiki/PageRank。

最大独立集算法

最大独立集算法实现了Maximal independent set算法。最大独立集是指在这个独立集之外没有可以加入它的点。一个图可能有许多大小差异很大的 MIS，算法找出其中一个。算法内容请参考 https://en.wikipedia.org/wiki/Maximal_independent_set#Sequential_algorithm。

Sybil检测算法

Sybil检测算法实现了Sybil Rank算法。SybilRank算法从非Sybil节点开始进行提前终止的随机游走。算法内容请参考论文：“Aiding the Detection of Fake Accounts in Large Scale Social Online Services”。

子图匹配算法

子图匹配算法实现了subgraph_isomorphism算法。subgraph_isomorphism算法对全图所有节点匹配子图，最后输出每个节点被匹配的次数。算法内容参考 https://www.jsjkx.com/CN/article/openArticlePDF.jsp?id=18105

模式匹配算法

模式匹配算法实现了motif算法。motif算法对指定的节点匹配k阶子图，最后输出每个指定节点每种k阶子图个数，每个k阶子图用一个64位整数表示，整数的第$i \times k + j$位为1表示子图中有边i->j。算法内容参考 https://en.wikipedia.org/wiki/Network_motif#mfinder

k阶团计数算法

k阶团计数算法实现了k-cliques算法。k-cliques算法对计算图中所有的k阶完全子图的个数，最后输出每个节点所在的k阶完全子图个数。算法内容参考 https://en.wikipedia.org/wiki/Clique_problem#Cliques_of_fixed_size

k阶桁架计数算法

k阶桁架计数算法实现了k-truss算法。k-truss指每条边都至少是k-2个三角形的边的子图。k-truss算法找出图的k-truss子图，最后输出每个节点在子图中的邻居节点列表。算法内容参考 https://louridas.github.io/rwa/assignments/finding-trusses/

莱顿算法

莱顿算法实现了了leiden算法。leiden算法是基于模块度的社区发现算法，与louvain算法优势在于leiden算法检测出社区中的断链，保证每个社区具有良好的连通性。算法内容参考 https://www.nature.com/articles/s41598-019-41695-z#Sec4