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

Kazuya Haraguchi ; Yusuke Momoi ; Aleksandar Shurbevski ; Hiroshi Nagamochi

Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 434-458.

Résumé

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.

Détail

DOI : 10.7155/jgaa.00497