CNN(Connecting Nearest Neighbor)モデルの実装
ＩＴ
2024-06-09
畳込みニューラルネットワークではなく、ソーシャルメディアのシミュレーションモデルとしてよく使われるもの。訳すと「最近隣人接続モデル」とでも言うのだろうか？ こういうのによく使われるPythonで実装してみようと。速度は遅いけれど、グラフがつくりやすいから。
import random
import networkx as nx
from pyvis.network import Network
class node:
def __init__(self,id):#コンストラクタ
self.edge=[]
self.id=id
class cnn:
def initialize(self):
#初期値は0,1,2の3つのnodeから成る
random.seed()
self.nodes={}
#nodeクラスにidを入れてインスタンス化し、
nodesリストに入れる
self.nodes[0]=node(0)
self.nodes[1]=node(1)
self.nodes[2]=node(2)
self.nodes[0].edge=[[0,self.nodes[2].id]]
self.nodes[1].edge=[[1,self.nodes[2].id]]
self.nodes[2].edge=[[2,self.nodes[0].id]]
self.nodes[2].edge+=[[2,self.nodes[1].id]]
self.node_number=3
self.potential_edge=[[0,1]]
#最初のpotential edgeはnode0とnode1の間にある
def generate(self,step,u):
self.initialize()
for var in range(step):
rnd=random.random()
if rnd < u:
self.addEdge()
else:
self.addNode()
def addNode(self):
self.nodes[self.node_number]
=node(self.node_number)
#idを引数にして新しいを追加する
rnd=int(random.uniform(0,self.node_number-1))
#既存のnodeからランダムに選ぶ
for n in range(len(self.nodes[rnd].edge)):
id1,id2=self.nodes[rnd].edge[n]
#id1がsource,id2がtarget
self.potential_edge
+=[[self.node_number,id2]]
#選んだ既存のnodeがエッジを持つ
すべてのnode（近傍ノード）との間に
#潜在エッジ（potential edge）を設定する
#新しいnodeと選んだnodeをつなげる
self.nodes[self.node_number].edge
+=[[self.node_number,rnd]]
self.nodes[rnd].edge
+=[[rnd,self.node_number]]
self.node_number+=1#nodeの個数を一つ増やす
def addEdge(self):
if len(self.potential_edge)==0:
return
#いきなり(0,1)間にエッジが引かれることもある
rnd
=int(random.uniform(0
,len(self.potential_edge)-1))
potential_edge
=self.potential_edge[rnd]
#潜在エッジから一つ選ぶ
id1=potential_edge[0]
id2=potential_edge[1]
self.nodes[id1].edge+=[[id1,id2]]
del self.potential_edge[rnd]
#選んだ潜在エッジを除外しておく
def drawNetwork(self):
net=Network()
for n in range(self.node_number):
net.add_node(n,label='%d' % n)
#add_nodeと同時並行だと
'non existent node'が出る
for n in range(self.node_number):
for edge in self.nodes[n].edge:
id1,id2=edge
net.add_edge(id1,id2)
net.show("example.html",notebook=False)
if __name__=="__main__":
grapf=cnn()
grapf.generate(100,0.6)
grapf.drawNetwork()
つくってはみたが、どこかに間違いがあるような（バグではなく、理論的に）。おかしいと思った人は下記の文献など頼りに自分で考えてみてください。
CNNの考え方は、「友達の友達は友達」というもの。ツイッターなどで誰かのフォロワーになると、その誰かがフォローしている人のフォロワーになることもある。こうやってフォロワー同士のつながりが拡大する様子をシミュレートしようというのがCNNだとか。
アルゴリズムは、
①確率1-uで新しいノード（結び目のこと。新しい参加者）を追加し、既存のノードとの間にエッジ（辺のこと。ソーシャルメディアではフォロワーになること）を張る。その際、既存のノードが持っていたエッジはすべて「潜在エッジ」とする。
②確率uで潜在エッジの中から一つ選び、エッジにする。つまり自分のフォローしている人がフォローしている人を新たにフォローする。
Pythonなら簡単かな～と思ってたら、意外にめんどくさかった（プログラミングは久しぶりなので…文系だし。言い訳ですが）。Pythonはどうも苦手です。Cでコツコツ一からつくる方が楽な気が…
ネット上には「NetworkXを使うと簡単にグラフにできる」と言ってるのを見かけますが、NetworkXのメソッドfrom_panda_edgelistはVisual Studio 2019では出なかった。Pyvisを使っても、Networkでつくったグラフをfrom_nxで可視化できませんでした。いずれもdepricatedになっているのでは？ 最初からPyvisを使った方が簡単にできました。このグラフ化で時間の大半を費やしてしまった。
step=100だとこんな感じ。40個ぐらいのノードができる。マウスでグラフをクリックすると、ゼリーか餅みたいにブニュンブニュンした感じで動く。ちっとキモいかも。
step=1000。宇宙空間か生物系の画像みたい。これが日ごろ使ってるツイッターやフェイスブックのモデルなのでしょうか？ 何だか不思議な感じがする（プログラムを正しくつくれていたらの話）。
一応各ノードには番号もふってあって（画像では小さくて見えませんが）、最初の参加者ほど多数のエッジを持つ傾向にある（当たり前）。端の方にも小さなかたまりが島宇宙のようにのびており、先端部にはまだ一人としかつながっていない参加者がいる。ネットワークが発展すればこの先端部もかたまりに飲み込まれていく。
中心部はエッジが混み合って見えないぐらいになり、複雑なハブを構成している。こういう少数のノードにエッジが集中する性質をスケールフリー性というらしい。一体どうして「スケールフリー」というのだか。「集中性」と言った方がいいような。
〈参考文献〉
「コミュニティ情報を考慮したネットワーク成長モデル」
三好栄次, 鈴木育男, 山本雅人, 古川正志 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2009 (8), 1-6, 2009-09-03
「マルチエージェントシミュレーションによる消費者行動の分析」
山本祐揮, 相場亮 第77回全国大会講演論文集 2015 (1), 313-314, 2015-03-17