Scalable Algorithms for Data and Network Analysis
In the age of Big Data, efficient algorithms are now in higher demandmore than ever before. While Big Data takes us into the asymptoticworld envisioned by our pioneers, it also challenges the classical notionof efficient algorithms: Algorithms that used to be considered efficient,according to polynomial time characterization, may no longer be adequatefor solving today's problems. It is not just desirable, but essential,that efficient algorithms should be scalable. In other words, their complexityshould be nearly linear or sub linear with respect to the problemsize. Thus, scalability, not just polynomial time computability, shouldbe elevated as the central complexity notion for characterizing efficientcomputation.In this tutorial, I will survey a family of algorithmic techniques forthe design of provably good scalable algorithms. These techniques includelocal network exploration, advanced sampling, sparsification, andgeometric partitioning. They also include spectral graph theoreticalmethods, such as those used for computing electrical flows and samplingfrom Gaussian Markov random fields. These methods exemplifythe fusion of combinatorial, numerical, and statistical thinking in networkanalysis. I will illustrate the use of these techniques by a few basicproblems that are fundamental in network analysis, particularly for theidentification of significant nodes and coherent clusters/communities insocial and information networks. I also take this opportunity to discusssome frameworks beyond graph theoretical models for studying conceptualquestions to understand multifaceted network data that arisein social influence, network dynamics, and Internet economics.
Found. Trends Theor. Comput. Sci.