Abstract Network science has emerged over the last years as an interdisciplinary area spanning traditional domains including mathematics, computer science, sociology, biology and economics. Since complexity in social, biological and economical systems, and more generally in complex systems, arises through pairwise interactions there exists a surging interest in understanding networks. In this tutorial, we will provide an in-depth presentation of the most popular random-graph models used for modeling real-world networks. We will then discuss efficient algorithmic techniques for mining large graphs, with emphasis on the problems of extracting graph sparsifiers, partitioning graphs into densely connected components, and finding dense subgraphs. We will motivate the problems we will discuss and the algorithms we will present with real-world applications. Our aim is to survey important results in the areas of modeling and mining large graphs, to uncover the intuition behind the key ideas, and to present future research directions. Who Should Attend The tutorial presents both classic and cutting-edge research topics on networks. We aim to go into depth for the following topics: random graphs, graph sparsifiers, graph partitioning, finding dense subgraphs and their applications. The tutorial will combine a blend of computer science rigor and real-world applications. It should be of theoretical and practical interest to the graph analysis community and a large part of the data mining community as well. Prerequisites Computer science background (B.Sc or equivalent); familiarity with undergraduate level concepts covered in probability and algorithm classes. BIO Dr. Alan Frieze is a professor in the Department of Mathematical Sciences at Carnegie Mellon University, Pittsburgh, United States. He graduated from the University of Oxford in 1966, and obtained his Ph.D. from the University of London in 1975. His research interests lie in combinatorics, discrete optimization and theoretical computer science. In 1991, Dr. Frieze received the Fulkerson Prize in Discrete Mathematics awarded by the American Mathematical Society and the Mathematical Programming Society. In 1997 he was a Guggenheim Fellow In 2000, he received the IBM Faculty Partnership Award. In 2006 he jointly received (with Michael Krivelevich) the Professor Pazy Memorial Research Award from the United States-Israel Binational Science Foundation. In 2011 he was selected as a SIAM Fellow. In 2012 he was selected as an AMS fellow. Dr. Aristides Gionis is an associate professor in the Department of Information and Computer Science, in Aalto University, Finland. Previously he has been a senior research scientist in Yahoo! Research. He received his Ph.D. from the Computer Science department of Stanford University in 2003. He is currently serving as an associate editor in the Transactions of Knowledge and Data Engineering (TKDE). He has served in the PC of numerous premium conferences, including being the PC co-chair for WSDM 2013 and ECML PKDD 2010. His research interests include data mining, web mining, and algorithmic data analysis. Dr. Charalampos Tsourakakis is an Aalto Science Fellow. He received his Ph.D. in Algorithms, Combinatorics and Optimization at Carnegie Mellon University. He holds a Diploma in Electrical and Diploma Engineering from the National Technical University of Athens and a Master of Science from the Machine Learning Department at Carnegie Mellon University. His research interests include algorithm design, random graphs and data mining.
