Tech Memo

networkxとmatplotlinでサイト内リンクマップを可視化

ken 技術 6月 23, 2019

サイト内の参照・相互リンクの関係を整理したい、と考えている人は多いと思います。

というのも、SEO的にサイト内の相互リンクは重要です。 サイト内の記事は、内容が関連する記事間で、相互にリンクを張っており、過去記事もリンクを張ることで、回遊による訪問者が増えることがあります。

ただ、手動で整理するのはとても大変です。

そこで、Pythonのnetworkxを使って、サイト内のリンク関係を可視化するツールを作成しました。

技術的に新しい点はないのですが、私自身が 初めて networkxを使ってグラフ作成をしたので、初心者（私）がつまづいた用語やライブラリの概要を残しておきたいと思います。

最終的に作成したグラフツールのサイトは以下になります。

リンクマップ作成

上記ツールの処理概要は以下の通りです。

  • WEBフレームワークにはbottle.pyを使用
  • 画面でリンクを整理したいサイトのURLを指定
  • 指定されたURLからurllibと BeautifulSoupを使って aタグ（アンカー）をスクレイピング（抽出）
  • 抽出した記事のURLをもとに、相互リンクを整理
  • 整理した情報はgmlファイルにしてダウンロード可能
  • 整理した記事間のリンク関係をmatplotlibで SVG形式で描画

初めに

「グラフ」というと、日常生活では、折れ線グラフやヒストグラムに代表される”統計的な”グラフを指すことが多いです。

一方、 組み合わせの問題を簡潔に記述するための道具 として「 グラフ理論 」があり、本記事でのグラフは、ネットワーク図のように「頂点」と「辺」で構成されたグラフを指します。

用語

  • グラフ
  • ノード／エッジ
    • ノードが節点・頂点
    • エッジが 枝・辺
    • 今回のサイト内リンクマップで例えると、サイト内の記事(URL)がノードで、その記事間の参照関係（リンク）がエッジになります。
  • 有向グラフ／無向グラフ
    • 有向グラフは、辺に向きがある（矢印）もの
    • 無向グラフは、辺に向きがない（線）もの
    • 今回のサイト内リンクマップでは、記事が参照しているのか／されているのか、も関心があるので、有向グラフを使います。
  • 次数
    • 頂点から出ている辺の本数。
    • 今回のサイト内リンクマップでは、次数が多いほど、重要な記事といえます。
    • 次数の大きさで、記事（ノード）の大きさ、または色の濃さを変えたりします。
  • 中心性
    • ネットワークにおける各頂点の重要性を評価したり、比較したりするための指標
    • 今回のサイト内リンクマップでは、次数に着目した次数中心性を使います。
  • PageRank
    • webサイト間の重要性を算出するために「リンク（流入）」を重視するようにした上で、さらに分離グラフや強連結でない有向グラフにも適用できるようにした指標
    • Googleの検索エンジンがWebページの重要度をはかる指標
    • networkxでは関数で用意されており、簡単に利用が可能
  • GML形式
    • GML (Graph Modeling Language) は、非常に簡単な構文でネットワークデータをサポートしたテキストファイルの形式です。
    • Graphlet、Pajek、yEd、LEDA、および NetworkX によって使われています。
  • DOT形式
    • DOT は、可読性に優れた構文を使用して、サブグラフや要素の外観 (色、幅、ラベルなど) をはじめとするネットワークデータを記述できる テキストファイルです。
    • NetworkX、Tulip、および ZGRViewer によって使われています。
  • Graphviz
    • 人や物のネットワーク、フローチャート、系統樹などに適したグラフ描画ツールです。
    • Pythonからは pygraphviz ライブラリで操作できます。

グラフ関連のライブラリ

  • networkx
    • NetworkXは、複雑なネットワークの構造、ダイナミクス、および機能を作成、操作、および研究するためのPythonパッケージ
    • ノードとエッジを追加すれば、あとは良しなにグラフデータを用意してくれます。
  • matplotlib
    • Pythonでよく利用されるデータ可視化ライブラリです。 散布図・ヒストグラム・折れ線グラフなど、色々なグラフを作成できます。
    • networkxとの連携も、多くのサンプルが ネット上に あります。
  • pygraphviz
    • DOT言語で記述されたファイルを読み込んでグラフを描画します。
    • matplotlibより気の利いたグラフを作成できるようですが、今回は利用していません。

