On the Properties of Gromov Matrices and their Applications in Network Inference
arXiv:1810.05333 · doi:10.1109/TSP.2019.2908133
Abstract
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.
References in corpus (14)
- Epidemic spreading in scale-free networks
- The Dynamics of Viral Marketing
- Immunization of complex networks
- Halting viruses in scale-free networks
- Locating the Source of Diffusion in Large-Scale Networks
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- Rooting out the Rumor Culprit from Suspects
- How to Identify an Infection Source with Limited Observations
- Locating the source of diffusion in complex networks by time-reversal backward spreading
- Robust Decentralized Detection and Social Learning in Tandem Networks
- Infection Spreading and Source Identification: A Hide and Seek Game
- Whose Opinion to follow in Multihypothesis Social Learning? A Large Deviations Perspective
- On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks
- On Distributed Algorithms for Cost-Efficient Data Center Placement in Cloud Computing
Cited by in corpus (5)
- Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
- Signal processing on simplicial complexes
- Graph Signal Processing over a Probability Space of Shift Operators
- Signal processing with a distribution of graph operators
- Social Bubbles and Superspreaders: Source Identification for Contagion Processes on Hypertrees