On Sampling and Reconstruction of Large-Scale Networks using Graph Geodesics, Matrix Completion and Machine LearningSpeaker: Anura Jayasumana – Fort Collins, CO, United States
Topic(s): Information Systems, Search, Information Retrieval, Database Systems, Data Mining, Data Science
AbstractExtracting 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 LectureNumber of Slides: 40 - 50
Duration: 50 minutes
Languages Available: English
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.