Graduate Exam Abstract
Gunjan MahindrePh.D. Preliminary
September 13, 2018, 8:00 am - 9:30 am
ECE Conference Room C101B
Efficient Representation, Measurement, and Recovery of Large-scale Networks
Abstract: Efficient Representation, Measurement, and Recovery for Large Scale Networks
Rapid growth in networks (e.g. social networks) is leading to a colossal amount of connections and data underneath. Analysis of network measurements and structures in terms of distances, network features, etc. helps extract patterns that are not in general noticed by humans. Thus, network analytics can be used for predicting how the network evolves, for customer interaction analysis to provide better user experience, and for effective business decisions based on client engagements. Ideally, one should have complete data associated with a network so as to apply the experimental procedures to the real network. However, computational, and storage limitations do not allow that.
Thus, a network is often sampled for its nodes or substructures in order to facilitate analysis. While extensive sampling can be computationally expensive for analysis or even unviable due to access restrictions, privacy issues, etc., sparse or locally targeted sampling techniques do not allow recovery of the complete information for the original network and missing facts may lead to altered network characteristics and biased research results.
This generates a need for techniques to correctly predict missing data as well as to represent and store networks in coherent yet compressed ways that preserve the original network characteristics for uncompromising network experiments.
Accordingly, here we attempt to derive and demonstrate novel techniques for detecting and representing network structures which are scalable in their computation, and graceful in their degradation in the presence of limited measurements. Though our results will be applicable to general graphs and data that can be represented as graphs, in this research, our initial focus will be on scale-free networks (small-world or random networks) and IoT networks as they represent many of the real-world networks.
The research involves theoretical developments relating network topology and path measurements in order to render meaningful relations and properties about the network. It also comprises of completing graphs from partial data, in terms of links and distances, using estimation methods. Subsequently, we work towards finding efficient network representation models by identifying defining nodes, such as link resolution nodes, which provide most of the information about the network. Based on the network properties, we introduce a novel concept of link dimension as a lossless way of compression and graph reconstruction. We also compute accurate bounds on and estimate values of missing entries for the given network via low-rank matrix completion. The results for matrix completion are evaluated for real-world social networks (Facebook, Email, and Collaboration networks). We plan to extend our work to static as well as dynamic networks.
Our methods are targeted toward compressed representations of networks to facilitate low cost analysis of large networks starting with incomplete information gathered by available infrastructure under sundry constraints. The derived techniques for network representation and recovery have to be scalable in their computation and help bridge the gap between network sampling and meaningful research deductions for real-world networks.
Adviser: Dr. Anura Jayasumana
Non-ECE Member: Dr. Michael Kirby
Member 3: Dr. Randy Paffenroth
Addional Members: Dr. Anthony Maciejewski
G. Mahindre and A. P. Jayasumana, "Post Failure Recovery
of Virtual Coordinates in Wireless Sensor Networks," Proc. 7th Int. Conf.
Information and Automation for Sustainability (CIAfS'14), Dec. 2014.
A.P. Jayasumana, R. Paffenroth, G. Mahindre, S. Ramasamy, K. Gajamannege,
"Network Topology Mapping from Partial Virtual Coordinates and Graph
Geodesics," (In review)
Program of Study: