Raspberry Pi,Arduino 回路図設計ソフトFritzingを使ってみる


これの続きです。
前回でLinuxの端末を見ることができましたが、GUIの起動も行ってみましょう。

startx

すると次の画面になります。
f:id:alstd:20150122134117p:plain
これで普通のOSっぽい感じに表示できました。
ブラウザやゴミ箱機能から、Wolfram先生やマインクラフトまで入っているので遊んでみるといいと思います。

ところで、ゴミ箱のアイコンを見ればわかる通り英語表記になっています。
表記はさておいておくとしても、日本語の入力方法さえ無い状態では困りますので、環境整備を行います。
まず、OS自体の言語設定です。前回行った人はスルーしても大丈夫です。

sudo dpkg-reconfigure locales

で設定画面を起動後、スペースキーで次の欄に*印をつけてください。

en_US.UTF-8 UTF-8 
ja_JP.EUC-JP EUC-JP
ja_JP.UTF-8 UTF-8

tabでOKを選択した後、システムデフォルトの言語を聞かれます。こちらはen_US.UTF-8 UTF-8にしてください。
日本語をデフォルトにすると、日本語対応していない表記が文字化けするためです。

続いて、フォントと入力メソッドのインストール

sudo apt-get install fonts-vlgothic
sudo apt-get install ibus-anthy

以上で設定ができたので、念のため再起動を行います。

sudo reboot

そしてGUIを起動するのですが、デフォルトは英語なので、日本語で起動するときは、

LANG=ja_JP.UTF-8 startx

です。
面倒だと感じるならば、aliasコマンドで割り当ててください。

 

さて、今のところマウスやキーボードをRaspberry Piに接続して使っていると思いますが、パソコンと一緒に使うときには不便です。
人によっては、PC用のキーボードを差し替えていると思います。
実はLANと電源さえあればキーボード・マウス・画面出力無しでも運用していく方法があります。それがVNCサーバです。
SSHやらSAMBAやら色々なサーバソフトがありますが、GUIで設定を行うならば一番最初にやっておくとよいと思われます。

まず、サーバ側(Raspberry Pi)にvncサーバのソフトを導入します。

sudo apt-get install tightvncserver

続いて、

tightvncserver

でパスワードの設定を行います。
なお、8文字以上のパスワードは語頭8文字までに短縮される模様なので注意してください。

ここまですると恐らく自動的にサーバが起動しますが、手動では

vncserver :1

として起動させてください。

あとはローカルIPアドレスの確認

ifconfig

からおそらく192.168.**.**の形になってるアドレスをメモしておきます。

クライアント側(Ubuntu)の設定ですが、UbuntuデフォルトのRemmina リモートデスクトップクライアントなるソフトを使ってみました。
f:id:alstd:20150122140307p:plain
なお、192.168.**.**:1の:1の部分は、vncserverの立ち上げによっては数字が変わります。
先ほど設定したvncサーバに対するパスワードを入れます(ログインパスワードではないです)。

接続すると…
f:id:alstd:20150122140509p:plain
これでRaspberry Piを(ローカルネットワークから)遠隔操作できるようになりました。

Raspberry Piが起動している間は、タスクを手動で殺さない限り、クライアントから接続を切っても仮想のディスプレイは生きつづける特徴がtightvncserverにはあります。
また、複数バイスから接続したり、Androidからの接続などもできました。

 

再起動して再接続するのは面倒くさいので自動起動の設定をしたり、IPアドレスの固定などが残っていますが、sshsambaサーバの構築と共に後々に回します。

2部グラフと、各々の集団内のネットワークの関係

数学やグラフ理論では、すべての頂点をうまく2つの集合に分けたときに、自分の集団内に対しては枝がなく、相手の集団間に枝が存在するグラフのことを「2部グラフ」と定義しています。

現実の世界での例を挙げてみます。
世界には様々な組織(大学、企業、高校、etc)があり、その組織に所属する人間がいます。
f:id:alstd:20150115182438p:plain
上が5つの塾、下が所属する生徒と考えてみましょう。
このとき、塾と生徒は「所属」という枝で結ばれていますが、塾と塾、生徒と生徒間の間には枝がないです。
ここで、塾と生徒をそれぞれ枝集合AとBに分けてみましょう。
すると、集合AとBの要素間に枝は存在するものの、A内の要素同士、B内の要素同士に枝は存在しません。
こういった分割が可能なグラフの関係性を2部グラフという、と定義した訳です。

 

ところでこの2部グラフ、関係性という枝によって結ばれる端点同士が、異なる2つの意味合いを持つときに現れやすいです。
ここでいうと所属という関係性の元、異なる意味合いを持つ塾と生徒が結ばれていますね。
他にも最も分かりやすい例では、性交渉をした関係性は(同性愛者を除き)異なる性別である男と女が枝で結ばれます。
例えば話したことがあるという関係性の元では男同士、女同士でも話すわけですから、二部グラフにはなりません。

 

では、ここで同じ塾に通う生徒同士のネットワークを描きたい、と思ったらどうなるでしょうか。
上の図では6,8,9さんは同じ塾に通っているから枝を張る、という訳です。
性交渉では、いわゆる穴兄弟のネットワークを張るという意味です。
このネットワークの定義を知らないので、「同所属ネットワーク」と以下呼んでみます。

 

これとは違う例ではありますが、同所属ネットワークを書く機会があったため、数学的な計算法を紹介しておきます。

まず、隣接行列を作ってください。
(n,m)成分は頂点nからmに枝があるとき、その成分を1とする行列です。
ここでは、上の図の例を使います。


{\displaystyle
A = \left(
    \begin{array}{ccccccccccccccc}
      0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
      0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
      0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0\\
      0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0\\
      0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
    \end{array}
  \right)
}

この隣接行列を2乗してください。

{\displaystyle
A^2 = \left(
    \begin{array}{ccccccccccccccc}
3 & 0 & 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 3 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
2 & 1 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
2 & 0 & 1 & 4 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 2 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 3 & 1 & 2 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 0 & 2 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 1 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
    \end{array}
  \right)
}

このとき、この2乗の行列の各成分は、


(n,m) = \begin{cases}
   n(さん/塾)がm(さん/塾)と共有する(塾/生徒)数 & (n\neq{m}) \\
   n(さん/塾)が所属(する/される)(塾/生徒)数 & (n=m)
\end{cases}


です。

 

これを使って、先ほどの2部グラフを、塾についてと生徒についての2つのグラフへ分けてみます。
f:id:alstd:20150115195214p:plain
1〜5の塾のネットワークと6〜15の生徒のネットワークに分かれていますね。
自分に対するループ枝は、自分の所属する塾あるいは生徒の数です。
他のノードに対する枝は、共通する塾に行く生徒同士、あるいは共通する生徒を持つ塾同士を繋いでいます。

 

背景にある定理は、


あるネットワークに対する隣接行列Aのl乗であるA^lの(n,m)成分は、\\
nからmを長さlで繋ぐパスの数となる。


であり、その系として、


2部グラフに対する隣接行列Aの2乗であるA^2の(n,m)成分は、\\
nからmを2の長さで繋ぐパスの数となる。\\
特に2部グラフの定義における頂点の2つの集合X,Yを考えたとき、\\
Xのある頂点から長さ1で到達しうる点はYに属し、更にそのような\\
Yの点から長さ1で到達しうる点はXに属する。\\
従って、A^2の隣接行列によって与えられるネットワークは、\\
X,Yの(少なくとも)2つのネットワークである。

 

証明をしておきましょう。

