ネットワークデータ分析の自己相似性

コンピュータ ネットワークでは、自己相似性はネットワーク データ転送ダイナミクスの特徴です。ネットワーク データ ダイナミクスをモデル化する場合、自己回帰移動平均モデルなどの従来の時系列モデルは適切ではありません。これは、これらのモデルではモデル内のパラメーターの数が有限であり、したがって有限の時間枠内での相互作用しか提供されないのに対し、ネットワーク データは通常、長期にわたる時間的構造に依存しているためです。自己相似プロセスは、このような長期の相関関係を持つネットワーク データ ダイナミクスをモデル化する 1 つの方法です。この記事では、自己相似プロセスのコンテキストでネットワーク データ転送ダイナミクスを定義し、説明します。プロセスの特性を示し、ネットワーク データの自己相似性をモデル化するパラメーターを グラフ化および推定する方法を示します。

が平均、分散、自己相関関数を持つ弱定常（2 次定常）過程であるとします。自己相関関数がという形式である とします。ここで、 および は無限大で緩やかに変化する関数であり、すべての に対してとなります。たとえば、および は緩やかに変化する関数です。 とします。ここで、 は、サイズ の重複しないブロック上の集約された点列を表します。各 は正の整数です。 ${\displaystyle X}$${\displaystyle \mu}$${\displaystyle \sigma ^{2}}$${\displaystyle \gamma (t)}$${\displaystyle \gamma (t)}$${\displaystyle \gamma (t)\rightarrow t^{-\beta }L(t)}$${\displaystyle t\to \infty }$${\displaystyle 0<\beta <1}$${\displaystyle L(t)}$${\displaystyle \lim _{t\to \infty}{\frac {L(tx)}{L(t)}}=1}$${\displaystyle x>0}$${\displaystyle L(t)=const}$${\displaystyle L(t)=\log(t)}$
${\displaystyle X_{k}^{(m)}={\frac {1}{m^{H}}}(X_{km-m+1}+\cdot \cdot \cdot +X_{km})}$${\displaystyle k=1,2,3,\ldots }$${\displaystyle m}$${\displaystyle m}$

• ${\displaystyle X}$と同じ分布に従う自己相似パラメータが存在する場合、 は完全自己相似過程と呼ばれます。 の完全自己相似過程の例としては、の分数ガウスノイズ(FGN)があります。${\displaystyle H}$${\displaystyle X_{k}^{(m)}}$${\displaystyle X}$${\displaystyle H}$${\displaystyle {\frac {1}{2}}<H<1}$

定義:分数ガウスノイズ (FGN)

${\displaystyle X(t)=B_{H}(t+1)-B_{H}(t),~\forall t\geq 1}$は分数ガウスノイズと呼ばれ、分数ブラウン運動である。^[1]${\displaystyle B_{H}(\cdot )}$

• ${\displaystyle X}$と同じ分散と自己相関を持つ自己相似パラメータが存在する場合、は正確に2次の自己相似過程と呼ばれます。${\displaystyle H}$${\displaystyle X_{k}^{(m)}}$${\displaystyle X}$

• ${\displaystyle X}$は、のとき、自己相似パラメータを持つ漸近的2次自己相似過程と呼ばれる。${\displaystyle H}$${\displaystyle \gamma^{(m)}(t)\to {\frac {1}{2}}[(t+1)^{2H}-2t^{2H​​}+(t-1)^{2H}]}$${\displaystyle m\to \infty }$${\displaystyle ~\forall t=1,2,3,\ldots }$

を平均、分散 の弱定常（2次定常）過程と 仮定する。ラグの自己相関関数（ACF）は次のように与えられる。${\displaystyle X(t)}$${\displaystyle \mu}$${\displaystyle \sigma ^{2}}$${\displaystyle t}$${\displaystyle \gamma (t)={\mathrm {cov} (X(h),X(h+t)) \over \sigma ^{2}}={E[(X(h)-\mu )(X(h+t)-\mu )] \over \sigma ^{2}}}$

意味：

弱定常過程は、次のような場合「長距離依存性」があると言われる。${\displaystyle \sum _{t=0}^{\infty }|\gamma (t)|=\infty }$

