CptS 591: Elements of Network Science — 2019 — Syllabus
Links: This syllabus in PDF Schedule Resources
Course Information
Credit hours: 3
Semester: Spring 2019
Meeting times and location: Tu, Th 12:00–13:15, Sloan 7
Course Website: CptS 591: Elements of Network Science | | Washington State University (wsu.edu)
The course website will be used to post relevant course material, including this syllabus, and course related resources. Additionally, the online portal OSBLE+ (plus.osble.org) will be used for posting lecture material, assignments, announcements, and messages, and for handling student submissions and instructor feedbacks.
Instructor Information
Assefaw Gebremedhin
Office: EME B43
Email: assefaw DOT gebremedhin AT wsu DOT edu
Homepage: www.eecs.wsu.edu/~assefaw
Office hours: Thursdays 3:00 — 4:30pm, or by appointment.
Course Description
This 3 credit, graduate-level course introduces fundamental elements of the emerging science of complex networks, with emphasis on social and information networks. Students will learn about mathematical and computational methods used to analyze networks, models used to understand and predict behavior of networked systems, and theories used to reason about network dynamics. Students will also be exposed to current research in the field, and they will be given an opportunity to explore a chosen topic through a semester project.
Topics to be covered include :
- Network structure, modeling and algorithms:
- Graph theory essentials; Basic network properties; Random graphs; Spectral graph theory; Centrality; PageRank; Hubs and Authorities; Graph similarity; Community detection; Signed networks and structural balance; Graph embeddings and representation learning;
- Network dynamics:
- Cascading behaviors; Information diffusion; Epidemics models; Influence maximization; The Small-world phenomenon;
- Temporal networks:
- Models and algorithms for analysis of time-varying networks.
Audience:
The course is suitable for graduate students in computer science, engineering, epidemiology, sociology, economics, mathematics, physics, and related fields.
Prerequisites:
Students are expected to have basic knowledge of algorithms (equivalent to completing an undergraduate algorithms course such as CptS 350), some programming experience (e.g. in Python, R, or C), and familiarity with basic linear algebra (e.g. solution of linear systems and eigenvalue/vector computation) and basic probability and statistics.
Learning Outcomes
At the conclusion of the course, students should be able to:
- Explain basic metrics and measures used to characterize networks
- Analyze a network using the various measures and a suitable network analysis software tool
- Discuss the strengths and weaknesses of random graph models
- Understand and apply key algorithms for link analysis (ranking), community identification, and network comparison
- Understand and apply models and theories used to reason about cascading behaviors, information spread, and decentralized navigation in networks
- Understand and explain the interdisciplinary nature of the area of network science
- Critique research papers in the area
- Apply knowledge gained in the course to carry out a project and write a scientific report
Course Work
The course consists of lectures (twice a week, 75 min each) and involves in-class quizzes, a set of assignments, one exam, and a semester project.
- Assignments (30%). There will be three assignments mostly spread through the first half of the semester. Assignments are to be completed and submitted individually.
- Semester Project (40%). Working in teams of two or three, students will complete a semester project. A semester project could take one of several forms: analysis of an interesting dataset using existing methods and software; comparison of existing methods and software tools in the context of a specific application; implementation of a new method; exploration of a chosen research topic.Each project will have required submissions at three different stages — the submissions are called Reaction Paper, Project Proposal and Final Report — and will culminate with an oral presentation in class.
- For the Reaction Paper part students will get to pick and read two closely related papers out of a list the instructor provides and write a short reaction paper summarizing and critiquing the two papers and identifying opportunities for further work. Project Proposal is a short document (2 or 3 pages long) that describes the proposed project and the tentative plan to carry it out. Ideally it is an outgrowth of the Reaction Paper component, but can also deviate from it. The outcome of the project will be a final report of about 8 to 12 pages long. Guidelines for writing the proposal and the final report will be provided at an appropriate time during the semester. A more complete project description detailing the various components will also be provided.
- The 40% weight of the semester project towards final grade is further broken down into its components as follows: Reaction Paper 5%, Project Proposal 5%, Presentation 5%, Final Report 25%.
- Quizzes (10%). There will be a few occasional quizzes (in-class or homework) throughout the semester.
- Mid-term Exam (15%). There will be one mid-term exam.
- Class Participation (5%). Students are expected to actively participate in class discussions and in scribing notes for select lectures.
Expectations for Student Effort
For each hour of lecture equivalent, students should expect to have a minimum of two hours of work outside class.
Grading
Letter grades will be given according to the following ranges:
A (93–100%), A- (90–92.99%), B+ (87–89.99%), B (83–86.99%), B- (80–82.99%), C+ (77–79.99%), C (70–76.99%), C- (67–69.99%), D (60–66.99%), F (less than 60%).
Books and Course Material
There is no required textbook for the course. Lecture notes, readings and related resources will be posted at the course website or the OSBLE page of the course as the course proceeds.
The following book will be used as a frequent reference:
- D. Easley and J. Kleinberg, Networks, Crowds and Markets, Cambridge Univ. Press, 2010.
The book is available on-line at Networks, Crowds and Markets book link.
Other related references include:
- M.E. J. Newman, Networks: An Introduction, Oxford University Press, 2010.
- U. Brandes and T. Erlebach (Eds.), Network Analysis: Methodological Foundations, Springer, 2005.
- This book is available online via the doi: Network Analysis book link
- A.L. Barabasi, Network Science, Network Science book link
- Keep checking this list as I expect to add more
Software:
The graph analysis package igraph will be used as the primary software resource. The package igraph is open-source and free.
Tentative Schedule Overview
| WEEKS | TOPICS | ASSIGNMENTS |
|---|---|---|
| 01 (Jan 08/10) | Introduction; Graph theory | Survey out |
| 02 (Jan 15/17) | Network properties | Survey due |
| 03 (Jan 22/24) | intro to igraph; Hands-on tutorial | Assignment 1 out |
| 04 (Jan 29/31) | Random graphs | |
| 05 (Feb 05/07) | Spectral graph theory | Assignment 1 due |
| 06 (Feb 12/14) | Centrality | Assignment 2 out |
| 07 (Feb 19/21) | PageRank; Hubs and Authorities | |
| 08 (Feb 26/28) | Graph embeddings and representation learning | Assignment 2 due |
| 09 (Mar 05/07) | Community detection; Semester project set-up | |
| 10 (Mar 12/14) | Spring Break | |
| 11 (Mar 19/21) | Graph similarity; Signed networks | Reaction paper due |
| 12 (Mar 26/28) | Cascading behaviors | Project proposal due |
| 13 (Apr 02/04) | Influence maximization; Epidemic models | Assignment 3 out |
| 14 (Apr 09/11) | Temporal networks | Assignment 3 due |
| 15 (Apr 16/18) | Wrap-up; Project presentations | |
| 16 (Apr 23/25) | Project presentations | |
| May 1 | Final project report due |
Policies
Conduct:
Students are expected to maintain a professional and respectful classroom environment. In particular, this includes:
- silencing personal electronics
- arriving on time and remaining throughout the class
Correspondence:
All class related correspondence with the instructor will be made via OSBLE. I will get an email notification when a message is sent to my Inbox or posted to the Dashboard, and will do my best to respond promptly. Students are encouraged to choose their OSBLE settings so that they get emails notifications when messages are sent or posted.
Attendance:
Regular attendance is required. While students may miss class for urgent reasons, repeated absences that are not cleared with the instructor will factor into the Class Participation portion of the semester grade.
Missing or Late Work:
Submissions will be handled via the OSBLE page of the course. Students are expected to submit assignments and reports by the specified due date and time. Submissions turned in up to 48 hours late will be accepted with a 10% grade penalty per 24 hours late. Except by prior arrangement, missing or work late by more than 48 hours will be counted as zero.
Academic Integrity:
Academic integrity is at the heart of all higher education philosophies. Adhering to academic integrity policies ensures that you provide yourself with the best education possible. Maintaining academic integrity assures you receive the credit you deserve for your ideas.
You are expected to know and understand Washington State University Academic Integrity Policies. Copying and plagiarism of other sources will result in an automatic 0 or F on the assignment. For a second offense, the student will receive an F as a final grade in this course, will not have the option to withdraw from the course and will be reported to the Office of Student Standards and Accountability. Cheating is defined in the Standards for Student Conduct WAC 504-26-010 (3). You can learn more about Academic Integrity on the WSU campus at academicintegrity.wsu.edu. Please also read this link carefully: EECS Academic Integrity Policy. Use these resources to ensure that you do not inadvertently violate WSU’s standard of conduct.
WSU’s AWARE Network:
As a student you have many responsibilities and obligations. One of the most important obligations that you may have is to your friends and peers at WSU. If you feel like one of your friends or peers is struggling with academics because of physical or mental health please inform the instructor and/or appropriate university personnel. For more information refer to aware.wsu.edu/.
WSU’s Campus Safety Plan:
Washington State University is committed to enhancing the safety of the students, faculty, staff, and visitors. It is highly recommended that you review the Campus Safety Plan (safetyplan.wsu.edu/) and visit the Office of Emergency Management web site (oem.wsu.edu/) for a comprehensive listing of university policies, procedures, statistics, and information related to campus safety, emergency management, and the health and welfare of the campus community.
WSU Classroom Safety:
Classroom and campus safety are of paramount importance at Washington State University, and are the shared responsibility of the entire campus population. WSU urges students to follow the “Alert, Assess, Act” protocol for all types of emergencies and the “Run, Hide, Fight” response for an active shooter incident. Remain ALERT (through direct observation or emergency notification), ASSESS your specific situation, and ACT in most appropriate way to assure your own safety (and the safety of others if you are able).
Please sign up for emergency alerts on your account at MyWSU. For more information on this subject, campus safety and related topics, please view the FBI’s Run, Hide, Fight video and visit the WSU safety portal.
Students with Disabilities:
Reasonable accommodations are available for students with a documented disability. If you have a disability and need accommodations to fully participate in this class, please either visit or call the Access Center (Washington Building 217; 509-335-3417) to schedule an appointment with an Access Advisor. All accommodations MUST be approved through the Access Center. For more information, consult the webpage accesscenter.wsu.edu or email at Access.Center@wsu.edu.
Important Dates and Deadlines:
Students are encouraged to refer to the WSU academic calendar often to be aware of critical deadlines throughout the semester. The academic calendar can be found at the academic calendar website.
Weather Policy:
For emergency weather closure policy, consult: alert.wsu.edu.
Changes:
This syllabus is subject to change. Updates will be posted on the course website.