Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@kyamaz

graphologyのライブラリ群の紹介

Posted at

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz :frog: です。

はじめに

以前のエントリ『JavaScriptでグラフ構造を扱う』で graphology を紹介しました。graphology は、純粋なJavaScriptで書かれたグラフ理論のためのライブラリで、グラフの作成や分析に使用することができます。graphology には、豊富なライブラリが別パッケージで準備されており、必要に応じて import するパッケージを選択して利用するように設計されています。本稿では、そのライブラリ群を紹介して、その１つのライブラリをピックアップして利用例をとりあげてみます。

graphology のライブラリ群

別パッケージにされているライブラリは、graphology-library のパッケージでまとめて読み込むことができますが、以下のようなライブラリ群が標準ライブラリとして用意されています。

  • graphology-assertions：アサーション（真偽値を返す）関数．同一ノード、同一エッジなど
  • graphology-bipartite：二部グラフに関連する補助関数
  • canvas: グラフのCanvasへのレンダリングルーチン
  • communities-louvain: コミュニティ検出のためのLouvain法
  • components: 連結成分．強連結成分、弱連結成分など
  • dag: 有向非巡回グラフ関連の関数．閉路検出、位相ソートなど
  • cores: k-cores関連の各種ユーティリティ
  • generators: グラフジェネレータ．ランダムグラフ、完全グラフなど
  • gexf: GEXFファイル形式のParserとWriter
  • graphml: GRAPHMLファイル形式のParserとWriter
  • indices: 各種特殊グラフインデックス．近傍、Louvainなど
  • layout: 基本的なグラフレイアウト
  • layout-force: 基本的なforceレイアウトのアルゴリズム
  • layout-forceatlas2: ForceAtlas2レイアウトのアルゴリズム
  • layout-noverlap: Noverlap衝突防止レイアウトのアルゴリズム
  • metrics: モジュール性、密度、中心性など
  • operators: グラフの単項演算子、二項演算子、キャスト演算子（逆行列、和集合、積集合、変換など）
  • shortest-path: 最短経路関数．ダイクストラ法、A*法など
  • simple-path: 単純な経路関連関数
  • svg: グラフのSVG形式のエクスポート
  • traversal: トラバーサル関数（DFS、BFSなど）
  • utils: 他のほとんどのモジュールで使用されるその他のユーティリティ

Louvain法

それぞれのライブラリについて用例を示していくのが嬉しいとは思いますが、多岐にわたる例示を考えなければならなさそうですので、本稿では上記のライブラリのなかで、コミュニティ検出のためのLouvain法の利用方法を取り上げてみます。

Louvain法についての詳細や用例は、以下の記事を参考にしてください。

Louvain法は、大規模なネットワーク（グラフ）においてコミュニティ構造を検出するためのアルゴリズムです。2008年にルーヴァン大学（ベルギー）の研究者らによって提案されたものです。コミュニティとは、グラフ内で互いに密に接続されたノードの集合のことを指します。アルゴリズムの特徴としては、

  • 高速: $O(n \log n)$ の計算量で、数百万ノード規模のグラフにも適用可能
  • 階層的: 複数の解像度でコミュニティ構造を発見できる
  • 貪欲法: モジュラリティを最大化する方向に最適化

とされています。モジュラリティ（Modularity） というミュニティ分割の品質を測る次の式で求められる指標 $Q$ を導入します。

$$
Q = \frac{1}{2m} \Big( \sum_{i,j} A_{ij} - \frac{k_i k_j}{2m} \Big) \delta(c_i, c_j)
$$

  • $A_{ij}$: ノード i と j 間のエッジの重み
  • $k_i, k_j$: 各ノードの次数
  • $m$: グラフ全体のエッジ数
  • $c_i, c_j$: 各ノードが属するコミュニティ
  • $\delta$: 同じコミュニティなら1、異なれば0

$Q$ の値でコミュニティ構造が存在するかがわかるとされています。

  • $Q \gt 0.3$ であれば、有意なコミュニティ構造が存在
  • $Q$ の最大値は理論上 1（実際には 0.3〜0.7 程度が一般的）

モジュラリティを最大化することでコミュニティを発見します。このアルゴリズムは、次のような分野で応用されているそうです。

分野 応用
ソーシャルネットワーク 友人グループの検出
生物学 タンパク質相互作用ネットワークの解析
交通 都市の地域クラスタリング
Web 関連ページのグルーピング
推薦システム 類似ユーザー/アイテムの発見

次に、このライブラリの利用例としてサンプルコードを記載します。

サンプルコード（例１〜例６）
例 内容
例1 基本的な使い方 - 3つのクリークを持つグラフでコミュニティ検出
例2 assign() - ノード属性として直接割り当て
例3 detailed() - モジュラリティ、コミュニティ数などの詳細情報を取得
例4 resolutionパラメータ - コミュニティの粒度を調整
例5 重み付きグラフでの使用
例6 有向グラフでの使用
louvain-example.js
var Graph = require('graphology');
var louvain = require('graphology-communities-louvain');

