グラフ理論

目次 グラフの応用を扱うにあたり、NetworkXの基本操作を練習していこうと思います。 基本的な操作→例題の流れで説明を進めていきます。 🎵 BGMを再生する 基本的操作 NetworkXの基本的な操作は、主に次の流れで行います。 グラフオブジェクトの作成 ノード・エッジの追加・削除 属性（重み・ラベルなど）の付与 グラフ情報の取得（ノード数・エッジ数・隣接情報など） 簡単な可視化 以下、それぞれをコード例とともに説明します。 1. グラフオブジェクトの作成 import networkx as nx # 無向グラフ G = nx.Graph() # 有向グラフ DG = nx.DiGrap…

目次 グラフ理論はネットワーク解析や、グラフニューラルネットワークを理解する上で必要な知識です。 そしてグラフ理論をPython上で実装する際にスタンダードとなっているライブラリがNetworkXです。 本日テーマ； NetworkXについて紹介し、何が出来るかイメージできるようにする 🎵 BGMを再生する NetworkXとは NetworkX は、グラフ（ネットワーク）構造の作成・操作・解析・可視化を行うための Python パッケージです。 NetworkX の主な特徴 グラフ構造のモデル化現実世界の「つながり」をグラフとして表現できます。 例：SNSのフォロー関係、道路網、分子構造、W…

目次 先日より話しているRAGシリーズです。 GraphRAGは因果関係を情報DBから取得する上で、単純な検索型のRAGより高い検索性能を示します。 検索に必要な情報を保持するDBについては、違いがつくのでしょうか。 本日テーマ： 情報DBを作成する上で、GraphDBはどのような違いが生じるか。について整理しました。 検索型RAGとの違い GraphRAGは、「データベース構築（インデックス構築）の段階」で従来のRAGと大きく異なる設計になっています。主な違いを整理します。 1. 目的の違い：検索 vs 構造理解 従来のRAG（検索型） 目的：**「クエリに最も関連するチャンクを素早く見つけ…

目次 前回グラフDBについて扱いました。グラフDBはデータの相関、因果関係をグラフ構造を用いて表現することが可能となり、通常のRDB検索では見つけずらい関係性を分析することに長けています。 本日はグラフDBの考えのもととなったグラフ理論の因果分析の仕組みと効果について説明していきます。 仕組み グラフネットワーク（特に「因果グラフ」や「因果ベイジアンネットワーク」）で因果関係を見つけられる理由は、単なる統計的な「相関」ではなく、データが生成される 「仕組み（メカニズム）」を構造的にモデル化しているから です。 なぜグラフを使うと「原因」と「結果」を区別できるのか、その主要な原理を3つのポイント…

概要 本稿は、無向木 (undirected tree) の形状に対して、一意の文字列表現を割り当てることを目標とします。 逆に、文字列表現から無向木を復元できます。 ここで、木の形状以外の情報 (頂点の ID など) は無視されるものとします。 すなわち、図に示すような 2 つの無向木は同一のものと見なします。 ある頂点を根としたときの (根付き木の) 文字列表現 まず、比較的簡単な場合として、根 (root) が指定された無向木を考えましょう。 根を表す頂点を出発して深さ優先探索 (DFS) を行い、各頂点に対して行きがけに左括弧 ( を、帰りがけに右括弧 ) を記録します。 ただし、子の…

こんにちは。ぱいです。 京大の院試を眺めていて、一見すると集合論の抽象的な問題のようだけどグラフ理論で考えて可視化したら瞬殺だな～という問題があって面白かったので解説します。 （解説の中で必要な知識は説明するので、グラフ理論を知らない人でも読めます。） ※解答が正しいことは保証しませんので、院試対策等として読む場合にはご留意ください。 問題 に対して, とおく. の濃度 の部分集合全体を と表し, また の濃度 の部分集合 のうち, 以下の条件 (＊) をみたすもの全体を と表す. (＊) 任意の について . さらに写像 を \begin{align} F_{n}(i) = \left\{ …

目次 ニューラルネットワーク（NN）をグラフ理論の視点から理解するための、最も効果的な実装例題は、NNの順伝播（Forward Propagation）を有向非巡回グラフ（DAG）の探索でしょうか。 ここでは、NNの基本形である「多層パーセプトロン（MLP）」を例に、グラフ理論とNNを結びつける実装例を提案します。 グラフ理論とは グラフ理論は、「点と線で表される関係の構造」を扱う数学の分野です。もう少し砕いて言うと、「つながり方のパターン」を研究する学問です。 1. グラフ理論の基本イメージ グラフ理論でいう「グラフ」は、棒グラフや折れ線グラフではなく、次のようなものです。 点（ノード）：人…