Home
Lectures
On Sampling and Reconstruction of Large-Scale Networks using Graph Geodesics, Matrix Completion and Machine Learning

On Sampling and Reconstruction of Large-Scale Networks using Graph Geodesics, Matrix Completion and Machine Learning

Speaker: Anura Jayasumana – Fort Collins, CO, United States
Topic(s): Information Systems, Search, Information Retrieval, Database Systems, Data Mining, Data Science

Abstract

Extracting connectivity information in massive social networks is important for many applications. We present a method to extract the network topology from a small sample of geodesics distances without the need for exhaustive measurements. Tolerating missing data is also necessary when certain nodes participate in message passing among the nodes, but are not accessible for direct measurements. The concept of construction set of a graph is defined, together with the associated link dimension, that specifies the minimum set of landmarks for loss-less reconstruction of a network. An anchor-based sampling approach is proposed and compared with random sampling for a wide range of networks. We demonstrate, that many real-world networks have hop-distance matrices that are low-rank, thus allowing the formulation of the problem as a low-rank matrix completion.

About this Lecture

Number of Slides: 40 - 50
Duration: 50 minutes
Languages Available: English
Last Updated:

Request this Lecture

To request this particular lecture, please complete this online form.

Request a Tour

To request a tour with this speaker, please complete this online form.

All requests will be sent to ACM headquarters for review.