時間的ネットワーク

時間的ネットワークは、時間変動ネットワークとも呼ばれ、リンクが特定の時点でのみアクティブになるネットワークです。各リンクは、アクティブになるタイミングに関する情報と、重みなどの他の可能な特性を保持します。時間変動ネットワークは、各リンクが接触の機会であり、接触の時間順序が含まれているため、情報や病気の拡散などの拡散プロセスに特に関連しています。

時間変動ネットワークの例としては、電話や電子メールなど、各リンクが比較的短く瞬間的な通信ネットワークが挙げられます。^{[1] [2]}情報は両方のネットワークを介して広がり、一部のコンピュータウイルスは 2 番目のネットワークを介して広がります。誰が誰にいつ遭遇したかをエンコードする物理的な近接性のネットワークは、時間変動ネットワークとして表すことができます。^[3]空気感染病原体などの一部の病気は、物理的な近接性を通じて広がります。時間分解された物理的な近接性ネットワークに関する実際のデータは、伝染病モデリングの改善に使用されています。^{[4]ニューロンの活性化は時間相関しているため、} ニューラルネットワークと脳ネットワークは時間変動ネットワークとして表すことができます。^[5]

時間変動ネットワークは、個々のリンクの規模で断続的に活性化されるという特徴があります。これは、ネットワーク全体の規模で全体的な時間依存性を含む可能性のある、ネットワーク進化のさまざまなモデルとは対照的です。

時間変動ネットワークは本質的に動的であり、ネットワーク上の拡散プロセスをモデル化するために使用されます。時間変動ネットワークを使用することで複雑さが増すかどうかは、問題となる相対的な時間スケールに依存します。時間変動ネットワークは、ネットワーク上の拡散プロセスとネットワーク自体が同様の時間スケールで進化するシステムを記述するのに最も役立ちます。^[6]

ネットワークの進化の特性タイムスケールを、拡散プロセスの進化の特性タイムスケールを とします。ネットワーク上のプロセスは、次の 3 つのカテゴリのいずれかに分類されます。 ${\displaystyle t_{N}}$${\displaystyle t_{P}}$

• 静的近似 – ここで、ネットワークは比較的ゆっくりと進化するため、プロセスのダイナミクスはネットワークの静的バージョンを使用して近似できます。${\displaystyle t_{N}\gg t_{P}}$
• 時間変動ネットワーク – ここで、ネットワークとプロセスは同程度の時間スケールで進化するため、それらの相互作用が重要になります。${\displaystyle t_{N}\sim t_{P}}$
• アニール近似 – ここで、ネットワークは比較的急速に進化するため、プロセスのダイナミクスはネットワークの時間平均バージョンを使用して近似できます。${\displaystyle t_{N}\ll t_{P}}$

インターネット上のデータの流れは、ネットワークパケットが通過するのにかかるほんの一瞬の間にネットワークがほとんど変化しないという、最初のケースの例です。 ^[7]性感染症の蔓延は、 2番目のケースの例です。性感染症の蔓延は、性行為ネットワーク自体の進化速度と直接相関して病気の蔓延が拡大するということです。^[8] 行動伝染は、3番目のケースの例です。行動は、多くの日常的な社会的相互作用を組み合わせたネットワークを介して人口全体に広がります。^[9]

時間とともに変化するネットワークデータには3つの一般的な表現方法がある。^[10]

• コンタクトシーケンス – 相互作用の持続時間が無視できる場合、ネットワークはコンタクトのセットとして表すことができます。ここで、はノード、 は相互作用の時間です。あるいは、各エッジがノードのペアであり、アクティブ時間のセットを持つエッジリストとして表すこともできます。${\displaystyle C}$${\displaystyle (i,j,t)}$${\displaystyle i}$${\displaystyle j}$${\displaystyle t}$${\displaystyle E}$${\displaystyle e}$${\displaystyle T_{e}=\{t_{1},\ldots ,t_{n}\}}$
• 間隔グラフ - 相互作用の持続時間が無視できない場合、エッジがアクティブになる間隔のセットになります。${\displaystyle T_{e}}$${\displaystyle e}$${\displaystyle T_{e}=\{(t_{1},t_{1}'),\ldots ,(t_{n},t_{n}')\}}$
• スナップショット - 時間とともに変化するネットワークは、各時間ステップごとに 1 つずつ、一連​​の静的ネットワークとして表すこともできます。

静的ネットワークを特徴付けるために使用される尺度は、時間変動ネットワークにそのまま転用できるものではありません。パス、接続性、距離、中心性を参照してください。ただし、これらのネットワーク概念は、時間変動ネットワークに適用できるように調整されています。

