スパースネットワーク

ネットワーク科学において、疎なネットワークとは、そのネットワーク内の可能な最大リンク数よりもはるかに少ないリンクを持つネットワークのことである（反対は密なネットワークである）。疎なネットワークの研究は、ソーシャルネットワークやコンピュータネットワークなどの実際のネットワークの研究によって主に刺激された比較的新しい分野である。^{[ 1 ]}

リンクがはるかに少ないという概念は、もちろん口語的で非公式なものです。特定のネットワークの閾値を考案することはできますが、実際に「はるかに少ない」が何を意味するのかを定義する普遍的な閾値はありません。その結果、ほとんどの経験的ネットワークが実際に疎であるという広く合意があるにもかかわらず、有限ネットワークには疎性の正式な意味はありません。ただし、無限ネットワークモデルの場合には、ノード数 (N) が無限大に近づくときのエッジ数 (L) および/または平均次数 (⟨k⟩) の挙動によって決定される疎性の正式な意味があります。^{[ 2 ]}

サイズの単純な非加重ネットワーク${\displaystyle N}$ リンクの数が${\displaystyle L}$最大可能なリンク数よりもはるかに少ない${\displaystyle L_{max}}$: ^{[ 1 ]}

${\displaystyle L\ll L_{max}={N \choose 2}}$。

任意の（実際の）ネットワークでは、ノード数Nとリンク数Lは 2 つの数値にすぎないため、はるかに小さい符号の意味は（${\displaystyle \ll }$上記のような表現は完全に口語的で非公式な表現であり、「実際のネットワークの多くは疎である」といった表現も同様です。

しかし、合成グラフシーケンスを扱う場合${\displaystyle G_{N}}$または、ネットワークに対して明確に定義されたネットワークモデル${\displaystyle G_{N}}$任意のサイズN = 1,2,...,${\displaystyle \infty }$すると、${\displaystyle \ll }$通常の形式的な意味を獲得する：

${\displaystyle L\ll L_{max}\iff L=o(L_{max})\iff \lim _{N\rightarrow \infty }{\frac {L}{L_{max}}}=0}$。

言い換えれば、ネットワークシーケンスまたはモデル${\displaystyle G_{N}}$平均次数が（期待値）${\displaystyle \langle k\rangle =2L/N}$で${\displaystyle G_{N}}$Nに対して線形または準線形にスケーリングする：^{[ 2 ] [ 3 ]}

${\displaystyle G_{N}}$密度 が高い場合${\displaystyle \langle k\rangle =O(N)}$;

${\displaystyle G_{N}}$疎で ある場合${\displaystyle \langle k\rangle =o(N)}$。

疎なネットワークの重要なサブクラスは、平均次数が一定であるか、または一定値に収束するネットワークです。一部の著者は、そのようなネットワークのみを疎と呼んでいますが、他の著者はそれらに特別な名前を残しています: ^{[ 4 ]}

${\displaystyle G_{N}}$真に疎、極めて疎、または超疎で ある場合${\displaystyle \langle k\rangle =O(1)}$。

ネットワークスパース性のより厳密な定義も存在し、次数分布の収束を要求する。${\displaystyle G_{N}}$明確に定義された限界まで${\displaystyle N\rightarrow \infty }$[ ^{5 ]}この定義によれば、Nスターグラフ^は${\displaystyle S_{N}}$例えば、は疎ではありません。

ノード次数分布は接続性の増加に伴って変化します。Flickr Network Analysis が示唆するように、複雑なネットワークではリンク密度が異なるとノード次数分布も異なります。^{[ 6 ]}疎に接続されたネットワークはスケールフリーのべき乗則分布を持ちます。接続性の増加に伴い、ネットワークはべき乗則からの乖離が大きくなります。ネットワークの接続性に影響を与える主な要因の 1 つはノードの類似性です。たとえば、ソーシャル ネットワークでは、共通の社会的背景、興味、嗜好、信念などを共有している場合、人々は互いにリンクされる可能性が高くなります。生物学的ネットワークの文脈では、タンパク質やその他の分子は、複雑な表面が正確にまたは相補的に適合する場合にリンクされます。^{[ 6 ]}

ネットワーク内のノードに重みが付けられていない場合、ネットワークの構造要素は隣接行列によって表すことができます。行列内のほとんどの要素がゼロである場合、そのような行列は疎行列と呼ばれます。対照的に、ほとんどの要素がゼロでない場合、行列は密行列です。行列の疎性または密度は、行列内の要素の総数に対するゼロ要素の割合によって識別されます。同様に、グラフ理論の文脈では、リンクの数が最大数に近い場合、グラフは密グラフとして知られています。リンクの数が最大リンク数よりも少ない場合、この種のグラフは疎グラフと呼ばれます。^{[ 7 ]}

スパースネットワークは、ソーシャルネットワーク、コンピュータネットワーク、バイオネットワークに見られるほか、輸送、電力線、引用ネットワークなどにも応用されています。実際のネットワークのほとんどは大規模で疎であるため、それらを理解および分析するためのモデルがいくつか開発されました。 ^{[ 8 ]}これらのネットワークは、マルチプロセッサ組み込みコンピュータエンジニアリングにおけるスパースネットワークオンチップ設計に影響を与えています。

スパースネットワークは、隣接行列ではなく隣接リストとしてネットワークを格納する方が効率的であるため、計算コストも安くなります。たとえば、隣接リストを使用する場合、ノードの隣接ノードを反復処理するのにO(L/N)かかりますが、隣接行列の場合はO(N)かかります。^{[ 2 ]}