COOMA: A Components Overlaid Mining Algorithm for Enumerating Connected Subgraphs with Common Itemsets

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.