TY - JOUR
T1 - Computing the p-Spectral Radii of Uniform Hypergraphs with Applications
AU - Chang, Jingya
AU - Ding, Weiyang
AU - Qi, Liqun
AU - Yan, Hong
PY - 2018/4
Y1 - 2018/4
N2 - The p-spectral radius of a uniform hypergraph covers many important concepts, such as Lagrangian and spectral radius of the hypergraph, and is crucial for solving spectral extremal problems of hypergraphs. In this paper, we establish a spherically constrained maximization model and propose a first-order conjugate gradient algorithm to compute the p-spectral radius of a uniform hypergraph (CSRH). By the semialgebraic nature of the adjacency tensor of a uniform hypergraph, CSRH is globally convergent and obtains the global maximizer with a high probability. When computing the spectral radius of the adjacency tensor of a uniform hypergraph, CSRH outperforms existing approaches. Furthermore, CSRH is competent to calculate the p-spectral radius of a hypergraph with millions of vertices and to approximate the Lagrangian of a hypergraph. Finally, we show that the CSRH method is capable of ranking real-world data set based on solutions generated by the p-spectral radius model.
AB - The p-spectral radius of a uniform hypergraph covers many important concepts, such as Lagrangian and spectral radius of the hypergraph, and is crucial for solving spectral extremal problems of hypergraphs. In this paper, we establish a spherically constrained maximization model and propose a first-order conjugate gradient algorithm to compute the p-spectral radius of a uniform hypergraph (CSRH). By the semialgebraic nature of the adjacency tensor of a uniform hypergraph, CSRH is globally convergent and obtains the global maximizer with a high probability. When computing the spectral radius of the adjacency tensor of a uniform hypergraph, CSRH outperforms existing approaches. Furthermore, CSRH is competent to calculate the p-spectral radius of a hypergraph with millions of vertices and to approximate the Lagrangian of a hypergraph. Finally, we show that the CSRH method is capable of ranking real-world data set based on solutions generated by the p-spectral radius model.
KW - Eigenvalue
KW - Hypergraph
KW - Large scale tensor
KW - Network analysis
KW - p-spectral radius
KW - Pagerank
UR - http://www.scopus.com/inward/record.url?scp=85026846146&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85026846146&origin=recordpage
U2 - 10.1007/s10915-017-0520-x
DO - 10.1007/s10915-017-0520-x
M3 - RGC 21 - Publication in refereed journal
VL - 75
SP - 1
EP - 25
JO - Journal of Scientific Computing
JF - Journal of Scientific Computing
SN - 0885-7474
IS - 1
ER -