NetworkXについて

簡易な利用手順としては、以下の通り。

利用イメージ用のソースのためコピペしても動きません。

    #networkxのグラフを用意
    G = nx.DiGraph()
    
    #ノードを追加
    G.add_node(article_name)
    
    #ノード間のエッジを追加
    G.add_edge(linking_article_name, linked_article_name)
    
    # グラフ形式を選択。ここではスプリングモデル
    pos = nx.spring_layout(G,k=k) 
    
    # pagerank の計算
    pr = nx.pagerank(G)
    
    # グラフ描画。 オプションでノードのラベル付きにしている
    nx.draw(G,
           pos,
           with_labels=label,
           alpha=alpha,
           font_size=font_size,
           node_size=[node_size_rate*v for v in pr.values()],
           node_color=list(pr.values()), cmap=plt.cm.Reds)
           
    #グラフを保存
    plt.savefig(savesvgpath,format='svg')
    
    #グラフのクリア
    plt.clf()
  • グラフの種類とNetworkXクラスの対応
    • 無向単純　 | Graph
    • 有向単純　 | DiGraph
    • 自己ループ | Graph ,DiGraph
    • 平行エッジ | MultiGraph、MultiDiGraph
  • グラフの形式
    • グラフの点を配置するいくつかのアルゴリズムが組み込まれている。
      これを利用すると自動的にレイアウトしてくれる。
    • circular_layout　:節点を円上に配置します。
    • random_layout　:単位正方形内でノードを一様にランダムに配置します。
    • shell_layout　:ノードを同心円に配置します。
    • spring_layout　:力指向アルゴリズムを使用してノードを配置します。
    • spectral_layout　:グラフラプラシアンの固有ベクトルを使ってノードを配置します。
  • matplotlibを使ってグラフを描画
    • draw：Matplotlibでグラフを描きます。
    • draw_networkx：Matplotlibを使ってグラフを描きます。
    • draw_networkx_nodes：グラフのノードを描く
    • draw_networkx_edges：グラフの辺を描く
    • draw_networkx_labels：グラフ上にノードラベルを描く
    • draw_networkx_edge_labels：エッジラベルを描きます。
    • draw_circular：円形のレイアウトでグラフを描きます。
    • draw_kamada_kawai：Kamada-Kawaiの強制指向のレイアウトでグラフを描きます。
    • draw_planar：平面レイアウトで平面ネットワークグラフを描きます。
    • draw_random：ランダムなレイアウトでグラフを描きます。
    • draw_spectral：スペクトル2Dレイアウトでグラフを描きます。
    • draw_spring：スプリングレイアウトでグラフを描く
    • draw_shell：シェルレイアウトでnetworkxのグラフを描きます。
  • drawの引数
    • G：グラフデータ
    • pos：ノードの位置情報（指定しない場合は spring_layout ）
    • with_labels：ノードにラベルを表示するか
    • alpha：図の透過度
    • font_size：フォントのサイズ
    • node_size：ノードの大きさ、ノードごとに指定可能
    • node_color：ノードの色、ノードごとに指定可能

おまけ：その他ライブラリ

本記事のメインはグラフ描画ですが、それ以外に利用したライブラリについても、概要を以下に記載します。

  • bottle
    • ボトルは、Python用の高速でシンプルかつ軽量のWSGIマイクロWebフレームワークです。
    • ユーザ認証もDBも必要ない、簡易なWEBツールを作成するには持って来いです。Djangoでは重いと感じたときはbottleです。
  • urlib
    • urllib3はPython用のHTTPクライアントです。
    • 私はライトユーザーなので、 ネット上にいくらでもサンプルがあり、使い方にこまることはありません。
  • BeautifulSoup
    • pythonで動作するHTMLとXMLのパーサーです。Beautiful Soupはパースしたツリーの操作、検索、変更を簡単にできます。
    • これも、 私はライトユーザーなので、 ネット上にいくらでもサンプルがあり、使い方にこまることはありません。
    • もっと高度にスクレイピングをしたい場合はscrapyなどを使います。ただし、scrapyが１つのフレームワークなので学習コストがかかります。
タグ: ,

About: ken

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。