// ===================================================
// 例1: 基本的な使い方 - 3つのクリークを持つグラフ
// ===================================================
console.log('=== 例1: 基本的な使い方 ===\n');

var graph = new Graph.UndirectedGraph();

// 3つのクリーク（完全連結グループ）を作成
// クリーク1: A, B, C, D
graph.mergeEdge('A', 'B');
graph.mergeEdge('A', 'C');
graph.mergeEdge('A', 'D');
graph.mergeEdge('B', 'C');
graph.mergeEdge('B', 'D');
graph.mergeEdge('C', 'D');

// クリーク2: E, F, G, H
graph.mergeEdge('E', 'F');
graph.mergeEdge('E', 'G');
graph.mergeEdge('E', 'H');
graph.mergeEdge('F', 'G');
graph.mergeEdge('F', 'H');
graph.mergeEdge('G', 'H');

// クリーク3: I, J, K, L
graph.mergeEdge('I', 'J');
graph.mergeEdge('I', 'K');
graph.mergeEdge('I', 'L');
graph.mergeEdge('J', 'K');
graph.mergeEdge('J', 'L');
graph.mergeEdge('K', 'L');

// クリーク間を弱く接続
graph.mergeEdge('D', 'E'); // クリーク1とクリーク2を接続
graph.mergeEdge('H', 'I'); // クリーク2とクリーク3を接続

// コミュニティを検出
var communities = louvain(graph);

console.log('検出されたコミュニティ:');
console.log(communities);
// 出力例: { A: 0, B: 0, C: 0, D: 0, E: 1, F: 1, G: 1, H: 1, I: 2, J: 2, K: 2, L: 2 }

// コミュニティごとにノードをグループ化して表示
var communityGroups = {};
for (var node in communities) {
  var communityId = communities[node];
  if (!communityGroups[communityId]) {
    communityGroups[communityId] = [];
  }
  communityGroups[communityId].push(node);
}

console.log('\nコミュニティごとのノード:');
for (var id in communityGroups) {
  console.log('  コミュニティ ' + id + ': ' + communityGroups[id].join(', '));
}

// ===================================================
// 例2: assign() - ノード属性として直接割り当て
// ===================================================
console.log('\n=== 例2: assign()メソッド ===\n');

var graph2 = graph.copy();

// コミュニティをノード属性として直接割り当て
louvain.assign(graph2);

console.log('各ノードのcommunity属性:');
graph2.forEachNode(function (node, attributes) {
  console.log('  ' + node + ': community = ' + attributes.community);
});

// カスタム属性名を指定することも可能
louvain.assign(graph2, {nodeCommunityAttribute: 'cluster'});

console.log('\nカスタム属性名(cluster)を使用:');
graph2.forEachNode(function (node, attributes) {
  console.log('  ' + node + ': cluster = ' + attributes.cluster);
});

// ===================================================
// 例3: detailed() - 詳細な結果を取得
// ===================================================
console.log('\n=== 例3: detailed()メソッド ===\n');

var details = louvain.detailed(graph);

console.log('詳細結果:');
console.log('  コミュニティ数: ' + details.count);
console.log('  モジュラリティ: ' + details.modularity.toFixed(4));
console.log('  デルタ計算回数: ' + details.deltaComputations);
console.log('  訪問ノード数: ' + details.nodesVisited);
console.log('  デンドログラムのレベル数: ' + details.dendrogram.length);
console.log('  各レベルでの移動回数: ' + JSON.stringify(details.moves));

// ===================================================
// 例4: resolution パラメータの調整
// ===================================================
console.log('\n=== 例4: resolutionパラメータ ===\n');

// resolutionが低いと大きなコミュニティに、高いと小さなコミュニティに分割される
var resolutions = [0.5, 1.0, 2.0];

resolutions.forEach(function (res) {
  var result = louvain.detailed(graph, {resolution: res});
  console.log(
    'resolution=' + res + ': ' + result.count + 'コミュニティ, モジュラリティ=' + result.modularity.toFixed(4)
  );
});

// ===================================================
// 例5: 重み付きグラフでの使用
// ===================================================
console.log('\n=== 例5: 重み付きグラフ ===\n');

var weightedGraph = new Graph.UndirectedGraph();

// 重み付きエッジを追加
weightedGraph.mergeEdge('X', 'Y', {weight: 10}); // 強い接続
weightedGraph.mergeEdge('X', 'Z', {weight: 10});
weightedGraph.mergeEdge('Y', 'Z', {weight: 10});
weightedGraph.mergeEdge('Z', 'W', {weight: 1}); // 弱い接続（ブリッジ）
weightedGraph.mergeEdge('W', 'V', {weight: 10}); // 強い接続
weightedGraph.mergeEdge('W', 'U', {weight: 10});
weightedGraph.mergeEdge('V', 'U', {weight: 10});

