类库方法

Gelly拥有越来越多的图算法，可以轻松分析大规模图形。

只需run()在输入图上调用方法即可使用Gelly的库方法：

  1. ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
  3. Graph<Long, Long, NullValue> graph = ...
  5. // run Label Propagation for 30 iterations to detect communities on the input graph
  6. DataSet<Vertex<Long, Long>> verticesWithCommunity = graph.run(new LabelPropagation<Long>(30));
  8. // print the result
  9. verticesWithCommunity.print();
  1. val env = ExecutionEnvironment.getExecutionEnvironment
  3. val graph: Graph[java.lang.Long, java.lang.Long, NullValue] = ...
  5. // run Label Propagation for 30 iterations to detect communities on the input graph
  6. val verticesWithCommunity = graph.run(new LabelPropagation[java.lang.Long, java.lang.Long, NullValue](30))
  8. // print the result
  9. verticesWithCommunity.print()

社区检测

概览

在图论中，社区指的是内部连接良好但与其他组稀疏连接的节点组。该库方法是在大型网络中实现实时社区检测的论文中描述的社区检测算法的实现。

细节

该算法使用分散 - 聚集迭代来实现。最初，每个顶点都分配一个Tuple2包含其初始值以及等于1.0的分数。在每次迭代中，顶点将其标签和分数发送给它们的邻居。在从其邻居接收消息时，顶点选择具有最高分数的标签，并随后使用边缘值，用户定义的跳跃衰减参数delta和超级步数对其进行重新分数。当顶点不再更新其值或达到最大迭代次数时，算法会收敛。

用法

该算法将Graph任何顶点类型，Long顶点值和Double边缘值作为输入a 。它返回Graph与输入相同的类型，其中顶点值对应于社区标签，即如果它们具有相同的顶点值，则两个顶点属于同一社区。构造函数有两个参数：

  • maxIterations：要运行的最大迭代次数。
  • delta：跳跃衰减参数，默认值为0.5。

标签传播

概览

这是本文中描述的众所周知的标签传播算法的实现。该算法通过在邻居之间迭代地传播标签来发现图中的社区。与社区检测库方法不同，此实现不使用与标签关联的分数。

细节

该算法使用分散 - 聚集迭代来实现。标签应为类型Comparable，并使用输入的顶点值进行初始化Graph。该算法通过传播标签迭代地细化发现的社区。在每次迭代中，顶点采用其邻居标签中最常见的标签。如果出现平局（即两个或多个标签出现频率相同），算法会选择更大的标签。当没有顶点改变其值或达到最大迭代次数时，算法收敛。请注意，不同的初始化可能会导致不同的结果。

用法

该算法需要输入一个Graph具有Comparable顶点型，Comparable顶点值类型和任意边缘值类型。它返回一个DataSet顶点，其中顶点值对应于此顶点在收敛后所属的社区。构造函数有一个参数：

  • maxIterations：要运行的最大迭代次数。

连接组件

概览

这是弱连通组件算法的实现。在收敛时，如果存在从一个到另一个的路径，则两个顶点属于同一组件，而不考虑边缘方向。

细节

该算法使用分散 - 聚集迭代来实现。该实现使用可比较的顶点值作为初始组件标识符（ID）。顶点在每次迭代中传播其当前值。在从其邻居接收到组件ID时，如果顶点的值低于其当前组件ID，则顶点采用新组件ID。当顶点不再更新其组件ID值或达到最大迭代次数时，算法会收敛。

用法

结果是一个DataSet顶点，其中顶点值对应于指定的组件。构造函数有一个参数：

  • maxIterations：要运行的最大迭代次数。

GSA连接组件

概览

这是弱连通组件算法的实现。在收敛时，如果存在从一个到另一个的路径，则两个顶点属于同一组件，而不考虑边缘方向。

细节

该算法使用collect-sum-apply迭代实现。该实现使用可比较的顶点值作为初始组件标识符（ID）。在聚集阶段，每个顶点收集其相邻顶点的顶点值。在总和阶段，选择这些值中的最小值。在应用阶段，算法将最小值设置为新顶点值（如果它小于当前值）。当顶点不再更新其组件ID值或达到最大迭代次数时，算法会收敛。

用法

结果是一个DataSet顶点，其中顶点值对应于指定的组件。构造函数有一个参数：

  • maxIterations：要运行的最大迭代次数。

单源最短路径

概览

加权图的单源最短路径算法的实现。给定源顶点，算法计算从该源到图中所有其他节点的最短路径。

细节

该算法使用分散 - 聚集迭代来实现。在每次迭代中，顶点向其邻居发送一条消息，该消息包含其当前距离和连接该顶点与邻居的边缘权重之和。在接收候选距离消息时，顶点计算最小距离，并且如果已发现较短路径，则其更新其值。如果顶点在超级步骤期间没有改变其值，则它不会为其下一个超级步的邻居生成消息。计算在指定的最大超级数之后或没有值更新时终止。

用法

该算法将Graph任何顶点类型和Double边值视为输入a 。顶点值可以是任何类型，并且此算法不使用。顶点类型必须实现equals()。输出是DataSet顶点的顶点，其中顶点值对应于距给定源顶点的最小距离。构造函数有两个参数：

  • srcVertexId 源顶点的顶点ID。
  • maxIterations：要运行的最大迭代次数。

GSA单源最短路径

该算法使用collect-sum-apply迭代实现。

有关实现详细信息和用法信息，请参阅单源最短路径库方法。

三角枚举器

概览

此库方法枚举输入图中存在的唯一三角形。三角形由三条边连接，三条边相互连接。此实现忽略边缘方向。

细节

基本三角形枚举算法将共享共同顶点的所有边组合并构建三元组，即由两条边连接的顶点三元组。然后，过滤所有三元组，其中不存在关闭三角形的第三条边。对于共享公共顶点的一组n条边，构建的三元组的数量是二次的（（n *（n-1））/ 2）。因此，算法的优化是将具有较小输出程度的顶点上的边分组以Reduce三元组的数量。该实现通过计算边缘顶点的输出度和在具有较小度数的顶点上的边缘上进行分组来扩展基本算法。

用法

该算法需要有向图作为输入，并且输出DataSet的Tuple3。顶点ID类型必须是Comparable。每个Tuple3对应一个三角形，其中的字段包含形成三角形的顶点的ID。

概要

概览

摘要算法通过基于顶点和边的值对顶点和边进行分组来计算输入图的压缩版本。通过这种方式，该算法有助于发现有关图中模式和分布的见解。一个可能的用例是社区的可视化，其中整个图形太大并且需要基于存储在顶点处的社区标识符来概括。

细节

在结果图中，每个顶点表示一组共享相同值的顶点。将顶点与其自身连接起来的边表示具有相同边缘值的所有边，这些边连接来自同一顶点组的顶点。输出图中不同顶点之间的边表示输入图中不同顶点组的成员之间具有相同边值的所有边。

该算法使用Flink数据 算子实现。首先，顶点按其值分组，并从每个组中选择代表。对于任何边缘，源和目标顶点标识符将替换为相应的代表，并按源，目标和边缘值分组。输出顶点和边缘是从其相应的分组创建的。

用法

该算法将有向的，顶点（可能是边缘）属性图作为输入并输出新图，其中每个顶点表示一组顶点，每个边表示来自输入图的一组边。此外，输出图中的每个顶点和边都存储公共组值和表示数据元的数量。

聚类

平均聚类系数

概览

平均聚类系数测量图的平均连通性。得分范围从0.0（邻居之间没有边缘）到1.0（完整图表）。

细节

有关聚类系数的详细说明，请参阅Local Clustering Coefficient库方法。平均聚类系数是具有至少两个邻居的所有顶点上的局部聚类系数得分的平均值。每个顶点与度数无关，对于该分数具有相同的权重。

用法

提供定向和无向变体。分析采用简单的图形作为输入和输出，AnalyticResult包含图形的顶点总数和平均聚类系数。图形ID类型必须为Comparable和Copyable。

  • setParallelism：覆盖处理少量数据的 算子的并行性

全局聚类系数

概览

全局聚类系数测量图的连通性。得分范围从0.0（邻居之间没有边缘）到1.0（完整图表）。

细节

有关聚类系数的详细说明，请参阅Local Clustering Coefficient库方法。全局聚类系数是整个图上连接的邻居的比率。具有较高度数的顶点对于该分数具有更大的权重，因为邻居对的计数在度数上是二次的。

用法