{\displaystyle
数学的帰納法によって証明する。\\
l=1のとき、A^1は隣接行列であり、定義より(n,m)成分はn-mを長さ1で繋ぐパスの数である。\\
l=pのとき、A^pの(n,m)成分がnからmを長さpで結ぶパス数であると仮定すると、\\
l=p+1のとき、\\
隣接行列のp乗をA^p=B=[b_{ij}]とおく。\\
A^{p+1}=A^{p}A=\sum_{k=1}^nb_{ik}a_{kj}=b_{i1}a_{1j}+b_{i2}a_{2j}+\cdots+b_{in}a_{nj}……(1)\\
ここで帰納法の仮定より、\alphaをi-jを長さpで繋ぐパスの数として、b_{ij}=\alpha\\
更に、隣接行列の定義より、\\
a_{ij} = \begin{cases}
   1 & (i-j間に枝がある) \\
   0 & (i-j間に枝がない)
\end{cases}\\

だから、\\
b_{ik}a_{kj} = \begin{cases}
   \alpha & (i-k間に枝 かつ k-j間に枝) \\
   0 & (それ以外)
\end{cases}\\
(1)のkについての総和を取ることで、i-(pの長さのパス)-k-jという結びつきの数が\\
数えあげられ、即ちこれは長さがp+1のパスを数え上げていることになっている。\\
よってl=p+1のときも成立するため、一般のlについても成立。\\
}

ただし、小さなネットワークに対してスマートな計算法であっても、大きなネットワークに対しては巨大な計算量とメモリを消費することになります。
巨大なものに対しては、疎行列に対するアルゴリズムを適用することで軽量化できます。
本当に莫大な計算が必要なときは、やはり枝リストから重みなしで数え上げるのが一番速いと思われます。(重みありならば疎行列に対する積と実質同じになる。)

今回の記事でRのプログラムを使ったので、後々紹介します。
疎行列積や枝リストからの数え上げはやる気が出次第取り組んでみます。

OpenCV+C++ カメラによる動画撮影

#include "opencv/highgui.h"
#include <stdio.h>
using namespace cv;

int main(void){
    //http://opencv.jp/opencv-1.0.0/document/opencvref_highgui_video.html
    CvCapture *camera=cvCreateCameraCapture(0);
    if(camera==NULL){
        printf("カメラが見つかりません");
        return -1;
    }

    double width=1920,height=1080;

    cvSetCaptureProperty(camera,CV_CAP_PROP_FRAME_WIDTH,width);
    cvSetCaptureProperty(camera,CV_CAP_PROP_FRAME_HEIGHT,height);

    while(cvWaitKey(1)==-1){
        //cvQueryFrameはCvCapture型の1フレームをIplImage型で返す。
        //IplImage型をMat型に変換している。(Matのほうが良いっぽい?違いが分からない)
        Mat image(cvQueryFrame(camera));
        imshow("camera",image);
    }

    cvReleaseCapture(&camera);
    cvDestroyWindow("camera");

    return 0;
}
g++ webcamera.cpp `pkg-config --cflags opencv` `pkg-config opencv --libs` -o OpenCV
./OpenCV


結果は、
f:id:alstd:20150315190142p:plain



ちなみに使ったカメラはELECOMのDLE300TBKです。
首振り機能は無いが画質は良いようです。

Raspberry Pi,Arduino 回路図設計ソフトFritzingを使ってみる

春休みの工作としてアクアリウム監視Raspberry Piサーバを作ってみようと思っています。(できれば帰省するまでに…)
大学のイベントでもArduinoを使ってラジコン車のようなものを作ります。
回路を組む機会が増えそうなのでメモする手段として回路図面を作ることにしました。


どうやらFritzingというソフトが評判がよく、WindowsMacLinuxいずれでも使えるためインストールしてみます。
例によって環境はUbuntu14.04(64bit)です。

sudo add-apt-repository ppa:ehbello/fritzing
sudo apt-get update
sudo apt-get install fritzing


早速起動してみました。
f:id:alstd:20150225201204j:plain
ペイント的な直感的な操作ができるので便利ですね。
ブレッドボードを動かしてもコードは指定の穴に繋がったまま伸びるため、回路構造を破壊しません。

出力は次のようになしました。
f:id:alstd:20150225201301p:plain


ArduinoRaspberry Piなど有名所の基板は網羅されていました。
もし無かったらGitHubから探して追加したり、自分で編集したりできるようです。

右の回路素子の一覧で右クリックしてimportをすればよいです。

Python 形態素解析エンジンMeCaBを使ってTwitterの分析

形態素解析は簡単にいうと文を名詞、動詞などの品詞分類をコンピュータを使って行うことをいいます。
そのソフトのひとつがMeCaBです。

