Welcome to EECS 4414/5414
Information Networks



About

Course Description

Information networks are effective representations of pairwise relationships between objects. Examples include technological networks (e.g., World Wide Web), online social networks (e.g., Facebook), biological networks (e.g., Protein-to-Protein interactions), and more. The study of information networks is an emerging discipline of immense importance that combines graph theory, probability and statistics, data mining and analysis, and computational social science. This course provides students with both theoretical knowledge and practical experience of the field by covering models and algorithms of information networks and their basic properties. In addition, analysis of information networks provides the means to explore large, complex data coming from vastly diverse sources and to inform computational problems and better decisions.

Topics
  • basic graph theory
  • network measurements
  • network models
  • community detection
  • graph partitioning
  • link analysis & link prediction
  • information cascades & epidemics
  • network ties
  • social recommendation systems
  • mining graphs
  • connections to problems in the social sciences and economics
Lectures & Office Hours

Lectures: Tue and Thu 13:00am-14:30am at DB 1005 (Victor Phillip Dahdaleh Building)

Office Hours: Tue and Thu 14:30am-15:30pm at LAS 3050 (or by appointment)

Instructor

Manos Papagelis

Contact: papaggel@gmail.com, papaggel@eecs.yorku.ca

Textbooks

The course will rely mainly on the following textbooks.

Syllabus

Download the syllabus (v1.0)

Handouts

Lecture 1. Introduction [Slides]

Introduction, administrivia, introduction to main problems about networks, basic mathematical concepts, bow-tie structure of the Web.

Readings:

Optional readings:

  • A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener. Graph structure in the Web. Computer Networks, 33, 2000.
Lecture 2. Network Measurements [Slides]

Degree distributions, shortest paths, clustering coefficient, measuring power-laws.

Readings:

Optional readings:

  • M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics.
Lecture 3. Network Models [Slides]

Erdos-Renyi random graph model, small-world model, configuration model.

Readings:

Optional readings:

  • 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.
  • 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. Arxiv 2012.
  • M. Papagelis, F. Bonchi, A. Gionis. Suggesting Ghost Edges for a Smaller World. In Proc. CIKM, 2011.
  • M. Papagelis. Refining Social Graph Connectivity via Shortcut Edge Addition. TKDD, 10(2), 2015.
Lecture 4. Power-Laws [Slides]

Power-law distributions, scale-free networks, the anatomy of the long-tail, mathematics of power-laws.

Readings:

Optional readings:

  • M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
  • A. Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009.
  • M.E.J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics 46(5), 323-351, 2005.
  • M. Faloutsos, P. Faloutsos, C. Faloutsos. On Power-Law Relationships of the Internet Topology. In Proc. SIGCOMM, 1999.
  • A.L Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
  • B.A. Huberman, L. A. Adamic. Growth dynamics of the World-Wide Web. Nature, 399, 1999.
  • H.A. Simon. On a class of skew distribution functions. Biometrika 42, 425-440, 1955.
  • D.J. de S. Price. A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soc. Inform. Sci. 27: 292-306, 1976.
  • A.L. Barabasi, R. Albert, H. Jeong. Mean-field theory for scale-free random networks. Physica A 272 173-187, 1999.
  • R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. Stochastic models for the Web graph. In Proc. FOCS 2000.
  • W. Aiello, F. Chung, L. Lu. Random evolution of massive graphs. Handbook of Massive Data Sets, Kluwer, pages 97-122, 2002.
  • B. Bollobas, C. Borgs, J. Chayes, O. Riordan. Directed scale-free graphs. In Proc. SODA 2003.
  • R. Kleinberg, J. Kleinberg. Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs. In Proc. SODA, 2005.
  • A. Fabrikant, E. Koutsoupias, C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. In Proc. ICALP, 2002.
  • N. Berger, C. Borgs, J. Chayes, R. D'Souza, R. Kleinberg. Competition-Induced Preferential Attachment. In Proc. ICALP 2004.
  • M. Molloy and B. Reed. A Critical Point for Random Graphs with a Given Degree Sequence. Random Structures and Algorithms 6, 161-180, 1995.
  • J. Carlson and J. Doyle. Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems. Physical Review E 60:2, 1999.
  • M.E.J. Newman. The first-mover advantage in scientific publication. European Physics Letters 86, 68001, 2009.
  • S. Redner. Citation statistics from 110 years of Physical Review. Physics Today 58, 49-54, 2005.
  • S. Goel, A. Broder, E. Gabrilovich, B. Pang. Anatomy of the Long Tail: Ordinary People with Extraordinary Tastes. In Proc. WSDM, 2010.
  • D. Pennock, G. Flake, S. Lawrence, E. Glover, C. Lee Giles. Winners don't take all: Characterizing the competition for links on the web. PNAS 99(8), 2002.
