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. 434-458, 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 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.
|
Submitted: January 2019.
Reviewed: April 2019.
Revised: June 2019.
Accepted: July 2019.
Final: July 2019.
Published: July 2019.
Communicated by
Seok-Hee Hong
|
Journal Supporters
|