untitled

ネットワーク理論最前線

基礎から応用まで

-独立行政法人 産業技術総合研究所

知能システム研究部門

分散システムデザイングループ

小島 一浩

イントロダクション

http://opte.org/ インターネットの地図 tracerouteコマンドでIPアドレス空間 を収集 注意：

Network Science発展の背景

†

大規模データを容易に入手

・インターネット

http://opte.org

http://research.lumeta.com/ches/map

http://www.caida.org/home

・映画データベース

http://www.imdb.com

・論文データベース

http://citeseer.ist.psu.edu http://arxiv.org

†

計算機の能力（計算速度，記憶容量）の向上

†

（統計）物理学者の参入

Network Scienceの歴史

1736 ケーニヒベルグ問題 1967 Small World実験 1960 Random Graphモデル 1998 Watts論文1999 Barabasi論文

アジェンダ

†

イントロダクション

†

基礎編：古典から現代へ

†

応用編：産総研の研究者コミュニティ

基礎編：

What is Complex Networks?

†

明確は定義はない

†

私的理解

Complex Networks理論とは

（１）ネットワークを構成する頂点や辺に対し特徴量を定義

（２）構造と機能の関係を探求

（３）所望する特徴量を有するネットワーク（構造→機能）を構成するア

ルゴリズムを探求

するグラフ理論の一分野

従来のネットワーク理論とは，どのように違うのか？

グラフ理論

†

L. Euler (1707 - 1783)

・

Konigsburg Problem (1736)

(ケーニヒベルグ問題)

グラフ理論： ノードの集合とエッジに集合で構成される グラフの性質を研究する． ネットワーク： エッジに重みや長さなどの属性が付与され たグラフ

グラフの定義

†

定義

頂点の集合

V，辺の集合E，各辺に2頂点を対

応させる接続関数Φ

Random Networks

†

P. Erdos (1913 - 1996)

・放浪の数学者

・多くの論文を残す

・

Erdos Number

・

Random Graphの研究

Erdos-Renyi Model

ER Random Graph Model

1 N

N nodes, M edges : G(N,M)

N(N-1)/2 edges

Probability p : G(N, p)

M =pN

ER Random Graph Model

1 N

G(N, p)

□p=N

-1

_閉路

□p=log(N)/N 連結

□Degree Distribution : P(k)

P(k)=

_N-1

C

_k

p

k

_(1-p)

N-1-k

-> exp(-λ)λ

k

_/k!

(N->∞, p->0, pN->λ)

□Diameter : d

d=log(N)/log(pN)

≒log(N)/log(<k>)

ネットワークの古典的クラス

Network Random Network Regular Network

この状態が

20世紀末までつづく

知的財産マネジメント研究会＠GRIPS 14

実際のネットワーク

†

World Wide Web

†

Erdos number

†

Protein network

†

Telephone network

†

Coauthor network

†

…

Model?

ER Random Network Model

Small World現象

acquaintance acquaintance

It’s a Small World!

Stanley Milgram

†

S. Milgram (1933 - 1984)

・

Yale University

・

social psychology

・巧みな実験

＊

Milgram実験

＊

Small World実験

実験設定に問題が多いという批判もある

J. Kleinfeld, The Small world problem, Society, 39(2),

pp.61-66, 2002

Small World現象

acquaintance acquaintance

It’s a Small World!

Q1. 任意のXとZは知り合いではないが， 共通の知人Yをもつのか？

Q2. 任意のXとZは知り合いではないが， a,b,…,yを介してつながっているのか？ またその仲介数は？

S. Milgram: ”The Small-World Problem”,

知的財産マネジメント研究会＠GRIPS 18

Small World実験

Target Name : Bob Business: Trader Address : Boston Source Nebraska 5.5 steps => ６次の隔たり Q1. 任意のXとZは知り合いではないが， 共通の知人Yをもつのか？ には答えていない！

ER Random Graph Model

X Z Y 1 N

G(N, p)

□

Diameter : d

d=log(N)/log(pN)≒log(N)/log(<k>)