Lecture 5. Models of Evolving Networks [Slides]

Preferrential attachment model, microscopic evolution of networks, macroscopic evolution of networks, forest-fire model.

Readings:

  • J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins. Microscopic Evolution of Social Networks. In Proc. KDD 2008
  • J. Leskovec, J. Kleinberg, C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM TKDD, 2007.

Optional readings:

  • R. Kumar, J. Novak, A. Tomkins. Structure and evolution of online social networks. In Proc. KDD, 2006.
  • A.L. Barabasi, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, T. Vicsek. Evolution of the social network of scientific collaborations. Physica A: Statistical, 2002.
  • G. Kossinets, D.J. Watts. Empirical Analysis of an Evolving Social Network. Science, 2006.
  • D. Fetterly, M. Manasse, M. Najork, J.L. Wiener. A large-scale study of the evolution of web pages. In Proc. WWW, 2003.
  • 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.
  • A.L. Barabasi. The origin of bursts and heavy tails in human dynamics. Nature 435, 207-211, 2005.
  • J. Kleinberg. Bursty and Hierarchical Structure in Streams. In Proc. KDD, 2002.
  • R. Kumar, J. Novak, P. Raghavan, A. Tomkins. On the bursty evolution of Blogspace. In Proc. WWW, 2003.
  • M. Dubinko, R. Kumar, J. Magnani, J. Novak, P. Raghavan, A. Tomkins. Visualizing Tags over Time. In Proc. WWW, 2006.
  • S. Lattanzi, D. Sivakumar. Affiliation Networks. In Proc. STOC, 2009.
Lecture 6. Strength of weak ties and Community structure in networks [Slides]

Strength of weak ties, structural holes, network communities, community detection, Girvan-Newman algorithm, modularity, modularity optimization.

Readings:

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.
Lecture 7. Network Community Detection: Graph Cuts and Spectral Clustering [Slides]

Graph partitioning, graph cuts, conductance, spectral graph theory, spectral graph clustering.

Readings:

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.
Lecture 8. Overlapping Communities in Networks [Slides]

Overlapping communities, cliques, clique percolation method, modeling networks with communities, community-affiliation graph model.

Readings:

  • G. Palla, I. Derenyi, I. Farkas, T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814-818, 2005.

Optional readings:

  • E. Tomita, A. Tanaka, H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, Volume 363, Issue 1, 2006.
  • G. Palla, A.L. Barabasi, T. Vicsek. Quantifying social group evolution. Nature 446, 664-667, 2007.
  • J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Statistical Properties of Community Structure in Large Social and Information Networks. In Proc. WWW, 2008.
  • J. Leskovec, K. Lang, M. Mahoney. Empirical Comparison of Algorithms for Network Community Detection. In Proc. WWW, 2010.
  • J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics, 2009.
  • G. Karypis, V. Kumar. Multilevel k-way Partitioning Scheme for Irregular Graphs. J. Parallel Distrib. Comput, 48(1): 96-129, 1998.
  • I. Dhillon, Y. Guan, and B, Kulis. A Fast Kernel-based Multilevel Algorithm for Graph Clustering. In Proc. KDD, 2005.
  • R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. In Proc. FOCS, 2006.
  • T. Leighton, S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 1999.
Lecture 9. Link Analysis: HITS and PageRank [Slides]

Web search, Hubs and Authorities (HITS), PageRank, topic-sensitive PageRank, personalised PageRank.

Readings:

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.
  • M. A. Najork. Comparing the effectiveness of HITS and SALSA. In Proc. CIKM, 2007.
  • B. Bahmani, A. Chowdhury, A. Goel. Fast Incremental and Personalized PageRank. In Proc. of VLDB, 2010.
Lecture 10. Link Prediction in Networks [Slides]