時間尊重パスは、次に通過するリンクが現在のリンクの後のある時点でアクティブになるという制約の下で、時間変動ネットワークで通過できるリンクのシーケンスです。有向グラフと同様に、からへのパスは、からへのパスがあることを意味しません。ただし、静的ネットワークや進化型ネットワークのパスとは対照的に、時間尊重パスは非推移的でもあります。つまり、 から へのパスと から へのパスがあるからといって、からへのパスがあるという意味ではありません。さらに、時間尊重パス自体が時間変動しており、特定の時間間隔でのみ有効なパスです。^[11]${\displaystyle i}$${\displaystyle j}$${\displaystyle j}$${\displaystyle i}$${\displaystyle i}$${\displaystyle j}$${\displaystyle j}$${\displaystyle k}$${\displaystyle i}$${\displaystyle k}$

静的ネットワークの連結性と類似しているが、到達可能性はネットワーク内の各ノードに対して最もよく定義される時間変動特性である。ノードの影響集合は、時間を考慮した経路を介して到達できるすべてのノードの集合であり、開始時間に依存することに注意する。ノードのソース集合は、指定された時間間隔内に時間を考慮した経路を介して到達できるすべてのノードの集合である。到達可能性比は、影響集合内のノードの割合のすべてのノードの平均として定義できる。^[12]${\displaystyle i}$${\displaystyle i}$${\displaystyle t}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$

ネットワーク全体の接続性は、いくつか提案されているものの、決定的に定義されていません。コンポーネント内のすべてのノードを両方向に接続する有向時間尊重パスがある場合、コンポーネントは強く接続されていると定義できます。コンポーネント内のすべてのノードを両方向に接続する無向時間尊重パスがある場合、コンポーネントは弱く接続されていると定義できます。 ^{[13]また、コンポーネント内のノードのサブセットに対して}推移性が成り立つ場合、コンポーネントは推移的に接続されていると定義できます。

因果忠実度は、時間的ネットワークの静的近似の良し悪しを定量化する。このような静的近似は、時間的ネットワークのエッジを時間の経過とともに集約することによって生成される。因果忠実度の考え方は、時間的ネットワーク内のすべてのノードペア間のパスの数（つまり、すべての時間を尊重するパス）を、ネットワークの静的近似内のすべてのノード間のパスの数と比較することです。 ^[14]因果忠実度は次のように定義されます。 ${\displaystyle P_{temp}}$${\displaystyle P_{stat}}$

${\displaystyle c={\frac {P_{temp}}{P_{stat}}}}$。

では、時間を尊重するパスのみが考慮されるため、 となり、結果としてとなります。因果忠実度が高いということは、考慮する時間的ネットワークが、その静的 (集約された) 対応物によって十分に近似されていることを意味します。 の場合、静的表現で到達可能なノード ペアのほとんどは、時間的ネットワーク内の時間を尊重するパスによって接続されていません。 ${\displaystyle P_{temp}}$${\displaystyle P_{temp}\leq P_{stat}}$${\displaystyle 0\leq c\leq 1}$${\displaystyle c\approx 1}$${\displaystyle c\ll 1}$

遅延は時間的距離とも呼ばれ、距離の時間変動に相当します。時間変動ネットワークでは、時間を考慮するパスにはいずれも期間、つまりそのパスをたどるのにかかる時間があります。2 つのノード間の最速のパスは遅延ですが、開始時間にも依存することに注意してください。時刻に始まるノード間の遅延は で示されます。 ${\displaystyle i}$${\displaystyle j}$${\displaystyle t}$${\displaystyle \lambda _{i,t}(j)}$

時間変動ネットワーク上の中心性の測定は、距離をレイテンシに単純に置き換えることで実現できる。^[15]静的ネットワーク上の中心性測定に関する議論については、Centralityを参照のこと。

• 近接中心性は、他のすべてのノードに近いノード（つまり、すべてのノードのレイテンシが小さい）では大きい。${\displaystyle i}$${\displaystyle \lambda _{i}(j)}$${\displaystyle j}$

${\displaystyle C_{C}(i,t)={\frac {N-1}{\sum _{j\not =i}{\lambda _{i,t}(j)}}}}$

• 媒介中心性は、他のノードペア間の最小遅延パスの一部であることが多いノードでは大きくなります。媒介中心性は、から通過する最小遅延パスの数とから通過する最小遅延パスの総数の比率として定義されます。${\displaystyle j}$${\displaystyle k}$${\displaystyle i}$${\displaystyle j}$${\displaystyle k}$

${\displaystyle C_{B}(i,t)={\frac {\sum _{i\not =j\not =k}{\nu _{i}(j,k)}}{\sum _{i\not =j\not =k}{\nu _{(}j,k)}}}}$