を満たすプロセスは長距離依存性があると言われています。長距離依存性のスペクトル密度関数は、原点付近でべき乗法則に従います。 と同様に、自己相関関数のスペクトル密度関数がとしての形を持ち、が 0 でゆっくり変化する 場合は、 は長距離依存性を持ちます。${\displaystyle \gamma (t)\rightarrow t^{-\beta }L(t)}$${\displaystyle t\to \infty }$${\displaystyle \gamma (t)\rightarrow t^{-\beta }L(t)}$${\displaystyle X}$${\displaystyle f_{t}(w)=\sum _{t=0}^{\infty }\gamma (t)e^{iwt}}$${\displaystyle w^{-\gamma }L(w)}$${\displaystyle w\to 0}$${\displaystyle 0<\gamma <1}$${\displaystyle L}$

参照

${\displaystyle X^{(m)}={\frac {1}{m}}(X_{1}+\cdot \cdot \cdot +X_{m})}$
自己相似過程の自己相関関数が を満たす場合、 も を満たすことを意味します。ここで、 はm に依存しない有限の正の定数であり、0<β<1 です 。${\displaystyle \gamma (t)\rightarrow t^{-\beta }L(t)}$${\displaystyle t\to \infty }$${\displaystyle Var(X^{(m)})\to am^{-\beta }}$${\displaystyle m\to \infty }$${\displaystyle a}$

基礎となるプロセスが分数ガウスノイズであると仮定します。級数 を考え、 とします。${\displaystyle X}$${\displaystyle X_{(1)},\ldots ,X_{(n)}}$${\displaystyle Y_{(n)}=\sum _{i=1}^{n}X_{(i)}}$

の標本分散は${\displaystyle X_{(i)}}$${\displaystyle S^{2}(n)={\frac {1}{n}}\sum _{i=1}^{n}X_{(i)}^{2}-({\frac {1}{n}})^{2}Y_{n}^{2}}$

定義:R/S 統計

${\displaystyle {\frac {R}{S}}(n)={\frac {1}{S(n)}}[\max _{0\leq t\leq n}(Y_{t}-{\frac {t}{n}}Y_{n})-\min _{0\leq t\leq n}(Y_{t}-{\frac {t}{n}}Y_{n})]}$

が FGN の場合、 回帰モデル の近似を検討します。 、ここで 特に、長さ の時系列 の場合、時系列データをサイズ のグループに分割し、各グループについて を計算します。 したがって、各 n について、データのペア ( ) が得られます。各 について点があるため、回帰モデルを近似してより正確に推定できます。回帰直線の傾きが 0.5~1 の場合、それは自己相似プロセスです。 ${\displaystyle X_{(i)}}$${\displaystyle E({\frac {R}{S}}(n))\to C_{H}\times n^{H}}$
${\displaystyle \log {\frac {R}{S}}(n)=\log(C_{H})+H\log(n)+\epsilon _{n}}$${\displaystyle \epsilon _{n}\thicksim N(0,\sigma ^{2})}$
${\displaystyle N}$${\displaystyle k}$${\displaystyle {\frac {N}{k}}}$${\displaystyle {\frac {R}{S}}(n)}$
${\displaystyle k}$${\displaystyle \log(n),\log {\frac {R}{S}}(n)}$${\displaystyle k}$${\displaystyle n}$${\displaystyle H}$

標本平均の分散は で与えられます。H を推定するには、長さ のサブシリーズの標本平均を計算します。全体の平均は、標本分散 で与えられます。 分散-時間プロットはに対して プロットすることで得られ、k の小さな値を無視して、平面上の結果の点を通る単純な最小二乗線を当てはめることができます。 ${\displaystyle Var({\bar {X}}_{n})\to cn^{2H-2},~\forall c>0}$
${\displaystyle {\bar {X}}_{1},{\bar {X}}_{2},\cdots ,{\bar {X}}_{m_{k}}}$${\displaystyle m_{k}}$${\displaystyle k}$
${\displaystyle {\bar {X}}(k)={\frac {1}{m_{k}}}\sum _{i=1}^{m_{k}}{\bar {X}}_{i}(k)}$${\displaystyle S^{2}(k)={\frac {1}{m_{k}-1}}\sum _{i=1}^{m_{k}}({\bar {X}}_{i}(k)-{\bar {X}}(k))^{2}}$
${\displaystyle \log S^{2}(k)}$${\displaystyle \log k}$

の大きな値の場合、プロット上の点は負の傾きを持つ直線の周りに散在することが予想されます。観測値間の短期的な依存性または独立性の場合、直線の傾きは-1に等しくなります。 自己相似性は、漸近的に-1と0の間の推定傾きの値から推測でき、自己相似性の程度の推定値は次のように与えられます。${\displaystyle k}$${\displaystyle 2H-2}$
${\displaystyle {\hat {H}}=1+{\frac {1}{2}}(slope).}$

