Algorithms for Learning Networks and Learning from Networks

There are many different networks we encounter in every day life. Social networks, internet (short form of interconnected network) and biological networks are some examples. With the enormous amount of data this is being generated in recent times, the size of these networks have grown substantially. Hence it is important to develop new models and algorithms for studying networks on a large scale. This thesis focuses on problems in graph theory that are related to learning and algorithms. We will explore how to formalise the question “How to learn a graph?” in the first two models. In the first model, we give the learner the power to query a graph and the objective is to learn the edges (or connections) of the graph with the least number of queries. In the second model, the learner gets to see some information about the graph that is generated by some process and the objective is to learn (or approximately learn) the edges. In the third model, suppose we observe some dynamic graph at two different times, we ask what changes in the edges caused the maximum change in the overall structure of the graph. The intuition here is that these changes correspond to anomalies. In this thesis, we have studied three models for various learning and algorithmic questions on graphs. For each of these models, we pick the quantities of most significance and give algorithms and bounds for them.