ググると導入方法がたくさんでてきますが、時々刻々環境が変わり、その度うまくいかない報告が出ているようです。
僕も苦心しましたが、試しにapt-getしたら、現時点では対応していました。メモしておきます。

sudo apt-get install mecab-ipadic-utf8 mecab-jumandic-utf8

MeCaB自体のインストール。

sudo pip install python-mecab

PythonからMeCaBを扱えるようになります。


TwitterからTweetを取得して、品詞分類するようなプログラムを実行してみます。
TwitterAPIを取得することと、

sudo pip install twitter

が必要です。

#coding:utf-8
import twitter
import json
import MeCab

MECAB_MODE = 'mecabrc'
PARSE_TEXT_ENCODING = 'utf-8'

CONSUMER_KEY=""
CONSUMER_SECRET=""
ACCESS_TOKEN=""
ACCESS_TOKEN_SECRET=""

def parse(unicode_string):
    tagger = MeCab.Tagger(MECAB_MODE)
    text = unicode_string.encode(PARSE_TEXT_ENCODING)
    node = tagger.parseToNode(text)

    words = []
    nouns = []
    verbs = []
    adjs = []
    while node:
        pos = node.feature.split(",")[0]
        word = node.surface.decode("utf-8")
        if pos == "名詞":
            nouns.append(word)
        elif pos == "動詞":
            verbs.append(word)
        elif pos == "形容詞":
            adjs.append(word)
        words.append(word)
        node = node.next
    parsed_words_dict = {
        "all": words[1:-1],
        "nouns": nouns,
        "verbs": verbs,
        "adjs": adjs
        }
    return parsed_words_dict

auth=twitter.OAuth(ACCESS_TOKEN,ACCESS_TOKEN_SECRET,CONSUMER_KEY,CONSUMER_SECRET)
twitter_stream=twitter.TwitterStream(auth=auth,domain="userstream.twitter.com")

for msg in twitter_stream.user():
    if "text" in msg:
        tweet = msg["text"]
        words_dict= parse(tweet)
        print "All:", ",".join(words_dict['all'])
        print "Nouns:", ",".join(words_dict['nouns'])
        print "Verbs:", ",".join(words_dict['verbs'])
        print "Adjs:", ",".join(words_dict['adjs'])
print "========END========"

実行結果は次のようになります。

All: いじわる,する,人,は,きらい,だ,ぬん
Nouns: いじわる,人,きらい
Verbs: する,ぬん
Adjs: 
========END========
All: 俺,も,頑張ろ,う
Nouns: 俺
Verbs: 頑張ろ
Adjs: 
========END========

うーん、微妙に間違えてはいるものの、機械にしては頑張っているのではないでしょうか。
恐らく理屈的に名詞の抽出の正確性は高いので、「地震」とか「飯」とか特定のワードに対して統計処理を行うならば、それなりに妥当かもしれませんが。

Raspberry Pi 初期設定その2 日本語化、vncサーバなど


これの続きです。
前回でLinuxの端末を見ることができましたが、GUIの起動も行ってみましょう。

startx

すると次の画面になります。
f:id:alstd:20150122134117p:plain
これで普通のOSっぽい感じに表示できました。
ブラウザやゴミ箱機能から、Wolfram先生やマインクラフトまで入っているので遊んでみるといいと思います。

ところで、ゴミ箱のアイコンを見ればわかる通り英語表記になっています。
表記はさておいておくとしても、日本語の入力方法さえ無い状態では困りますので、環境整備を行います。
まず、OS自体の言語設定です。前回行った人はスルーしても大丈夫です。

sudo dpkg-reconfigure locales

で設定画面を起動後、スペースキーで次の欄に*印をつけてください。

en_US.UTF-8 UTF-8 
ja_JP.EUC-JP EUC-JP
ja_JP.UTF-8 UTF-8

tabでOKを選択した後、システムデフォルトの言語を聞かれます。こちらはen_US.UTF-8 UTF-8にしてください。
日本語をデフォルトにすると、日本語対応していない表記が文字化けするためです。

続いて、フォントと入力メソッドのインストール

sudo apt-get install fonts-vlgothic
sudo apt-get install ibus-anthy

