Network Analysis

This course explores network analysis, a cross-disciplinary field that studies the structure and dynamics of complex systems. The course will cover the mathematical concepts of graph theory including the study of network structure, information flow dynamics and the processes through which we model the evolution of networks over time. The course will also introduce students to state-of-the-art tools and software used for network analysis, with a focus on efficiently processing very large graphs. The syllabus covers:

• Graph theory & mathematical modeling
• Network measures
• Graph algorithms, proofs based on network structure
• Information propagation - ranking algorithms, epidemic models, viral marketing
• Community detection, and clustering algorithms
• Practical considerations - working with large graphs, efficient frameworks, and visualizations

Syllabus: Download here
Class Time: MWF, 1:35pm - 2:40pm, Dodge 430
Class Forum: Campuswire (Group join code 6182)

Instructor

Raj Venkat Office: Meserve 303 r.venkatesaramani@northeastern.edu Office Hours: Mondays, after class To request appointments outside of office hours, click here. If you decide to swing by on a whim, and my office door is open, feel free to bug me.

Organization

Overview

In teaching a special topics course, I place a lot of emphasis on class participation. The goal is not for me to lecture at you for a whole semester. Rather, I think of this as an opportunity for you and me to discover new topics and applications and get familiar with the latest research in the field, together.

I expect students to come to class having gone through posted readings in advance. This will ensure that lecture time is used effectively to engage in deeper discussions and tailor the course to the class’s interests. I will lecture in a somewhat traditional format for the first 2–3 weeks to cover the basic theory and set the pace, but will then transition to a more discussion-driven classroom.

Later in the semester, we will spend some time discussing research papers, where students will take turns leading these discussions. I expect you to come to these lectures prepared with summaries of your understanding of the paper (it is okay to not understand every detail - I’m here to help with that), some open questions, and perhaps some examples of related work that you may have found along the way.

A strong background in linear algebra is recommended. We will be relying extensively on Python 3, learning many new packages; strong programming skills are a must.

Attendance Policies

While attendance is not formally recorded, in-class activities count toward 20% of your grade and are distributed throughout the semester. There is flexibility for occasional activities missed due to health concerns, emergencies, etc.; however, repeated or prolonged absence is bound to affect this portion of your grade.

Small classes are also an opportunity to work closely with your instructors, engage in deeper discussions, and receive personalized feedback to enhance your learning experience, and attendance is highly encouraged.

Support

In addition to being your instructor, I hope you also think of me as an advisor/mentor whom you can freely talk to for any reason1. I am open to questions about anything that has to do with your education, even if it does not strictly fall within the scope of CS4973. I strive to foster a nonjudgmental learning environment at all times, and I am never inconvenienced by a student reaching out for support.

Late Joiners

Please note that by joining the course late, you knowingly accept the responsibility of catching up on missed material and should not expect any preferential treatment or adjustments to deadlines. Please stop by my office hours, or book an appointment with me, and I will be more than happy to briefly review content and point you to the right resources.

Textbooks

Network Science by Albert-László Barabási and Social Media Mining by Reza Zafarani, Mohammad Ali Abbasi and Huan Liu are my primary sources. These books are freely available online and are excellent introductory texts on network science.

If you are interested in developing a deeper mathematical understanding of graph theory, I highly recommend Introduction to Graph Theory by Douglas B. West. I would be happy to lend students my copy for a week at a time when I am not using it actively.

Slides & Readings

Tentative schedule for the semester, subject to change based on class progress/interests. Slides, when used, will be uploaded after the lecture.

