プログラミング言語の影響グラフを視覚化する

Gephi と Sigma.js を使用したネットワーク可視化チュートリアル

これが今日作成するもののプレビューです:プログラミング言語はグラフに影響を与えます。リンクをチェックして、過去と現在の 250 を超えるプログラミング言語間の「デザインの影響」の関係を調べてください!

あなたの番です!

今日の高度に接続された世界では、ネットワークは現代生活のいたるところにある側面です。

これまでの一日の始まり — ロンドンの交通網を利用しました 町に旅行する。それから支店に入りました お気に入りのコーヒー ショップの Wi-Fi ネットワークに接続するために Chromebook を使用しました .次に、さまざまなソーシャル ネットワーキングにログインしました 私がよく訪れるサイト

過去数十年で最も影響力のある企業のいくつかが、その成功をネットワークの力に負っていることは周知の事実です。

Facebook、Twitter、Instagram、LinkedIn、およびその他のソーシャル メディア プラットフォームは、ソーシャル ネットワークの小さな世界の特性に依存しています。これにより、ユーザー同士 (および広告主) を効果的に結び付けることができます。

Google の現在の成功の多くは、検索エンジン市場を早期に支配したことに負っています。これは、ページ ランク ネットワーク アルゴリズムの助けを借りて、関連する結果を返す能力によって可能になった部分もあります。

Amazon の効率的な流通ネットワークにより、一部の主要都市では同日配達を行うことができます。

ネットワークは、人工知能や機械学習などの分野でも非常に重要です。ニューラル ネットワークは、非常に活発な研究分野です。コンピュータ ビジョンに不可欠な多くの特徴検出アルゴリズムは、ネットワークを使用して画像のさまざまな部分をモデル化することに大きく依存しています。

ネットワークモデルの観点からも、幅広い科学現象を理解することができます。これには、量子力学、生化学的経路、生態系および社会経済システムが含まれます。

その否定できない重要性を考えると、ネットワークとその特性をよりよく理解するにはどうすればよいでしょうか?

ネットワークの数学的研究は「グラフ理論」として知られており、数学のよりアクセスしやすい分野の 1 つです。この記事は、予備知識や経験がほとんどないことを前提として、概要を説明することを目的としています。

Python 3.x と Gephi という素晴らしいオープンソース ソフトウェアを使用して、過去と現在のさまざまなプログラミング言語が影響によってどのようにリンクされているかをネットワークで視覚化します。

まずは…

ネットワークとは正確には何ですか?

上記の例は、いくつかの手がかりを与えてくれます。輸送ネットワークは 目的地 で構成されています ルートでつながっています .ソーシャル ネットワークは個人で構成されています 、関係を通じてつながっています 互いに。 Google の検索エンジン アルゴリズムは、さまざまな ウェブページ の「ランク」を評価します。 どのページがリンクしているかを見る

より一般的には、ネットワークとはノードの観点から説明できるシステムです。 とエッジ 、または口語で「点と線」。

一部のシステムは、この方法で簡単に抽象化できます。ソーシャル ネットワークは、おそらく最も明白な例です。コンピューターのファイル システムは別のものです。フォルダーとファイルは、「親」と「子」の関係によってリンクされています。

しかし、ネットワークの真の力は、非常に多くのシステムをネットワーク用語で抽象化およびモデル化できるという事実から生まれます。たとえ最初はその方法が明らかではなかったとしてもです。

ネットワークの表現

ネットワークを数学的に分析して記述するには、ペンと紙のスケッチを少し超える必要があります。点や線の絵を計算できる数字に変えるにはどうすればよいでしょうか?

解決策の 1 つは、 隣接行列 を作成することです。 私たちのネットワークを代表してください。

行列は、慣れていない場合は少し難しそうに聞こえるかもしれない概念の 1 つですが、恐れる必要はありません。それらは、多くの計算を一度に実行するために使用できる数値のグリッドと考えてください。以下に例を示します:

      Python Java Scala C#
Python     0    1     0  0
Java       0    0     0  1
Scala      0    1     0  0
C#         0    1     0  0

このマトリックスでは、それぞれの言語がリンクされているかどうかに応じて、各行と列の交点が 0 または 1 になります。上のイラストと照らし合わせてみてください！