以上で設定ができたので、念のため再起動を行います。

sudo reboot

そしてGUIを起動するのですが、デフォルトは英語なので、日本語で起動するときは、

LANG=ja_JP.UTF-8 startx

です。
面倒だと感じるならば、aliasコマンドで割り当ててください。


さて、今のところマウスやキーボードをRaspberry Piに接続して使っていると思いますが、パソコンと一緒に使うときには不便です。
人によっては、PC用のキーボードを差し替えていると思います。
実はLANと電源さえあればキーボード・マウス・画面出力無しでも運用していく方法があります。それがVNCサーバです。
SSHやらSAMBAやら色々なサーバソフトがありますが、GUIで設定を行うならば一番最初にやっておくとよいと思われます。

まず、サーバ側(Raspberry Pi)にvncサーバのソフトを導入します。

sudo apt-get install tightvncserver

続いて、

tightvncserver

でパスワードの設定を行います。
なお、8文字以上のパスワードは語頭8文字までに短縮される模様なので注意してください。

ここまですると恐らく自動的にサーバが起動しますが、手動では

vncserver :1

として起動させてください。

あとはローカルIPアドレスの確認

ifconfig

からおそらく192.168.**.**の形になってるアドレスをメモしておきます。

クライアント側(Ubuntu)の設定ですが、UbuntuデフォルトのRemmina リモートデスクトップクライアントなるソフトを使ってみました。
f:id:alstd:20150122140307p:plain
なお、192.168.**.**:1の:1の部分は、vncserverの立ち上げによっては数字が変わります。
先ほど設定したvncサーバに対するパスワードを入れます(ログインパスワードではないです)。

接続すると…
f:id:alstd:20150122140509p:plain
これでRaspberry Piを(ローカルネットワークから)遠隔操作できるようになりました。

Raspberry Piが起動している間は、タスクを手動で殺さない限り、クライアントから接続を切っても仮想のディスプレイは生きつづける特徴がtightvncserverにはあります。
また、複数バイスから接続したり、Androidからの接続などもできました。


再起動して再接続するのは面倒くさいので自動起動の設定をしたり、IPアドレスの固定などが残っていますが、sshsambaサーバの構築と共に後々に回します。

2部グラフと、各々の集団内のネットワークの関係性

数学やグラフ理論では、すべての頂点をうまく2つの集合に分けたときに、自分の集団内に対しては枝がなく、相手の集団間に枝が存在するグラフのことを「2部グラフ」と定義しています。

現実の世界での例を挙げてみます。
世界には様々な組織(大学、企業、高校、etc)があり、その組織に所属する人間がいます。
f:id:alstd:20150115182438p:plain
上が5つの塾、下が所属する生徒と考えてみましょう。
このとき、塾と生徒は「所属」という枝で結ばれていますが、塾と塾、生徒と生徒間の間には枝がないです。
ここで、塾と生徒をそれぞれ枝集合AとBに分けてみましょう。
すると、集合AとBの要素間に枝は存在するものの、A内の要素同士、B内の要素同士に枝は存在しません。
こういった分割が可能なグラフの関係性を2部グラフという、と定義した訳です。


ところでこの2部グラフ、関係性という枝によって結ばれる端点同士が、異なる2つの意味合いを持つときに現れやすいです。
ここでいうと所属という関係性の元、異なる意味合いを持つ塾と生徒が結ばれていますね。
他にも最も分かりやすい例では、性交渉をした関係性は(同性愛者を除き)異なる性別である男と女が枝で結ばれます。
例えば話したことがあるという関係性の元では男同士、女同士でも話すわけですから、二部グラフにはなりません。


では、ここで同じ塾に通う生徒同士のネットワークを描きたい、と思ったらどうなるでしょうか。
上の図では6,8,9さんは同じ塾に通っているから枝を張る、という訳です。
性交渉では、いわゆる穴兄弟のネットワークを張るという意味です。
このネットワークの定義を知らないので、「同所属ネットワーク」と以下呼んでみます。


これとは違う例ではありますが、同所属ネットワークを書く機会があったため、数学的な計算法を紹介しておきます。

