Skip to content

二分图

译者：flink.sojb.cn

注意 Bipartite Graph目前仅在Gelly Java API中受支持。

二分图

二分图（也称为双模图）是一种图形，其中顶点被分成两个不相交的集合。这些集通常称为顶部和底部顶点。此图中的边可以仅连接来自相对集的顶点（即底部顶点到顶部顶点），并且不能连接同一集中的两个顶点。

这些图在实践中具有广泛的应用，并且对于特定域可以是更自然的选择。例如，为了表示科学论文的作者，顶部顶点可以代表科学论文，而底部节点代表作者。当然，顶部和底部节点之间的边缘将代表特定科学论文的作者。二分图应用的另一个常见例子是演员和电影之间的关系。在这种情况下，边缘表示在电影中播放的特定演员。

出于以下实际原因，使用二分图代替常规图（单模）：

  • 它们保存了有关顶点之间连接的更多信息。例如，代表两位研究人员之间的单一链接，代表他们一起撰写了一篇论文，二分图保存了他们撰写的论文信息。
  • 二分图可以比单模图更紧凑地编码相同的信息

图表表示

A BipartiteGraph代表：

  • 一个DataSet顶级节点
  • 一个DataSet底部节点
  • 一个DataSet顶部和底部节点之间的边

在Graph类中，节点由Vertex类型表示，并且相同的规则适用于其类型和值。

图形边缘由BipartiteEdge类型表示。A BipartiteEdge由顶部ID（顶部的ID Vertex），底部ID（底部的ID Vertex）和可选值定义。Edge和之间的主要区别在于BipartiteEdge它链接的节点的ID可以是不同类型。没有值的边具有NullValue值类型。

BipartiteEdge<Long, String, Double> e = new BipartiteEdge<Long, String, Double>(1L, "id1", 0.5);

Double weight = e.getValue(); // weight = 0.5

// Scala API is not yet supported

图形创建

您可以BipartiteGraph通过以下方式创建：

  • 从一个DataSet顶部顶点，一个DataSet底部顶点和一个DataSet边缘：

  • Java

  • Scala
ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();

DataSet<Vertex<String, Long>> topVertices = ...

DataSet<Vertex<String, Long>> bottomVertices = ...

DataSet<Edge<String, String, Double>> edges = ...

Graph<String, String, Long, Long, Double> graph = BipartiteGraph.fromDataSet(topVertices, bottomVertices, edges, env);

// Scala API is not yet supported

图形转换

  • Projection：Projection是二分图的常见 算子操作，可将二分图转换为常规图。有两种类型的Projection：顶部和底部Projection。顶部Projection仅保存结果图中的顶部节点，并且仅当顶部节点在原始图中连接到中间底部节点时才在新图中创建它们之间的链接。底部Projection与顶部Projection相反，即仅保存底部节点并连接一对节点（如果它们在原始图形中连接）。

二分图Projection

Gelly支持两种子类型的Projection：简单Projection和完整Projection。它们之间的唯一区别是数据与结果图中的边相关联。

在简单Projection的情况下，结果图中的每个节点都包含一对连接原始图中节点的二分边值：

ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
// Vertices (1, "top1")
DataSet<Vertex<Long, String>> topVertices = ...

// Vertices (2, "bottom2"); (4, "bottom4")
DataSet<Vertex<Long, String>> bottomVertices = ...

// Edge that connect vertex 2 to vertex 1 and vertex 4 to vertex 1:
// (1, 2, "1-2-edge"); (1, 4, "1-4-edge")
DataSet<Edge<Long, Long, String>> edges = ...

BipartiteGraph<Long, Long, String, String, String> graph = BipartiteGraph.fromDataSet(topVertices, bottomVertices, edges, env);

// Result graph with two vertices:
// (2, "bottom2"); (4, "bottom4")
//
// and one edge that contains ids of bottom edges and a tuple with
// values of intermediate edges in the original bipartite graph:
// (2, 4, ("1-2-edge", "1-4-edge"))
Graph<Long, String, Tuple2<String, String>> graph bipartiteGraph.projectionBottomSimple();

// Scala API is not yet supported

完整Projection保存有关两个顶点之间连接的所有信息，并将其存储在Projection实例中。这包括中间顶点的值和id，源和目标顶点值以及源和目标边缘值：

ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();
// Vertices (1, "top1")
DataSet<Vertex<Long, String>> topVertices = ...

// Vertices (2, "bottom2"); (4, "bottom4")
DataSet<Vertex<Long, String>> bottomVertices = ...

// Edge that connect vertex 2 to vertex 1 and vertex 4 to vertex 1:
// (1, 2, "1-2-edge"); (1, 4, "1-4-edge")
DataSet<Edge<Long, Long, String>> edges = ...

BipartiteGraph<Long, Long, String, String, String> graph = BipartiteGraph.fromDataSet(topVertices, bottomVertices, edges, env);

// Result graph with two vertices:
// (2, "bottom2"); (4, "bottom4")
// and one edge that contains ids of bottom edges and a tuple that 
// contains id and value of the intermediate edge, values of connected vertices
// and values of intermediate edges in the original bipartite graph:
// (2, 4, (1, "top1", "bottom2", "bottom4", "1-2-edge", "1-4-edge"))
Graph<String, String, Projection<Long, String, String, String>> graph bipartiteGraph.projectionBottomFull();

// Scala API is not yet supported
回到顶部