Back
CS60078 Complex Networks
(Spring Semester 2022)
Teaching Assistants
Arpan Dam ARPANDAM1 [AT] gmail.com
Rima Hazra itsrima.iitkgp [AT] gmail.com
Notices
06.04.2022 The End-Sem Exam has been scheduled on April 12 (Tue), during 8.00am-10.00am.
06.04.2022 Final Term project presentation on April 14 (Thu), at 18.30.
01.03.2022 Extra (doubt clearing) class on April 5 at 8.00pm.
01.03.2022 Mid-Term project presentation on March 6 (Sun), at 18.30.
15.02.2022 The First Test has been scheduled on Feb 22 (Tue), during 8.30am-9.45am.
19.01.2022 Term project option submission deadline : Jan. 24 EOD (Hard deadline)
14.01.2022 Term project group submission deadline (of size 4) : Jan. 20 EOD (Hard deadline)
02.01.2022 First class: Jan 10, 2022, Monday. Venue: Microsoft Teams, Time: 11.00am.
Course outline
General Information
Lectures
Evaluation
Assignments
Course outline
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 graphs and mathematics. The outline of the course is given below
Syllabus
Introduction
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
Random Graphs
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
Social Network
Homophily, Cohesiveness, Cliques, Clans, Clubs, Plex, Equivalence of ties, Ego-centric networks, Cascade formation and information diffusion in Social media (say Twitter).
Applications
Search on networks, exhaustive network search, guided network search, network navigation; network visualization and semantic zooming.
Advanced topics
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.
General Information
Lectures : Mon(11:00-11:55), Tue(8:00-9:55)
Room # : Microsoft Teams
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!
Attendance Policy
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
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).
Evaluation
Term project, Attendance : TBD
Continuous Evaluation: TBD
Lectures
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. Equivalence & Social Cohesivity (Paper1, Paper2, Paper3, Paper4)
4. Community Detection (General reference, Paper1, Paper2, K-L, Louvain).
5. Random graph (Paper1, Paper2)
6. Growth Models (Paper1)