ランダムグラフにおけるグラフ構造のブートストラップの性質
大阪大学 大学院基礎工学研究科
永田 晴久
大阪大学 大学院基礎工学研究科
下平 英寿
本研究では，グラフ構造で表されるデータに対するブートストラップ法を提案する．グラフ構造にブート
ストラップ法が適用できれば，グラフ上の統計量の分布を観測データから求めることができるようになる．
しかし，グラフ構造はノード集合とエッジ集合の組として表されるため，通常の標本データと違ってリサン
プリング方法は自明ではなく，従来法をそのまま適用できないという問題がある．また，グラフ構造に対す
るブートストラップ法の研究は少なく，数理的な考察はほとんど行われていないのが現状である．
1
グラフ構造に対するブートストラップ法
いま，ノード数 n の無向グラフ G が観測されているとし，G の隣接行列を X = (xij ) とする．また，
エッジの総数を m =
∑
i<j
xij とおく．
提案法では，ブートストラップ複製 G∗ の隣接行列 X ∗ = (x∗ij ) を，次のように生成する．
∗
Xij
∗
Xij
∼ Po(1) (i < j, xij = 1)
= 0
(i < j, xij = 0)
このとき，G∗ は，多重エッジを持つ無向グラフとなる．
この複製方法は，エッジリサンプリング [1] の考えに基づいている．エッジリサンプリングとは，G のエッ
ジ集合 E = {e1 , . . . , em } を標本集合として，新しい標本集合 E ∗ = {ei(1) , . . . , ei(m) } を生成することであ
る．この方法で G∗ を作った場合には，エッジ数が元のグラフ G と常に等しく，ブートストラップ法として
適切でない場合がある．そこで，先に E ∗ の要素数 m∗ をポアソン分布 Po(m) によって決め，サンプリング
回数を変化させることで対応したのが上記の方法である．
2
ランダムグラフにおけるブートストラップ統計量
グラフ構造に対するブートストラップ法の例として，ランダムグラフにおけるエッジ数の分散の推定を考え
る．ランダムグラフ（Erd˝
os-R´enyi モデル）は，エッジ生成確率 p をパラメータとして Xij ∼ Bi(1, p) i.i.d.
によって生成される確率グラフである．このとき，エッジ数に関する統計量 T を
1 ∑
T (X) = √
Xij
n p i<j
とおくと，n → ∞ の極限で
E [V{T (X ∗ )|X}] = V{T (X)}
となる．ただし，p は n に依存して決まるとする．
同様にして，ノード次数など，Xij の部分和で表される統計量についても分散の一致性が成り立つ．この
結果は，Stochastic Block Model のようなランダムグラフベースのモデルにも容易に拡張できる．
参考文献
[1] 永田晴久，下平英寿 (2011)．グラフ構造のリサンプリングを行うブートストラップ法．2011 年度 統計関
連学会連合大会．
© Copyright 2024 ExpyDoc
