Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/79589
Title: Computation of problems related with tensors arising from hypergraphs
Authors: Chang, Jingya
Advisors: Qi, Liqun (AMA)
Li, Xun (AMA)
Keywords: Hypergraphs
Calculus of tensors
Issue Date: 2018
Publisher: The Hong Kong Polytechnic University
Abstract: Because the edge of a hypergraph can join more than two vertices, hypergraphs are much more powerful than graphs in storing multi-dimensional information, modelling complex relationship in real world. Tensors arising from a hypergraph, such as adjacency tensor, Laplacian tensor and signless Laplacian tensor, provide us a fundamental instrument to analyse the structure of a hypergraph, enrich the hypergraph theory, resolve the application problems in hypergraph. Eigenvalues of tensors associated with hypergraphs are the core objects in spectral hypergraph theory. Although many achievements have been made in computation of tensor eigenvalues, the problem of computing eigenvalues of tensors arising from hypergraphs has not been completely settled yet, especially for large scale hypergraphs. By taking advantage of the sparsity of these tensors, we avoid saving the tensor information and propose a fast computational framework for the most time consuming operations. For the eigenvalue problem, we introduce a first-order optimization method called CEST (Computing Eigenvalues of large Sparse Tensors arising from hypergraphs) to solve it. It is proved that the sequence of function values and iterate points produced by the CEST method converge to the extremal eigenvalue and its associated eigenvector with a high probability. The CEST method is capable of calculating eigenvalues of tensors from hypergraphs with millions of vertices. The p-spectral radius of a hypergraph is a concept that covers many important invariants and connected with Turan-type problems in the extremal hypergraph theory. The existing results about p-spectral radius problem are mainly based on theoretical analysis. Upper bounds or lower bounds of p-spectral radius of several structured hypergraphs are given, and as far as we know, there is not any computational method designed particularly for the p-spectral radius problem. By using adjacency tensors, we reformulate the original p-spectral radius problem to a spherical constraint maximization model and propose a method, named CSRH (Computing p-Spectral Radii of Hypergraphs), to solve it. The CSRH method can calculate the p-spectral radius when p is greater than 1, and estimate the 1-spectral radii of uniform hypergraphs with high accuracy. As an application, we link the p-spectral radius model to data rank problems and successfully apply the CSRH method to rank 10305 authors according to their publication information from real life data set.
Description: ix, 102 pages : color illustrations
PolyU Library Call No.: [THS] LG51 .H577P AMA 2018 Chang
URI: http://hdl.handle.net/10397/79589
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
991022165758403411_link.htmFor PolyU Users167 BHTMLView/Open
991022165758403411_pira.pdfFor All Users (Non-printable)1.55 MBAdobe PDFView/Open
Show full item record
PIRA download icon_1.1View/Download Contents

Page view(s)

6
Citations as of Jan 14, 2019

Download(s)

4
Citations as of Jan 14, 2019

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.