ほとんどの場合、隣接行列はネットワークを数学的に表現する優れた方法です。ただし、計算の観点からは、少し面倒な場合があります。

たとえば、ノードの数が比較的少ない (1000 など) でも、行列の要素数ははるかに多くなります (1000² =1,000,000 など)。

多くの現実世界のシステムはまばらなネットワークを生み出します .これらのネットワークでは、ほとんどのノードは他のすべてのノードのごく一部にのみ接続します。

コンピュータ メモリ内の 1000 ノードの疎ネットワークを隣接行列として表すと、RAM に格納されたデータは 1,000,000 バイトになります。ほとんどがゼロになります。これにはもっと効率的な方法が必要です。

別のアプローチは、エッジ リストを使用することです 代わりは。これらはまさに彼らが言っていることです。それらは、どのノード ペアが相互にリンクしているかの単なるリストです。

たとえば、上記のプログラミング言語ネットワークは次のように表すことができます:

Java, Python
Java, Scala
Java, C#
C#, Java

大規模なネットワークの場合、これはそれらを表現するための計算効率の高い手段です。もちろん、エッジ リストから隣接行列を生成することも可能です (その逆も可能です)。どちらかを選ばなければならないというわけではありません。

ネットワークを表すもう 1 つの手段は、隣接リストです。これにより、すべてのノードがリストされ、その後にリンク先のノードが続きます。例:

Java: Python, Scala, C#
C#: Java

データの収集、接続の作成

ネットワーク モデルと視覚化は、それを構築するために使用されるデータと同じくらい優れています。これは、データが正確かつ完全であることを保証するだけでなく、ノード間のエッジを推測する手段を正当化する必要があることを意味します.

多くの点で、これは 重要なステップ。ネットワークに関するその後の分析と推論は、「リンケージ基準」を正当化できるかどうかにかかっています。

たとえば、ソーシャル ネットワーク分析では、ソーシャル メディアで相互にフォローしているかどうかに基づいて人々を関連付けることができます。分子生物学では、共発現に基づいて遺伝子を関連付けることができます。

多くの場合、ノードをリンクするために使用される方法では、重みが可能です。 エッジに割り当てられ、「強さ」の尺度を与えます。

たとえば、オンライン小売のコンテキストでは、一緒に購入される頻度に基づいて製品をリンクできます。一緒に購入されることが多い商品は、加重エッジが高くなります。 たまにしか一緒に買わない商品よりも偶然に予想されるよりも頻繁に一緒に購入されない製品は、まったくリンクされません。

ご想像のとおり、ノードを相互にリンクする方法は、好きなだけ洗練されたものにすることができます。

ただし、このチュートリアルでは、プログラミング言語を接続するためのより簡単な方法を使用します。ウィキペディアの正確さに依存します。

私たちの目的では、これで問題ありません。ウィキペディアの成功は、ウィキペディアが正しいことをしているに違いないことの証です。オープンソースの協力的な方法で記事を作成することにより、ある程度の客観性が保証されます。

また、ページ構造が比較的一貫しているため、Web スクレイピング手法を試すのに便利です。

もう 1 つのボーナスは、詳細に文書化された広範な Wikipedia API で、情報検索がさらに簡単になります。始めましょう。

ステップ 1 — Gephi のインストール

Gephi は、Linux、Mac、および Windows で利用できます。ここからダウンロードできます。

このプロジェクトでは、Lubuntu を使用していました。 Ubuntu/Debian を使用している場合は、以下の手順に従って Gephi を起動して実行できます。それ以外の場合、インストール プロセスは、慣れ親しんだプロセスとほぼ同じになります。

お使いのシステム用の Gephi の最新バージョン (執筆時点では v.0.9.1) をダウンロードします。準備ができたら、ファイルを抽出する必要があります。

cd Downloads
tar -xvzf gephi-0.9.1-linux.tar.gz
cd gephi-0.9.1/bin./gephi

Java JRE のバージョンを確認する必要がある場合があります。 Gephi には最新バージョンが必要です。 Lubuntu の比較的新しいインストールで、default-jre をインストールするだけで、そこからすべてが機能しました。

apt install default-jre
./gephi

