ryamadaのコンピュータ・数学メモ

2019-04-13

グラフのモーメント

グラフモーメント

こんなペイパーがある
グラフのモーメントと言うのを定義している
各ノードに $\rho(i)$ なる値が与えられているときに $M_G^\rho = \sum_{u \in V} (\sum_{u,v \in V}dist(u,v)(\rho(u)+\rho(v)))$
これを $\rho$ モーメントと呼ぶと言う
他にも定義があり、別の呼び名がある
mean distance (平均距離) $d(G) = \frac{1}{|V|^2} M^1_G$ 。これは $\rho$ を全ノードで１に統一して $\rho$ モーメントを計算し、それを計算に要したノードペア数で割ったものである。逆に言えば $\rho$ モーメントと言うのは平均距離の $|V|^2$ 倍と言うことになる
鎖状グラフを考え、全てのノードに $\rho=1$ を与え、全てのエッジの長さを等しくすると、これは、ある意味、その線分を、その線分の置かれた軸を座標とした時の平均位置になる。そう言う意味合いでの、１次モーメントとなっている
$\rho=1/2$ とした時、Wiener indexと呼んで、化学構造で用いるグラフの不変量とすると言う(Wiki記事)
ノードの次数を $\sigma$ とした時 $M^\sigma_G = D'(G)$ と書き、degree distanceと呼ぶと言う
ノードの次数情報を使うのは、ノード周りの「面積の大小」情報を使うことと近いニュアンスがある
さらにこのノード次数情報を使って $MTI(G) = \sum_{u \in V} \sigma(u)^2 + M^\sigma_G$ と言う指標がありSchultz indexとか、Molecular topological indexと呼ぶ