グラフの木分割を用いたコミュニティ発見手法

概要

論文の詳細を見る
A number of researches in graph mining have been devoted in the discovery of communities. In this report, we study a query-dependent variant of the community-detection problem based on the tree decomposition methodology. In the tree decomposition of a graph, each tree node is labeled with a set of graph vertices, and each clique in the graph is always contained by a tree node. Also, tree nodes containing an identical graph vertex are always connected. Using such properties, we discuss an algorithm that finds a community that contains a given query node. By pre-computing tree decomposition, the task of finding a community can be reduced. We show the experimental results on community detection over real data sets.
2011-10-27