Whittle の近似最大尤度推定量 ( MLE ) は、 のスペクトル密度を介してハーストパラメータを解くために適用されます。これは、ハーストパラメータを視覚化するツールであるだけでなく、MLE の漸近特性を介してパラメータに関する統計的推論を行う方法でもあります。特に、 はガウス過程 に従います。 のスペクトル密度、 、ここで 、およびは、を伴う である短期時系列自己回帰 (AR) モデルを構築します。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle f_{x}(w;\theta )=\sigma _{\epsilon }^{2}f_{x}(w;(1,\eta ))}$${\displaystyle \theta =(\sigma _{\epsilon }^{2},\eta )=(\sigma _{\epsilon }^{2},H,\theta _{3},\ldots ,\theta _{k}),H={\frac {\gamma +1}{2}}}$${\displaystyle \theta _{3},\ldots ,\theta _{k}}$${\displaystyle X_{j}=\sum _{i=1}^{k}\alpha _{i}X_{j-i}+\epsilon _{j}}$${\displaystyle Var(\epsilon _{j})=\sigma _{\epsilon }^{2}}$

したがって、ホイットルの の推定量は関数 を最小化します。ここで、は Xの周期グラムを として表します。これらの積分はリーマン和によって評価できます。${\displaystyle {\hat {\eta }}}$${\displaystyle \eta }$${\displaystyle Q(\eta )=\int _{-\pi }^{\pi }{\frac {I(w)}{f(w;(1,\eta ))}}\,dw}$${\displaystyle I(w)}$${\displaystyle (2\pi n)^{-1}|\sum _{j=1}^{n}X_{j}e^{iwj}|^{2}}$${\displaystyle {\hat {\sigma }}^{2}=\int _{-\pi }^{\pi }{\frac {I(w)}{f(w;(1,{\hat {\eta }}))}}\,dw}$

無限移動平均モデルの形式として表現できる場合、漸近的 には正規分布に従います。${\displaystyle n^{1/2}({\hat {\theta }}-\theta )}$${\displaystyle X_{j}}$

を推定するには、まずこのピリオドグラムを計算する必要があります。 はスペクトル密度の推定値であるため、長距離依存性を持つ系列は、原点の近くで に比例するピリオドグラムを持つ必要があります。 ピリオドグラムのプロットは、 に対してプロットすることで得られます。次に、の 回帰モデルを に当てはめると、傾き が得られます。 当てはめられた直線の傾きは、 の推定値でもあります。 したがって、推定値が得られます。 ${\displaystyle H}$${\displaystyle I_{n}(w)}$${\displaystyle |\lambda |^{1-2H}}$${\displaystyle \log(I_{n}(w))}$${\displaystyle \log(w)}$
${\displaystyle \log(I_{n}(w))}$${\displaystyle \log(w)}$${\displaystyle {\hat {\beta }}}$${\displaystyle 1-2H}$${\displaystyle {\hat {H}}}$

注:
ピリオドグラム法を適用する場合、2 つの一般的な問題があります。まず、データがガウス分布に従わない場合、データの変換によってこの種の問題を解決できます。次に、想定されるスペクトル密度から外れたサンプル スペクトルも別の問題です。この問題を解決するには、集約法が提案されています。 がガウス過程であり、 のスペクトル密度関数がを満たす場合、関数 は として分布的に FGN に収束します。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle w^{-\gamma }L(w)}$${\displaystyle w\to \infty }$${\displaystyle m^{-H}L^{-{\frac {1}{2}}}(m)\sum _{i=(j-1)m+1}^{m}k(X_{i}-E(|X_{i}|)),~j=1,2,\ldots ,[{\tfrac {n}{m}}]}$${\displaystyle m\to \infty }$

• P. Whittle、「定常時系列の推定と情報」、Art. Mat. 2、423-434、1953 年。
• K. PARK、W. WILLINGER、「自己相似ネットワークトラフィックとパフォーマンス評価」、WILEY、2000 年。
• WE Leland、W. Willinger、MS Taqqu、DV Wilson、「イーサネット トラフィックの自己相似性について」、ACM SIGCOMM Computer Communication Review 25、202-213、1995。
• W. Willinger、MS Taqqu、WE Leland、DV Wilson、「高速パケット トラフィックの自己相似性: イーサネット トラフィック測定の分析とモデル化」、Statistical Science 10、67-85、1995。