Link prediction, neighborhood-based prediction methods, node proximity based prediction methods, supervised learning models, Facebook's "PYMK" algorithm, Twitter's "WtF" algorithm.

Readings:

  • D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. CIKM, 2003.
  • L. Backstrom, J. Leskovec. Supervised Random Walks: Predicting and Recommending Links in Social Networks. In Proc. WSDM, 2011.
  • P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, R.Zadeh. WTF: The Who to Follow Service at Twitter, WWW 2013.

Optional readings:

  • D. Liben-Nowell, and J. Kleinberg, The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7) 1019–1031 (2007)
  • R. Lichtenwalter, J. T. Lussier, N. V. Chawla: New perspectives and methods in link prediction. KDD 2010: 243-252
  • S. A. Myers, J. Leskovec. On the Convexity of Latent Social Network Inference. Neural Information Processing Systems (NIPS), 2010.
  • M. Gomez-Rodriguez, D. Balduzzi, B. Schoelkopf. Uncovering the Temporal Dynamics of Diffusion Networks. In Proc. ICML 2011.
  • A. Clauset, C. Moore, M.E.J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 2008.
  • M. Kim, J. Leskovec. The Network Completion Problem: Inferring Missing Nodes and Edges in Networks. In Proc. SDM, 2010.
  • F. Chierichetti, J. Kleinberg, D. Liben-Nowell. Reconstructing Patterns of Information Diffusion from Incomplete Observations. Neural Information Processing Systems (NIPS), 2011.
  • B. Taskar, M.F. Wong, P. Abbeel, D. Koller. Link prediction in relational data. Neural Information Processing Systems (NIPS), 2006.
  • G. Jeh, J. Widom: SimRank: a measure of structural-context similarity. KDD 2002: 538-543
  • R. Lempel, S. Moran: SALSA: the stochastic approach for link-structure analysis. ACM Trans. Inf. Syst. 19(2): 131-160 (2001)
  • P. D’haeseleer, S. Liang, R. Somogyi. Genetic network inference: from co-expression clustering to reverse engineering. Bioinformatics, vol. 16, 2000.
Lecture 11. Cascading Behavior: Decision Based Models of Cascades [Slides]

Spreading through networks, Granovetter’s model of collective action, decision based model of diffusion, game theoretic model of cascades.

Readings:

Optional readings:

  • S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
  • N. Immorlica, J. Kleinberg, M. Mahdian, T. Wexler. The Role of Compatibility in the Diffusion of Technologies Through Social Networks. In Proc. ACM EC, 2007.
  • E. Berger. Dynamic Monopolies of Constant Size. Journal of Combinatorial Theory Series B 83, 191-200, 2001.
  • D. Centola, M. Macy. Complex Contagions and the Weakness of Long Ties. American Journal of Sociology, 2007.
  • M. Jackson, L. Yariv. Diffusion of Behavior and Equilibrium Properties in Network Games. American Economic Review , Vol 97, No. 2, 2007.
  • S. Bikhchandani, D. Hirshleifer, I. Welch. A theory of fads, fashion, custom and cultural change as information cascades. Journal of Political Economy. Vol. 100, pp. 992-1026, 1992.
  • T. Schelling. Micromotives and Macrobehavior. Norton, 1978.
  • D. Strang, S. Soule. Diffusion in organizations and social movements: From hybrid corn to poison pills. Annual Review of Sociology, 24:265--290, 1998.
  • D. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci., vol. 99 no. 9, 5766-5771, 2002.
  • H. P. Young. The Diffusion of Innovations in Social Networks. Santa Fe Institute Working Paper 02-04-018.
  • P. Dodds and D. J. Watts. Universal Behavior in a Generalized Model of Contagion. Phyical Review Letters, 2004.
  • E. Lieberman, C. Hauert, M. A. Nowak. Evolutionary Dynamics on Graphs. Nature 433: 312-316, 2005.
  • D. Centola, M. Macy, V. Eguiluz. Cascade Dynamics of Multiplex Propagation. Physica A 374, 449-456, 2007.
  • D. Centola. The Spread of Behavior in an Online Social Network Experiment. Science, 2010.
  • M. Granovetter. Threshold models of collective behavior. American Journal of Sociology 83(6):1420-1443, 1978.
  • A. V. Banerjee. A Simple Model of Herd Behavior. The Quarterly Journal of Economics, Vol. 107, No. 3, pp. 797-817, 1992.
