TY - JOUR
T1 - The analytic connectivity in uniform hypergraphs
T2 - Properties and computation
AU - Cui, Chunfeng
AU - Luo, Ziyan
AU - Qi, Liqun
AU - Yan, Hong
PY - 2023/3
Y1 - 2023/3
N2 - The analytic connectivity (AC), defined via solving a series of constrained polynomial optimization problems, serves as a measure of connectivity in hypergraphs. How to compute such a quantity efficiently is important in practice and of theoretical challenge as well due to the non-convex and combinatorial features in its definition. In this article, we first perform a careful analysis of several widely used structured hypergraphs in terms of their properties and heuristic upper bounds of ACs. We then present an affine-scaling method to compute some upper bounds of ACs for uniform hypergraphs. To testify the tightness of the obtained upper bounds, two possible approaches via the Pólya theorem and semidefinite programming respectively are also proposed to verify the lower bounds generated by the obtained upper bounds minus a small gap. Numerical experiments on synthetic datasets are reported to demonstrate the efficiency of our proposed method. Further, we apply our method in hypergraphs constructed from social networks and text analysis to detect the network connectivity and rank the keywords, respectively.
AB - The analytic connectivity (AC), defined via solving a series of constrained polynomial optimization problems, serves as a measure of connectivity in hypergraphs. How to compute such a quantity efficiently is important in practice and of theoretical challenge as well due to the non-convex and combinatorial features in its definition. In this article, we first perform a careful analysis of several widely used structured hypergraphs in terms of their properties and heuristic upper bounds of ACs. We then present an affine-scaling method to compute some upper bounds of ACs for uniform hypergraphs. To testify the tightness of the obtained upper bounds, two possible approaches via the Pólya theorem and semidefinite programming respectively are also proposed to verify the lower bounds generated by the obtained upper bounds minus a small gap. Numerical experiments on synthetic datasets are reported to demonstrate the efficiency of our proposed method. Further, we apply our method in hypergraphs constructed from social networks and text analysis to detect the network connectivity and rank the keywords, respectively.
KW - affine-scaling
KW - analytic connectivity
KW - Laplacian tensor
KW - uniform hypergraph
UR - http://www.scopus.com/inward/record.url?scp=85138395727&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85138395727&origin=recordpage
U2 - 10.1002/nla.2468
DO - 10.1002/nla.2468
M3 - RGC 21 - Publication in refereed journal
VL - 30
JO - Numerical Linear Algebra with Applications
JF - Numerical Linear Algebra with Applications
SN - 1070-5325
IS - 2
M1 - e2468
ER -