グラフ日記(初回)

# はじめまして
はじめまして、Hajime.Oと申します。

しがないのテクニカルサポート屋ですが、ソフトウェアエンジニアリングやデータサイエンスに興味を持ち、自己学習を進めてきました。Power of Networksを読んだことで、ソーシャルネットワーク分析やグラフ解析に興味を持っています。
現在は、空いた時間で、グラフ解析を使って、職場のナレッジベースの構造の最適化するみたいなことを画策しています。

# この記事シリーズについて
これは知識定着、現状の整理を目的とした備忘録、日記です。
できる限り、グラフやプロットを添えた絵日記的なものにしたいなと考えています。

技術ブログではないので、学んだ技術を体系的にまとめるといったことはしません。些細な内容でも、学びがあった日、作業をした日は書きたいと思います。

# Gephiのチュートリアルを終えました。
仕事でネットワークグラフを視覚化する必要があり、1/6にGephiをインストールして、使い方を勉強していました。

# 今回使用したチュートリアルとデータセット

- Gephiのチュートリアル：https://gephi.org/users/quick-start/
- 今回使ったデータセット：小説レ・ミゼラブルのキャラクターのcoappearance(同時に登場する度合い)によって重み付けしたソーシャルネットワーク。
＞Les Miserables: coappearance weighted network of characters in the novel Les Miserables. D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, Reading, MA (1993).

[LesMiserables.gexf](https://gephi.org/datasets/LesMiserables.gexf)

ざっくりとこんなことをしました。
- GMLファイルをGephiで開き、ネットワークグラフを表示
- レイアウトを調整して、視覚的な表現を改善。
- ノードやエッジのランキングを可視化
- Modularity関数によって、コミュニティを抽出
- ラベルの追加などのビジュアルの微調整をしたのち、png形式でエクスポート

# レイアウト
`レイアウト`では、ネットワークグラフの表現の仕方を変更することができます。
今回は、チュートリアルに沿って、`Force Atlas`のアルゴリズムを利用しました。
簡単に説明すると、エッジをばね、ノードを電子に見立てて、ノード間に働く引力・斥力をシミュレートすることで、ノード間の関係性を維持しつつも、ノードの被りを減らし、
ネットワークグラフを見やすくする感じです。

備忘録：
`ForceAtlas`を実行すると、グラフがうねうね動き始めました。
自動で計算が終わり、勝手に理想のグラフが得られるのかなと思い、しばらく待っていたのですが、まったく収束する素振りを見せずにうねうねし続けるグラフ。
レイアウトの実行に終わりはないので、適切なタイミングで自分で中止をする必要があるようです。
https://forum-gephi.org/viewtopic.php?t=1889

![Screen Recording 2024-01-10 at 21.23.09.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490420/9fa4900d-6c9b-6fad-e695-6ee7005e8f0b.gif)


斥力を200→15000にしたら、いい感じにノードたちが離れて、混雑が緩和されました。
![lesmiserables_斥力15000.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490420/f6c181e2-6df2-0d8b-5f3d-9d01c5da20d2.png)

# ランキング
ランキングは、ノードやエッジに対して、特定の指標に基づきランク付けをし、色のグラデーションによって、可視化することができます。

例えば、ノードに対して、次数（他ノードとのつながりの数）によってランキングすると、以下のようになりました。
これでネットワークの中でどの辺りが中心そうなのか（中心の定義の仕方にも拠りますが）がなんとなく分かると思います。

![lesmiserables_ranking_nodes_degree.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490420/a2765ee8-fe1c-7ebd-35e9-f855eafc7c41.png)


# モジュラリティ
モジュラリティは、ネットワークからコミュニティを見つけ出すために使われる指標です。
モジュラリティを最大化することで、コミュニティを抽出することができます。
（数学的な定義については、まだ理解が追い付いていないので、追々勉強したいと思います）

とりあえず、モジュラリティという指標を最大化することで、コミュニティを抽出するアルゴリズムがあるんだということを理解したところで、実際にこれまで見てきたLes miserablesのネットワークに対して実行してみます。

以下はGephiのModularityを実行して得た、Modularity reportです。
Modularityは0.555、抽出されたコミュニティの数は6ということが分かります。


抽出したコミュニティを可視化したいと思います。
`Partition`機能を使って、`Attribute`に`Modularity Class`を指定します。
実際に6つのコミュニティが表示され、カラーラベルとパーセンテージが表示されました。

![lesmiserables_partition.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490420/6c63d679-c65b-9a19-7582-26e60ef9ba24.png)


適用をしてみると、こんな感じ。
ネットワークが6つのコミュニティに分類されている様子が視覚化されました。

![lesmiserables_community_detection.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490420/6470a09a-f3aa-e545-e564-8e31bb77b00d.png)

# ビジュアルの微調整
その他、ビジュアルを整えるために、以下を実施しました。
- ノードの大きさを次数に応じて調整
- 上記によって大きくなったノードが周辺にあるノードと被ってしまったので、`Force Atlas`で`大きさによる調整`にチェック。これによって、ノードの重複が改善されました。
- ノードにラベルを追加し、ラベルのサイズをノードのサイズと線形に。
- 上記でラベルが重複してしまったので、レイアウトにある`ラベルの調整`を実行し補正。（この機能は、ノード位置に関して、最終的なレイアウトが決まってから実行すると良さそうです。）
引用元：https://stackoverflow.com/questions/12721535/avoid-label-overlapping-in-gephi

以下が最終的なネットワークグラフです。
当たり前ですが、一番大きく見えている、Valjeanがレミゼの主人公です。
詳細な分析（ネットワークグラフから見える特徴を見つける）はまた別の機会にやりたいと思います。

![lesmiserables.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490420/4c2fb614-58eb-6891-d398-2fec53ea4ab3.png)