レイテンシは時間とともに変化する性質があり、特に、時間がネットワーク間隔の終了に近づくにつれて、すべてのノード ペアに対して無限大になるため、近さの代替測定が役立ちます。効率では、代わりにレイテンシの逆数を使用するため、効率は発散するのではなくゼロに近づきます。効率の値が高いほど、ネットワーク内のノードの中心度が高くなります。

${\displaystyle C_{E}(i,t)={\frac {1}{N-1}}\sum _{j\not =i}{\frac {1}{\lambda _{i,t}(j)}}}$

時間変動ネットワークにより、ネットワークの時間依存特性を明示的に分析できます。時間変動データから、繰り返し発生する持続的な接触パターンをさまざまな方法で抽出できます。これは現在も研究が続けられている分野です。

• システムの特性時間は、到達可能性比などの変数の明確な変化を探すことで見つけることができます。たとえば、レイテンシを計算する際にすべてのノードで有限の待機時間のみを許可すると、結果として得られる到達可能性比に興味深いパターンが見つかります。モバイル通話ネットワークの場合、少なくとも2日間の遅延を許可すると到達可能性比が大幅に増加することが判明しており、航空会社のネットワークでは約30分で同じ効果が見られました。^[16]さらに、時間ネットワークの特性時間スケールは、最短パス期間の分布のモードによって与えられます。この分布は、ネットワーク内のすべてのノードペア間の到達可能性を使用して計算できます。^[14]
• 永続的なパターンとは、システム内で頻繁に繰り返されるパターンのことです。システムのさまざまな時間間隔にわたって平均化し、指定されたしきい値を超えて繰り返されるパターンを探すことで、永続的なパターンを発見できます。^[17]${\displaystyle \Delta t}$
• モチーフとは、システム内で予想されるよりも頻繁に発生する特定の時間的パターンです。たとえば、Facebookのウォール投稿の時間変動ネットワークでは、ランダム化されたネットワークで予想されるよりも高い頻度でチェーン、スター、および前後の相互作用が発生します。^[18]
• エゴセントリック・テンポラル・モチーフは、時間的エゴネットワークを活用するために使用できます。その一次複雑性により、大規模なグラフでも妥当な実行時間でカウントできます。たとえば、Longa ら^{[19] は、}さまざまな社会的コンテキストでの対面インタラクションネットワーク間の距離を測定するためにエゴセントリック・テンポラル・モチーフを使用する方法を示しています。
• 欠落したリンクの検出

時間変動ネットワークにより、ネットワーク上の動的プロセスのまったく新しい次元を分析できます。ネットワークとプロセスの進化の時間スケールが類似している場合、時間変動ネットワークの時間的構造は、ネットワーク上のプロセスの広がりに劇的な影響を及ぼします。

個々のノードまたはリンクにおける 2 つの連続するイベント間の時間は、イベント間時間と呼ばれます。重要な実世界の時間変動ネットワークのイベント間時間の分布はバースト性があることがわかってきています。つまり、イベント間時間は非常に不均一で、裾が重い分布になっています。これは、アクティビティがバースト的に発生し、その間に長い非アクティビティ期間が挟まれるという活性化パターンにつながります。^[20]

イベント間の時間のバースト性は、ネットワーク上の拡散プロセスを劇的に遅らせる可能性があり、^[21]これは病気、情報、アイデア、コンピュータウイルスの拡散に影響を及ぼします。しかし、バースト性は拡散プロセスを加速させる可能性があり、他のネットワーク特性も拡散速度に影響を与えます。 [ ^22]したがって、現実世界の時間変動ネットワークは、イベント間の時間の分布がバースト的であるにもかかわらず、拡散プロセスを促進する可能性があります。^[23]

経験量としてのバースト性は、任意のイベント間時間のシーケンス に対して、そのシーケンスをポアソン過程によって生成されたシーケンスと比較することによって計算できます。ポアソン過程の標準偏差と平均の比は。この測定値は1 と比較されます。 ${\displaystyle \tau }$${\displaystyle \sigma }$${\displaystyle m}$${\displaystyle \sigma _{\tau }/m_{\tau }\ }$

${\displaystyle B={\frac {\sigma _{\tau }/m_{\tau }\ -1}{\sigma _{\tau }/m_{\tau }\ +1}}}$

バースト性は−1から1まで変化する。B = 1は 最大バーストシーケンスを示し、B  = 0はポアソン分布を示し、B  = −1は周期シーケンスを示す。^[24]

• 複雑な伝染
• 複雑なネットワーク
• 流行モデル
• 指向性浸透
• 動的ネットワーク分析
• 指数ランダムグラフモデル
• リンク中心の優先接続
• スケールフリーネットワーク
• 浸透理論