Information Limits for Community Detection in Hypergraph with Label Information

In network data mining, community detection refers to the problem of partitioning the nodes of a network into clusters (communities). This is equivalent to identifying the cluster label of each node. A label estimator is said to be an exact recovery of the true labels (communities) if it coincides w...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Xiaofeng Zhao, Wei Zhao, Mingao Yuan
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	community detection uniform hypergraph label information exact recovery Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/5784e698c94c4263b71c7c06a7aa7e56
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5784e698c94c4263b71c7c06a7aa7e56
record_format	dspace
spelling	oai:doaj.org-article:5784e698c94c4263b71c7c06a7aa7e562021-11-25T19:06:25ZInformation Limits for Community Detection in Hypergraph with Label Information10.3390/sym131120602073-8994https://doaj.org/article/5784e698c94c4263b71c7c06a7aa7e562021-11-01T00:00:00Zhttps://www.mdpi.com/2073-8994/13/11/2060https://doaj.org/toc/2073-8994In network data mining, community detection refers to the problem of partitioning the nodes of a network into clusters (communities). This is equivalent to identifying the cluster label of each node. A label estimator is said to be an exact recovery of the true labels (communities) if it coincides with the true labels with a probability convergent to one. In this work, we consider the effect of label information on the exact recovery of communities in an <i>m</i>-uniform Hypergraph Stochastic Block Model (HSBM). We investigate two scenarios of label information: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula> a noisy label for each node is observed independently, with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>−</mo><msub><mi>α</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> as the probability that the noisy label will match the true label; <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula> the true label of each node is observed independently, with the probability of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>−</mo><msub><mi>α</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>. We derive sharp boundaries for exact recovery under both scenarios from an information-theoretical point of view. The label information improves the sharp detection boundary if and only if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>n</mi></msub><mo>=</mo><msup><mi>n</mi><mrow><mo>−</mo><mi>β</mi><mo>+</mo><mi>o</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow></msup></mrow></semantics></math></inline-formula> for a constant <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>β</mi><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula>.Xiaofeng ZhaoWei ZhaoMingao YuanMDPI AGarticlecommunity detectionuniform hypergraphlabel informationexact recoveryMathematicsQA1-939ENSymmetry, Vol 13, Iss 2060, p 2060 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	community detection uniform hypergraph label information exact recovery Mathematics QA1-939
spellingShingle	community detection uniform hypergraph label information exact recovery Mathematics QA1-939 Xiaofeng Zhao Wei Zhao Mingao Yuan Information Limits for Community Detection in Hypergraph with Label Information
description	In network data mining, community detection refers to the problem of partitioning the nodes of a network into clusters (communities). This is equivalent to identifying the cluster label of each node. A label estimator is said to be an exact recovery of the true labels (communities) if it coincides with the true labels with a probability convergent to one. In this work, we consider the effect of label information on the exact recovery of communities in an <i>m</i>-uniform Hypergraph Stochastic Block Model (HSBM). We investigate two scenarios of label information: <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula> a noisy label for each node is observed independently, with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>−</mo><msub><mi>α</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula> as the probability that the noisy label will match the true label; <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></semantics></math></inline-formula> the true label of each node is observed independently, with the probability of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>−</mo><msub><mi>α</mi><mi>n</mi></msub></mrow></semantics></math></inline-formula>. We derive sharp boundaries for exact recovery under both scenarios from an information-theoretical point of view. The label information improves the sharp detection boundary if and only if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>α</mi><mi>n</mi></msub><mo>=</mo><msup><mi>n</mi><mrow><mo>−</mo><mi>β</mi><mo>+</mo><mi>o</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow></msup></mrow></semantics></math></inline-formula> for a constant <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>β</mi><mo>></mo><mn>0</mn></mrow></semantics></math></inline-formula>.
format	article
author	Xiaofeng Zhao Wei Zhao Mingao Yuan
author_facet	Xiaofeng Zhao Wei Zhao Mingao Yuan
author_sort	Xiaofeng Zhao
title	Information Limits for Community Detection in Hypergraph with Label Information
title_short	Information Limits for Community Detection in Hypergraph with Label Information
title_full	Information Limits for Community Detection in Hypergraph with Label Information
title_fullStr	Information Limits for Community Detection in Hypergraph with Label Information
title_full_unstemmed	Information Limits for Community Detection in Hypergraph with Label Information
title_sort	information limits for community detection in hypergraph with label information
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/5784e698c94c4263b71c7c06a7aa7e56
work_keys_str_mv	AT xiaofengzhao informationlimitsforcommunitydetectioninhypergraphwithlabelinformation AT weizhao informationlimitsforcommunitydetectioninhypergraphwithlabelinformation AT mingaoyuan informationlimitsforcommunitydetectioninhypergraphwithlabelinformation
_version_	1718410278667812864

Information Limits for Community Detection in Hypergraph with Label Information

Ejemplares similares