からだにいいもの Rで解析：ホップ数（Hop Count）と幾何学的距離を対応させてグラフを配置する「grip」パッケージの紹介
ネットワーク構造を図にするとき、頂点の位置が整理されていないと、つながりの全体像や中心的な部分を読み取ることが難しくなります。しかし、頂点数が増えたグラフで、距離や接続関係を保ったまま配置を調整するには手間がかかります。
「grip」パッケージは、2次元および3次元の空間で、辺をたどるホップ数と配置後の幾何学的距離を対応させながらグラフのレイアウトを計算する機能を提供します。グラフを多スケールの階層に粗視化してから配置を求める方式が採用されており、複数の配置候補を共通の指標で比較することが可能です。また、配置の良し悪しを表す目的関数を個別に評価することも可能です。
本パッケージの利用で、大きめのネットワークでも構造を保った図を効率よく用意できるのではないかと考えます。
パッケージバージョンは0.2.0。Windows 11 x64 (build 26200)のR version 4.6.1で確認しています。
パッケージのインストール
下記コマンドを実行してください。
# パッケージのインストール
install.packages("grip")
# パッケージの読み込み
library("grip")スポンサーリンク
コマンド例
詳細はコメント、パッケージのヘルプを確認してください。
グラフレイアウトとは、頂点（ノード）の座標を決めて辺のつながりを図にできる形にする処理です。gripは、辺をいくつたどるかで測る距離であるホップ数（metric = “hop”）と、辺の長さを足し合わせた距離（metric = “edge_length”）のいずれかをグラフ上の距離として扱い、その距離と配置後の座標上の距離（幾何学的距離）ができるだけ対応するように頂点を動かします。
配置は一度に求めるのではなく、グラフをMISF（maximal independent set filtration、極大独立集合フィルトレーション）と呼ぶ入れ子の階層に粗視化し、粗いレベルから順に細かいレベルへ座標を引き継ぎながら求めます。また、頂点同士が近づきすぎないように働く反発（repulsion）の強さは、辺の長さを合わせる項と別々に目的関数として評価できます。
共通データとして、京都の主要駅を模した頂点11個・辺12本の無向グラフを作成します。辺リストは1始まりの頂点番号を2列に並べた行列で表します。
# 頂点（駅）のラベル
stations <- c("京都", "二条", "円町", "嵯峨嵐山", "亀岡",
"東福寺", "伏見稲荷", "宇治", "六地蔵", "山科", "出町柳")
# 駅間の接続を辺リスト（1始まりの頂点番号）で定義
edges <- rbind(
c(1, 2), c(2, 3), c(3, 4), c(4, 5),
c(1, 6), c(6, 7), c(7, 8), c(8, 9), c(9, 10),
c(10, 1), c(1, 11), c(11, 3))
# 頂点数
n <- length(stations)
グラフのレイアウト座標を計算：gripコマンド
辺リストと頂点数を渡すと、ホップ数に基づく多スケールのレイアウト座標を計算します。dim = 2で2次元、metric = “hop”でホップ数を距離として使います。
| オプション | 意味 | 初期値 |
|---|---|---|
| edges | 辺の端点を並べた2列の整数行列（1始まりの頂点ID） | NULL |
| n | 頂点の数 | NULL |
| adj_list | 無向グラフの隣接リスト（1始まり） | NULL |
| weight_list | adj_listに対応する辺長のリスト。edge_length計量では必須で、hop計量ではNULLだと全辺を長さ1として扱う。指定する長さはすべて有限かつ正 | NULL |
| edge_weights | edgesの行と同じ順に並べた辺長のベクトル。edge_length計量では必須で、hop計量ではNULLだと全辺を長さ1として扱う。指定する長さはすべて有限かつ正。計量の選択によって長さがグラフ距離を定めるかどうかが変わる | NULL |
| dim | レイアウトの次元（2または3）。既定は3 | 3 |
| placement | 初期配置の方法。”circle”は2次元でのみ使われる | c(“barycenter”, “circle”) |
| preset | 調整用のプリセット。NULLは品質優先の既定値を使う。”carpet”はシェルピンスキーカーペット型、”mesh”は長方格子型、”torus”は3次元トーラス型、”tree”は対称な木型のグラフ向けに調整した値を、明示指定しなかった調整用引数にだけ補う | NULL |
| rounds | 調整の初期ラウンド数 | 160 |
| final_rounds | 調整の最終ラウンド数 | 384 |
| num_init | 最も粗いレベルの初期頂点数 | 24 |
| num_nbrs | 各フィルトレーションレベルで局所調整に残すグラフ距離近傍の最大数 | 20 |
| r | 主たる局所温度の適応率。[0, 1]の範囲 | 0.03 |
| s | 連続する変位の向きがそろったときに掛かる非負のブースト係数 | 7.5 |
| repulsion_factor | 最細レベルの反発力スケールに掛ける非負の倍率 | 2.5 |
| coarse_repulsion_factor | 粗いレベルの追加反発項に掛ける非負の倍率。0でこの追加項を無効化 | 1.5 |
| coarse_repulsion_sample | 大きめの粗いレベルで全体反発を近似するための正整数のサンプル数 | 16 |
| coarse_repulsion_exact_below | 正整数のしきい値。アクティブ集合のサイズがこれ以下なら、粗い反発をサンプリングせず全アクティブ頂点に対して厳密に計算する | 64 |
| final_anchor_factor | 最終FR段階を最終前の全体レイアウトへ引き戻すアンカー項の非負倍率。0でアンカーを無効化し現在の挙動を保つ | 0 |
| final_move_scale_after_first | 最細レベル最初のラウンドの後に最終FRの変位へ掛ける[0, 1]のスカラー。1未満で以降の全体移動を減衰させ、最初のFRラウンドは変えない | 1 |
| final_mode | 最終の全体調整モード。”fr”は現在のFruchterman-Reingold型の最終段階、”kk_repulse”はアクティブ集合の明示的な反発を伴うKK型の局所距離適合を使う | c(“fr”, “kk_repulse”) |
| insertion_anchor_count | 非初期のMISF調整レベルで多スケール挿入に使うアンカー頂点数（正整数）。現在の実装で大域的なK_mishに最も近い | 3 |
| insertion_anchor_scope | 多スケール挿入時のアンカー選出範囲。”any_higher”は従来のGRIPと同じで配置済みの任意の上位MISFレベルからアンカーを取る。”prev_misf”は直前のMISFレベルだけに限定する | c(“any_higher”, “prev_misf”) |
| insertion_anchor_strategy | 多スケール挿入時のアンカー選択規則。”first”は従来のBFSで最初に見つかったものを使う。”distance_band”はK_mish番目の距離帯まで探索してから選ぶ。”balanced_band”は同じ帯拡張の後、重心が中央に保たれつつ幾何的に広がる部分集合を選ぶ。”spread_prev”はinsertion_anchor_scope = “prev_misf”と組で使う対称性重視の帯戦略 | c(“first”, “distance_band”, “balanced_band”, “spread_prev”) |
| level0_insertion_mode | 最細フィルトレーションレベルを最初に埋めるときだけ使うレベル0の配置上書き。”inherit”は現在の挙動、”barycenter”はレベル0で2次元の円ヒューリスティックを無効化して重心配置にする、”least_squares”は局所微調整の前に多アンカーの最小二乗距離適合を使う | c(“inherit”, “barycenter”, “least_squares”) |
| level0_anchor_count | レベル0挿入で集める配置済みアンカーの数（正整数）。既定ではinsertion_anchor_countを引き継ぐ。従来の挙動は3 | insertion_anchor_count |
| level0_local_kk_steps | 各レベル0挿入の直後に適用する小さな局所KK微調整のステップ数（非負整数）。従来の挙動は3 | 3 |
| lgkk_polish_rounds | 主GRIP求解の後に適用するランドマーク測地KG研磨の反復数（非負整数）。0で無効 | 0L |
| lgkk_multiscale_rounds | 多スケール求解の中で、各対象MISFレベルが標準のGRIPラウンドを終えた後に適用するコンパイル済みランドマーク測地KK調整のラウンド数（非負整数）。以下の段階別予算がNULLのときのフォールバックになる | 0L |
| lgkk_rounds_coarse | misf_level > 1の粗いMISFレベルで適用するLGKKラウンド数（非負整数、任意）。NULLならlgkk_multiscale_roundsにフォールバック | NULL |
| lgkk_rounds_pre_final | 全グラフを開く直前の最後の粗いレベル（misf_level == 1）で適用するLGKKラウンド数（非負整数、任意）。NULLならlgkk_multiscale_roundsにフォールバック | NULL |
| lgkk_rounds_final | 全グラフレベル（misf_level == 0）が標準GRIPラウンドを終えた後に適用するLGKKラウンド数（非負整数、任意）。NULLならlgkk_multiscale_roundsにフォールバック | NULL |
| lgkk_local_nbrs | いずれかのLGKK段階が有効なとき、LGKKの疎な局所集合として頂点ごとに残すグラフ計量近傍の数 | 20L |
| lgkk_landmark_count | いずれかのLGKK段階が有効なとき、LGKKの疎な長距離集合として頂点ごとに残す最遠点ランドマークの数 | 8L |
| lgkk_multiscale_scope | コンパイル済み多スケールLGKK段階の適用範囲。”all”は最終の全グラフレベルを含む対象レベルすべての後に適用、”coarse”は粗いレベルにのみ適用 | c(“all”, “coarse”) |
| lgkk_active_limit | コンパイル済み多スケールLGKKのキャッシュ構築に使うアクティブ集合サイズの上限（正整数）。これより大きいレベルは多スケールLGKK段階を飛ばす | 4096L |
| tinit_factor | 初期温度の係数 | 6 |
| seed | 再現性のための乱数シード（任意）。NULLなら現在時刻を使う | 6 |
| disconnected | 非連結グラフの扱い。”components”（既定）は連結成分ごとに配置して1つの座標行列にまとめる、”error”はエラーで停止する | c(“components”, “error”) |
| metric | 多スケールGRIPエンジンが使うグラフ計量。”hop”（既定）は重みなし最短経路のホップ数でMISF階層と近傍を作る、”edge_length”は与えた正の辺長を足した最短経路距離を使う | c(“hop”, “edge_length”) |
| metric_neighbor_cap | metric = “edge_length”のときだけ使う重み付き探索の上限。NULLは厳密な重み付き近傍探索、正整数は探索ごとの確定頂点数を制限した近似探索。metric = “hop”と併用するとエラー | NULL |
| length_normalization | metric = “edge_length”のときだけ適用する大域正規化。”median”（既定）は各辺長を中央値で割る、”mean”は平均で割る、”none”は与えた数値スケールを保つ。metric = “hop”と併用するとエラー | c(“median”, “mean”, “none”) |
# ホップ数を距離として2次元レイアウト座標を計算
coords_hop <- grip(edges, n = n, dim = 2, metric = "hop", seed = 1)
# 座標の行名に駅ラベルを設定
rownames(coords_hop) <- stations
# 座標を小数第2位で表示
round(coords_hop, 2)
[,1] [,2]
京都 0.75 -9.73
二条 -13.57 15.59
円町 -37.54 28.29
嵯峨嵐山 -58.81 49.24
亀岡 -76.85 66.98
東福寺 29.63 -18.03
伏見稲荷 50.98 -35.67
宇治 50.80 -59.91
六地蔵 26.56 -60.01
山科 9.02 -38.59
出町柳 -24.61 4.47計算した座標はplot.layoutで辺付きの図にできます。
レイアウトを辺付きで描画：plot.layoutコマンド
# レイアウトを辺付きで描画
plot.layout(coords_hop, edges = edges, main = "京都の路線網レイアウト",
pch = 16, vertex.col = "#4C72B0")
# 各頂点の少し上に駅ラベルを表示
text(coords_hop, labels = stations, pos = 3, cex = 0.8)
複数のレイアウト候補の比較：compare.layoutsコマンド
candidatesに複数の配置設定を渡すと、同じグラフに対してそれぞれのレイアウトを計算し、応力（stress）や辺交差数などの指標をまとめた要約を返します。
| オプション | 意味 | 初期値 |
|---|---|---|
| edges | 辺の端点を並べた2列の整数行列（1始まりの頂点ID） | NULL |
| n | 頂点の数 | NULL |
| adj_list | 無向グラフの隣接リスト（1始まり） | NULL |
| weight_list | 正の辺重みの並列リスト（任意） | NULL |
| edge_weights | edgesに並列な正の辺重みベクトル（任意） | NULL |
| dim | レイアウトの次元（2または3） | 2 |
| candidates | c(“default”, “mesh”, “tree”)のような文字列ベクトル、または候補レイアウト仕様の名前付きリスト。各要素はNULL（既定を使う）、単一のプリセット名、preset・placement・rounds・repulsion_factorなどgrip()の調整用引数の名前付きリストのいずれか | c(“default”) |
| search | レイアウト設定のグリッド探索を表す名前付きリスト（任意）。preset・placement・rounds・final_rounds・num_init・num_nbrs・r・s・repulsion_factor・tinit_factorをベクトルで渡せる。全組み合わせがcandidatesに展開される。candidate.prefixとinclude.baseで候補名と基準設定の有無を制御する | NULL |
| clusters | cluster.separationの計算に使うクラスタまたはコミュニティのラベル（任意） | NULL |
| seeds | 繰り返し実行に使う整数シード | 1:3 |
| sample.size.stress | sampled.stressに使うサンプルペア数 | 2000L |
| sample.size.nonedge | sampled.nonedge.sep.ratioに使う非隣接ペアのサンプル数 | 5000L |
| edge.crossings | 2次元レイアウトでedge.crossingsをどう計算するか | c(“auto”, “always”, “never”) |
| edge.crossings.max.edges | edge.crossings = “auto”のときの辺数のしきい値 | 1000L |
| score.weights | score.compositeの計算に使う名前付き数値ベクトル（任意）。NULLにすると合成スコアを省く | grip.default.compare.score.weights() |
| return.layouts | TRUEなら実現した座標行列を戻り値に含める | FALSE |
| disconnected | grip()へそのまま渡す | c(“components”, “error”) |
# 既定・木型プリセット・格子型プリセットの3候補を比較
cmp <- compare.layouts(
edges = edges, n = n, dim = 2,
candidates = c("default", "tree", "mesh"),
seeds = 1:2
)
# 候補ごとの主要な指標を表示
cmp$summary[, c("candidate", "n.ok", "sampled.stress.mean",
"edge.crossings.mean", "score.composite")]
candidate n.ok sampled.stress.mean edge.crossings.mean score.composite
1 mesh 2 0.1429575 0.5 0.2368421
2 tree 2 0.1894848 0.0 0.6184211
3 default 2 0.1913013 0.0 0.6447368![Rユーザのためのtidymodels[実践]入門〜モダンな統計・機械学習モデリングの世界](https://images-na.ssl-images-amazon.com/images/P/4297132362.09.LZZZZZZZ.jpg)
反発状態の目的関数の評価：edge.repulsive.stateコマンド
座標・辺リスト・辺の目標長を渡すと、辺の長さを合わせる項と頂点間の反発項からなる目的関数の値（エネルギー）と、その勾配ノルムを返します。lambdaで反発の強さを指定します。
| オプション | 意味 | 初期値 |
|---|---|---|
| coords | n行dim列の数値座標行列 | なし |
| edges | 1始まりのグラフ辺の端点を並べた2列の整数または数値行列 | なし |
| edge.lengths | edgesに並列な目標辺長の数値ベクトル | なし |
| edge.weights | 非負の辺重み（任意）。既定は1 | NULL |
| edge.family | 辺ポテンシャルの族。”quadratic”または”upper_barrier” | c(“quadratic”, “upper_barrier”) |
| eps.plus | upper_barrierのスラックパラメータ | 0.35 |
| beta | upper_barrierの強さ。beta <= 0のとき辺ポテンシャルはquadraticになる | 0 |
| lambda | 反発の強さ | 0 |
| pair.index | 反発項に使う1始まりの頂点ペアの2列行列（任意）。NULLかつlambda > 0なら全ての非順序ペアを使う | NULL |
| pair.weights | pair.indexに並列なペア重み（任意） | NULL |
| repulsion.family | 反発ポテンシャルの族。”log”または”inverse_power” | c(“log”, “inverse_power”) |
| repulsion.delta | ペア距離に対する小さな正の平滑化パラメータ | 0.001 |
| repulsion.power | inverse_power反発が使うべき指数 | 1 |
| distance.eps | 微分で使う小さな正の距離下限 | 1e-10 |
| engine | バックエンドエンジン。”cpp”が既定、”R”は参照実装を使う | c(“cpp”, “R”) |
# 全辺の目標長を1として反発状態を評価
state <- edge.repulsive.state(
coords_hop, edges, edge.lengths = rep(1, nrow(edges)),
lambda = 0.1, repulsion.family = "log", engine = "R"
)
# エネルギーと勾配ノルムを表示
state[c("energy", "edge.energy", "repel.energy", "gradient.norm")]
$energy
[1] 4254.681
$edge.energy
[1] 4277.338
$repel.energy
[1] -226.5672
$gradient.norm
[1] 61.67321重み付きMISF階層の構築：build.weighted.misfコマンド
辺の重み（ここでは区間の所要時間を想定した擬似値）を与えて、重み付きGRIPが使う多スケールのMISF階層を構築します。戻り値から各レベルの頂点数や階層の高さを取り出せます。
| オプション | 意味 | 初期値 |
|---|---|---|
| edges | 辺の端点を並べた2列の整数行列（1始まりの頂点ID） | NULL |
| n | 頂点の数 | NULL |
| adj_list | 無向グラフの隣接リスト（1始まり） | NULL |
| weight_list | 厳密に正の辺長の並列リスト | NULL |
| edge_weights | edgesに対する辺長のベクトル（任意） | NULL |
| num_init | 最も粗いレベルの初期頂点数 | 24 |
| num_nbrs | レベルごとに残す局所近傍の最大数 | 20 |
| length_normalization | 辺長の大域正規化。”median”（既定）、”mean”、”none” | c(“median”, “mean”, “none”) |
| seed | 再現性のための乱数シード（任意）。NULLなら現在時刻を使う | 6 |
# 各区間の所要時間を想定した擬似的な辺の重み（分）
travel_min <- c(3, 4, 5, 9, 5, 3, 12, 6, 4, 7, 6, 8)
# 重み付きMISF階層を構築
misf <- build.weighted.misf(
edges = edges, n = n, edge_weights = travel_min,
num_init = 3, num_nbrs = 2, seed = 1
)
# 各レベルの頂点数・階層の高さ・最上位レベルのサイズを表示
misf[c("misf_size", "misf_height", "top_level_size")]
$misf_size
[1] 11 7 4 2
$misf_height
[1] 3
$top_level_size
[1] 2
k分木の辺リストを生成：edges.kary.treeコマンド
分岐数kと深さdepthを指定して、k分木の辺リストを生成します。組織図のような階層構造をレイアウトの入力に使いたいときに便利です。
| オプション | 意味 | 初期値 |
|---|---|---|
| k | 分岐数 | 2 |
| depth | 根より下のレベル数 | 2 |
# 分岐数2・深さ3のk分木の辺リストを生成
tree_edges <- edges.kary.tree(k = 2, depth = 3)
# 生成された辺の先頭6行を表示
head(tree_edges)
edge_parent edge_child
[1,] 1 2
[2,] 1 3
[3,] 2 4
[4,] 2 5
[5,] 3 6
[6,] 3 7
# 木全体の頂点数を表示
max(tree_edges)
[1] 15この記事が誰かの役に立ちますように。
スポンサーリンク