Date	Topic	Readings
6-Jan	Introduction, logistics
8-Jan	Overview, complex systems, examples, applications	https://networksciencebook.com/chapter/1
9-Jan	Definitions and Notations, Types of Graphs	https://networksciencebook.com/chapter/2
13-Jan	Representing Networks in Memory	https://rushter.com/blog/scipy-sparse-matrices
15-Jan	Native Python v/s NetworkX - BFS for connected components	https://snap.stanford.edu/data/index.html https://networkx.org/documentation/stable/tutorial.html
16-Jan	Visualizing network statistics	https://mathinsight.org/degree_distribution https://networkx.org/documentation/stable/auto_examples/drawing/plot_degree.html
20-Jan	NO CLASS - MLK JR DAY
22-Jan	Node Importance	https://www.socialmediamining.info/chapters/SMM-ch3.pdf
23-Jan	Node Importance (contd.)
27-Jan	Random Graph Models	https://networksciencebook.com/chapter/3
29-Jan	Random Graph Models (contd.)
30-Jan	The Small World Effect	https://snap.stanford.edu/class/cs224w-readings/milgram67smallworld.pdf https://arxiv.org/pdf/1111.4503
3-Feb	Scale Free Property	https://networksciencebook.com/chapter/4
5-Feb	Scale Free Property (contd)
6-Feb	Preferential Attachment	https://networksciencebook.com/chapter/5 https://www.nature.com/articles/nature11486
10-Feb	Preferential Attachment (contd.)
12-Feb	Paper Discussion 1	Generating preferential attachment graphs via a Pólya urn with expanding colors
13-Feb	Introducing Graphtool	https://graph-tool.skewed.de
17-Feb	NO CLASS - PRESIDENTS DAY
19-Feb	Evolving Networks	https://networksciencebook.com/chapter/6
20-Feb	Degree Correlations	https://networksciencebook.com/chapter/7
24-Feb	NO LECTURE - Work on Project
26-Feb	NO LECTURE - Work on Project
27-Feb	NO LECTURE - Work on Project
3-Mar	SPRING BREAK
5-Mar	SPRING BREAK
6-Mar	SPRING BREAK
10-Mar	Network Robustness	https://networksciencebook.com/chapter/8
12-Mar	Community Detection	https://networksciencebook.com/chapter/9 https://www.socialmediamining.info/chapters/SMM-ch6.pdf
13-Mar	Community Detection (contd.)
17-Mar	Viral Marketing & Epidemics	https://www.socialmediamining.info/chapters/SMM-ch7.pdf https://networksciencebook.com/chapter/10
19-Mar	Graph ML - Recommendations	https://www.socialmediamining.info/chapters/SMM-ch9.pdf
20-Mar	Graph Neural Networks
24-Mar	Paper Discussion 2
26-Mar	Paper Discussion 3
27-Mar	Paper Discussion 4
31-Mar	TBD
2-Apr	TBD
3-Apr	TBD
7-Apr	PRESENTATIONS
9-Apr	PRESENTATIONS
10-Apr	PRESENTATIONS
14-Apr	Wrap Up

Components & Grading

Grading will be based on the following split over deliverables:

• 3 Assignments, worth 30%
• Final Project, worth 50%
  (proposal, progress report, final report and presentation)
• In-class activities, worth 20%
  (missing a total of 2-3 lectures is fine, prolonged absence will affect this grade)

For in-class activities, I will communicate participation expectations on a regular basis, as activities will vary. I will record a ‘satisfactory’ or ‘unsatisfactory’ level of participation for each student at the end of each of the 15 weeks in the semester. If no activities are held during a certain week, then class participation counts towards this score. At the end of the semester, I will drop the three lowest scores, and your remaining participation score will be normalized to be worth 10%. The remaining 10% will be graded based on the research paper discussion(s) you lead. I will lead the first discussion as an example.

Final grades will be assigned based on the following scale (note open and closed intervals). Natural rounding will be used, i.e., percentages $\ge x.5$ get rounded up to the next integer, $x + 1$ (94.5 becomes 95, 94.4 does not).

A	[93, 100]
A-	[90, 93)
B+	[87, 90)
B	[82, 87)
B-	[80, 82)
C+	[77, 80)
C	[72, 77)
C-	[70, 72)
D+	[67, 70)
D	[62, 67)
D-	[60, 62)
F	[0, 60)

Class Policies

Homework Submissions & Grading

