著者

鈴木 智也

出版者

情報処理学会

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.2, no.1, pp.70-78, 2009-02-20

---

自然界や社会に存在するネットワークには,スモールワールド現象を示すものが数多く存在する.スモールワールド現象とは,各ノードが局所的にクラスタ化している割には他の遠いノードと短いステップでアクセス可能という特徴を持ち,情報伝達のしやすさに関係している.この性質は Watts らによって,クラスタ係数と平均最短経路長により定義されている.平均最短経路長はダイクストラの方法を用いればネットワークの種類を問わず算出できるが,クラスタ係数においては有向グラフの場合,前処理なしでは計算できない.そこで本研究では,情報伝達の仕方を考慮することで前処理の方法を検討し,有向グラフでも適切にクラスタ係数を計算する手法を提案する.その妥当性を検証するために,Watts らが提案した Small-world ネットワークモデルを重み付き有向グラフに拡張し,本提案手法を適用した.さらに,今まで調査されてきた線虫の神経網などの実ネットワークについて本提案手法を適用したところ,従来よりも顕著にスモールワールド現象が確認された.To analyze a structure of natural or social networks, the small-world network structure is often discussed. In the small-world network, each node can be more highly clustered than the random network, and can access other nodes through fewer edges than the regular network. It is well known that the small-world network can effectively communicate and share information, and is defined by two measures: the cluster coefficient and the shortest path length. The shortest path length can be calculated by Dijkstra's algorithm, which can be applied to directed and/or weighted graphs. However, the cluster coefficient cannot be applied to directed networks. In this report, we propose a method to estimate the cluster coefficient for directed and weighted networks on the basis of how to propagate information sent by parent nodes. Then, we confirm the validity of the proposed method with the numerical network models which we proposed by extending the Watts-Strogatz model to directed and weighted type. Moreover, we apply the proposed method to real directed networks discussed by previous studies, and can confirm the small-world phenomena of real networks more clearly from the viewpoint of directed and weighted networks.