研究概要

一般的に？，人間関係であれば，集合内の他の要素との共起関係などを使って人間間の類似度の計算を行う．本文では，２種類の要素集合を設定し，一方の集合に属する要素の評価を他方の集合を用いて行い，その値を用いて要素間の類似度を計算する．２種類の要素集合から構成されるネットワークは，２部グラフと呼ばれ，マッチング問題などにて利用される．

本文では，この２部グラフを用いたマイニングに関する研究を列挙し，論文の方向性などを概観する．

bipartite graph analysis

Mining Social Networks in 19th Century American Novels

Xin Xiang

Chicago Colloquium on Digital Humanities and Computer Science (2006),

同じchapterに登場する人物同士を近い関係にあると捉える．Coburn, Caudrado, Schine らが始めにグラフベースでの分析を提唱したが，それらとは matrix-based approach をとる点で異る．matrix-based とは，チャプタごとにcharacterが登場する回数を数え挙げて，一定の閾値で 0, 1 に置き換え，同じ章で1となっている character同士には tie があるものとすることの様子．それで，２部グラフとかをプロットしているが，そのネットワーク図をみて勝手に理解するというものらしい．

Google

Max-Flow コミュニティグラフとその特徴分析

今藤紀子, 喜連川優

DBSJ Letter(2004), pp.69--72

HIT系手法に比べてコミュニティのトピックの抽出が詳細になる傾向のある Max-Flow手法を利用したコミュニティグラフを作成するとでどのような分析が可能であるかを考察した論文？
先にMax-Flowコミュニティとは何かを知る必要があるみたい．

Google

コミュニティーの発見

Trawling the Web for emerging Cybercommunities,

Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins, P.Krishna Reddy, Masaru Kitsuregawa

Journal of American Society for Information Science(1973), pp.265--269

citation network の話っぽい

Google

Trawling the Web for emerging Cyber communities

Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins, P.Krishna Reddy, Masaru Kitsuregawa

WWW Conference(1999),

CBG(Complete Bipartite Graph) abstration から comnunity phenomena がキャプチャできる? でも，大きなコミュニティは発見できないらしい．

Google

2部グラフ抽出に基づく関連コミュニティ発見の試み

P.Krishna Reddy, 喜連川優

DBWS(2001),

Web Page のリンク構造を利用して，同じ興味をもつ作者が作成したページは，同じようなリンクをいくつかは持っているであろうという考えのもと，それを２部グラフのアブストラクションを通してしることを目的としている．
本論文では，コミュニティの発見手法としてcocitation relationship の緩和法を用いている．具体的には，co-cite は互いに同じページへのリンクを持っているページ同士の意味の様子．relax_cocite は，推移も含める．

喜連川研究室の発表論文(2001)

An Approach to Relate the Web Communities Through Bipartite Graphs

P.Krishna Reddy, Masaru Kitsuregawa

International Conference on Web Information Systems Engineering(2001),

喜連川研究室の発表論文(2001)

同姓同名人物分離問題

要素の同定を行うのに，その要素の属性となる要素との共起関係を利用していることから，ある意味２部グラフを利用しているといえないこともない．