二部グラフ的性質を考慮した複雑ネットワーク成長モデル

現実世界の様々な現象はノードとノード間を結ぶリンクで構成されるネットワークとして捉えることができる.ネットワーク中のリンクが密に存在するノード集合をコミュニティと呼び,コミュニティが成長過程に影響を及ぼしている.ネットワークの中には,二部グラフで表現できるものが多数存在し,二部グラフでもコミュニティがネットワーク成長に影響を及ぼす.しかし,二部グラフのコミュニティは,一部グラフとは異なり,各コミュニティが多数のコミュニティと関係を持つと考えられる.従って,影響の仕方が一部グラフとは異なるはずである.これまでのネットワークコミュニティ抽出手法では,二部グラフのコミュニティにおける多対多の関係を適切に捉えているとは言えない.そこで報告者は,これまでコミュニティ解析によく用いられてきた指標を多対多の関係を持つコミュニティを評価するように拡張した.この提案指標で多対多のコミュニティ構造を持つ二部グラフに対して適切なコミュニティ構造を評価すると,ランダムに生成したコミュニティ構造よりも高い値を示すことを確認した.また,指標の値を高くするようなコミュニティ構造を得る高速な手法を開発した.前年度に開発したコミュニティ分割手法を用いて二部グラフをコミュニティ分割し,対応度行列を観察することによって,現実のコミュニティはほぼ一対一のコミュニティ対応関係を持つことが分かった.しかし,現在の指標では,コミュニティ間リンク密度に対してコミュニティ数が多い場合,誤った分割が得られることが分かった.そのため,指標を改良する必要が出てきている。また,有向グラフを二部グラフ化することにより,同手法を有向グラフ対応させることに成功した.その結果,有向グラフの流れ構造を明らかにできた.今年度の成果によって,二部グラフ,及び有向グラフのコミュニティの性質が明らかになったと言える.

現実世界の様々な現象はノードとノード間を結ぶリンクで構成されるネットワークとして捉えることができる.ネットワーク中のリンクが密に存在するノード集合をコミュニティと呼び,コミュニティが成長過程に影響を及ぼしている.ネットワークの中には,二部グラフで表現できるものが多数存在し,二部グラフでもコミュニティがネットワーク成長に影響を及ぼす.しかし,二部グラフのコミュニティは,一部グラフとは異なり,各コミュニティが多数のコミュニティと関係を持つと考えられる.従って,影響の仕方が一部グラフとは異なるはずである.これまでのネットワークコミュニティ抽出手法では,二部グラフのコミュニティにおける多対多の関係を適切に捉えているとは言えない.そこで報告者は,これまでコミュニティ解析によく用いられてきた指標を多対多の関係を持つコミュニティを評価するように拡張した.この提案指標で多対多のコミュニティ構造を持つ二部グラフに対して適切なコミュニティ構造を評価すると,ランダムに生成したコミュニティ構造よりも高い値を示すことを確認した.また,指標の値を高くするようなコミュニティ構造を得る高速な手法を開発した.前年度に開発したコミュニティ分割手法を用いて二部グラフをコミュニティ分割し,対応度行列を観察することによって,現実のコミュニティはほぼ一対一のコミュニティ対応関係を持つことが分かった.しかし,現在の指標では,コミュニティ間リンク密度に対してコミュニティ数が多い場合,誤った分割が得られることが分かった.そのため,指標を改良する必要が出てきている。また,有向グラフを二部グラフ化することにより,同手法を有向グラフ対応させることに成功した.その結果,有向グラフの流れ構造を明らかにできた.今年度の成果によって,二部グラフ,及び有向グラフのコミュニティの性質が明らかになったと言える.