Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs

Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs

A maximal clique (<inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>) is a complete subgraph satisfying that no other cliques can take it as their proper subgraph. Given an uncertain graph, the <inline-formula> <tex-math notatio...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Jing Bai, Junfeng Zhou, Ming Du, Peng Zhong
Formato: article
Lenguaje:EN
Publicado: IEEE 2021
Materias:
Uncertain graph
maximal clique
<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">top-K</italic>
Electrical engineering. Electronics. Nuclear engineering
TK1-9971
Acceso en línea:https://doaj.org/article/b554445da06c4e41a07fa51d01a42232
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
id oai:doaj.org-article:b554445da06c4e41a07fa51d01a42232
record_format dspace
institution DOAJ
collection DOAJ
language EN
topic Uncertain graph
maximal clique
<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">top-K</italic>
maximal clique
Electrical engineering. Electronics. Nuclear engineering
TK1-9971
spellingShingle Uncertain graph
maximal clique
<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">top-K</italic>
maximal clique
Electrical engineering. Electronics. Nuclear engineering
TK1-9971
Jing Bai
Junfeng Zhou
Ming Du
Peng Zhong
Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs
description A maximal clique (<inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>) is a complete subgraph satisfying that no other cliques can take it as their proper subgraph. Given an uncertain graph, the <inline-formula> <tex-math notation="LaTeX">$top\text{-}K\,\,{MC}\text{s}$ </tex-math></inline-formula> enumeration problem studies how to return <inline-formula> <tex-math notation="LaTeX">$k {MC}\text{s}$ </tex-math></inline-formula> with the highest rank value. Existing algorithms rank <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> according to their probabilities, thus usually return <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> with higher probabilities but less number of vertices, and fail to return large <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> that convey more useful information. Considering this problem, this paper studies the problem of enumerating <inline-formula> <tex-math notation="LaTeX">$top\text{-}K\,\,{MC}\text{s}$ </tex-math></inline-formula>. Our approach returns <inline-formula> <tex-math notation="LaTeX">$k {MC}\text{s}$ </tex-math></inline-formula> with the most number of vertices satisfying that their probabilities <inline-formula> <tex-math notation="LaTeX">$\geq \alpha $ </tex-math></inline-formula>, where each <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> is called an <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>, and computing <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> largest <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> is called as <inline-formula> <tex-math notation="LaTeX">$(k,\alpha)$ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula>. We propose an efficient <inline-formula> <tex-math notation="LaTeX">$(k,\alpha)$ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> enumeration algorithm, <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC$ </tex-math></inline-formula>, which works in three steps, including partition, enumeration and verification. Here, partition means that we compute the set <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula> of all <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> without considering the probability information, as if the graph is partitioned into a set of subgraphs. Enumeration means that we compute <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> from each <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>. As each such subgraph is an <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>, the cost of computing common neighbors for finding <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> can be reduced. Verification means that we need to verify whether an <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> is a subgraph of another <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>. If not, it is an <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>; otherwise, it is a useless <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> and should be removed. We further propose an optimized algorithm <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC+$ </tex-math></inline-formula> to reduce both time and space by merging the above three steps into a whole step. The experimental results on real datasets show that both <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC+$ </tex-math></inline-formula> can return <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> largest <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> efficiently.
format article
author Jing Bai
Junfeng Zhou
Ming Du
Peng Zhong
author_facet Jing Bai
Junfeng Zhou
Ming Du
Peng Zhong
author_sort Jing Bai
title Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs
title_short Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs
title_full Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs
title_fullStr Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs
title_full_unstemmed Efficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs
title_sort efficient <italic>(k, &#x03b1;)</italic>-maximal-cliques enumeration over uncertain graphs
publisher IEEE
publishDate 2021
url https://doaj.org/article/b554445da06c4e41a07fa51d01a42232
work_keys_str_mv AT jingbai efficientitalickx03b1italicmaximalcliquesenumerationoveruncertaingraphs
AT junfengzhou efficientitalickx03b1italicmaximalcliquesenumerationoveruncertaingraphs
AT mingdu efficientitalickx03b1italicmaximalcliquesenumerationoveruncertaingraphs
AT pengzhong efficientitalickx03b1italicmaximalcliquesenumerationoveruncertaingraphs
_version_ 1718425246271275008
spelling oai:doaj.org-article:b554445da06c4e41a07fa51d01a422322021-11-18T00:03:24ZEfficient <italic>(k, &#x03B1;)</italic>-Maximal-Cliques Enumeration Over Uncertain Graphs2169-353610.1109/ACCESS.2021.3125198https://doaj.org/article/b554445da06c4e41a07fa51d01a422322021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9599685/https://doaj.org/toc/2169-3536A maximal clique (<inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>) is a complete subgraph satisfying that no other cliques can take it as their proper subgraph. Given an uncertain graph, the <inline-formula> <tex-math notation="LaTeX">$top\text{-}K\,\,{MC}\text{s}$ </tex-math></inline-formula> enumeration problem studies how to return <inline-formula> <tex-math notation="LaTeX">$k {MC}\text{s}$ </tex-math></inline-formula> with the highest rank value. Existing algorithms rank <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> according to their probabilities, thus usually return <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> with higher probabilities but less number of vertices, and fail to return large <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> that convey more useful information. Considering this problem, this paper studies the problem of enumerating <inline-formula> <tex-math notation="LaTeX">$top\text{-}K\,\,{MC}\text{s}$ </tex-math></inline-formula>. Our approach returns <inline-formula> <tex-math notation="LaTeX">$k {MC}\text{s}$ </tex-math></inline-formula> with the most number of vertices satisfying that their probabilities <inline-formula> <tex-math notation="LaTeX">$\geq \alpha $ </tex-math></inline-formula>, where each <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> is called an <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>, and computing <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> largest <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> is called as <inline-formula> <tex-math notation="LaTeX">$(k,\alpha)$ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula>. We propose an efficient <inline-formula> <tex-math notation="LaTeX">$(k,\alpha)$ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> enumeration algorithm, <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC$ </tex-math></inline-formula>, which works in three steps, including partition, enumeration and verification. Here, partition means that we compute the set <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula> of all <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> without considering the probability information, as if the graph is partitioned into a set of subgraphs. Enumeration means that we compute <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> from each <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}$ </tex-math></inline-formula>. As each such subgraph is an <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>, the cost of computing common neighbors for finding <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> can be reduced. Verification means that we need to verify whether an <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> is a subgraph of another <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>. If not, it is an <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula>; otherwise, it is a useless <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}$ </tex-math></inline-formula> and should be removed. We further propose an optimized algorithm <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC+$ </tex-math></inline-formula> to reduce both time and space by merging the above three steps into a whole step. The experimental results on real datasets show that both <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$Top\text{-}KMC+$ </tex-math></inline-formula> can return <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> largest <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>- <inline-formula> <tex-math notation="LaTeX">${MC}\text{s}$ </tex-math></inline-formula> efficiently.Jing BaiJunfeng ZhouMing DuPeng ZhongIEEEarticleUncertain graphmaximal clique<italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">top-K</italic>maximal cliqueElectrical engineering. Electronics. Nuclear engineeringTK1-9971ENIEEE Access, Vol 9, Pp 149338-149348 (2021)

Ejemplares similares