星雲グラフにおけるGraphxによるグラフ計算の実践

9985 ワード

pagerank graphdatabase nebulagraph graphx テキストリンク

ネットワーク情報技術の急速な発展に伴い,データは次第にマルチソースの不均一性に向けて発展しつつある.マルチソースの不均質データの中に無数の不可解な関係がある.そして、この種の関係は、ネットワーク構造とともに、データ分析のために確かである.残念なことに、大規模なデータ分析に関しては、従来の関係データベースは関連発見と表現で貧しいです.したがって、グラフデータは、その表現の強力な能力に大きな注目を集めている.グラフコンピューティングは、グラフモデルを使用して、問題を解決し、解決します.グラフは、マルチソースデータ型と統合できます.データの静的な基本的な機能を表示することに加えて、グラフコンピューティングはまた、グラフの構造と関係のデータに隠された表示する機会を見つけます.このようにグラフは、社会的ネットワーク、勧告システム、知識グラフ、金融リスク管理、ネットワークセキュリティ、およびテキスト検索の重要な分析ツールになります.

実用アルゴリズム

大規模グラフ計算のビジネスニーズを支援するためにNebula Graph 提供PageRank and Louvain に基づくグラフ発見アルゴリズムGraphX . ユーザーは、スパークタスクを送信することによって、これらのアルゴリズムアプリケーションを実行することができます.また、ユーザーはまた、LelelVeltage、ConnectedComponentなどのようなGraphXの他の組み込みグラフアルゴリズムを呼び出すためにスパークコネクタを使用してスパークプログラムを書くことができます.

ページランク

PageRankは、Googleの検索エンジンの結果でWebページをランク付けするために提起されたアルゴリズムです.PageRankは、ウェブサイトのページの重要性を測定する方法です.

PageRank入門

PageRankは、アメリカ合衆国のスタンフォードからラリーページとSergey Brinの後で命名されました.PageRankは、ウェブサイトがどれくらい重要かについての粗い見積もりを決定するために、ページへのリンクの数と品質を数えることによって動きます.根底にある仮定は、より重要なウェブサイトが他のウェブサイトからより多くの関連を受けそうであるということです.

PageRankのアプリケーション

類似性に基づくコンテンツ推薦
PageRankの助けを借りて、TwitterやFacebookなどの社会的なアプリケーションを分析するときに閲覧履歴やビューの時刻に基づいてユーザーに同様のコンテンツをお勧めすることができます.
ユーザーの社会的影響の分析
あなたは社会的ネットワーク分析のPageRank値に応じてユーザーの社会的影響を分析することができます.
論文の重要性研究
そのPageRank値に従って紙の品質を判断します.実際にPageRankアルゴリズムは、論文の品質判断のアイデアから来ている.そのうえ、PageRankもデータ分析と鉱業でその使用法を見つけます.

PageRankの実装

GraphXのPageRankはプレジェルコンピューティングモデルに基づいて実装されます.このアルゴリズムには3つの手順があります.

グラフ内のすべての頂点に対して同じPageRank値を設定します

最初の反復:エッジに沿ってメッセージを送信します.各頂点は、関連するエッジに沿ってすべての頂点情報を受け取り、新しいPageRank値を取得する

番目の反復:最初の反復で取得するPageRank値を、異なるアルゴリズムモデルに対応する式に入れ、新しいPageRank値を取得します.

ルーバン法

コミュニティ検出のためのルーヴン法は,大規模ネットワークからコミュニティを抽出する方法である.この方法はグラフの集合アルゴリズムである.

ルーヴン入門

ルーヴルのためのインスピレーションは、アルゴリズムの進行としてモジュール性の最適化です.ノードがあるコミュニティに結合して、コミュニティのモジュール性を最大にするなら、ノードはコミュニティに属します.ノードが他のコミュニティに加わった後にモジュール性を増加させないなら、それは現在のコミュニティにとどまるべきです.
モジュール性
モジュール式
モジュールQはコミュニティ間のリンクに比べてコミュニティ内のリンクの密度を測定する.モジュール化は以下のように定義されます:

どこ

モジュール式の変形
この式では、ノードIとノードJが同じコミュニティに属するとき、公式は意味があるだけです.したがって、公式は特定のコミュニティの中で親近感を測ります.この式の単純変形は以下の通りである.

どこ

モジュラリティ変化の計算
ルーヴン法では、各コミュニティの特定のモジュラリティを計算する必要はありません.コミュニティに特定のノードを追加した後、モジュールの変更を比較する必要があります.つまり、計算する必要があるだけです△q
あるノードにノードiを挿入するとき、モジュールの変更は以下の通りです.

どこ

ルーヴンの応用

金融リスク管理

金融リスクコントロールのシナリオでは、ユーザーの行動に基づいて詐欺ギャングを識別する方法を使用することができます.

社会的ネットワーク

ルーヴンは、グラフ内のノードの関連の幅と強さに基づいて社会的ネットワークを分割します.ルーヴンも複雑なネットワークと人々のグループの間の近さを分析します.

推薦制度

ユーザの興味に基づくコミュニティ検出より正確かつ効果的なカスタマイズ勧告は、コミュニティと協調フィルタリングアルゴリズムに基づいて実装することができます.

ルーバンを実装する

