My research is centered around efficient algorithms for optimization problems on complex networks. A network or graph is a way to represent pairwise interactions between objects. Common examples of networks include computer networks such as the internet, telecommunication networks, biological networks, and social networks. For example, the users of Facebook together with their friendship connections form an online social network.
Given a network, important questions about the network may often be formulated as combinatorial optimization problems. For example, if a company wants to advertise on Facebook, identify which users should it target under a specified budget. When properly formalized, this is known as the Influence Maximization problem.
Since many important combinatorial problems are NP-hard, it is unlikely that a polynomial-time algorithm exists to solve these problems optimally. However, since real-world networks are very large (on the order of billions of nodes and edges), even algorithms that run in cubic time would require on the order of 1018 operations. At around 16 FLOPS per cycle, a single core at 4.0 GHz would require roughly 500 years to do 1018 operations.
For the field of approximation algorithms, efficient is taken to mean "polynomial-time"; however, by the above example, many polynomial-time algorithms would take an impracticably long amount of time on these billion-scale networks. Therefore, a focus of my research has been to develop algorithms scalable to very large networks that retain a performance guarantee with respect to the optimal solution. Furthermore, since modern networks are also highly dynamic, with new connections and nodes being added and old connections being deleted constantly, I am interested in algorithms that can update their solution quickly in response to changes in the network, rather than recomputing from scratch.
Here is a word cloud generated from the content of my papers: