二分グラフ

注意二分グラフは現在のところGelly Java APIでのみサポートされます。

二分グラフ
グラフの表現
グラフの生成
グラフの変換

二分グラフ

二分グラフ (2モードグラフとも呼ばれます)は頂点が2つの関節セットに分割されるグラフです。これらのセットは通常トップおよびボトム頂点と呼ばれます。グラフ内の辺は反対セット(つまり、ボトム頂点からトップ頂点)から辺にのみ接続することができ、同じセット内の2つの頂点を接続することはできません。

これらのグラフは実際問題として広い応用があり、特定のドメインのためにはより良い自然な選択になりえます。例えば、科学的な論文の著者を表すために、トップ頂点は科学的な論文を表すことができ、一方でボトムノードは著者を表すでしょう。自然と、トップとボトムノードの間の辺は特定の科学的な論文の著者を表すでしょう。二分グラフの応用の他の一般的な例は、俳優と映画の間の関係です。この場合、辺は映画の中で特定の俳優が演じたことを表します。

二分グラフは通常グラフ(1モード)の代わりに以下の実践的な理由で使われます: * それらは頂点間の接続についてのより多い情報を保持する。例えば、2人の研究者が一緒に著作した論文を表す、グラフ内で2人の研究者間の1つのリンクの代わりに、二分グラフは彼らがどの論文を著作したかについての情報を保持します * 二分グラフは同じ情報を1モードのグラフよりコンパクトに符号化することができます。

グラフの表現

BipartiteGraph は以下によって表されます: * トップノードのDataSet * ボトムノードのDataSet * トップおよびボトムのノード間の辺のDataSet

Graphクラス内のノードがVertex 型によって表されるのと同じく、同じルールが型と値に適用されます。

グラフの辺はBipartiteEdge型によって表されます。BipartiteEdge はトップID (トップ VertexのID)、ボトムID (ボトムVertexのID)、任意の値によって定義されます。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を作成することができます:

from a DataSet of top vertices, a DataSet of bottom vertices and a DataSet of edges:

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

グラフの変換

投影: 投影は二分グラフを通常のグラフに変換する、二分グラフのための一般的な操作です。二種類の投影があります: トップおよびボトム投影。トップ投影は結果グラフ内のトップノードのみ保持し、元のグラフ内で両方のトップノードが接続している中間のボトムノードがある場合のみ、新しいグラフ内でそれらの間にリンクを作成します。ボトム投影はトップ投影の反対です。つまり、ボトムノードのみ保持し、元のグラフでボトムノードが接続されている場合はノードのペアを接続します。

二分グラフの投影

Gelly は投影の2つのサブタイプをサポートします: 単純な投影と完全な投影。それらの唯一の違いは、結果のグラフでどのデータが辺と関連するかです。

単純な投影の場合、結果グラフでの各ノードは元のグラフでノードに接続する二分辺の2つの値を含みます:

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

完全な投影は2つの頂点間の接続の全ての情報を保持し、それをProjection インスタンスに格納します。This includes value and id of an intermediate vertex, source and target vertex values and source and target edge values:

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

上に戻る