Social networks, auctions, and stock-markets appear to be very different phenomena, but they share a common foundation—the science of networks. The learning goal: to provide a broad, accessible introduction to the foundations of network science. We shall draw on ideas from mathematical sociology, and from game theory to understand strategic interaction over networks. We shall develop algorithms to identify network properties, and models for explaining network dynamics, including viral behavior.
Prerequisites: CS 225, CS 173, one of (MATH 225 or MATH 257 or MATH 415 or MATH 416 or ASRM 406), CS 361.
Meeting Times and Location: Wednesdays and Fridays 12:30pm--1:45pm. 7th floor, classroom (Chicago), 1404 Siebel. (Urbana); Zoom link links on Canvas
Prof. Hari Sundaram, hs1@illinois.edu, Office hours: Wednesdays 10am-11am, Online
Fall 2025 TAs: Agam Goyal, agamg2@illinois.edu, and Yian Wang, yian3@illinois.edu
You can find the join codes for Campuswire and Gradescope on Canvas.
This is a hybrid, flipped, class, taught across two locations: Urbana and Chicago. When I am in person in Chicago on Wednesdays, Urbana students should come to Room 1404 in Siebel. We'll connect the classrooms via Zoom. I'll be in Urbana on Fridays roughly every two weeks, and the other Friday class will be in-person (Urbana students should go to Siebel 1404 to work with the TAs; Chicago students will work with me). In this flipped class, students shall watch pre-lecture videos that cover essential ideas (available on canvas) and then complete in-class worksheets, working in small groups.
This class focuses on students learning by doing — students will learn key ideas by work on worksheets in class and though short homeworks, quizzes and long homework assignments. Note: late assignments are not accepted.; see the late submissions policy below.
Four credits students have the opportunity to dive deeper into the topics discussed in class through research survey on a topic related to the class or by developing a functional design prototype for an app (e.g., on Figma). Regardless of the project type, the instructor will enforce work parity across all projects. For the literature review, the expectation is that the review should be of publishable quality at a journal. For the system-building project, the expectation is that the functional prototype is mature and ready to be put into development. Here are two examples each of past projects that were lit reviews [Review 1], [Review 2] or app development projects [App 1], [App 2].
Use of Generative AI technologies is prohibited in this class. If you use generative AI to summarize papers or generate responses to questions, for example, you are not reflecting on the ideas in the paper and developing new ideas. It is critical that the work that you submit in response to class-related assessments (e.g., long homework, project, short and long homework and quizzes), is your own. Tools for grammar, rephrasing your written text and spell checks are allowed.
| Type | Number | Points (3-credit) | Points (4-credit) | Location |
|---|---|---|---|---|
| Short Homework (best 10 out of 12) | 10 | 10 | 10 | PrairieLearn |
| Short Quiz (best 5 out of 6) | 5 | 40 | 40 | CBTF |
| Long Homework | 2 | 40 | 50 | Gradescope |
| Class Participation | 29 | 10 | 10 | In Class |
| Final Project, Report (25) + Presentation (25) (4 credit students) | 1 | 0 | 50 | Gradescope |
| Final | 1 | 40 | 40 | CBTF |
| Total | 140 | 200 |
The grade cutoffs are (lower end of the range is shown for each grade; the upper bound is below the next higher grade):
A+: ≥ 98, A ≥ 90, A- ≥ 85, B+ ≥ 80, B ≥ 75, B- ≥ 70, C+ ≥ 65, C ≥ 60, C- ≥ 55, D ≥ 45, E ≥ 35, F ≤ 35
The scores will be rounded upwards and then the grade will be assigned. So for example, a score of 89.4 would be rounded to 90 and receive an A.
| Lecture Location | Class Date | Topic | Lesson | Worksheets | Short Homework | CBTF Quiz date | Long Homework |
|---|---|---|---|---|---|---|---|
| Chicago | Wed, Aug 27, 2025 | Introduction | Lesson #0 | Worksheet #0 | |||
| Urbana | Fri, Aug 29, 2025 | ties, triads and holes (chapter 3) | Lesson #1 | Worksheet #1.1 | |||
| Chicago | Wed, Sep 3, 2025 | structural balance (chapter 5) | Worksheet #1.2 | ||||
| Online | Fri, Sep 5, 2025 | homophily (chapter 4) | Worksheet #1.3 | S-HW #1 | |||
| Chicago | Wed, Sep 10, 2025 | Introduction to Game Theory (Chapter 6) | Lesson #2 | Worksheet #2.1 | |||
| Urbana | Fri, Sep 12, 2025 | Game Theory Contd. (Chapter 6) | Worksheet #2.2 | S-HW #2 | |||
| Chicago | Wed, Sep 17, 2025 | Introduction to Auctions (Chapter 9) | Lesson #3 | Worksheet #3.1 | Quiz (#1): Tue, Sep 16-Thu, Sep 18, 2025 | ||
| Online | Fri, Sep 19, 2025 | Auctions Contd. (Chapter 9) | Worksheet #3.2 | S-HW #3 | |||
| Chicago | Wed, Sep 24, 2025 | Matching Markets (Chapter 10) | Lesson #4 | Worksheet #4.1 | |||
| Urbana | Fri, Sep 26, 2025 | Matching Markets contd. (Chapter 10) | Worksheet #4.2 | S-HW #4 | L-HW #1 (Released) | ||
| Chicago | Wed, Oct 1, 2025 | No class, Own time | Lesson #5 skipped | No Worksheet | Quiz (#2): Tue, Sep 30-Thu, Oct 2, 2025 | ||
| Online | Fri, Oct 3, 2025 | No class, Own time | No Worksheet | No Short Homework | |||
| Chicago | Wed, Oct 8, 2025 | Introduction to Web (chapter 13) and Web search (chapter 14) | Lesson #6 | Worksheet #6.1 | |||
| Urbana | Fri, Oct 10, 2025 | Web search contd. (Chapter 14) | Worksheet #6.2 | S-HW #6 | Qualitative L-HW#1 due | ||
| Chicago | Wed, Oct 15, 2025 | Introductions to Sponsored Search Markets (chapter 15) | Lesson #7 | Worksheet #7.1 | Quiz (#3): Tue, Oct 14-Thu, Oct 16, 2025 | ||
| Online | Fri, Oct 17, 2025 | Sponsored search contd. (chap. 15) | Worksheet #7.2 | S-HW #7 | L-HW #2 (Released), (L-HW #1 due) | ||
| Chicago | Wed, Oct 22, 2025 | Random Graphs Introduction (Instructor Notes) | Lesson #8 | Worksheet #8.1 | |||
| Urbana | Fri, Oct 24, 2025 | Random Graphs contd. | Worksheet #8.2 | S-HW #8 | |||
| Chicago | Wed, Oct 29, 2025 | Power Laws (Chapter 18) | Lesson #9 | Worksheet #9.1 | Quiz (#4): Tue, Oct 2-Thu, Oct 4, 2025 | ||
| Online | Fri, Oct 31, 2025 | Power Laws contd. (Chapter 18) | Worksheet #9.2 | S-HW #9 | Qualitative L-HW#2 due | ||
| Chicago | Wed, Nov 5, 2025 | Community Discovery (Instructor Notes) | Lesson #10 | Worksheet #10.1 | |||
| Urbana | Fri, Nov 7, 2025 | Community Discovery contd. | Worksheet #10.2 | S-HW #10 | L-HW #2 due | ||
| Chicago | Wed, Nov 12, 2025 | Network Effects Introduction (chapter 17) | Lesson #11 | Worksheet #11.1 | Quiz (#5): Tue, Nov 11-Thu, Nov 13, 2025 | ||
| Urbana | Fri, Nov 14, 2025 | Network effects contd. (chapter 17) | Worksheet #11.2 | S-HW #11 | |||
| Chicago | Wed, Nov 19, 2025 | Cascading behavior Intro (chapter 19) | Lesson #12 | Worksheet #12.1 | |||
| Online | Fri, Nov 21, 2025 | No class, Own time | No Worksheet | S-HW #12 | |||
| 11/22—11/30 | Thanksgiving break | ||||||
| Chicago | Wed, Dec 3, 2025 | Small World Phenomena (Chapter 20) | Lesson #13 | Worksheet #13.1 | Quiz (#6): Tue, Dec 2-Thu, Dec 4, 2025 | ||
| Urbana | Fri, Dec 5, 2025 | Small World Phenomena Contd. (Chapter 20) | Worksheet #13.2 | S-HW #5 | Final Project Report / Presentations due (4-credit students) Mon, Dec 8, 2025 | ||
| Chicago (Last Day!) | Wed, Dec 10, 2025 | No class, Own time | No Worksheet |
| Class | Topic | Lesson | Broad Learning Goals | Learning Outcome #1 | Learning Outcome #2 | Learning Outcome #3 | |
|---|---|---|---|---|---|---|---|
| Wed, Aug 27, 2025 | Introduction | Lesson #0 | |||||
| Fri, Aug 29, 2025 | ties, triads and holes (chapter 3) | Lesson #1 | Be able to appreciate: the role of ties in information diffusion; how tie asymmetry affects persuasion Understand how tie strength is manifest in observed behavior on Social and Communication Networks | Students will identify nodes in example graphs that violate strong triadic closure property | Students will be able to compute node properties including node clustering coefficients as well as identify essential graph elements including bridges and local bridges in graphs | Students will be able to prove that local bridges attached to nodes that satisfy the strong triadic closure property in a graph must be weak ties | |
| Wed, Sep 3, 2025 | homophily (chapter 4) | Understand homophily and mechanisms for its existence. Selection and Socialization mechanisms are generically confounded in observational social network data Spatial segregation can arise out of weak preferences. | Students will change the degree of homophily in example graphs, by adding or removing edges and vertices | Students will be able to prove that we cannot dis-entangle homophily from influence in observational data. | Students will apply Schelling’s model with different mobility thresholds to example spatial graphs and evaluate degree of segregation. | ||
| Fri, Sep 5, 2025 | structural balance (chapter 5) | Understand that structural balance is both a local and a global property Understand evolution of structural balance Understand how to extend structural balance theory to non-complete graphs | Students will identify triangles in example graphs that violate structural balance | Students will be able to prove the structural balance theorem | Students will analyze non-complete, signed graphs to determine if they are balanced | ||
| Wed, Sep 10, 2025 | Introduction to Game Theory (Chapter 6) | Lesson #2 | Be able to identify essential elements of Game Theory Understand the differences between dominant strategies, best-responses and Nash equilibria Understand the different kinds of welfare | Students will identify best-responses, dominant strategies in example payoff matrixes | Students will determine pure or mixed Nash equilibria in example payoff matrixes | Students will identify strategies that are either Pareto-optimal or which maximize social welfare in example payoff matrixes | |
| Fri, Sep 12, 2025 | Game Theory Contd. (Chapter 6) | ||||||
| Wed, Sep 17, 2025 | Introduction to Auctions (Chapter 9) | Lesson #3 | Understand the differences and equivalencies between different auction types Understand differences between mechanisms and games Know if an auction has a dominant strategy | Students will be able to prove that bidding true value is the dominant strategy in a second priced auction | Students will be able to show that degree of shading in first-price auctions depends on the number of participants | Students will be able to determine optimal reserve price in a second priced auction | |
| Fri, Sep 19, 2025 | Auctions Contd. (Chapter 9) | ||||||
| Wed, Sep 24, 2025 | Matching Markets (Chapter 10) | Lesson #4 | Be able to use bi-partite graphs to represent a buyer-seller market Know the central role of constricted sets in preventing maximal matching Understand the importance of matching in social welfare | Students will be able to identify constricted sets in example graphs | Students will be able to construct that a preferred seller graph given buyer valuations and seller prices. | Students will be able to construct market clearing prices in an example buyer-seller graph. | |
| Fri, Sep 26, 2025 | Matching Markets contd. (Chapter 10) | ||||||
| Wed, Oct 1, 2025 | Bargaining in Networks (Chapter 12) | Lesson #5 | Understand that power-asymmetries may arise out of network structure Understand the importance of an outside option in bargaining | Students will be able to identify nodes in simple graph that exhibit limited, weak or strong power | Students will be able to determine the bargaining outcome across an edge using Nash Bargaining Solution. | ||
| Fri, Oct 3, 2025 | Bargaining in Networks (Chapter 12) | ||||||
| Wed, Oct 8, 2025 | Introduction to Web (chapter 13) and Web search (chapter 14) | Lesson #6 | Know that the Web is a large directed graph, with several strongly connected components Understand that searching the Web is difficult because of: polysemy\sidenote{same word has different meanings}; synonymy\sidenote{different words mean the same thing}; the large number of authors; and the dynamic nature of web content. The key idea behind web search is recursive: a web page's importance lies in its ability to point to useful web pages, and that a page's utility depends on the number of important pages that point to it. | Students will be able to identify strongly connected components in example directed graphs | Students will be able to compute the hub and authority scores in example directed graphs by applying the HITS algorithm. | Students will be able to compute the PageRank scores in example directed graphs by applying the PageRank algorithm. | |
| Fri, Oct 10, 2025 | Web search contd. (Chapter 14) | ||||||
| Wed, Oct 15, 2025 | Introductions to Sponsored Search Markets (chapter 15) | Lesson #7 | Know the role of Sponsored search advertising in facilitating free access to services, including search, and social media. Understand the importance of auctions for efficiently allocating advertising slots to prospective advertisers. Know that VCG auctions are incentive-compatible, but widely used GSP auctions are not. | Students will be able to compute costs of each ad slot in an example auction. | Students will be able to compute the harm that a participant causes by participating in a VCG auction. | Students will be able to identify the assignments of slots to advertisers in a GSP auction. | |
| Fri, Oct 17, 2025 | Sponsored search contd. (chap. 15) | ||||||
| Wed, Oct 22, 2025 | Random Graphs Introduction (Instructor Notes) | Lesson #8 | Know how Erdös-Réyni (E-R) family of random graphs are parameterized. Know different properties to characterize Erdös-Réyni family of random graphs ; clustering coefficient; degree distribution; diameter. Know that Erdös-Réyni family of random graphs undergo phase transitions resulting in a giant component. | Students will be able to compute the degree distribution of an Erdös-Réyni graph when $np = \lambda$, for large $n$. | Students will be able to show that the diameter of an Erdös-Réyni graph is $O(\frac{\log n}{\log z})$, where $z=(n-1)p$. | By examining example graphs, students will be able to reason about the value of $p$ in relation to the phase transition point probability. | |
| Fri, Oct 24, 2025 | Random Graphs contd. | ||||||
| Wed, Oct 29, 2025 | Power Laws (Chapter 17) | Lesson #9 | Know how large scale networks exhibit Power-law like distributions and are not well described by Erdös-Réyni family of random graphs. Power-law distributions can emerge from simple preferential attachment (i.e., ``rich get richer'') processes. Know that scaling laws appear in a variety of contexts. | Students will be able to derive basic properties of a Power-law distribution. | Students will be able to compute the exponent of a Power-law distribution given data. | Students will be able to show the preferential attachment process leads to a power-law | |
| Fri, Oct 31, 2025 | Power Laws contd. (Chapter 17) | ||||||
| Wed, Nov 5, 2025 | Community Discovery (Instructor Notes) | Lesson #10 | 1. Know that community discovery aims to identify groups of individuals consistent with prior work on homophily, triadic-closure and weak ties. 2. That algorithms for discovering communities are part of a larger family of graph partitioning algorithms. | Students will be able to compute the betweenness centrality measure in an undirected graph. | Students will be able to compute the partition quality using modularity. | ||
| Fri, Nov 7, 2025 | Community Discovery contd. | ||||||
| Wed, Nov 12, 2025 | Network Effects Introduction (chapter 17) | Lesson #11 | 1. Know what externalities are. 2. Intrinsic interest in a good along with population effects, that is multiplicative benefits from a fraction of the population adopting the good, can cause rapid adoption of the good. | Students will be able to identify the market equilibrium when there are no population effects. | Students will be able to compute the market equilibrium when there are intrinsic and population effects. | ||
| Fri, Nov 14, 2025 | Network effects contd. (chapter 17) | ||||||
| Wed, Nov 19, 2025 | Cascading behavior Intro (chapter 19) | Lesson #12 | Know the linear threshold model of behavior spread in a social network. | Given payoffs of two behaviors A, B and a graph, and locations of initial adopters of the superior behavior A, students will be able to determine how the behavior A spreads in the graph by applying the linear threshold model. | The students will be able to identify the cascade capacity of an arbitrary graph. | The students will determine how a superior behavior spreads when nodes in a social network can be bi-lingual. | |
| Fri, Nov 21, 2025 | Cascading behavior contd. (chapter 19) | ||||||
| 11/21/2020-11/29/2020 | Thanksgiving break | ||||||
| Wed, Dec 3, 2025 | Small World Phenomena (Chapter 20) | Lesson #13 | Know that short paths are in abundance in social networks and that individuals can efficiently discover them through decentralized search. | Be able to reason the importance of random links in reducing the diameter. | Be able to reason about the presence of attribute that acts as information gradient that allows for efficient myopic search. | Prove that when the probability of random links between nodes 𝑢, 𝑣 encodes distance information as in$p(u,v) \propto d(u,v)^{-q}$, the social network supports efficient myopic search. | |
| Fri, Dec 5, 2025 | Small World Phenomena Contd. (Chapter 20) | ||||||
| Wed, Dec 10, 2025 | Voting (Chapter 22), Summary | Lesson #14 | 1. Know that we can compute accurate aggregates from crowd estimates, provided there is cognitive diversity and independence of observations. 2. Understand the role of signaling in markets with asymmetric information. | Be able to compute the state prices in horse racing and in the stock market. | Be able to reason about the self fulfilling expectations equilibria in markets with asymmetric information. |
All assignments are due at the date and time marked for the Assignments. Late submissions will not be accepted except in the case of documented emergencies or religious absences approved in advance. If you have any questions about the policies, please ask the instructor.
The University of Illinois at Urbana-Champaign Student Code should also be considered as a part of this syllabus. Students should pay particular attention to Article 1, Part 4: Academic Integrity. Read the Code at the following URL:http://studentcode.illinois.edu/ Also, read the CS honor code here.
Academic dishonesty may result in a failing grade. Every student is expected to review and abide by the Academic Integrity Policy. Ignorance is not an excuse for any academic dishonesty. It is your responsibility to read this policy to avoid any misunderstanding. Do not hesitate to ask the instructor(s) if you are ever in doubt about what constitutes plagiarism, cheating, or any other breach of academic integrity.
Illinois law requires the University to reasonably accommodate its students' religious beliefs, observances, and practices in regard to admissions, class attendance, and the scheduling of examinations and work requirements. You should examine this syllabus at the beginning of the semester for potential conflicts between course deadlines and any of your religious observances. If a conflict exists, you should notify your instructor of the conflict and request appropriate accommodations. This should be done in the first two weeks of classes.
All members of the Illinois Computer Science department - faculty, staff, and students - are expected to adhere to the CS Values and Code of Conduct. The CS CARES Committee is available to serve as a resource to help people who are concerned about or experience a potential violation of the Code. If you experience such issues, please contact the CS CARES Committee. The instructors of this course are also available for issues related to this class.
To obtain disability-related academic adjustments and/or auxiliary aids, students with disabilities must contact the course instructor and the Disability Resources and Educational Services (DRES) as soon as possible. To contact DRES, you may visit 1207 S. Oak St., Champaign, call 333-4603, email or go to this URL. If you are concerned you have a disability-related condition that is impacting your academic progress, there are academic screening appointments available that can help diagnosis a previously undiagnosed disability. You may access these by visiting the DRES website and selecting “Request an Academic Screening” at the bottom of the page.
Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.
Counseling Center: 217-333-3704, 610 East John Street Champaign, IL 61820
McKinley Health Center: 217-333-2700, 1109 South Lincoln Avenue Urbana, IL 61801
The University of Illinois is committed to combating sexual misconduct. Faculty and staff members are required to report any instances of sexual misconduct to the University’s Title IX Office. In turn, an individual with the Title IX Office will provide information about rights and options, including accommodations, support services, the campus disciplinary process, and law enforcement options.
A list of the designated University employees who, as counselors, confidential advisors, and medical professionals, do not have this reporting responsibility and can maintain confidentiality, can be found here
Other information about resources and reporting is available here:Any student who has suppressed their directory information pursuant to Family Educational Rights and Privacy Act (FERPA) should self-identify to the instructor to ensure protection of the privacy of their attendance in this course. See https://registrar.illinois.edu/academic-records/ferpa/ for more information on FERPA.