開始する準備が整う前に、もう 1 つのステップがあります。グラフを Web にエクスポートするには、Gephi 用の Sigma.js プラグインを使用できます。

Gephi のメニュー バーから [ツール] オプションを選択し、[プラグイン] を選択します。

[利用可能なプラグイン] タブをクリックして、[SigmaExporter] を選択します (JSON Exporter もインストールしました。これも便利なプラグインです)。

「インストール」ボタンを押すと、プロセスが進められます。完了したら、Gephi を再起動する必要があります。

ステップ 2 — Python スクリプトを書く

このチュートリアルでは、Python 3.x と、作業を容易にするいくつかのモジュールを使用します。 pip モジュール インストーラーを使用して、次のコマンドを実行します。

pip3 install wikipedia

次に、新しいディレクトリに script.py のような名前のファイルを作成します 、お気に入りのコード エディター/IDE で開きます。以下は、主なロジックの概要です:

<オール>

まず、含めるプログラミング言語のリストが必要です。

次に、そのリストを調べて、関連するウィキペディアの記事の HTML を取得します。

これから、各言語が影響を与えたプログラミング言語のリストを抽出します。これは大雑把なリンケージ基準になります。

同時に、各言語に関するメタデータを取得するとよいでしょう。

最後に、収集したすべてのデータを .csv ファイルに書き込みます

完全なスクリプトは、この要点にあります。

いくつかのモジュールをインポート

script.py で 、作業を容易にするいくつかのモジュールをインポートすることから始めます:

import csv
import wikipedia
import urllib.request
from bs4 import BeautifulSoup as BS
import re

OK — 含めるノードのリストを作成することから始めます。ここでウィキペディア モジュールが役に立ちます。これにより、Wikipedia API へのアクセスが非常に簡単になります。

次のコードを追加してください:

pageTitle = "List of programming languages"
nodes = list(wikipedia.page(pageTitle).links)
print(nodes)

このスクリプトを保存して実行すると、ウィキペディアの記事「プログラミング言語の一覧」からのすべてのリンクが表示されます。いいね！

ただし、自動的に収集されたデータを手動で検査することは常に賢明です。一見すると、多くの実際のプログラミング言語と同様に、スクリプトがいくつかの追加のリンクも取得していることがわかります。

たとえば、「マークアップ言語のリスト」、「プログラミング言語の比較」などがあります。

Gephi では含めたくないノードを削除できますが、先に進む前にデータを「消去」しても害はありません。どちらかといえば、後で時間を節約できます。

removeList = [
    "List of",
    "Lists of",
    "Timeline",
    "Comparison of",
    "History of",
    "Esoteric programming language"
    ]

nodes = [i for i in nodes if not any(r in i for r in removeList)]

これらの行は、データから削除する部分文字列のリストを定義します。次に、スクリプトはデータを調べて、不要な部分文字列を含む要素を削除します。

Python では、これに必要なコードは 1 行だけです!

いくつかのヘルパー関数

これで、ウィキペディアのスクレイピングを開始して、エッジ リストを作成 (およびメタデータを収集) できます。これを簡単にするために、まずいくつかの関数を定義してください。

HTML の取得

最初の関数は、BeautifulSoup モジュールを使用して、各言語のウィキペディア ページの HTML を取得します。

base = "https://en.wikipedia.org/wiki/"

def getSoup(n):
    try:
        with urllib.request.urlopen(base+n) as response:
            soup = BS(response.read(),'html.parser')
            table = soup.find_all("table",class_="infobox vevent")[0]                return table
     except:
         pass

この関数は、urllib.request モジュールを使用して、“https://en.wikipedia.org/wiki/” + “programming language” のページの HTML を取得します。 .

次に、これが BeautifulSoup に渡され、HTML が読み取られて解析され、情報の検索に使用できるオブジェクトになります。

次に、find_all() を使用します 関心のある HTML 要素を抽出するメソッド。

ここでは、各プログラミング言語の記事の上部にある概要表になります。これらはどのように識別できますか?

最も簡単な方法は、プログラミング言語のページの 1 つにアクセスすることです。ここでは、ブラウザーの開発者ツールを使用して、関心のある要素を調べることができます。

集計表には HTML タグ <tab があります le> と CSS classes "in fobox" and "v event" であるため、これらを使用して HTML 内のテーブルを識別できます。

