COOMA: A Components Overlaid Mining Algorithm for Enumerating Connected Subgraphs with Common Itemsets
Kazuya Haraguchi, Yusuke Momoi, Aleksandar Shurbevski, and Hiroshi Nagamochi
Vol. 23, no. 2, pp. 434-458, 2019. Regular paper.
Abstract 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,\sigma)$ that consists of a graph $G=(V,E)$, an item set $I$, and a function $\sigma:V\rightarrow 2^{I}$. For $X\subseteq V$, we define $A_\sigma(X)\triangleq\bigcap_{v\in X}\sigma(v)$. Note that, for $X,Y\subseteq V$, $X\subseteq Y$ implies that $A_\sigma(X)\supseteq A_\sigma(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 $v\in V\setminus X$, $G[X\cup\{v\}]$ is disconnected or $ A_\sigma(X\cup\{v\})\subsetneq A_\sigma(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.
Submitted: January 2019.
Reviewed: April 2019.
Revised: June 2019.
Accepted: July 2019.
Final: July 2019.
Published: July 2019.
Communicated by Seok-Hee Hong
article (PDF)