まず、隣接行列を作ってください。
(n,m)成分は頂点nからmに枝があるとき、その成分を1とする行列です。
ここでは、上の図の例を使います。


{\displaystyle
A = \left(
    \begin{array}{ccccccccccccccc}
      0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
      0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
      0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0\\
      0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0\\
      0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
      0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
    \end{array}
  \right)
}

この隣接行列を2乗してください。

{\displaystyle
A^2 = \left(
    \begin{array}{ccccccccccccccc}
3 & 0 & 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 3 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
2 & 1 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
2 & 0 & 1 & 4 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 2 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 3 & 1 & 2 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 0 & 2 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 1 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
    \end{array}
  \right)
}

このとき、この2乗の行列の各成分は、


(n,m) = \begin{cases}
   n(さん/塾)がm(さん/塾)と共有する(塾/生徒)数 & (n\neq{m}) \\
   n(さん/塾)が所属(する/される)(塾/生徒)数 & (n=m)
\end{cases}

です。


これを使って、先ほどの2部グラフを、塾についてと生徒についての2つのグラフへ分けてみます。
f:id:alstd:20150115195214p:plain
1〜5の塾のネットワークと6〜15の生徒のネットワークに分かれていますね。
自分に対するループ枝は、自分の所属する塾あるいは生徒の数です。
他のノードに対する枝は、共通する塾に行く生徒同士、あるいは共通する生徒を持つ塾同士を繋いでいます。



背景にある定理は、


あるネットワークに対する隣接行列Aのl乗であるA^lの(n,m)成分は、\\
nからmを長さlで繋ぐパスの数となる。

であり、その系として、

2部グラフに対する隣接行列Aの2乗であるA^2の(n,m)成分は、\\
nからmを2の長さで繋ぐパスの数となる。\\
特に2部グラフの定義における頂点の2つの集合X,Yを考えたとき、\\
Xのある頂点から長さ1で到達しうる点はYに属し、更にそのような\\
Yの点から長さ1で到達しうる点はXに属する。\\
従って、A^2の隣接行列によって与えられるネットワークは、\\
X,Yの(少なくとも)2つのネットワークである。


証明をしておきましょう。

{\displaystyle
数学的帰納法によって証明する。\\
l=1のとき、A^1は隣接行列であり、定義より(n,m)成分はn-mを長さ1で繋ぐパスの数である。\\
l=pのとき、A^pの(n,m)成分がnからmを長さpで結ぶパス数であると仮定すると、\\
l=p+1のとき、\\
隣接行列のp乗をA^p=B=[b_{ij}]とおく。\\
A^{p+1}=A^{p}A=\sum_{k=1}^nb_{ik}a_{kj}=b_{i1}a_{1j}+b_{i2}a_{2j}+\cdots+b_{in}a_{nj}……(1)\\
ここで帰納法の仮定より、\alphaをi-jを長さpで繋ぐパスの数として、b_{ij}=\alpha\\
更に、隣接行列の定義より、\\
a_{ij} = \begin{cases}
   1 & (i-j間に枝がある) \\
   0 & (i-j間に枝がない)
\end{cases}\\

だから、\\
b_{ik}a_{kj} = \begin{cases}
   \alpha & (i-k間に枝 かつ k-j間に枝) \\
   0 & (それ以外)
\end{cases}\\
(1)のkについての総和を取ることで、i-(pの長さのパス)-k-jという結びつきの数が\\
数えあげられ、即ちこれは長さがp+1のパスを数え上げていることになっている。\\
よってl=p+1のときも成立するため、一般のlについても成立。\\
}

ただし、小さなネットワークに対してスマートな計算法であっても、大きなネットワークに対しては巨大な計算量とメモリを消費することになります。
巨大なものに対しては、疎行列に対するアルゴリズムを適用することで軽量化できます。
本当に莫大な計算が必要なときは、やはり枝リストから重みなしで数え上げるのが一番速いと思われます。(重みありならば疎行列に対する積と実質同じになる。)

今回の記事でRのプログラムを使ったので、後々紹介します。
疎行列積や枝リストからの数え上げはやる気が出次第取り組んでみます。