これを引数で指定します:

• "table" そして
• class_="infobox vevent"

find_all() 条件に一致するすべての要素のリストを返します。興味のある要素を実際に指定するには、インデックス [0] を追加します .関数が成功すると、table が返されます。 物体。それ以外の場合は、None を返します .

自動化されたデータ収集手順では、例外を完全に処理することが常に重要です。そうでない場合、最良のシナリオではスクリプトがクラッシュし、最初からやり直す必要があります。

最悪の場合、不整合やエラーだらけのデータ セットになってしまいます。これでは、今後の作業は悪夢のようになります。

メタデータを取得

次の関数は table を使用します いくつかのメタデータを探すためのオブジェクト。ここでは、その言語が最初に登場した年をテーブルで検索します。

def getYear(t):
    try:
        t = t.get_text()
        year = t[t.find("appear"):t.find("appear")+30]
        year = re.match(r'.*([1-3][0-9]{3})',year).group(1)
        return int(year)
    except:
        return "Could not determine"

この短い関数は table を取ります object を引数として使用し、BeautifulSoup の get_text() を使用します 文字列を生成する関数。

次のステップは、year という部分文字列を作成することです .これは、単語 "appear" の最初の出現から 30 文字を取ります .この文字列には、言語が最初に登場した年が含まれている必要があります。

年だけを抽出するには、正規表現を使用します (re の礼儀 モジュール) を使用して、1 から 3 までの数字で始まり、その後に 3 桁の数字が続く任意の文字に一致します。

re.match(r'.*([1-3][0-9]{3})',year)

これが成功した場合、関数は year を返します。 整数として。それ以外の場合は、悲しそうな「Could not determine」が返されます。パラダイム、デザイナー、タイピングの規律など、さらにメタデータをスクレイピングしたい場合があります。

リンクの収集

もう 1 つの関数 — 今回は table を入力します。 特定の言語のオブジェクトを取得し、できれば他のプログラミング言語のリストを受け取ります。

def getLinks(t):
    try:
        table_rows = t.find_all("tr")
        for i in range(0,len(table_rows)-1):
            try:
                if table_rows[i].get_text() == "\nInfluenced\n":
                    out = []
                    for j in table_rows[i+1].find_all("a"):
                        try:
                            out.append(j['title'])
                        except:
                            continue
                    return out
            except:
                continue
        return
    except:
        return

おお、入れ子になっているのを見てください…では、実際にここで何が起こっているのでしょうか?

