Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00497
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. 434458, 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 totalpolynomial 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 depthfirstsearch based algorithm.

Submitted: January 2019.
Reviewed: April 2019.
Revised: June 2019.
Accepted: July 2019.
Final: July 2019.
Published: July 2019.
Communicated by
SeokHee Hong

Journal Supporters