var weightedCommunities = louvain(weightedGraph);
console.log('重み付きグラフのコミュニティ:');
console.log(weightedCommunities);

// 重みを無視する場合
var unweightedCommunities = louvain(weightedGraph, {getEdgeWeight: null});
console.log('\n重みを無視した場合:');
console.log(unweightedCommunities);

// カスタム重み属性を使用
weightedGraph.forEachEdge(function (edge, attributes) {
  weightedGraph.setEdgeAttribute(edge, 'importance', attributes.weight * 2);
});

var customWeightCommunities = louvain(weightedGraph, {
  getEdgeWeight: function (edge, attributes) {
    return attributes.importance;
  }
});
console.log('\nカスタム重み属性(importance)を使用:');
console.log(customWeightCommunities);

// ===================================================
// 例6: 有向グラフでの使用
// ===================================================
console.log('\n=== 例6: 有向グラフ ===\n');

var directedGraph = new Graph.DirectedGraph();

// 有向グラフを構築
directedGraph.mergeEdge('1', '2');
directedGraph.mergeEdge('2', '1');
directedGraph.mergeEdge('1', '3');
directedGraph.mergeEdge('3', '1');
directedGraph.mergeEdge('2', '3');
directedGraph.mergeEdge('3', '2');

directedGraph.mergeEdge('3', '4'); // コミュニティ間のブリッジ

directedGraph.mergeEdge('4', '5');
directedGraph.mergeEdge('5', '4');
directedGraph.mergeEdge('4', '6');
directedGraph.mergeEdge('6', '4');
directedGraph.mergeEdge('5', '6');
directedGraph.mergeEdge('6', '5');

var directedCommunities = louvain(directedGraph);
console.log('有向グラフのコミュニティ:');
console.log(directedCommunities);

このプログラムを試すには、ライブラリのインストール等の環境を整えて、次のように実行します。

$ node louvain-example.js

出力結果は次のようになります。

サンプルの出力 
=== 例1: 基本的な使い方 ===

検出されたコミュニティ:
{
  A: 0,
  B: 0,
  C: 0,
  D: 0,
  E: 1,
  F: 1,
  G: 1,
  H: 1,
  I: 2,
  J: 2,
  K: 2,
  L: 2
}

コミュニティごとのノード:
  コミュニティ 0: A, B, C, D
  コミュニティ 1: E, F, G, H
  コミュニティ 2: I, J, K, L

=== 例2: assign()メソッド ===

各ノードのcommunity属性:
  A: community = 0
  B: community = 0
  C: community = 0
  D: community = 0
  E: community = 1
  F: community = 1
  G: community = 1
  H: community = 1
  I: community = 2
  J: community = 2
  K: community = 2
  L: community = 2

カスタム属性名(cluster)を使用:
  A: cluster = 0
  B: cluster = 0
  C: cluster = 0
  D: cluster = 0
  E: cluster = 1
  F: cluster = 1
  G: cluster = 1
  H: cluster = 1
  I: cluster = 2
  J: cluster = 2
  K: cluster = 2
  L: cluster = 2

=== 例3: detailed()メソッド ===

詳細結果:
  コミュニティ数: 3
  モジュラリティ: 0.5662
  デルタ計算回数: 31
  訪問ノード数: 17
  デンドログラムのレベル数: 2
  各レベルでの移動回数: [9,0]

=== 例4: resolutionパラメータ ===

resolution=0.5: 3コミュニティ, モジュラリティ=0.7331
resolution=1: 3コミュニティ, モジュラリティ=0.5662
resolution=2: 3コミュニティ, モジュラリティ=0.2325

=== 例5: 重み付きグラフ ===

重み付きグラフのコミュニティ:
{ X: 0, Y: 0, Z: 0, W: 1, V: 1, U: 1 }

重みを無視した場合:
{ X: 0, Y: 0, Z: 0, W: 1, V: 1, U: 1 }

カスタム重み属性(importance)を使用:
{ X: 0, Y: 0, Z: 0, W: 1, V: 1, U: 1 }

=== 例6: 有向グラフ ===

有向グラフのコミュニティ:
{ '1': 0, '2': 0, '3': 0, '4': 1, '5': 1, '6': 1 }

グラフを javascript で扱うためのライブラリの具体的な用例を取り上げてみました。

おわりに

最後に、本稿を記載するために検証した環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

本稿の環境

本稿のために使用した環境は以下となります。

macOS: Sequoia 15.6.1 (chip: Apple M1)
node: v22.14.0
npm: 10.9.2

ご一読いただきまして有り難うございます。

（●）（●） Happy Hacking!
/""　＿＿""＼

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?