Back

CS60078 Complex Networks

(Spring Semester 2023)

Teaching Assistants
Arpan Dam ARPANDAM1 [AT] gmail.com
Sugandh Pargal sugandhpargal [AT] gmail.com
Burgula Pavani pavaniburgula99 [AT] gmail.com

Notices

10.04.2023 Final-Term project presentation on April 15 (Sat), at 18.30, Venue: CSE-126 (Conference Room).
27.02.2023 Mid-Term project presentation on March 3 (Friday), at 18.30, Venue: CSE-126 (Conference Room).
11.01.2023 Term project option submission deadline : Jan. 16 EOD (Hard deadline)
08.01.2023 Term project group submission deadline (of size 3) : Jan. 11 EOD (Hard deadline)
30.12.2022 First class: Jan 3, 2023, Tuesday. Venue: CS-107, Time: 4.00pm.

       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(14.00:00-15:00), Tue(16:00-18:00)
Room # : CSE-107
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, TA : 30
Mid-sem : 30
End-sem : 40

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, Assortative mixing, Clique percolation).
5. Random graph (Paper1, Paper2)
6. Growth Models (Paper1, Paper2,)
7. Epidemics models (Paper1)