日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念 - アジマティクス
Ｑ：これは何の構造を表しているでしょう？ グラフ理論 上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。 （余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ ○○」や「グラフ理論 ○○」とググるよりも、「ネットワーク ○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています） さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例
機は熟した！グラフ構造に対するDeep Learning、Graph Convolutionのご紹介 - ABEJA Tech Blog
はじめまして。ABEJAでResearcherをやらせていただいている白川です。 先日、化合物の物性推定をDeep Learningをつかって従来手法より300,000倍高速に処理するという論文がでました（[1], [2]）。この論文の手法は、Graph Convolutionというグラフ上に定義されたConvolution演算がベースとなっています。物性推定に限らず、グラフ解析全般を Deep Learning で上手にこなせるようになれば、Deep Learningのアプリケーションの幅がぐっと拡がり、さらなるイノベーションが起きそうな予感がします。 ICMLやNIPSなどの機械学習系の主要国際会議でも数年前からGraph Convolutionについての論文がちらほら出現しはじめており、とくに最近その勢いが増してきている印象があります。個人的にも最近（前から？）にわかにグラフづいてい
平面グラフと交通ネットワークのアルゴリズム - iwiwiの日記
本日，PFI セミナーにて「平面グラフと交通ネットワークのアルゴリズム」というタイトルで話をさせてもらいました．スライドは以下になります． 「平面グラフでは色々な問題が効率的に解けると聞くけど一体何故？」 「道路ネットワークを処理するにはそういうアルゴリズムが使われているの？」 というような自分が昔持っていた疑問に答える，そんなつもりで準備をしました．そんな疑問を持っている方は，是非ご覧ください． 内容は以下のような感じです． 平面グラフのアルゴリズム（理論コミュニティ） 平面グラフとは何か 平面グラフのアルゴリズムテクニックとその応用例 双対グラフ 小さいセパレータの存在 (r-division) グラフ分割 (Deletion Decomposition) 交通ネットワークのアルゴリズム（応用コミュニティ） どのような課題が取り組まれているか 道路ネットワークは平面グラフなのか？ 経路
Link Analysis and Related Topics - Home
2008年度 先端情報科学特論 II & IV リンク解析と周辺の話題 担当 新保 仁 shimbo@is.naist.jp 日時 2008/11/10, 11/17, 12/1, 12/8 (全 4 回) - 4限 15:10-16:40 場所 情報棟 L3 講義室 リンク解析は, グラフ (ネットワーク) データの構造から有用な情報を抽出するための, データマイニングの一研究分野です. この講義ではまず, リンク解析が取り扱う 2 種類の尺度 (重要度と関連度) について述べ, それぞれの代表的な計算手法を紹介します. 後半では, 近年機械学習分野で盛んに研究されているカーネルのうち, グラフ上の節点に対して定義されたカーネル (グラフカーネル) と, そのリンク解析への応用について紹介します. 第1回 11月10日 スライド 第2回 11月17日 スライド 第3回 12月1日
The Operations Research Society of Japan Archive
雑誌別 英文論文誌 和文論文誌 機関誌 シンポジウム予稿集 研究発表大会アブストラクト集 索引 タイトル一覧 著者索引 注意事項 著作権規定 OR学会HP 検索
数学者もスペインの勝利を予言していた - 蝉コロン
ぼやぼや… that could rival the psychic octopus.Mathematical formula predicts clear favourite for the FIFA World Cup, Queen Mary, University of Londonvia Mathematical formula predicts clear favorite for the FIFA World Cup先週末の記事。ロンドン大学の数学者Dr. Javier López PeñaとDr. Hugo Touchetteが、スペインが勝つことを「数学的に」予測していましたので紹介。 それまでの全試合からパスのデータを集めて、グラフ理論っていうので、パスの「ネットワーク」を解析した。それぞれの選手のcentralityをスコア付けしている。その人がいないと困るネットワーク
リンク解析とか: 重要度尺度と von Neumann カーネル - smly’s notepad
NAIST の入学手続を終えた. 残りの期間はサーベイするぞーということで shimbo 先生の講義資料「リンク解析とその周辺の話題」を読んでいます. 一日目, 二日目の資料は PageRank, HITS, SALSA などの重要度尺度の紹介と, von Neumann Kernels と HITS の関係についてのお話が中心. これらを実装してみた. 後半に進むほど力尽きて記述が適当になってます:)PageRankポイントはランダム遷移行列による random walk では定常分布に収束しない (エルゴード性 (ergodic) を満たさない) という点. どうして満たさないかというと. sink (出次数のない節点) が存在するとき, 明らかに既約 (irreducible) でないのでエルゴード性を満たさない. 複数の強連結成分を持つケース => 周期性を持つと考えてよい? 周期
最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ？
最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた． 最小全域木について クラスカル法 プリム法 PKUの問題 クラスカル法による解答 プリム法による解答 メモリ使用量と実行時間の比較 最小全域木について まず，全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと．つまり，連結グラフから適当な辺を取り除いていき，閉路をもたない木の形にしたものが全域木となる．ここで，グラフの各辺に重みがある場合，重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という． 最小全域木を求めるアルゴリズムとしては以下の二つが有名である． クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲
オイラーの多面体定理の証明
オイラーの多面体定理の証明 幾何学の有名な定理に、オイラーの多面体定理があります。 ＜オイラーの多面体定理＞ 凸多面体において、頂点の数をV，面の数をF，辺の数をEとすると、 V+F-E=2 が成り立つ。 例えば立方体ならば、V=8,，F=6，E=12だから、V+F-E=2が成り立ちます。 グラフ理論を使って証明されます。 グラフがいまいちわからない人はこちらへ→グラフ理論をちょっと勉強する。 まずは、任意の多面体の１つの面をはずし、それを広げるような形で平面に押しつぶすと、頂点と辺によって平面グラフが出来上がります。なお、任意の多面体の表面は球面に同相なので、必ず、平面グラフを作ることができます。なお、平面グラフにおける面は、図形の外側（無限に広がっていくエリア）も面の１つと数えることにします。これにより、１つの面をはずしたとしても数字のつじつまが合うことになります。
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
Jitendra Malik's Home Page
Arthur J. Chick Professor of EECS University of California at Berkeley CA 94720-1776 Asst: Angie Abbatecola, angie@eecs.berkeley.edu Email: malik@berkeley.edu Prospective graduate students-you do not need to contact me. Follow this link instead. Office: Berkeley Way West Brief Bio Curriculum Vitae Publications List Academic Family Tree as of 2010 Teaching Spring 2015: CS 280 Computer Vision Resear
スペクトラルクラスタリングは次元圧縮しながらKmeansする手法 - 武蔵野日記
機械学習系のエントリを続けて書いてみる。クラスタリングについて知らない人は以下のエントリ読んでもちんぷんかんぷんだと思うので、クラスタリングという概念については知っているものとする。 それで、今日はスペクトラルクラスタリングの話。自然言語処理以外でも利用されているが、これはグラフのスペクトルに基づくクラスタリングの手法で、半教師あり学習への拡張がやりやすいのが利点。なにをするかというとクラスタリングをグラフの分割問題(疎であるエッジをカット)に帰着して解く手法で、どういうふうに分割するかによって Normalized cut (Ncut) とか Min-max cut (Mcut) とかいろいろある。 完全にグラフが分割できる場合はこれでめでたしめでたしなのだが、実世界のグラフはそんな簡単に切れないことが往々にしてある。それで近似してこのグラフ分割問題を解くのだが、Normalized c
Rで学ぶクラスタ解析
第２章 クラスタリング入門 2.1 クラスタリングとは 2.2 クラスタリング手法の概要 2.3 クラスタリング結果の評価
点と線の部屋
平成１６年２月２３日 第一部 第五十四章 「アフィン平面と射影平面」 新規公開 平成１６年１月４日 第一部 第五十二章 第三節 「4次のアフィン平面」 追加 第一部 第五十三章 「麻雀の組合せの問題（ラテン方陣とアフィン平面）」 新規公開 第二部 第三十三章 「有限体クラスの拡張」 新規公開 平成１５年２月１１日 第二部 第三十二章 「有限体クラス」 新規公開 平成１５年２月３日 第一部 第五十二章 「体とアフィン平面」 新規公開 平成１５年１月１３日 第一部 第三十一章 第三節を不備訂正のため大幅に変更し、また一部を第四節に分離独立させた 平成１４年１１月３日 第一部 第五十一章 「再構成問題 その１」 新規公開 平成１４年７月１５日 第一部 第五十章 「最短経路問題」 新規公開 平成１４年５月１３日 第一部 第四十九章 「弦グラフ その１」 新規公開 平成１４年２月４日
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://ocw.hokudai.ac.jp/Course/Faculty/Engineering/GraphTheory/2007/index.php?lang=ja&page=materials
[PDF] 卒業論文 ポケモンつなげるもん♪ ―最長しりとり問題を整数計画法で解く― 愛知教育大学 初等教育教員養成課程 数学選修 s2070268 佐藤 一生
はてなブログ | 無料ブログを作成しよう
Minimum Linear Arrangement - algorithm, implementation, and experiments
SpectralClustering - PukiWiki