この関数は table オブジェクトは一貫した構造を持っています。テーブル内の情報は行に格納されます (関連する HTML タグは < です) tr> )。これらの行の 1 つに ` テキスト "\nInfluenced\n" が含まれます .関数の最初の部分は、これがどの行であるかを見つけます。

この行が見つかったら、次の行が確実に 行には、現在のプログラミング言語の影響を受ける各プログラミング言語へのリンクが含まれています。 find_all("a") を使用してこれらのリンクを見つけます — 引数 "a" HTML タグ <a> に対応 .

リンクごと j 、その ["title"] を追加します out というリストへの属性 . ["title"] に興味を持った理由 属性は、これが 正確に 一致するためです nodes に格納されている言語名 .

たとえば、Java は nodes に格納されます。 "Java (programming language)" として であるため、データ セット全体でこの正確な名前を使用する必要があります。

成功した場合、getLinks() プログラミング言語のリストを返します。関数の残りの部分は、いずれかの段階で問題が発生した場合に備えて、例外処理を処理します。

データの収集

ようやく、座ってスクリプトに任せる準備がほぼ整いました。データを収集し、2 つのリスト オブジェクトに保存します。

edgeList = [["Source,Target"]]
meta = [["Id","Year"]]

ここで、前に定義した関数を nodes のすべてのアイテムに適用するループを作成します。 、出力を edgeList に保存します と meta .

for n in nodes:
    try:
        temp = getSoup(n)
    except:
        continue
    try:
        influenced = getLinks(temp)
        for link in influenced:
            if link in nodes:
                edgeList.append([n+","+link])
                print([n+","+link])
    except:
        continue
    year = getYear(temp)
    meta.append([n,year])

この関数は各言語を nodes で受け取ります ウィキペディアのページから要約表を取得しようとします。

次に、テーブルにリストされているすべての言語を、問題の言語の影響を受けているものとして取得します。

nodes にも登場する言語ごとに リスト、edgeList に要素を追加 ["source,target"] の形式で .このようにして、Gephi にフィードするエッジ リストを作成します。

デバッグ目的で、 edgeList に追加された各要素を出力します —すべてが正常に機能していることを確認するためだけに。さらに徹底している場合は、except に print ステートメントを追加できます。 句も。

次に、言語の名前と年を取得し、これらを meta に追加します リスト。

CSV への書き込み

ループが実行されたら、最後のステップは edgeList の内容を書き込むことです と meta カンマ区切り値 (CSV) ファイルに。これは csv で簡単に実行できます モジュールが以前にインポートされました。

with open("edge_list.csv","w") as f: 
    wr = csv.writer(f)
    for e in edgeList:
        wr.writerow(e)

with open("metadata.csv","w") as f2:
    wr = csv.writer(f2)
    for m in meta:
        wr.writerow(m)

終わり！スクリプトを保存し、ターミナルから以下を実行します:

$ python3 script.py

スクリプトがエッジ リストを構築する際に、ソースとターゲットの各ペアを出力するスクリプトが表示されるはずです。インターネット接続が安定していることを確認し、スクリプトが魔法のように動作するまで座ってください。

ステップ 3 — Gephi によるグラフ構築

Gephi を以前にインストールして実行していることを願っています。これで、新しいプロジェクトを作成し、収集したデータを使用して有向グラフを作成できます。これにより、さまざまなプログラミング言語が互いにどのように影響し合っているかがわかります!

まず、Gephi で新しいプロジェクトを作成し、[Data Laboratory] ​​ビューに切り替えます。これにより、Gephi でデータを処理するためのスプレッドシートのようなインターフェイスが提供されます。最初にエッジ リストをインポートします。

• [スプレッドシートをインポート] をクリックします。
• edge_list.csv を選択してください Python スクリプトによって生成されたファイル。 Gephi がカンマを区切り記号として使用することを認識していることを確認してください。
• リストの種類から「エッジ リスト」を選択します。
• [次へ] をクリックして、ソース列とターゲット列の両方を文字列としてインポートしていることを確認します。

これにより、Data Lab がノードのリストで更新されます。次に、metadata.csv をインポートします ファイル。今回は、リストタイプから必ず「ノードリスト」を選択してください。

[プレビュー] タブに切り替えて、ネットワークがどのように見えるかを確認してください。

あ…ちょっと…モノクロです。そして乱雑。スパゲッティのプレートのように。これを修正しましょう。

きれいにする

プレゼンテーションに取り組むにはさまざまな方法がありますが、ここで少し創造的な自由が生まれます。ネットワーク ビジュアライゼーションでは、基本的に 3 つの考慮事項があります。

<オール>

ポジショニング ネットワークのレイアウト パターンを生成できるアルゴリズムはいくつかあります。一般的な選択肢は、Gephi で利用可能な Fruchterman-Reingold アルゴリズムです。

サイジング グラフ内のノードのサイズを使用して、興味深いプロパティを表すことができます。多くの場合、これは中心性の尺度です .中心性を測定する方法はたくさんありますが、それらはすべて、特定のノードがネットワークの残りの部分にどれだけうまく接続されているかという点で、そのノードの「重要性」を反映しています。

着色 色を使用してノードのプロパティを表示することもできます。多くの場合、色はコミュニティ構造を示すために使用されます .これは、「グラフの残りの部分よりも相互に関連しているノードのグループ」として広く定義されています。ソーシャル ネットワークでは、友情、家族、または職業上のグループを明らかにすることができます。コミュニティ構造を検出できるアルゴリズムはいくつかあります。 Gephi には Louvain メソッドが組み込まれています。

これらの変更を行うには、いくつかの統計を計算する必要があります。 「概要」ウィンドウに切り替えます。ここで、右側にパネルが表示されます。 「統計」タブが含まれている必要があります。これを開くと、さまざまなオプションが表示されます。

Gephi には、多くの統計機能が組み込まれています。それぞれについて、[実行] をクリックすると、ネットワークに関する洞察を明らかにするレポートが生成されます。

知っておくと便利なものには次のようなものがあります:

• 平均学位 平均的な言語は、約 4 つの他の言語に接続されています。このレポートには、次数分布グラフも表示されます。これは、ほとんどの言語はつながりが非常に少なく、一部の言語はつながりが多いことを示しています。これは、これがスケールフリーであることを示唆しています ネットワーク .スケールフリー ネットワークとそれを生成するプロセスについて、多くの研究が行われています。
• 直径 このネットワークの直径は 12 です。つまり、これは任意の 2 つの言語間の接続の「最も広い」数です。平均パスの長さは 4 弱です。これは、平均して、任意の 2 つの言語が 4 つのエッジで区切られていることを意味します。これらの数値は、ネットワークの「サイズ」の目安となります。
• モジュール性 これは、ネットワークがどの程度「区画化」されているかを示すスコアです。ここで、モジュール性スコアは約 0.53 です。これは比較的高く、このネットワーク内に個別のモジュールがあることを示唆しています。繰り返しますが、これは基盤となるシステムについて興味深いことを示しています。言語は、異なる「影響グループ」に分類される傾向があります。

いずれにせよ、ネットワークの外観を変更するには、左側のパネルに進んでください。

「レイアウト」タブでは、使用するレイアウト アルゴリズムを選択できます。 「実行」を押して、グラフがリアルタイムで変化するのを見てください。どのレイアウト アルゴリズムが最も効果的かを確認してください。

[レイアウト] タブの上に [外観] タブがあります。ここでは、ノードとエッジの色、サイズ、ラベルのさまざまな設定を試すことができます。これらは、属性に基づいて構成できます (Gephi に計算させる統計情報を含む)。

提案として、次のことができます:

• モジュール性属性によってノードに色を付けます。これにより、コミュニティ メンバーシップに応じて色分けされます。
• 次数によってノードのサイズを変更します。接続の良好なノードは、接続の少ないノードよりも大きく表示されます。

ただし、いろいろ試して、一番気に入ったレイアウトを見つけてください。

グラフの外観に満足したら、最後のステップである Web へのエクスポートに進みます!

ステップ 4 — Sigma.js

Gephi で探索できるネットワーク ビジュアライゼーションがすでに構築されています。スクリーンショットを撮るか、グラフを SVG、PDF、または PNG 形式で保存するかを選択できます。

ただし、以前に Sigma.js プラグインをインストールした場合は、グラフを HTML にエクスポートしてみませんか?これにより、オンラインでホストしたり、GitHub にアップロードして他のユーザーと共有したりできるインタラクティブな視覚化が作成されます。

これを行うには、Gephi のメニュー バーから [エクスポート]> [Sigma.js テンプレート…] を選択します。

必要に応じて詳細を入力します。プロジェクトをエクスポートするディレクトリを必ず選択してください。タイトル、凡例、説明、ホバー動作、その他多くの詳細を変更できます。準備ができたら、[OK] をクリックします。

ここで、プロジェクトをエクスポートしたディレクトリに移動すると、Sigma.js によって生成されたすべてのファイルを含むフォルダーが表示されます。

index.html を開く お気に入りのブラウザで。タダ！あなたのネットワークがあります！ CSS と JavaScript を少し知っている場合は、生成されたさまざまなファイルを調べて、必要に応じて出力を微調整できます。

これでこのチュートリアルは終了です!

まとめ

• 多くのシステムをネットワークとしてモデル化し、視覚化できます。グラフ理論は、ネットワークの構造と特性を理解するのに役立つツールを提供する数学の一分野です。
• Python を使用してウィキペディアからデータを取得し、プログラミング言語の影響グラフを作成しました。リンクの基準は、特定の言語が別の言語の設計に影響を与えるものとしてリストされているかどうかでした。
• Gephi と Sigma.js は、ネットワークの分析と視覚化を可能にするオープンソース ツールです。ネットワークを画像、PDF、または Web 形式でエクスポートできます。

読んでくれてありがとう — コメントや質問があればお待ちしております!グラフ理論の詳細については、Albert-László Barabási のインタラクティブなオンライン ブックを参照してください。

このチュートリアルの完全なコードは、ここにあります。