ルーヴン法には2段階がある.手順は実際には2段階の反復です.
ステージ1:連続的にグラフのノードを横切って、各隣人コミュニティのノードによって導入されたモジュール性変化を比較してください.それから、モジュール性を最大にすることができるコミュニティに一つのノードを加えてください.(例えば、ノードVはコミュニティA、BとCに追加されます.3つのコミュニティのモジュール化増分は- 1、1、2です.
ステージ2:第1段階に基づくプロセス.同じコミュニティに属するノードは、スーパーノードに統合され、グラフを再構築します.すなわち、コミュニティは、グラフの新しいノードと見なされる.このとき、2つのスーパーノード間のエッジの重みは、2つのスーパーノードのオリジナルノードに接続されたエッジの重みの和である.すなわち、2つのコミュニティのエッジの重みの合計.
以下に2段階の詳細を示す.

最初のステージでは、ノードが横断され、それらが属するコミュニティに追加されます.このように、我々は中央のグラフと4つのコミュニティを得る.
第2のステージにおいて、コミュニティのノードは、スーパーノードに合併される.コミュニティノードは、重みがコミュニティのすべてのノードの間に接続されたエッジの重みの2倍である自己接続のエッジを持っています.コミュニティ間のエッジ重量は、2つのコミュニティを接続しているエッジの重みの合計である.例えば、レッドコミュニティとライトグリーンコミュニティは(8,11)、(10,11)、(10,13)によって接続されている.それで、2つのコミュニティの間のエッジの重さは3です.

Note: The weight inside the community is twice the weight of the edges between all internal nodes, because the concept of Kin is the sum of the edges of all nodes in the community and node i. When calculating the Kin for a certain community, each edge is actually counted twice.

ルーヴン法は、アルゴリズムが安定するまで(グラフのモジュール性が変化しない)、または反復が最大に達するまで、ステージ1とステージ2を連続的に繰り返す.

手続きアルゴリズムを実行する

デモ環境

つの仮想マシン

インテル( R ) Xeon ( R )プラチナ8260 M CPU＠2.30 GHz

プロセッサ: 32

CPUコア:16

メモリーサイズ:128 g

ソフトウェア環境:

スパークスパークリング7つのノードがあるクラスタ

糸V 2.10.0 : 3ノードのクラスタ

星雲グラフV 11.0 :配備されて、デフォルト構成を使用しました

テスト用データセット

スペースの作成

CREATE SPACE algoTest(partition_num=100, replica_factor=1);

CREATE TAG PERSON() CREATE EDGE FRIEND(likeness double);

スキーマ作成

CREATE TAG PERSON()
CREATE EDGE FRIEND(likeness double);

データのインポート

スパークライターを使用してデータを雲星雲にオフラインでインポートします.

試験結果

スパークジョブを起動するリソース割り当ては、ドライバメモリ= 20 g -- ExecuteMemory = 100 G -- ExecuteCore = 3です.

1億個のノードを持つデータセットのPageRankアルゴリズム実行時間は21分です.

億万のノードを持つデータセットのルーヴンアルゴリズム実行時間は1.3時間です.

星雲グラフアルゴリズムを使う方法

Nebulaアルゴリズムプロジェクトをダウンロードしてパックします.

$ git clone [email protected]:vesoft-inc/nebula-java.git $ cd nebula-java/tools/nebula-algorithm $ mvn package -DskipTests

src/main/resources/applicationを設定します.コンパス.

{ 
# Spark relation config 
spark: { 
  app: { 
    # not required, default name is the algorithm that you are going to execute. 
    name: PageRank 

    # not required partitionNum: 12 
 } 

 master: local 

 # not required 
 conf: { 
    driver-memory: 8g 
    executor-memory: 8g 
    executor-cores: 1g 
    cores-max:6 
  } 
 } 

# Nebula Graph relation config 
nebula: { 
  # metadata server address 
  addresses: "127.0.0.1:45500" 
  user: root 
  pswd: nebula 
  space: algoTest 
  # partition specified while creating nebula space, if you didn't specified the partition, then it's 100. 
  partitionNumber: 100 
  # nebula edge type 
  labels: ["FRIEND"] 

 hasWeight: true 
 # if hasWeight is true，then weightCols is required， and weghtCols' order must be corresponding with labels. 
 # Noted: the graph algorithm only supports isomorphic graphs, 
 # so the data type of each col in weightCols must be consistent and all numeric types. 
 weightCols: ["likeness"] 
} 

algorithm: { 
 # the algorithm that you are going to execute，pick one from [pagerank, louvain] 
 executeAlgo: louvain 
 # algorithm result path 
 path: /tmp 

 # pagerank parameter 
 pagerank: { 
   maxIter: 20 
   resetProb: 0.15 # default 0.15 

} 

 # louvain parameter 
 louvain: { 
    maxIter: 20 
    internalIter: 10 
    tol: 0.5 
  } 
 } 
}

インストールし、マシン上でスパークサービスを開始したことを確認します.

Nebulaアルゴリズムアプリケーションを送信します.

spark-submit --master xxx --class com.vesoft.nebula.tools.algorithm.Main /your-jar-path/nebula-algorithm-1.0.1.jar -p /your-application.conf-path/application.conf

コンテンツに興味があれば、Nebulaアルゴリズムを試してみてください.