直径は小さくて知人ネットワークのモデル

として妥当？

□問題

Small World現象：XとZが共通の知人を持つ

確率は「結構」高い．

ERモデル：XとZが共通に知人Yを持つ確率は，

ほぼ

p(<<1)

Small World Networks

†

Duncan J. Watts

・

Columbia University

D. J. Watts and S. H. Strogatz:

“Collective dynamics of ’small-world’ networks”,

Nature, Vol. 393, No. 4, pp. 440–442 (1998)

∑

=

Γ

=

= N i i i k i i

C

N

C

C

E

C

1 2

1

,

)

(

・Clustering coefficient: X ・Small World: 1. Low Diameter 2. High Clustering

Random Rewiringアルゴリズム

Small World

Small World:

□

Low Diameter

□

High Clustered

Low Diameter

<=Shortcut Path,

知的財産マネジメント研究会＠GRIPS 22

Scale Free Networks

†

Albert-László Barabási

・

University of Notre Dame

A. L. Barabasi and R. Albert: “Emergence of Scaling in Random Networks”, Science,

Vol. 286, pp. 509–512 (1999) ・WWWのHyperlink

(Pages：325,729，Links：1,469,680) ・degree distribution:P(k)∝k-γ

Power Low = Scale Free ・diameter :d ≒ 11.2 => New class!

Scale Free Networks

・degree distribution:P(k)∝k-γ

Hub Node

Preferential Attachmentアルゴリズム

∑

=

∂

∂

j j i i

k

k

t

k

・

Growing Process

・

Preferential Attachment

Small World Networks

or Scale Free Networks

□ER Random Network ・Low Diameter

□Small World Network ・Low Diameter

・High Clustered (Clustering Coefficient) □Scale Free Network

・Low Diameter

・Hub Node (Power Low Degree Distribution) def1. 広義のSmall World = Low Diameter

ER Random Network, Small World Network, Scale Free Network def2. 狭義のSmall World = Low Diameter and High Clustered Small World Network

ネットワークのクラス

Networks Random Networks Regular Networks Small World Networks Scale Free Networks

Comple

x Netw

_orks

Complex Networks

†

Mark E. J. Newman

・

Santa Fe Institute

Complex Systems

Self-Organizing Systems

の流れを汲む

M. E. J. Newman: “The Structure and Function of Complex Networks”, SIAM Review, vol45, pp167-256 (2003)

ネットワークの構造と特徴量

† パス長(characteristic path length)

† 中心性(centrality) † 次数分布(degree distribution) † クラスタリング係数(clustering coefficient) † 次数相関(degree correlation) † 隣接行列スペクトル(spectrum) † モジュール性(modularity) ,etc モデル リアル

階層構造と特徴量：モデル

E. Ravasz and A. L. Barabasi,

Physical Review E, 67, 026112, 2003, Hierarchical organization in complex networks

階層構造と特徴量：理論値

階層構造の有無（なし：優先的選択モデル）の比較 ・次数 – クラスタリング係数分布

・クラスタリング係数のサイズ効果 で明らかな違い

最近のトピック

†

コミュニティ構造，モジュール構造

†

構造から機能へ

†

ネットワーク上のダイナミクス（拡散・伝播）

†

ネットワークのダイナミクス（生成・崩壊・組み

換え）

†

Navigation問題

†

可視化

応用編：

明示的組織構造 – 縦割り組織

□研究センター 重要課題解決に向けた短期集中的研究展開 (最長7 年) 研究資源(予算，人，スペース) の 優先投入トップダウン型マネージメント． 25 センター設置． □研究部門 一定の継続性をもった研究展開とシーズ発掘 ボトムアップ型テーマ提言と長のリーダーシッ プによるマネージメント． 21 研究部門設置． □研究ラボ 分野融合の促進，行政ニーズへの機動的対応 新しい研究センター，研究部門の立ち上げに 向けた研究推進． 5 研究ラボ設置．

内側からの視点

□ 組織改変による人事異動 □ 地理的分散 □ 日常業務の増加 ■ 隣の研究室でどのような研究をしているか分からない ■ 連帯感の欠如 ■ 蛸壺的 例： ある研究を始めるのに専門家を外部の人から紹介してもらったら， 隣の研究室の人だった．．． 疑問： 異分野連携を唱えているが，本当に実行されているのか？

成果データベース

論文の共著関係を使用 産総研では，研究成果発表をデータベース化 1.誌上発表 2.口頭発表 3.著書・刊行物・調査報告 5.地球科学情報 6.計量技術情報・工業標準化 7.ソフトウェア， 8.データベース 9.プレス発表 10.イベント展示 記録属性： □発表属性： 記録ID, 登録日，発表タイトル，要旨，キーワード □筆頭者・共著者属性： 職員ID，名前，所属コード，所属

調査データ

2001 – 2005年度の誌上および口頭発表

注：内部研究者，外部研究者の識別は職員IDを使用．

外部研究者でIDが付与される場合がある 外部研究者は名前で識別

ネットワーク解析

†

ネットワーク特徴量

・

Size Rank

・次数累積分布

・次数

-クラスタリング係数相関

†

ネットワークの可視化

・最大連結成分の可視化

・粗視化

（

betweenness centrality clustering ）

・異分野連携の抽出

Rank-Size

Zipf則 最大連結成分と2nd連結成分

次数累積分布

degree-clustering coefficient

知的財産マネジメント研究会＠GRIPS 44

可視化

a. 2001 b. 2002 c. 2002

粗視化

†

Betweenness Centrality Clustering

†

Boost Graph Library

†

Brandes beetweenness centrality

Ulrik Brande, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology 25 (2):163-177, 2001.

†

bc_clustering.hpp修正

前：最大値を持つedgeのうち，1つだけremove 後：最大値を持つedgeを全てremove

Newman Modularity

2004

†

Betweenness

Shortest Path Betweenness

→

グループ（結合が密な部分）を橋渡し

するリンク（疎リンク）は，貴重なリン クである．

異分野連携の抽出

†

最大連結成分から，異分野連携部分のみを

アプリケーションの開発

†

自分の周辺でどのような

研究が行われているか？

†

簡単なインターフェースに

まとめ

†

基本的特徴量

・次数分布の

Scale Free性は疑問

・クラスタ性の強い階層性

†

可視化

+粗視化

・ナノテク分野と環境分野が支配的コミュニティ

・最大連結成分の異分野連携は

10%程度

参考文献

† 啓蒙書

・スモールワールド・ネットワーク―世界を知るための新科学的思考法， ダンカン ワッツ (著), Duncan

J. Watts (原著), 辻 竜平 (翻訳), 友知 政樹 (翻訳)

・新ネットワーク思考―世界のしくみを読み解く， アルバート・ラズロ・バラバシ (著), 青木 薫 (翻訳)

・Six Degrees: The Science of a Connected Age，Duncan J. Watts (著)

・ Linked: The New Science of Networks， Albert-Laszlo Barabasi (著)

† もう少し高度

・モールワールド―ネットワークの構造とダイナミクス ，ダンカン ワッツ (著), Duncan J. Watts (原

著), 栗原 聡 (翻訳), 福田 健介 (翻訳), 佐藤 進也 (翻訳)

・Small Worlds: The Dynamics of Networks Between Order and Randomness，Duncan J. Watts (著)

・複雑ネットワークの科学，増田 直紀 (著), 今野 紀雄 (著)

† 論文集

・The Structure And Dynamics of Networks， Duncan J. Watts (著), Mark Newman (著)

† Web Site

・http://www.nd.edu/~alb/

ツール群

†

解析＋可視化

・

Pajek, http://vlado.fmf.uni-lj.si/pub/networks/pajek/

†

可視化

・

Otter, http://www.caida.org/tools/visualization/otter/

・

GraphViz, http://www.graphviz.org/

・

Large Graph Layout, http://apropos.icmb.utexas.edu/lgl/

†

プログラミング・ライブラリ

・

Boost Graph Library,