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 problemof 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 connectorif (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 boundedwith respect to the input and output size.We show the efficiency of COOMAin comparison with COPINE [Sese et al., 2010],a depth-first-search based algorithm.