P. Erdos, A. Renyi. On Random Graphs I. Publ. Math. Debrecen, 1959.
P. Erdos, A. Renyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960.
B. Bollobas. Random Graphs. Cambridge University Press.
M.E.J. Newman, S. H. Strogatz and D.J. Watts. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118, 2001.
R. Milo, N. Kashtan, S. Itzkovitz, M.E.J. Newman, U. Alon. On the uniform generation of random graphs with prescribed degree sequences. Arxiv, 2004.
D. Ellis. The expansion of random regular graphs. Lecture notes from Algebraic methods in combinatorics, Cambridge University, 2011.
S. Arora, S. Rao and U. Vazirani. Expander Flows, Geometric Embeddings and Graph Partitioning. In proc. STOC ‘04, 2004.

第二讲 Measuring Networks and Random Graph Model

From Easley and Kleinberg’s Book : Chapter 20 The Small-World Phenomena
D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature 393:440-42, 1998.

Optional Readings

Demo: Erdos-Renyi random graph
Demo: Watts-Strogatz small-world model
S. Milgram. The small world problem. Psychology Today 1(1967).
J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry 32, 1969.
P. S. Dodds, R. Muhamad, D. J. Watts. An Experimental Study of Search in Global Social Networks. Science 301(2003), 827.
J. Leskovec, E. Horvitz. Worldwide Buzz: Planetary-Scale Views on an Instant-Messaging Network. Proc. International WWW Conference, 2008.
P. Killworth and H. Bernard, Reverse small world experiment. Social Networks 1, 1978.
J. Kleinfeld. Could it be a Big World After All? The `Six Degrees of Separation’ Myth. Society, 2002.
P. Killworth, C. McCarty, H.R. Bernard, M. House. The accuracy of small-world chains in social networks. Social Networks 28, 85-96, 2006.
F. Menczer. Growing and Navigating the Small World Web by Local Content. Proc. Natl. Acad. Sci., 99(22): 14014-14019, 2002.
L. Backstrom, P. Boldi, M. Rosa, J. Ugander, S. Vigna. Four Degrees of Separation. ACM Web Science Conference. 2012.
J. Ugander, B. Karrer, L. Backstrom, C. Marlow. The Anatomy of the Facebook Social Graph. 2012.

第三讲 Link Analysis: PageRank

Chapter 14 from Easley and Kleinberg: Link Analysis and Web Search

Optional Readings

S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998.
J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
P. Berkhin. A Survey of PageRank Computing. Internet Mathematics, 2005.
S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. Mining the link structure of the World Wide Web. IEEE Computer, August 1999.
A. Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, S. Raghavan. Searching the Web. ACM Transactions on Internet Technology 1(1): 2-43, 2001.
A. Borodin, J. S. Rosenthal, G. O. Roberts, P. Tsaparas, Finding Authorities and Hubs From Link Structures on the World Wide Web.10th International World Wide Web Conference, May 2001.
D. Achlioptas, A. Fiat, A. Karlin, F. McSherry. Web Search via Hub Synthesis. 42nd IEEE Symposium on Foundations of Computer Science, p.611-618, 2001.
D. Rafiei, A. Mendelzon. What is this Page Known for? Computing Web Page Reputations. Proc. WWW Conference, 2000.
P. Domingos, M. Richardson. The Intelligent Surfer: Probabilistic Combination of Link and Content Information in PageRank. In Proc. NIPS, 2002.
T. H. Haveliwala. Topic-Sensitive PageRank. 11th International World Wide Web Conference, 2002.
A. Altman, M. Tennenholtz. Ranking Systems: The PageRank Axioms. In Proc. of ACM EC, 2005.
Z. Gyongyi, H. Garcia-Molina, J. Pedersen. Combating Web Spam with TrustRank. In Proc. of VLDB, 2004.
Z. Gyongyi, P. Berkhin, H. Garcia-Molina, J. Pedersen. Link Spam Detection Based on Mass Estimation. In Proc. of VLDB, 2006.
A. Borodin, G. O. Roberts, J. S. Rosenthal, P Tsaparas. Link Analysis Ranking: Algorithms, Theory, and Experiments. ACM TOIT, 2005.
A. Ntoulas, J. Cho, C. Olston. What’s New on the Web? The Evolution of the Web from a Search Engine Perspective. In Proc. WWW, 2004.
B. Bahmani, A. Chowdhury, A. Goel. Fast Incremental and Personalized PageRank. In Proc. of VLDB, 2010.

第四讲 Network Construction, Inference, and Deconvolution

Dong, Wei, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. WWW, 2011.
Goh, Kwang-Il, Michael E. Cusick, David Valle, Barton Childs, Marc Vidal, and Albert-László Barabási. The human disease network. Proceedings of the National Academy of Sciences, 104, no. 21 (2007): 8685-8690. Optional Readings
Tang, Jian, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high-dimensional data. WWW, 2016.
Horvát, Emoke-Agnes, and Katharina A. Zweig. One-mode projection of multiplex bipartite graphs. ASONAM, 2012.
Martínez, Víctor, Fernando Berzal, and Juan-Carlos Cubero. A survey of link prediction in complex networks. CSUR, 2017.
Chen, Jie, Haw-ren Fang, and Yousef Saad. Fast approximate kNN graph construction for high dimensional data via recursive Lanczos bisection. Journal of Machine Learning Research, (2009):10, 1989-2012.
Boccaletti, Stefano, Ginestra Bianconi, Regino Criado, Charo I. Del Genio, Jesús Gómez-Gardenes, Miguel Romance, Irene Sendina-Nadal, Zhen Wang, and Massimiliano Zanin. The structure and dynamics of multilayer networks. Physics Reports 544, no. 1 (2014): 1-122.
Wang, Jing, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, and Shipeng Li. Scalable k-nn graph construction for visual descriptors. CVPR, 2012.
Zhang, Yan-Ming, Kaizhu Huang, Guanggang Geng, and Cheng-Lin Liu. Fast kNN graph construction with locality sensitive hashing. ECML PKDD, 2013.
Feizi, Soheil, Daniel Marbach, Muriel Médard, and Manolis Kellis. Network deconvolution as a general method to distinguish direct dependencies in networks. Nature Biotechnology, 31, no. 8 (2013): 726.
Han, Xiao, Zhesi Shen, Wen-Xu Wang, and Zengru Di. Robust reconstruction of complex networks from sparse data. Physical Review Letters, 114, no. 2 (2015): 028701.
Wang, Bo, Armin Pourshafeie, Marinka Zitnik, Junjie Zhu, Carlos D. Bustamante, Serafim Batzoglou, and Jure Leskovec. Network Enhancement as a general method to denoise weighted biological networks. Nature Communications, 9 (2018): 3108.
Hallac, David, Youngsuk Park, Stephen Boyd, and Jure Leskovec. Network inference via the time-varying graphical lasso. KDD, 2017.

第五讲 Motifs and Graphlets

Milo, Ron, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298, no. 5594 (2002): 824-827.
Milo, Ron, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. Superfamilies of evolved and designed networks. Science, 303, no. 5663 (2004): 1538-1542.
Przulj, Nataša. Biological network comparison using graphlet degree distribution. Bioinformatics, 23, no. 2 (2007): 177-183.

Optional Readings

Shen-Orr, Shai S., Ron Milo, Shmoolik Mangan, and Uri Alon. Network motifs in the transcriptional regulation network of Escherichia coli. Nature Genetics, 31, no. 1 (2002): 64.
Kashtan, Nadav, Shalev Itzkovitz, Ron Milo, and Uri Alon. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics, 20, no. 11 (2004): 1746-1758.
Itzkovitz, Shalev, and Uri Alon. Subgraphs and network motifs in geometric networks. Physical Review E, 71, no. 2 (2005): 026117.
Kashtan, Nadav, Shalev Itzkovitz, Ron Milo, and Uri Alon. Topological generalizations of network motifs. Physical Review E, 70, no. 3 (2004): 031909.
Ahmed, Nesreen K., Jennifer Neville, Ryan A. Rossi, and Nick Duffield. Efficient graphlet counting for large networks. ICDM, 2015.
Ribeiro, Pedro, Fernando Silva, and Luis Lopes. Efficient parallel subgraph counting using g-tries. IEEE ICCC, 2010.
Estrada, Ernesto, and Juan A. Rodriguez-Velazquez. Subgraph centrality in complex networks. Physical Review E, 71, no. 5 (2005): 056103.
Ribeiro, Pedro, Fernando Silva, and Luís Lopes. Parallel discovery of network motifs. Journal of Parallel and Distributed Computing, 72, no. 2 (2012): 144-154.
Hayes, Wayne, Kai Sun, and Nataša Przulj. Graphlet-based measures are suitable for biological network comparison. Bioinformatics, 29, no. 4 (2013): 483-491.
Malod-Dognin, Noël, and Nataša Przulj. L-GRAAL: Lagrangian graphlet-based network aligner. Bioinformatics, 31, no. 13 (2015): 2182-2189.
Wernicke, Sebastian. Efficient detection of network motifs. IEEE/ACM TCBB 3, no. 4 (2006): 347-359.
Kovanen, Lauri, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences. Proceedings of the National Academy of Sciences, (2013): 201307941.
Agrawal, Monica, Marinka Zitnik, and Jure Leskovec. Large-scale analysis of disease pathways in the human interactome. PSB, 2018.
Paranjape, Ashwin, Austin R. Benson, and Jure Leskovec. Motifs in temporal networks. WSDM, 2017.
Kashani, Zahra Razaghi Moghadam, Hayedeh Ahrabian, Elahe Elahi, Abbas Nowzari-Dalini, Elnaz Saberi Ansari, Sahar Asadi, Shahin Mohammadi, Falk Schreiber, and Ali Masoudi-Nejad. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics, 10, no. 1 (2009): 318.
Kashtan, Nadav, and Uri Alon. Spontaneous evolution of modularity and network motifs. Proceedings of the National Academy of Sciences, 102, no. 39 (2005): 13773-13778.
Onnela, Jukka-Pekka, Jari Saramäki, János Kertész, and Kimmo Kaski. Intensity and coherence of motifs in weighted complex networks. Physical Review E, 71, no. 6 (2005): 065103.
Rotabi, Rahmtin, Krishna Kamath, Jon Kleinberg, and Aneesh Sharma. Detecting strong ties using network motifs. WWW, 2017.

第六讲 Community Structure in Networks

Chapter 3 from Easley and Kleinberg: Strong and Weak Ties
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008.
Henderson K, Gallagher B, Eliassi-Rad T, Tong H, Basu S, Akoglu L, Koutra D, Faloutsos C, Li L. Rolx: structural role extraction & mining in large graphs. In Proc. of KDD, 2012.

Optional Readings

M. Granovetter. The strength of weak ties. American Journal of Sociology, 78(6):1360-1380, 1973.
J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.L. Barabasi. Structure and tie strengths in mobile communication networks. PNAS, 2007
M. Girvan and M.E.J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99, 8271-8276, 2002.
M.E.J. Newman. Modularity and community structure in networks., Proc. Natl. Acad. Sci., 2002.
C. Marlow, L. Byron, T. Lento, I. Rosenn. Maintained relationships on Facebook. 2009.
B.A. Huberman, D.M. Romero, F. Wu. Social networks that matter: Twitter under the microscope. First Monday, 14(1), 2009.
L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006.
P.S. Bearman, J. Moody. Suicide and Friendships Among American Adolescents. Am J Public Health, 94(1): 89-95, 2004.
R. Burt. Structural Holes versus Network Closure as Social Capital. Chapeter in Social Capital: Theory and Research, 2001.
R. Burt. Structural Holes and Good Ideas. American Journal of Sociology, Vol. 110, No. 2 2004.
G. Flake, S. Lawrence, C.L. Giles, F. Coetzee. Self-Organization and Identification of Web Communities. IEEE Computer, 35:3, 2002.
G. Flake, K. Tsioutsiouliklis, R.E. Tarjan. Graph Clustering Techniques based on Minimum Cut Trees. Technical Report 2002-06, NEC, Princeton, NJ, 2002.
S. Fortunato Community detection in graphs, Arxiv 2009.
A. Clauset, M.E.J. Newman, C. Moore. Finding community structure in very large networks. Phys. Rev. E 70, 066111, 2004
M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.
U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001.
J. Reichardt, S. Bornholdt. Statistical Mechanics of Community Detection., Phys. Rev. E 74 016110, 2006.
S. Fortunato, S. Barthelemy. Resolution limit in community detection. Proc. Natl. Acad. Sci., 2007.
U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, D. Wagner. On Modularity Clustering. IEEE TKDE, 2007.

第七讲 Community Detection: Spectral Clustering

A. Rajaraman, J. Ullman, J. Leskovec. Chapter 10.4 of Mining Massive Datasets, 2013.

Optional Readings

J. Shi, J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions On Pattern Analysis And Machine Intelligence, vol. 22, no. 8, 2000.
R. Kannan, S. Vempala, A. Vetta. On clusterings: Good, bad and spectral. Journal of the ACM, 51(3):497-515, 2004.
M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 1973.
A. Pothen, H.D. Simon, K.P. Liou. Partitioning sparse matrices with egenvectors of graph. SIAM Journal of Matrix Anal. Appl., 11:430–452, 1990.
L. Hagen, A.B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992.
A. Ng, M. Jordan, Y. Weiss. On spectral clustering: Analysis and an algorithm. NIPS, 2001.
U. von Luxburg. Tutorial on spectral clustering. Arxiv 2009.
S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web. In Proc. VLDB, 2001.

第八讲 Link Prediction

Nowicki K, Snijders TA. Estimation and Prediction for Stochastic Blockstructures. Journal of the American statistical association. 2001.
McDaid AF, Murphy TB, Friel N, Hurley NJ.Improved Bayesian inference for the stochastic block model with application to large networks. Computational Statistics & Data Analysis. 2013.
Moore C. The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness. arXiv preprint arXiv:1702.00467. 2017.

Optional Readings

Rohe K, Chatterjee S, Yu B. Spectral Clustering and the High-dimensional Stochastic Blockmodel. The Annals of Statistics. 2011.
Abbe E. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research. 2018.
Resnik P, Hardisty E. Gibbs Sampling for the Uninitiated. MARYLAND UNIV COLLEGE PARK INST FOR ADVANCED COMPUTER STUDIES; 2010.
Holland PW, Laskey KB, Leinhardt S. Stochastic Blockmodels: First Steps. Social networks. 1983.
Karrer B, Newman ME. Stochastic blockmodels and community structure in networks. Physical review E. 2011.