TELCOM2125: Network Science and Analysis
|
 |
|---|
Overview
This course explores networks as a primary metaphor and mechanism for a variety of information-related 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, socially-inspired 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
Projects
Announcements
Course Policies
Basic Information
Instructor: Konstantinos Pelechrinis (kpele AT pitt.edu)
Office: IS Building, 717B
Office hours: Thursday 5:00-6:00pm
Lectures:
Thursday 6:00 p.m. - 9:00 p.m. IS 404
Textbook:
- M.E.J. Newman, Networks:An Introduction, Oxford University Press, ISBN 978-0-19-920665-0, 2010.
Other References:
- M. O. Jackson, Social and Economic Networks, Princeton University Press, ISBN 978-1-400-83399-3, 2010.
- D. Easley and J. Kleinberg, Networks, Crowds and Markets: Reasoning about a Highly Connected World, Cambridge University Press, ISBN 978-0-521-19533-1, 2010.
- M. Chiang, Networked Life: 20 Questions and Answers, Cambridge University Press, ISBN 978-1-107-02494-3, 2012.
- T.G. Lewis, Network Science: Theory and Applications, Wiley, ISBN 978-0-470-33188-0, 2009.
- D.J. Watts, Six Degrees: The Science of a Connected Age, W.W. Norton and Company, ISBN 0-393-32542-3, 2003.
Course Requirements:
Command of (i) Linear Algebra, and (ii) Probability theory. Knowledge of calculus will help tremendously as well.
Course Grading:
- Homework - 15%
- Pop-up quizzes - 15%
- (Research) Project - 60%
- Participation in discussions - 10%
Course Outline
- Graph Theory Basics
- Basic definitions, measures and metrics, large-scale 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
- Module 1
- Adjacency matrix, directed networks, acyclic networks, bipartite networks, trees, degree, paths, components, max-flow/min-cut, diffusion, graph Laplacian, random walks.
- Module 2
- 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
- Network analysis, the small world effect, degree distributions, power laws, scale free networks.
- Module 4
- Random graphs, degree distribution of random graphs, clustering coefficient of random graphs, giant component, small components, path legnths, problems of random graph model.
- Module 5
- 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, small components for the configuration model, random graphs with power law degree distribution.
- Module 6
- Network growth models, preferential attachment, Price model, Barabasi-Albert model, effect of age on a node's degree, variations of preferential attachment, vertices with varying quality, vertex copying models, network optimization models.
- Module 7
- Small-world network model, exponential random graphs
- Module 8
- Navigation in networks, web search, distributed database search, message passing, Kleinberg's model, hierarchical model for message passing.
- Module 9
- Graph partitioning, Kernighan-Lin algorithm, spectral partitioning, community detection, simply modularity maximization, spectral modularity maximization, betweenness-based community detection, hierarchical clustering.
Reading List and Interesting Materials
- The slide from our guest speaker can be found here.
- M.E.J. Newman,"Power laws, Pareto distributions and Zipf's law",in arXiv:cond-mat/0412004: Details on the power law distribution and their presence in real-world networks.
- X.F. Wang and G. Chen,"Complex Networks: Small-World, Scale-Free 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.
- You can test the NetLogo Giant Component model library here.
- An interesting social network analysis article that uses the notion of k-cores.
- A TED talk that exploits the fact that your friends have more friends than you do. The actual study can be found here.
- D.J. Watts and S.H. Strogatz, "Collective dynamics of 'small-world' networks", in Nature 393, 440-442 (4 June 1998)
- P. Dodds, R. Muhamad and D.J. Watts,"An Experimental Study of Search in Global Social Networks", in Science 301 (5634): 827-829.
Homework
Projects
Announcements
- Our last lecture for the semester will be a guest lecture from Charalampos Tsourakakis.
- Presentation module7.ppt has been updated.
- On April 18th, we will have a guest lecturer. More details to follow!
- Presentation module5.ppt has been updated.
- Homework 2 posted.
- Deadline for homework 1 extended to February 21st.
- Presentation module4.ppt has been updated.
- Reading list posted.
- Homework 1 posted.
- Presentations module1.ppt and module2.ppt have been updated with some typo corrections and some additional clarifications.
- Classroom has changed to IS 404!
- The lectures begin on the 10th of January.
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.
This page was last updated on 01/06/2014 20:50:41.