この記事では、グラフ分析用の Databricks 機能の概要と、基本的なグラフの概念の概要について説明します。 グラフは、ネットワークとも呼ばれ、特にソーシャル ネットワークや通信ネットワークなどの特定の領域のコンテキストで使用されます。
グラフは、エッジによって接続される頂点のセットです。 頂点はノードとも呼ばれ、エッジはリンク、リレーションシップ、または円弧と呼ばれることもあります。 たとえば、ソーシャル ネットワークは、ユーザー間の接続を表します。 その他の例としては、都市間のフライト、電車、バスの接続などの交通ネットワークや、サーバー間のインターネット トラフィックを伝送するケーブルなどの通信ネットワークなどがあります。 グラフ処理は、不正行為や脅威の検出、製品の推奨事項などの分野でも一般的に使用されます。 多くのビジネス上の問題は、グラフ処理によるネットワークの理解と分析の恩恵を受け、機械学習などの他の分析手法と組み合わせると特に強力です。
この図は、簡単な例を示しています。 このネットワーク内のノードは、西ヨーロッパと中央ヨーロッパの 6 か国です。 図の線 (エッジ) は、2 つの国が境界線を共有していることを示しています。
Databricks Runtime ML には、あらゆる規模の問題に対するネットワーク分析パッケージが含まれています。 1 つのコンピューティング ノードで処理できる比較的小規模なネットワークの場合は、 NetworkX を使用します。 分散処理を必要とする大規模なネットワークの場合は、 GraphFrames を使用します。 必要に応じて追加のオープンソース パッケージをインストールしたり、グラフの処理と視覚化のために外部パートナーやツールに接続したりすることもできます。
この記事の残りの部分では、基本的なネットワーク分析の概念について説明し、パッケージ NetworkX を使用してこれらの概念の一部を説明するノートブックが含まれています。
グラフとネットワーク分析の概念
このセクションでは、ネットワーク分析の基本的な概念について説明します。
ノードとエッジ
ネットワーク分析では、ネットワークまたはグラフは、ノードのセットと、ノードを接続する一連のエッジ (リンク) で構成されます。 ノードは、人や都市など、接続されているモノを表します。 エッジは、共同作業を行った人や、それらの間に直接リンクを持つ駅など、それらの間の接続または関係を表します。
ノードは、頂点、ポイント、またはエンティティとも呼ばれます。 エッジは、線、リレーションシップ、またはリンクとも呼ばれます。
有向ネットワークと無向ネットワーク
ネットワーク内のエッジは、ソーシャル ネットワーク上の著名人をフォローするファンや、同僚などの双方向の関係など、一方向の関係を表すことができます。 エッジを一方向にできる場合、ネットワークはダイレクトと呼ばれます。 エッジに方向が関連付けられていない場合、ネットワークは無向と呼ばれます。
重み付きエッジ
エッジには重みを設定できます。 ネットワーク内の重みの例としては、高速道路やケーブルの持ち運び容量が考えられます。
学位
ノードの次数は、ノードにリンクするエッジの数です。 たとえば、前の図では、ノード "France" の次数は 4 です。
有向グラフの場合、次数はノードに入ってくるエッジの数であり、out-degree はノードから離れたエッジの数です。
ネットワークとノードのプロパティ
最短パス
最短パスは、方向リンクと必要に応じてエッジウェイトを考慮して、2 つのノード間の最小距離です。 たとえば、前の図では、ドイツとスペインのノード間の最短パスはフランスを経由し、パスの距離は 2 です。
中心
一元性は、ネットワーク内のノードの重要性を測定する方法です。 中心性にはいくつかの異なる尺度があります。 ノードの次数の中心性は、ノードが直接接続されているネットワーク内のノードの割合に基づきます。 ノードの間の中心性は、ノードを通過するネットワーク内の最短パスの割合です。
度分布
ネットワークの次数分布は、各次数のノード数です。 ネットワークの構造と編成に関する情報を提供します。
直径
ネットワークの直径は、任意の 2 つのノード間の最短パスの最大値です。 直径は、ネットワーク内のノードの最大偏心度に相当します。
密度
グラフの密度は、グラフ内のエッジの数を、使用可能なエッジの合計数で割った値です。 無向グラフの場合、使用可能なエッジの合計数は n(n-1)/2 で、n はノードの数です。 有向グラフの場合、各エッジには 2 つの方向があるため、使用可能なエッジの合計数は n(n-1) です。
小規模なネットワーク
ほとんどの実際のネットワークはランダムに接続されず、代わりに何らかのパターンとサブ構造を示します。 人を巻き込むネットワークにおけるこのようなパターンの例として、密接にリンクされたサブグループと、任意の 2 つのノード間の短い平均パス長を観察する"小さな世界現象" があります。 これらのパターンは実際には非常に一般的であり、大規模なグラフ処理で一般的な問題が発生します。たとえば、大規模なグラフを処理するときに競合するデータ スキューの自然な発生などです。
ノートブックの例
次のノートブック例では、Databricks Runtime for ML に組み込まれている NetworkX パッケージを使用して、いくつかの基本的なネットワーク分析の概念を示します。