ネットワークの時間発展を評価するDensification Power-law（密化のべき乗則）

Published in

DeNAデータ分析ブログ

Jan 29, 2024

こんにちは、DeNAのデータアナリスト兼プロダクトマネージャーの佐々木亮です。この記事では、ネットワークサイエンスにおけるネットワークの構造と、その時間発展を評価する指標「Densification Power-law（密化のべき乗則）」について紹介します。

この記事では、まずは世の中でよく見られる特徴的なネットワークである「スケールフリーネットワーク（scale-free network）」について触れ、それらの時間発展がどのようにマクロ的な目線で観察できるのかを整理していきます。

スケールフリーネットワークとは？

ネットワークとは、ノード（点）とリンク（線）から成る複雑な組織体のことを指します。ネットワークの形成や機能についての研究がネットワークサイエンスです。その中で、最も基礎的な指標は登場するノード数と、それらをつなぐエッジ数です。それらの時間発展が、ネットワークのマクロな性質を決定します。

https://www.researchgate.net/figure/The-random-network-and-scale-free-network-A-Random-network-follows-Poisson_fig1_257301086

ネットワークには様々なタイプがあります。その中でもスケールフリーネットワーク（scale-free network）は、世の中でよく観察されるタイプで、特徴的な性質を持ちます。

スケールフリーネットワークでは、少数のノードが大量のリンクを持つ一方で、大多数のノードは少数のリンクしか持ちません。これは社会ネットワーク（人間関係）、インターネットにおけるハイパーリンク、生物ネットワーク（タンパク質の相互作用）など、自然界や社会全般に見られるパターンです。

例えば1例を詳しく書くと、インターネット上では一部のウェブサイトが非常に多くのリンクを集めている一方で、多くのウェブサイトは非常に少数のリンクしか得られない状況が見られるケースです。

このスケールフリーネットワークの特性には、ネットワーク全体の耐性や情報の伝播速度などさまざまな指標が大きく影響されます。また、この特性を理解することで、ネットワークの最適化や意思決定、予測などに役立てることができるようになります。

ネットワークサイエンスは、このように自然界や人間社会が持つネットワークの理解を深め、それらを応用して問題解決に取り組む学問と言えます。スケールフリーネットワークの理解は、それを達成する上で重要な一歩となるので、DeNAではこれらをサービス理解に応用しています。

ネットワークの時間発展の評価

ネットワークに新たなノード追加されてリンクを張る際に、既存のリンク数が多いノードに対して優先的にリンクを張る（優先的接続）性質が働くことがあります。この性質によって、スケールフリーネットワークが形成されます。

その影響で、ネットワークはどんどん”密化”していくことになります。このセクションでは、その密化と時間発展の関係性について整理していきます。特に、時間が経過しながら新たなノードが追加されてネットワークが成長していく過程を評価する時に利用できるのが、「Densification Power-law（密化のべき乗則）」です。

この法則を理解することで、ネットワークがどのように発展し変化していくかの予測や、ネットワークの挙動のマクロ分析が可能となります。具体的な数式を確認していきます。

ある時点tでのノード数をN(t)、エッジ数をE(t)とします。その次の時刻t+1のときのノード数が2倍になっているケースを考えます。すると、以下のように表現できると思います。

では、その時のエッジ数 E(t+1) はどうなるのでしょうか。スケールフリーネットワークのように優先的接続が発生するネットワークでは、 2E(t)ではなく、それよりも大きくなります。

その結果、エッジ数とノード数の関係性は以下のように記述されます。

これをDensificatino Power-law（密化のべき乗則）と言います。この時、αは密度指数であり、1 ≦ α ≦ 2の値をとります。スケールフリーではないネットワークでもこの式は成り立つため、αは1を含みます。α = 1の時、線形進化していくことを指すからです。この記事では、スケールフリーネットワークにフォーカスしているため、便宜上、上のような表現をしました。

α=2の時、ノード数の増加の2乗でエッジが増えていくため全結合ネットワークとなります。

これが実際のデータでどのような関係性になっているのかを論文をベースに確認していきます。

実際のネットワークで見る密化

こちらの研究でDensification Power-lawの挙動を確認していきます。

https://cis.temple.edu/~vasilis/Courses/CIS664/Papers/kdd05-Graphs-Over-Time.pdf

この研究では、論文オープンソースプラットフォームのarXivと特許（Patents）のサイテーションネットワーク、インターネットの自律システムネットワーク（Autonomous System）、arXivの著者と論文の2部グラフから出したAffiliation networkの4つについて分析しています。

これらの数年から数10年にわたるネットワークの時間発展をみているのが以下です。