ネットワーク分析 - 歴史、トピック、用語集


###歴史的な視点から####
#グラフ理論の創始者
オイラー(1707 - 1783)
ケーニヒスベルグの橋の問題

#グラフ理論を数学的に体系化 
ジョージ・ポリア(1887 - 1985)

#近代グラフ理論の父
フランク・ハラリー(1921 - 2005)
グラフ理論の数学的側面だけでなく、応用面にも広く興味を示した。
グラフ理論が様々な分野で実用化される契機を作った立役者
数学、物理学、人類学、生物学、化学、コンピュータ科学、地理学、言語学、音楽、政策科学、心理学など多岐にわたる分野で論文を約700報執筆

#日本のグラフ理論の開拓者
秋山仁
アメリカにハラリーに師事

###トピック###
#エルデシュ数
20世紀の大数学者、ポール・エルデシュ(1913 - 1996)の共著関係のネットワーク。
エルデシュからスタートして、ある研究者に到達するのに必要な枝数をエルデシュ数と呼ぶ。
#ケビン・ベーコンゲーム
アメリカの有名俳優ケビン・ベーコンと他の俳優の共有関係を結びつけるゲーム
ケビン・ベーコンの神託(http://oracleofbacon.org//movielinks.php)

Kevin Baconとleonardo DiCaprioの関係

#ベースボールのネットワーク
アメリカのベースボールで同じチームでプレイしたことのある選手を結んだ線によるネットワーク
ベースボールの神託(http://www.baseball-reference.com/oracle/)
#ミルグラムのスモールワールド実験
1960年代後半、アメリカの心理学者スタンレー・ミルグラム(1933 - 1984）のチームが行った社会実験。アメリカ東海岸北部にあるボストンにすむX氏に向けて、ボストン市内やアメリカ中部から手紙をリレーして届けるというものである。現実の人間関係ネットワークを模擬するために、手紙を渡していい相手はファースト・ネームで呼び合えるくらいの関係に限定。この実験の結果、平均６回程度のリレーでX氏まで手紙が到達した。すなわちネットワークの平均距離は６であるといえる。

#ワッツのスモールワールド実験
コロンビア大学のダンカン・ワッツ(1971 -)の率いるスモールワールド・プロジェクトによって行われた、現代版スモールワールド実験。国をまたぐ形で実験計画が組まれた。その結果、スタートとゴールが同じ国の場合は5, 違う国の場合は7と推定された。これは、ミルグラムのスモールワールド実験を指示する結果であった。

#スモールワールド実験が示唆するもの
異なる職業の人々や離れたところに住む人々を結びつける近道が、たくさんではないにしても適量存在することが、情報を早く伝えるためには重要である。

#現実のネットワークが持っているべき特徴
・スモールワールド性（小さい平均距離、大きいクラスター係数）
・大きすぎない平均次数

#ネットワークの種類と比較



###用語###
#ネットワークの平均距離
ネットワークのすべての頂点対の距離の平均。
ネットワークの平均距離が6の場合、「6次の隔たり」と呼ぶことがある。

#次数
一つの頂点から出る枝のこと数のこと。

#クラスター係数
ネットワーク全体の三角形を数えて、最も多いときを1、最も少ないときを0とするおうに調節して、クラスター係数は定義されている。


###ネットワークの種類####


【参考文献】
増田直紀 今野紀雄　『「複雑ネットワーク」とは何か』 講談社 2006 
ラベル:

隣接行列から有向グラフを作成する



##以下, Rのスクリプト##

dg <- matrix(c(0,1,1,0,  1,0,1,0,  0,0,0,0,  1,0,0,000) , nrow = 4, ncol = 4, byrow = T)

dg
      [,1] [,2] [,3] [,4]
[1,]    0    1    1    0
[2,]    1    0    1    0
[3,]    0    0    0    0
[4,]    1    0    0    0

#igraphで利用可能なグラフオブジェクトを作成する。
g <- graph.adjacency(dg, mode="directed")

png("directed-graph.png")
plot(g)
dev.off()

【参考文献】
金明哲『Rで学ぶデータサイエンス 8 ネットワーク分析』2009 共立出版 序文、2 - 5 pp


######数式のtexスクリプト#####
%graph.tex
\documentclass{jarticle}
\usepackage{amsmath}
\begin{document}
ある特定のネットワークを数学的にグラフ$G$として表記するには以下のようにします。
\begin{eqnarray} 
G = (V, E)
\end{eqnarray}
ここで$V$と$E$はそれぞれ頂点と辺の集合を表しています。\\
今、頂点と辺の数を各々$i$, $j$とすると、$V$と$E$は以下のように表すことができます。
\begin{eqnarray} 
V = \{v_1, v_2, \dots, v_i\} \\
E = \{e_1, e_2, \dots, e_j\} 
\end{eqnarray}
グラフの特徴を知るにためにはさまざまな演算をするので、グラフを隣接行列: adjacency matrixによって
表現します。隣接行列は、頂点間の関係性の有無を総当たりで記述するものですので、$n$個の頂点から構成される
グラフの隣接行列$A$は$n \times n$の正方行列となります。
\begin{eqnarray} 
A= (a_{k,l})
=\left[ 
\begin{array}{ccc}
a_{0,0} & \cdots & a_{1,n} \\
\vdots & \ddots & \vdots \\
a_{n,1} & \cdots & a_{n,n} \\
\end{array} 
\right]
\end{eqnarray}
ただし、$a_{i,j}$は以下の値を取る。
\begin{eqnarray}
a_{i,j} = \begin{cases}
1 & 頂点iから頂点jへの辺がある \\
0 & 頂点iから頂点jへの辺がない
\end{cases}
\end{eqnarray}
隣接行列から有向グラフを作成する例として、以下の隣接行列を考えたい。
\begin{eqnarray}
\left(
\begin{array}{cccc}
0 & 1 & 1 & 0\\
1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 \\
\end{array}
\right)
\end{eqnarray}
この隣接行列が示す有向グラフをRを用いて作成する。
\pagestyle{empty}
\end{document}



#####ここまで####


ラベル:

R : igraphのインストールとテスト


#Rの起動
$ R

#igraphのインストール
> install.packages("igraph")

#igraphのロード
> library("igraph")

#テストとして、頂点50個、p = 0.1の無向ランダムグラフを作成する。
> g <- random.graph.game(50, p=0.1, direct=F)
> png("random.graph.png")
> plot(g, main = "random graph n = 50, p = 0.1")
> dev.off()


ラベル:

このブログで使用しているtexの基本的フォーマット


###この下から###

% test.tex
\documentclass{jarticle}
\usepackage{amsmath}
\begin{document}
これはテスト文書です。
\begin{eqnarray} 
f(x) = x
\end{eqnarray}
終わります。
\pagestyle{empty}
\end{document}

###この上まで###


###pdfファイルを取得するには以下

$ platex test.tex
$ dvipdfm test.dvi

#GUIで切り取りpng形式で保存してブログに張っています。



ラベル:

ネットワーク分析とは


『Rで学ぶデータサイエンス 8 ネットワーク分析』 の冒頭の文書から、ネットワーク分析とはいかなる学問であるかがわかる部分を抜粋します。

##ネットワーク分析とは##
ネットワーク分析とは、さまざまな対象における構成要素間の関係構造を探る研究方法である。
さまざまな種類のネットワークは”複数の点が何らかの関係でつながったものという点で共通しており、それゆえ同じ方法で研究することができる"という発想が根本にある。
ネットワーク分析では、人間関係やウェブページのリンクなどの構造を、点と線によって構成される構造として抽象化してとらえる。

##ネットワークの具体例##
人間関係などの社会ネットワーク
流通網
WWW
食物連鎖
神経ネットワーク

##部分と全体##
全体について何か知ろうとするとき、その構成要素について知るだけでは十分ではない。
例えば、集団の構成員を知るだけではその集団を十分にわかったことにはならないし、物質に含まれる分子を知っただけではその物質を知ったことにはならない。
重要なのはそれらの構成要素がどのように結合して全体としてのネットワークを形作っているかということである。
ネットワーク分析には、個々の構成要素だけでなく、それらの間の関係についての情報が必要となる。

##ネットワークとグラフ##
人間関係やコンピュータネットワークのような具体的な関係構造のことをネットワーク: network
それらを点(頂点 node)と辺(edge / link)の抽象化したものをグラフ: graph

【参考文献】
金明哲『Rで学ぶデータサイエンス 8 ネットワーク分析』2009 共立出版 序文、1,2pp
ラベル:
登録: 投稿 (Atom)