Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2018-002 (December 27, 2018)
COOMA: A Components Overlaid Mining Algorithm for Enumerating Connected Subgraphs with Common Itemsets
by Kazuya Haraguchi, Yusuke Momoi, Aleksandar Shurbevski, and Hiroshi Nagamochi
In the present paper, we consider a graph mining problem of enumerating what we call connectors.
Suppose that we are given a data set (G,I,s) that consists of a graph G=(V,E), an item set I,
and a function s from V to the family of all subsets of I.
For each subset X of V, we define A(X) to be the set of items common to s(v) for all vertices v in X.
A vertex subset X is called a connector if (i) the subgraph G[X] induced from G by X is connected;
and (ii) for any proper super set Y of X, G[Y] is disconnected or |A(Y)|<|A(X)|.
To enumerate all connectors, we propose a novel algorithm named COOMA (components overlaid mining algorithm).
Interestingly, COOMA is a total-polynomial time algorithm,
i.e., the running time is polynomially bounded with respect to the input and output size.
We show the efficiency of COOMA in comparison with COPINE [Sese et al., 2010], a depth-first-search based algorithm.