• All homework submissions and labs must be uploaded to Gradescope by 6:00 pm Eastern on the due date. Deadlines will typically be on a Friday. Written submissions must be in PDF format.
• All written solutions must be typed (i.e., no scans of handwritten assignments will be accepted). Scanned figures are only permitted where explicitly specified in the assignment instructions. Any such figures must be clear and perfectly legible.
• The use of LaTeX to typeset mathematical equations is highly encouraged. Overleaf is an excellent browser-based LaTeX editor with real-time compilation capabilities. Overleaf Professional is free to all Northeastern students.
• Discussions and collaborating on homework is encouraged! All I ask is that you disclose your collaborators, and write your solutions in your own words. Direct copying will, however, be treated as a violation of academic integrity and incur penalties.
• Grading: All grades will be released via Gradescope.
• Regrade Requests: All regrade requests must be submitted within 1 week of receiving your grade. Requests for all submissions must be submitted from within Gradescope. Requests submitted via email will almost certainly be missed.

Policy on the use of Generative AI

Generative AI may not be used to solve any assignments in this course. I also discourage relying on completion tools such as GitHub Copilot to get the most out of this course. Any indication of the use of generative AI in assignment submissions will be treated as an academic integrity violation, and penalties levied accordingly (see section below).
Generative AI tools, however, may be used to assist in understanding research papers - I often do this myself when a paper is overwhelming at first glance. Generative AI can help organize your reading by focusing on one section at a time, and acting as a ready reference for terms you may not be familiar with, with the following caveats:

• You must understand the content to a level where you can summarize and critique the paper, and contribute meaningfully to in-class discussions.
• Be cautious of mistakes that gen AI tools may make in this process. Hallucinations are very commonplace when trying to use tools like ChatGPT with mathematically heavy content; sometimes, the outputs are brazen lies.

Academic Integrity

• Please familiarize yourself with Northeastern University's Academic Integrity Policy.
• Any discussions of assignment material held with classmates must be clearly disclosed in the submission by all parties.
• The use of generative AI should be limited to understanding research papers. Generative AI may not be used for assignments. See section above.
• Any violation of academic integrity (as outlined by homework policies above) will result in the following penalties:
  • Academic penalties up to, and including, a grade of F for the course.
  • A report of the violation will be filed with OSCCR, where outcomes can range from warnings or academic probation to dismissal.
• Recognize that most violations are easily avoided by simply acknowledging any difficulties you may be having with the course and seeking help from your professor in a timely fashion. We're here to help you learn.
• Remember that I was a student until not very long ago. I am happy to talk to you about any issues you may be facing, and offer you my support and guidance. However, it is imperative that these conversations happen in the absence of an academic integrity violation. Once a violation is identified, I will have no choice but to report it in the interest of fairness.

Late Policy

• Assignment and problem set deadlines will typically be on Fridays at 6:00 pm Eastern. Students will receive an automatic extension until Sunday 6:00 pm, without penalty. Deadlines for submissions related to the final project are absolute, and no extensions will be provided for those.
• Treat the automatic extensions as a fallback for genuine emergencies - assignments in this course will take a significant amount of time to complete due to high runtimes. I prioritize my personal life on the weekends, and will likely be very slow to respond during the extension period.
• Requests to submit assignments after the late deadline due to last-minute difficulties will be ignored. It is your responsibility to ensure that the correct files are properly uploaded, submitted, and reflected in Gradescope well in advance of the deadline.
• Beyond the automatic late deadline, I will not grant further extensions, except in the case of limited and verifiable emergency situations, or University and DRC-sanctioned accommodations. It is imperative that you communicate with me early on when circumstances permit.
• In case you are close to the late deadline, and feel that you will be unable to submit an assignment in time, please reach out to me. I may not always be able to give you an extension, but I will certainly offer you the right resources to help you make the most of your assignment.

Classroom Environment

• Digital devices are permitted for note-taking purposes and to engage with course material such as lecture slides, or in-class activities as instructed. However, any use of laptops/tablets must not be disruptive to your classmates. No phones please.
• To create and preserve a healthy classroom atmosphere that facilitates teaching and learning, all participants share a responsibility in creating a civil, nonjudgmental, and non-disruptive forum for the discussion of ideas. Students are expected to conduct themselves at all times in a manner that does not disrupt teaching or learning.
• Your comments to others should be constructive and free from any harassing or disrespectful statements. You are welcome to disagree with other students and the instructor, but such disagreements need to be respectful, and based on facts, evidence and documentation (rather than prejudices and personalities).
• The instructor reserves the right to interrupt conversations that deviate from these expectations. Repeated unprofessional or disrespectful conduct will be treated as a violation of the Code of Student Conduct.