COOMA: A Components Overlaid Mining Algorithm for Enumerating Connected Subgraphs with Common Itemsets - Haraguchi, Kazuya; Momoi, Yusuke; Shurbevski, Aleksandar; Nagamochi, Hiroshi (Journal of Graph Algorithms and Applications, 2019)
In the present paper, we consider the graph mining problem of enumerating what we call connectors. Suppose that we are given a data set (G,I,σ) that consists of a graph G=(V,E), an item set I, and a function σ:V→ 2^I. For XV, we define A_σ(X) riangleq_vXσ(v). Note that, for X,YV, XY implies that A_σ(X)A_σ(Y). 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 vVX, G[X{v}] is disconnected or A_σ(X{v})A_σ(X). To enumerate all connectors, we propose a novel algorithm named COOMA (components overlaid mining algorithm). The algorithm mines connectors by "overlaying" an already discovered connector on a certain subgraph of G iteratively. By overlaying, we mean taking an intersection between the connector and connected components of a certain induced subgraph. 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.