提供定向和无向变体。分析采用简单的图形作为输入和输出，AnalyticResult包含图形中三元组和三角形的总数。结果类提供了一种计算全局聚类系数得分的方法。图形ID类型必须为Comparable和Copyable。

  • setParallelism：覆盖处理少量数据的 算子的并行性

局部聚类系数

概览

局部聚类系数测量每个顶点邻域的连通性。分数范围从0.0（邻居之间没有边缘）到1.0（邻居是一个集团）。

细节

顶点的邻居之间的边是三角形。计算邻居之间的边缘等同于计算包括顶点的三角形的数量。聚类系数得分是邻居之间的边数除以邻居之间的潜在边数。

有关三角形枚举的详细说明，请参阅三角形列表库方法。

用法

提供定向和无向变体。这些算法以一个简单的图形作为输入，并输出一个DataSet的UnaryResult包含顶点ID，顶点度，以及含有该顶点的三角形的数量。结果类提供了一种计算局部聚类系数得分的方法。图形ID类型必须为Comparable和Copyable。

  • setIncludeZeroDegreeVertices：包含度数为零的顶点的结果
  • setParallelism：覆盖处理少量数据的 算子的并行性

三位一体人口普查

概览

三元组由图中的任意三个顶点形成。每个三元组包含三对顶点，可以连接或不连接。所述三元普查计数与所述图中的每个类型三联体的出现。

细节

此分析通过计算三角形列表中的三角形并运行“ 顶点度量”以获取三元组和边的数量，对四个无向三元组类型（由0,1,2或3个连接边形成）或16个有向三元组类型进行计数。然后从三元组计数中扣除三角形计数，并从边缘计数中删除三角形和三元组计数。

用法

提供定向和无向变体。分析采用简单的图形作为输入，并输出一个AnalyticResult访问器方法，用于查询每个三元组类型的计数。图形ID类型必须为Comparable和Copyable。

  • setParallelism：覆盖处理少量数据的 算子的并行性

三角形清单

概览

枚举图中的所有三角形。三角形由三个边连接三个顶点组成3个小团。

细节

通过将三元组端点上的边连接开放三元组（具有公共邻居的两条边）来列出三角形。此实现使用Schank算法的优化来提高高度顶点的性能。三重峰是从最低度顶点生成的，因为每个三角形只需要列出一次。这极大地Reduce了生成的三元组的数量，这三元组的顶点度是二次的。

用法

提供定向和无向变体。这些算法以一个简单的图形作为输入，并输出一个DataSet的TertiaryResult含有三个三角形顶点，并且对于定向算法，一个位掩码标记每个连接的三个顶点的六个潜在的边缘。图形ID类型必须为Comparable和Copyable。

  • setParallelism：覆盖处理少量数据的 算子的并行性
  • setSortTriangleVertices：规范化三角形列表，使得对于每个结果（K0，K1，K2），顶点ID被排序K0

链接分析

超链接引发的主题搜索

概览

超链接引发的主题搜索（HITS或“集线器和权限”）计算有向图中每个顶点的两个相互依赖的分数。良好的 Hub是那些指向许多良好权威的 Hub，而良好的权威则是许多优秀 Hub所指向的。

细节

为每个顶点分配相同的初始中心和权限分数。然后算法迭代地更新分数直到终止。在每次迭代期间，根据权威分数计算新的中心分数，然后根据新的中心分数计算新的权限分数。然后对得分进行归一化并任选地测试收敛。HITS类似于PageRank，但顶点得分全部发送到每个邻居，而在PageRank中，顶点得分首先除以邻居的数量。

用法

该算法需要一个简单的向图作为输入，并且输出一个DataSet的UnaryResult包含顶点ID，毂得分，和权威得分。终止由迭代次数和/或收敛阈值配置在所有顶点上的得分变化的迭代和。

  • setIncludeZeroDegreeVertices：是否在迭代计算中包括零度顶点
  • setParallelism：覆盖 算子并行性

网页排名

概览

PageRank是一种首先用于对Web搜索引擎结果进行排名的算法。今天，算法和许多变体被用在各种图形应用领域中。PageRank的想法是重要的或相关的顶点倾向于链接到其他重要的顶点。

细节

该算法在迭代中运行，其中页面将其分数分配给它们的邻居（它们具有链接的页面），并且随后基于它们接收的值的总和来更新它们的分数。为了考虑从一个页面到另一个页面的链接的重要性，将得分除以源页面的外链接的总数。因此，具有10个链接的页面将其分数的1/10分配给每个邻居，而具有100个链接的页面将其分数的1/100分配给每个相邻页面。

