TELCOM2125/INFSCI2125: Network Science and Analysis



Overview
This course explores networks as a primary metaphor and mechanism for a variety of informationrelated phenomena. The advancement of interconnected information and communication technologies has made networks one of the dominant ways of analyzing the use and flow of information among individuals, institutions, and societies. The course starts with the basics of graph theory and moves to studying network structures and how they emerge through various network models. We begin with the traditional random graph model and we move to more realistic, sociallyinspired models such as preferential attachment. We will further explore processes in a network such as diffusion of epidemics and network search. Finally, we will study issues related to games on networks. As a prerequisite, students should have a command of mathematics through linear algebra as well as probability theory. Knowledge of calculus is also helpful.
Learning outcomes
Upon satisfactory completion of this course, students will:
 understand the metrics that describe the various different properties of a network
 be able to identify the crucial metrics to be examined for a variety of different network analysis tasks
 command the analysis and properties of random graph models
 learn the different network formation models that have been proposed to explain the mechanisms dictating the formation and evolution of social networks
 be able to develop their own software for analyzing large network datasets
 be able to use third party network analysis software for analyzing and visualizing networks
Basic Information
Course Grading
Course Outline
Lectures
Homework
Announcements
Course Policies
Basic Information
Instructor: Konstantinos Pelechrinis (kpele AT pitt.edu)
Office: IS Building, 717B
Office hours: Monday, 56pm
Teaching Assistant:
Xiao Ma
(xim12 AT pitt.edu)
Office: IS Building, LG11
Office hours: Tuesday/Thursday 1:303:30 p.m
Lectures:
Wednesday 12:00 p.m.  2:50 p.m. IS 502
Textbook:
 M.E.J. Newman, Networks:An Introduction, Oxford University Press, ISBN 9780199206650, 2010.
Other References:
 M. O. Jackson, Social and Economic Networks, Princeton University Press, ISBN 9781400833993, 2010.
 D. Easley and J. Kleinberg, Networks, Crowds and Markets: Reasoning about a Highly Connected World, Cambridge University Press, ISBN 9780521195331, 2010.
 M. Chiang, Networked Life: 20 Questions and Answers, Cambridge University Press, ISBN 9781107024943, 2012.
 T.G. Lewis, Network Science: Theory and Applications, Wiley, ISBN 9780470331880, 2009.
 D.J. Watts, Six Degrees: The Science of a Connected Age, W.W. Norton and Company, ISBN 0393325423, 2003.
Course Requirements:
Command of (i) Linear Algebra, and (ii) Probability theory. Knowledge of calculus will help tremendously as well.
Course Grading:
 Homework  30%
 Midterm  30%
 Final  30%
 Participation in discussions  10%
Course Outline
 Graph Theory Basics
 Basic definitions, measures and metrics, largescale network structure, power laws.
 Network Models
 Random graphs, configuration model, preferential attachment models, network optimization models.
 Dynamic Processes in Networks
 Web search, percolation, network resiliance, epidemics in networks.
 Games on Networks
 The notion of Nash equilibrium, games on networks, coloring, consensus, biased voting, trading in networks, behavioral game theory.
Lectures
 Introductory Lecture (pdf)
 Why a science for networks? Examples of networks, a small history of network science, basic probabilities and linear algebra.
 Module 1 (pdf)
 Adjacency matrix, directed networks, acyclic networks, bipartite networks, trees, degree, paths, components, maxflow/mincut, diffusion, graph Laplacian, random walks.
 Module 2 (pdf)
 Centrality metrics (degree centrality, eigenvector centrality, Katz centrality, PageRank), HITS, betweenness, transitivity, clustering coefficient, structural balance, structural and regular equivalence, homophily, assortativity coefficient.
 Module 3 (pdf)
 Network analysis, the small world effect, degree distributions, power laws, scale free networks.
 Module 4 (pdf)
 Graph partitioning, KernighanLin algorithm, spectral partitioning, community detection, simply modularity maximization, spectral modularity maximization, betweennessbased community detection, hierarchical clustering.
 Module 5 (pdf)
 Random graphs, degree distribution of random graphs, clustering coefficient of random graphs, giant component, small components, threshold functions, path legnths, problems of random graph model.
 Module 6 (pdf)
 Configuration model, probability generating functions, neighbor's degree distribution, excess degree, generating functions for degree distribution, number of second neighbors, giant component for the configuration model, random graphs with power law degree distribution.
 Module 7 (pdf)
 Network growth models, preferential attachment, Price model, BarabasiAlbert model, effect of age on a node's degree, variations of preferential attachment, vertices with varying quality, vertex copying models, network optimization models.
 Mean Field Approximation
 Module 8 (pdf)
 Smallworld network model.
 Module 9 (pdf)
 Navigation in networks, web search, distributed database search, message passing, Kleinberg's model, hierarchical model for message passing.
 Module 10 (pdf)
 Diffusion, Bass Model, SIS model.
 Basics of iGraph(ppt)
 A basic introduction to iGraph (in R). Examples, are based on this toynetwork. This presentation will be updated throughout the duration the class.
Reading List and Interesting Materials
 X.F. Wang and G. Chen,"Complex Networks: SmallWorld, ScaleFree and Beyond"., IEEE Circuits and Systems Magazine, 2003: Basic reviews of properties of real world networks and network formation models that attempt to reproduce them.
 D. Chakrabarti and C. Faloutsos, Graph mining: Laws, generators, and algorithms, in ACM Computing Surveys, vol. 38, no. 1, 2006.
 J. Leskovec, J. Kleinberg and C. Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, in ACM SIGKDD, 2005.
 An overlapping community detection algorithm (pdf)
 An interesting social network analysis article that uses the notion of kcores.
 M.E.J. Newman,"Power laws, Pareto distributions and Zipf's law",in arXiv:condmat/0412004: Details on the power law distribution and their presence in realworld networks.
 D.J. Levitin, P. Chordia and V. Menon, Musical rhythm spectra from Bach to Joplin obey a 1/f power law, in PNAS, vol 109, no. 10, 2012.
 M.E.J. Newman and J. Park, "Why social networks are different from other types of networks", in Phys. Rev. E 68, 036122 (2003).
 A TED talk that exploits the "friendship paradox". The actual study can be found here.
 You can test the NetLogo Giant Component model library here.
 D.J. Watts and S.H. Strogatz, "Collective dynamics of 'smallworld' networks", in Nature 393, 440442 (4 June 1998)
 P. Dodds, R. Muhamad and D.J. Watts,"An Experimental Study of Search in Global Social Networks", in Science 301 (5634): 827829.
 D. Kempe, J. Kleinberg and E. Tardos, Maximizing the Spread of Influence through a Social Network",, in ACK SIGKDD, 2003."
 You can find a nice summary of some of the results we discussed in the class here
Homework
Announcements
 The final will be given on April 22nd, and will include the material from modules 510.
 The midterm will be given on March 4th, and will include the material from modules 14.
 Class room has changed to room 502.
 During the first class we will have a short (entry) exam on probabilities and linear algebra. The exam will be neither graded nor it will be eponymous and it serves a dual purpose; (i) you get to see what is the minimum level of math required for this class and (ii) I can get an idea of the aggregate level of math in the class.
Course Policies

Material Covered: You are responsible for all material covered in
lecture and assigned reading.

Collaboration policy: There is no collaboration at any part of the course unless otherwise specified.