Lecture 12. Cascading Behavior: Probabilistic Models of Information Flow [Slides]

Epidemic model based on trees, models of disease spreading (SIR, SIS, SIRS), independent cascade model, modeling interactions between contagions.

Readings:

  • Networks, Crowds, and Markets (chapter 21)
  • D. Romero, B. Meeder, J. Kleinberg. Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter. In Proc. WWW, 2011.
  • S. Myers, J. Leskovec. Clash of the Contagions: Cooperation and Competition in Information Diffusion. In Proc. ICDM 2012.

Optional readings:

  • M. Papagelis, V. Murdock, R. van Zowl. Individual Behavior and Social Influence in Online Social Systems. In Proc. HT, 2011.
  • S. Myers, C. Zhu, J. Leskovec. Information Diffusion and External Influence in Networks. In Proc. KDD, 2012.
  • A. Goyal, F. Bonchi, L.V.S. Lakshmanan. Learning influence probabilities in social networks. In Proc. WSDM, 2010.
  • D. Cosley, D. Huttenlocher, J. Kleinberg, X. Lan, S. Suri.Sequential Influence Models in Social Networks. In Proc. ICWSM, 2010.
  • J. Leskovec, A. Singh, J. Kleinberg. Patterns of Influence in a Recommendation Network In Proc PAKDD, 2006.
  • L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006.
  • M. Papagelis, N. Bansal, N. Koudas. Information Cascades in the Blogosphere: A Look Behind the Curtain. In Proc. ICWSM, 2009.
  • E. Adar, L. Adamic. Tracking information epidemics in blogspace. In Proc. Wed intelligence, 2005.
  • J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, M. Hurst. Cascading Behavior in Large Blog Graphs. In Proc. SIAM International Conference on Data Mining, 2007.
  • D. Gruhl, R. Guha, D. Liben-Nowell, A. Tomkins. Information Diffusion through Blogspace. In Proc. International WWW Conference, 2004.
  • M. Goetz, J. Leskovec, M. Mcglohon, C. Faloutsos. Modeling blog dynamics, In AAAI Conference on Weblogs and Social Media (ICWSM), 2009.
  • M. Miller, C. Sathi, D. Wiesenthal, J. Leskovec, C. Potts. Sentiment Flow Through Hyperlink Networks. In Proc. ICWSM, 2011.
  • J. Ugander, L. Backstrom, C. Marlow, J. Kleinberg. Structural Diversity in Social Contagion. In Proc. National Academy of Sciences, 2012.
Lecture 13. Influence Maximization [Slides]

The Influence Maximization Problem (IMP), IMP hardness, IMP approximation, submodularity.

Readings:

  • D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. In Proc. KDD 2003.

Optional readings:

  • M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In Proc. KDD, 2002.
  • M. Richardson, P. Domingos. Mining the Network Value of Customers. In Proc. KDD, 2001.
  • S. Hill, F. Provost, C. Volinsky. Network-Based Marketing: Identifying Likely Adopters via Consumer Networks. Statistical Sciece, 2006.
  • J. Leskovec, L. Adamic, B. Huberman. The Dynamics of Viral Marketing. TWEB, 2007.
  • E. Bakshy, J. M. Hofman, W. A. Mason, and D. J. Watts, Everyone’s an influencer: quantifying influence on twitter. In Proc. WSDM, 2011.
  • S. Aral, L. Muchnik, A. Sundararajan. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. In Proc. National Academy of Sciences, 2009.
  • A. Goyal, W. Lu, L. S.V. Lakshmanan. SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In Proc. ICDM, 2011.
  • W. Chen, Y. Wang, S. Yang. Efficient Influence Maximization in Social Networks. In Proc. KDD, 2009.
  • W. Chen, Y. Yuan, L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In Proc. ICDM, 2010.
  • C. Lerman, R. Ghosh. Information Contagion: Empirical Study of the Spread of News on Digg and Twitter Social Networks. In Proc. ICWSM, 2010.
  • Y. Singer. How to win friends and influence people, truthfully: Influence maximization mechanisms for social networks. In Proc. WSDM, 2012.
  • A. Gionis, E. Terzi, P. Tsaparas. Opinion maximization in social networks. In Proc. SDM, 2013.
  • M. Papagelis. Refining Social Graph Connectivity via Shortcut Edge Addition. TKDD, 10(2), 2015.
