Computing the p-Spectral Radii of Uniform Hypergraphs with Applications

Jingya Chang, Weiyang DING, Liqun Qi*, Hong Yan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

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.

Original languageEnglish
JournalJournal of Scientific Computing
Volume75
Issue number1
DOIs
Publication statusPublished - 1 Apr 2018

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Engineering(all)
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Eigenvalue
  • Hypergraph
  • Large scale tensor
  • Network analysis
  • p-spectral radius
  • Pagerank

Fingerprint

Dive into the research topics of 'Computing the p-Spectral Radii of Uniform Hypergraphs with Applications'. Together they form a unique fingerprint.

Cite this