講演 1： 見村 万佐人（東北大学） Masato Mimura (Tohoku University)
タイトル：「エクスパンダーと有限群と無限群」
概要：有限群とその生成系の組の列のケイリーグラフからエクスパンダー族を構成する手法は有名である。本講演では、有限群の列を固定し生成系の列を変更したときに、できる有限ケイリーグラフの列がどの程度変わりうるかを述べる。その際、有限群の極限として現われる無限群が効いてくる。
Title: “Expanders, finite groups and infinite groups”
Abstract: One well-known way of constructing expanders is to take Cayley graphs of a certain
sequence of pairs of finite groups and generating sets. In this talk, I will discuss how changing
generating sets affects the resulting Cayley graphs for a fixed sequence of finite graphs. Here, the"limit groups" of finite marked groups play a key role.

講演 2:

清水 伸高 (東京工業大学)

Nobutaka Shimizu (Tokyo Institute of Technology)

タイトル: 「エクスパンダーグラフと脱乱択化」
概要:

ランダムネスを用いると様々な問題に対して効率的なアルゴリズムが設計できることが知られている. 例えば グラフ到達性判定, 多項式同一性判定, 行列積判定, 数え上げの近似などは効率的な乱択アルゴリズムが知られている. 一方で, これらの問題を同等の時間で決定的に解けるかどうかはよく分かっていない. このように, 乱択アルゴリズムを決定的なアルゴリズムに変換する手法は脱乱択化と呼ばれ, ランダムネスが本質的に必要かどうかという理論計算機科学の基本的な問いと密接に関連するため盛んに研究されている. 本発表ではエクスパンダーグラフの理論計算機科学への応用の一つとして脱乱択化に焦点を当てて紹介していく.
Title: “Derandomization and Expander Graphs”
Abstract: We can design efficient randomized algorithms for various problems including graphreachability, polynomial identity testing, checking matrix multiplication, and approximate counting.
On the other hand, it is not known whether there exists a deterministic algorithm with the samerunning time for them. One possible way to obtain such a deterministic algorithm is to eliminate
the randomness of randomized algorithms. This transformation is called derandomization, which
has been a fundamental topic in theoretical computer science. In this talk, as an application of
expanders in theoretical computer science, we introduce the technique of derandomization based onexpanders.

講演 3:

田村 光太郎 (野村総合研究所) Kotaro Tamura (Nomura Research Institute)

タイトル： 「社会データ分析におけるグラフアルゴリズムの適用」
概要： 経済社会データにおけるトランザクションデータの解析が増えている。我々は 100 万社の企業間取引データを大規模なグラフ構造データとみなすことで、その構造を数値解析するとともにモデル化した。
グラフの数値解析では、グラフが疎性であるときにグラフアルゴリズムを効率的に適用できる。たとえば、隣接行列の固有解析は、グラフの疎性を利用することで効率的に行えて、ノードのランキングの計算に利用されている。また、関節点や橋のような連結性に重要なノードやエッジを抽出するなど、グラフの特徴点の抽出にも活かされる。これら解析の結果から、企業間の取引構造は、グラフ上において非常に短距離であることや、モチーフ構造に偏りがあること、取引数分布がべき分布に従うことを得ている。
また、我々は、企業間の取引を介して流れる財やサービスの流れを非線形の輸送方程式としてモデル化した。この輸送方程式は定常解の性質として、非線形性から来る解の不安定性がグラフ構造に起因して発現する。グラフの線形化や不安定性を遷移行列から評価するための固有解析を行った。
本講演では、解析に用いたグラフアルゴリズムの利用とその特徴の紹介を含める形で行う。
Title： “Application of Graph Algorithms in Social Data Analysis”
Abstract： Transactional data related to economic and social activities are increasingly beinganalyzed. We have numerically analyzed data of one million Japanese firms' transaction aslarge-scale graph-structured data and modeled its money flow as a transport system.
In numerical analysis of graph data, algorithms can be applied efficiently if the graph is sparse. For
example, we can apply the eigenanalysis of adjacency matrices efficiently by taking advantage ofthe sparsity of the graph, and it has been used to compute node rankings or some centrality
analysis. We can also use the sparsity to extract feature points of the graph, such as articulation
points and edges. These analysis brought us the results that the network is small-world network,
which means distance between firms is short, that the motif structure is significantly biased
comparing to the random graph, and that the distribution of the number of transactions follows apower distribution.
Also, we model a nonlinear transport equation defined on the inter-firm transaction network,
based on the real data of the money-flow between firms. The steady-state solution of this transport
equation emerges instability depending on the nonlinear parameter and graph structure. We
evaluated the linear stability of the solution by performing the eigenanalysis to the transition
matrix.
This presentation will take the form of including an introduction to the graph algorithm used inthe analysis