用法

该算法将有向图作为输入并输出DataSet每个Result包含顶点ID和PageRank分数的位置。终止配置有最大迭代次数和/或对迭代之间每个顶点的得分变化之和的收敛阈值。

  • setParallelism：覆盖 算子并行性

公

顶点指标

概览

此图分析计算有向图和无向图的以下统计信息：

  • 顶点数
  • 边数
  • 平均学位
  • 三胞胎的数量
  • 最大程度

  • 三胞胎的最大数量另外还为有向图计算了以下统计数据：

  • 单向边数

  • 双向边数
  • 最大程度
  • 最大程度的

细节

统计数据是根据degree.annotate.directed.VertexDegrees或生成的顶点度数计算的degree.annotate.undirected.VertexDegree。

用法

提供定向和无向变体。分析采用简单的图形作为输入，并输出AnalyticResult带有访问器方法的计算统计数据。图形ID类型必须是Comparable。

  • setIncludeZeroDegreeVertices：包含度数为零的顶点的结果
  • setParallelism：覆盖 算子并行性
  • setReduceOnTargetId（仅限无向）：可以从边缘源或目标ID计算度数。默认情况下，会计算源ID。如果输入边缘列表按目标ID排序，则Reduce目标ID可以优化算法

边缘度量

概览

此图分析计算以下统计信息：

  • 三角形三胞胎的数量
  • 矩形三元组的数量
  • 最大三角形三元组数
  • 最大矩形三元组数

细节

统计数据是根据从顶点生成degree.annotate.directed.EdgeDegreesPair或degree.annotate.undirected.EdgeDegreePair由顶点分组的边缘度计算的。

用法

提供定向和无向变体。分析采用简单的图形作为输入，并输出AnalyticResult带有访问器方法的计算统计数据。图形ID类型必须是Comparable。

  • setParallelism：覆盖 算子并行性
  • setReduceOnTargetId（仅限无向）：可以从边缘源或目标ID计算度数。默认情况下，会计算源ID。如果输入边缘列表按目标ID排序，则Reduce目标ID可以优化算法

相似

亚当 - 亚达

概览

Adamic-Adar测量顶点对之间的相似性，作为共享邻居的度的反对数之和。分数是非负的且无界限的。具有较高程度的顶点具有较大的整体影响，但对每对邻居的影响较小。

细节

该算法首先用顶点度的对数的倒数来注释每个顶点，然后通过源顶点将该得分连接到边缘上。在源顶点上分组，每对邻居都以顶点分数发出。对顶点对进行分组，将Adamic-Adar得分相加。

有关类似算法，请参阅Jaccard Index库方法。

用法

该算法需要一个简单的无向图作为输入，并且输出一个DataSet的BinaryResult含有两个顶点ID和亚当-亚达相似度得分。图形ID类型必须是Copyable。

  • setMinimumRatio：过滤掉Adamic-Adar得分低于给定比率乘以平均得分
  • setMinimumScore：过滤掉Adamic-Adar得分低于给定的最小值
  • setParallelism：覆盖处理少量数据的 算子的并行性

Jaccard指数

概览

Jaccard指数测量顶点邻域之间的相似性，并且被计算为共享邻居的数量除以不同邻居的数量。分数范围从0.0（无共享邻居）到1.0（所有邻居共享）。

细节

计算顶点对的共享邻居相当于计算长度为2的连接路径。通过存储顶点对的度数之和并减去共享邻居的计数来计算不同邻居的数量，这些邻居在度数之和中被重复计数。

该算法首先用目标顶点的度数注释每个边缘。在源顶点上进行分组，每个邻居对都以度和进行发射。对顶点对进行分组，计算共享邻居。

用法

该算法采用简单的无向图作为输入，并输出DataSet包含两个顶点ID，共享邻居数和不同邻居数的元组。结果类提供了计算Jaccard Index分数的方法。图形ID类型必须是Copyable。

  • setMaximumScore：过滤掉Jaccard Index得分大于或等于给定的最大分数
  • setMinimumScore：过滤掉Jaccard指数得分低于给定的最小分数
  • setParallelism：覆盖处理少量数据的 算子的并行性