Lecture 14. Outbreak Detection [Slides]

The outbreak detection problem, greedy hill-climbing approx. algorithm, cost-effective lazy forward-selection (CELF) algorithm.

Readings:

  • J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance. Cost-effective Outbreak Detection in Networks. In Proc. KDD, 2007.

Optional readings:

  • E. Mossel and S. Roch. On the Submodularity of Influence in Social Networks. In Proc. STOC, 2007.
  • N. Agarwal, H. Liu, L. Tang, P. Yu. Identifying the Influential Bloggers in a Community In Proc. WSDM, 2008.
  • A. Krause, J. Leskovec, C. Guestrin, J. VanBriesen, C. Faloutsos. Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks. Journal of Water Resources Planning and Management, 2008.
  • A. Krause, C. Guestrin, A Note on the Budgeted Maximization on Submodular Functions. Technical report, Carnegie Mellon University, no. CMU-CALD-05-103, 2005.
  • A. Ostfeld et al. The Battle of the Water Sensor Networks (BWSN): A Design Challenge for Engineers and Algorithms. Journal of Water Resources Planning and Management, 2009.
  • M. Cha, H. Haddadi, F. Benevenuto, K.P. Gummadi. Measuring user influence in Twitter: The million follower fallacy. In Proc. ICWSM, 2010.
  • A. Goyal, W. Lu, L. V.S. Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In Proc. WWW, 2011.
  • R. Pastor-Satorras, A. Vespignani. Immunization of complex networks. Physical Review E, 2002.
  • T. Lappas, E. Terzi, D. Gunopoulos, H. Mannila. Finding Effectors in Social Networks. In Proc. KDD, 2010.
Lecture 15. Recommender Systems I [Slides]

Recommender systems, content-based systems, collaborative filtering.

Readings:

Optional readings:

  • G. Adomavicius, A. Tuzhilin. Towards the next generation of recommender systems: a survey of the state-of-the-art and possible extensions. TKDE, 2005.
  • M. Papagelis, D. Plexousakis. Qualitative analysis of user-based and item-based prediction algorithms for recommendation agents. Eng. Appl. Artif. Intel., 2005.
  • C. Anderson. The Long Tail: Why the Future of Business is Selling Less of More, Hyperion Books, New York, 2006.
  • G. Linden, B. Smith, and J. York. Amazon.com recommendations: item-to-item collaborative filtering. Internet Computing, 7:1, 2003.
  • Y. Koren. The bellkor solution to the netflix grand prize. Netflix prize documentation, 2009.
  • M. Piotte, M. Chabbert. The pragmatic theory solution to the netflix grand prize. Netflix prize documentation, 2009.
  • A. Töscher, M. Jahrer, R. M. Bell. The bigchaos solution to the netflix grand prize. Netflix prize documentation, 2009.
Lecture 16. Recommender Systems II [Slides]

Latent factor models for recommender systems, The Netflix challenge.

Readings:

Optional readings:

  • Y. Koren. The bellkor solution to the netflix grand prize. Netflix prize documentation, 2009.
  • M. Piotte, M. Chabbert. The pragmatic theory solution to the netflix grand prize. Netflix prize documentation, 2009.
  • A. Töscher, M. Jahrer, R. M. Bell. The bigchaos solution to the netflix grand prize. Netflix prize documentation, 2009.
Lecture 17. Review [Slides]

The age of networks, review of key topics covered (your superpowers), applying your superpowers, what's next?

Assignments

Project

Resources

Software Tools and Libraries

Online resources for mining and exploration of graphs/networks.

  • SNAP Libary for working with massive network datsets (C++, Python)
  • NetworkX Library for studying graphs and networks (Python)
  • JUNG Library for modeling, analysis, and visualization of graphs (Java)
  • Metis Family of programs for partitioning graphs
  • Pajek Program for large network analysis and visualization
  • Gephi Program for graph visualization and exploration
Tutorials

A list of useful online tutorials relating to the course material.

Similar Courses

Similar courses about information networks and network analysis.