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

摘要

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:Vightarrow 2^{I}$. For $Xsubseteq V$, we define $A_sigma(X)riangleqigcap_{vin X}sigma(v)$. Note that, for $X,Ysubseteq V$, $Xsubseteq 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 $vin Vsetminus X$, $G[Xcup{v}]$ is disconnected or $ A_sigma(Xcup{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.