CS60078 Complex Networks
(Spring Semester 2019)
Ayan Kumar Bhowmick ayankumarbhowmick [AT] gmail.com
Snigdha Das snigdha00582 [AT] gmail.com
Aakash Verma aakashverma1996 [AT] gmail.com
08.04.2019 Extra class on April 9 @2.00pm
05.04.2019 Final-Term project presentation on April 17.
01.04.2019 Extra class on April 2 @2.00pm
11.03.2019 Mid-Term project presentation on March 12 & 14.
05.02.2019 Extra class on Feb 12 (Tue) from 14.00-16.00.
09.01.2019 Term project group submission deadline : Jan. 14 EOD (Hard deadline)
02.01.2019 First class: Jan 8, 2019, Tue. Venue: CS 119, Time: 15.00.
The objective of this course is to acquaint participants with some of the fundamental concepts and state-of-the-art research in the
areas of complex networks and network science. This is a research oriented course with wide applications in the fields of social network, data science, information retrieval, communication system and economics and finance.
The major focus of this course is to study of the models and behaviors of networked systems.
Empirical studies of social, technological, information and financial networks. Exploring the concepts of small world effect, degree distribution,
clustering, network correlations, random graphs, models of network growth, and preferential attachment and dynamical processes taking place on networks.
This course has no official prerequisites. However, it is implicitly expected that the registrants have already
gone through the basic courses on mathematics. The outline of the course is given below
Overview of Network science, Motivation, Large scale dynamic networks, Challenges of graph theory
Basic Concepts related to Networks
Small world effect, transitivity and clustering, degree distribution, scale free networks, maximum degree; network resilience; mixing patterns; degree correlations; community structures; network navigation
Community Structure Analysis
Basic concepts of network communities, Modularity, various community finding approaches like Girvan-Newman Algorithm, Spectral Bisection Algorithm, Radicchi Edge Clustering Algorithm (for binary as well as weighted graphs), Wu-Hubermann Algorithm, and Random Walk based Algorithm, Louvain, InfoMap
Poisson random graphs, generalized random graphs, the configuration model, generating functions, power-law degree distribution, directed graph, bipartite graph, degree correlations
Models of Network Growth
Price model, Barabasi & Albert model, other growth models, vertex copying models, Bipartite Network
Processes taking place on Networks
Percolation theory and network resilience, Epidemiological processes, Cascades and information spread
Homophily, Cohesiveness, Cliques, Clans, Clubs, Plex, Equivalence of ties, Ego-centric networks, Cascade formation and information diffusion in Social media (say Twitter).
Search on networks, exhaustive network search, guided network search, network navigation; network visualization and semantic zooming.
Temporal network, Multilayer networks, Interdependent networks, Controllability of complex networks, Economic and financial network analytics
1. Networks: An Introduction, Oxford University Press, Oxford, 2010.
2. Evolution of Networks, Oxford University Press, Oxford, 2003.
3. The structure and function of complex networks, SIAM Review 45, 167-256, 2003.
4. Statistical mechanics of complex networks, Rev. Mod. Phys., 74(1), 2002.
5. Papers from the ACM and IEEE digital libraries.
Lectures : Mon(15:00-16:55), Tue(15:00-15:55)
Room # : CSE-119
Units : 3-0-0
Credits : 3
Contact : Room #322 (CSE), Phone 82358
Class attendance is mandatory! Any time your attendance falls below 85%, you have 100% chance of being de-registered irrespective of your class performance, CGPA etc!
If you are not present in the class (or do not respond), when I call by your name (may be randomly or sequentially....surprise!), you will lose 1.5 credit (instead of one) for the attendance for that week. If that happens twice in a week, you will be marked as absent for the entire week (i.e. you will lose all the three credits for attendance for that week).
Term project is the most significant component of this course. You have to form a team and each team will be assigned a term project and a mentor to execute. The project should have a definite and achievable objective. In this course, the progress of the term project will be evaluated twice; mid-term evaluation (in Feb) and final evaluation (in April).
Term project, Attendance, TA : 30
Mid-sem : 30
End-sem : 40
Slides just contain very informal outlines of the topics; details will be discussed in the class.
Graph Theory Basics (Resource 1, Resource 2)
General Reference: Introduction to Network Science
1. Introduction (Paper).
2. Network Analysis (Paper1, Paper2, Paper3)
3. Social Cohesivity(Paper1, Paper2, Paper3, Paper4)
4. Community Detection (General reference, Paper1, Paper2, BFS1, BFS2, Radicchi, K-L, Louvain, Assortative mixing, Clique percolation, Spectral Bisection1, Spectral Bisection2, Spectral Bisection-Examples)
5. Random graph (Paper1, Paper2)
6. Growth Models (Paper1, Paper2)
7. Epidemics models (Paper1)