On the properties of Gromov matrices and their applications in network inference

The spanning tree heuristic is a commonly adopted procedure in network inference and estimation. It allows one to generalize an inference method developed for trees, which is usually based on a statistically rigorous approach, to a heuristic procedure for general graphs by (usually randomly) choosin...

Full description

Saved in:
Bibliographic Details
Main Authors: Ji, Feng, Tang, Wenchang, Tay, Wee Peng
Other Authors: School of Electrical and Electronic Engineering
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/145422
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:The spanning tree heuristic is a commonly adopted procedure in network inference and estimation. It allows one to generalize an inference method developed for trees, which is usually based on a statistically rigorous approach, to a heuristic procedure for general graphs by (usually randomly) choosing a spanning tree in the graph to apply the approach developed for trees. However, there are an intractable number of spanning trees in a dense graph. In this paper, we represent a weighted tree with a matrix, which we call a Gromov matrix. We propose a method that constructs a family of Gromov matrices using convex combinations, which can be used for inference and estimation instead of a randomly selected spanning tree. This procedure increases the size of the candidate set and hence enhances the performance of the classical spanning tree heuristic. On the other hand, our new scheme is based on simple algebraic constructions using matrices, and hence is still computationally tractable. We discuss some applications on network inference and estimation to demonstrate the usefulness of the proposed method.