川名ゼミ 研究会 3/12 長井さんレジュメ ### 3.2 > エージェント i が どのくらいのエージェントと相互作用させるのかは計算時間、計算資源の問題になると思う。 仮に、すべてのエージェント間が相互作用するとして $$o^i(t+1) = \sum_{j \neq i}^{N} F[o^i{t}, o^j{t}] + Z[o^i(t)]$$ のような和の形で表すのであれば、エージェントの個数を$N$とすると、計算量は$O(N^2)$となるので、現実的な計算時間で終了するには$N = 10^4 〜 10^5$のオーダーでないといけない。 （しかも、これはC++のような、事前にコンパイル済言語の話であり、pythonなどを用いると$N = 10^4$が妥当な範囲となってしまう。） さらに、仮にエージェント間が何かの指標に基づいて定数個しか、相互作用しないとしても、愚直実装では（値の持ち方などにかなり工夫を加えないと） $O(N^2)$かかり、値の昇順（or降順）という実装しやすいケースでも$O(N \log{N})$かかる。 また、これらはすべて１回の相互作用の話をしているので、この計算量がかかる処理をシミュレーションの試行回数$M$だけ、実行することになる。 ただし、上記の処理は計算を愚直に行っているので、累積和など、データの持ち方に工夫を凝らせば計算量を削減できる可能性は大いにある。（これは、どのようなモデルを採用するかにかかっている。） また、メモリ制限も関係してくる。 次元数$n$と漸化式を$k$項間漸化式とすると、最低でも$n\times k$のサイズのメモリを常に維持する必要がある。また、データの持ち方は`queue`もしくは`priority_queue`のような形が望ましいが、ランダムアクセスを許容する場合は、毎回データの破棄、移動が必要となるのでメモリサイズ効率化のために、時間計算量が悪化するという事態を招きかねない。 次元数をどれくらいにするのかはかなり重要 - GitHub [Link](https://github.com/bencabrera/spiral_of_silence_abm) 参考になるかもしれないRepository - https://github.com/knazeri/sznajd-model - https://github.com/dfrodriguezp/PiCM-cpp - https://github.com/dweser/PedestrianDM - https://github.com/KaikeWesleyReis/agent-based-modelling 上記のうちのひとつ > Agents are placed on the nodes of a network with randomly assigned opinions, confidences on their opinion and an expression threshold. Agents with confidence higher than their expression threshold speak out their mind and influence neighbors in the network. Agents may consequently change their confidence over time depending on the opinion climate they observe in their immidiate neighborhood 長井さんの近接投票に関連する箇所 $\omega$の値だけでなく、確率的勾配降下法のように、ランダム性をいれてみても面白いかも 実装方法としては、点が動くタイプ（多次元配列型） or グラフ理論+重み付け いずれの場合でも、１次元でも$n$次元でも実装可能 ## メモ 初期値敏感性がある そのあたりはちゃんと考えないとダメ 角度のとり方を変えると面白い？（位相角にあわせて） 分極しきった社会 -> あらたな平衡 or あらたな非平衡 作るなら、UnionFindで一定回数一緒になったら、外部要因 or 斥力導入とか ある程度分極化が進んだら、片方の勢力が消滅？(実装方法がうーんって感じ) グラフのサイズを記憶は結構めんどい...