image of a large network

Network & Matrix Computations

David Gleich

Purdue University

Fall 2011

Course number CS 59000-NMC

Tuesdays and Thursday, 10:30am-11:45am

CIVL 2123

CS 59000-NMC Syllabus

Course information

Fall 2011
T-Th 10:30am-11:45am
CIVL 2123
http://www.cs.purdue.edu/homes/dgleich/nmcomp

Instructor

David F. Gleich
Lawson 1207
dgleich@purdue.edu
http://www.cs.purdue.edu/homes/dgleich

Office hours

Tentative office hours: Thursday 2:30-4:30pm

Description

This topics class will probe the intersection and relationship between problems stated on a network (a graph) and their solution, or approximation, via a matrix computation.

Selected topics will include

Prerequisites

This class is a graduate topics class. While there are no formal prerequisites, the class will favor students with additional preparation. Those without an appropriate background will likely find some of the material challenging. Students should be familiar with standard graph algorithms including shortest paths, spanning trees, etc; additionally, students should be familiar with standard matrix computations including solving linear systems, eigenvalue problems, and optimization problems including least-squares.

Goals and objectives

The major goal of this course is to describe network computations, including modern network analysis procedures and graph algorithms, by using the matrix paradigm. This paradigm simplifies and unifies the analysis and application of the methods to new data. Particular goals are:

Requirements

The formal requirements and percentage of the total course grade are:

Quizzes

These will be worth 10% of the total grade and are graded as taken/missed. Students can miss up to 5 quizzes with no penalty. Make sure you contact the instructor if you anticipate missing more than 5 quizzes due to any planned absenses.

References

There is no required text book. Instead, the course will proceed based on research papers as well as class notes.

Suggested

For those who wish a formal book, I highly recommend

Network Analysis: Methodological Foundations Ulrik Brandes (Eds.) This book is available via the doi: http://dx.doi.org/10.1007/b106453

Additional references

Other useful references will be listed on the web-page.

Policies

Conduct

Students are expected to maintain a professional and respectful classroom environment. In particular, this includes:

You may use any non-disruptive personal electronics during class. One exception is during in-class quizzes, for which personal electronics are prohibited.

Correspondence

Please feel free to email me with any questions, but please prefix all email titles with the string CS-59000 NMC: to aid in filtering email.

I will make every effort to respond promptly, however, replies could be delayed due to circumstances outside of my control. In particular, do not rely on a response between the hours of 8pm and 8am.

Please do not attempt to call, google chat, skype, facebook, or tweet with me without prior arrangement.

Assignment clarity

I expect all assignments to be legible and well-written. For this, I will suggest using a computer with LaTeX to prepare all submitted materials.

If you do not plan to use a computer and LaTeX to prepare solutions to homeworks, you must let me know.

Missing or late work

Except as discussed below, and or by prior arrangement, missing or late work will be counted as a zero.

Collaboration

Collaboration on homework is allowed. The final assignments must contain a list of all collaborators. However, students must prepare solutions individually. As an example of the ideal scenario, the following situation is permissible:

A group of students meets to develop the solution to a problem on a white board. Each student records individual notes from this problem solving meeting. All students then prepare solutions individually and without further collaboration. These solutions show the names of all members in the initial group.

Examples of collaborations that are not allowed include, but are not limited to:

Collaboration on the projects must be discussed with the instructor.

Computer codes

The assignments will involve producing computer codes. These need to be documented and written in accordance with best software engineering practices. Failure to follow this advice may result in solutions receiving zero points. Moreover, these should be prepared individually. Groups may discuss implementation strategies, algorithms, and approaches; but codes, like written homework solutions, must be prepared separately.

Grading

The anticipated grade ranges are:

These may be adjusted downward by up to 10% to achieve a reasonable grade distribution. They also may be minor upward adjustments.

Dishonesty

Behavior consistent with cheating, copying, and academic dishonesty is not tolerated. Depending on the severity, this may result in a zero score on the assignment, and could result in a failing grade for the class.

Purdue prohibits “dishonesty in connection with any University activity. Cheating, plagiarism, or knowingly furnishing false information to the University are examples of dishonesty.” (Part 5, Section III-B-2-a, University Regulations) Furthermore, the University Senate has stipulated that “the commitment of acts of cheating, lying, and deceit in any of their diverse forms (such as the use of substitutes for taking examinations, the use of illegal cribs, plagiarism, and copying during examinations) is dishonest and must not be tolerated. Moreover, knowingly to aid and abet, directly or indirectly, other parties in committing dishonest acts is in itself dishonest.” (University Senate Document 72-18, December 15, 1972)

Please review the Purdue’s guide to academic integrity

Attendance

Students are expected to be present for every meeting of the classes in which they are enrolled. Only the instructor can excuse a student from a course requirement or responsibility. When conflicts or absences can be anticipated, such as for many University sponsored activities and religious observations, the student should inform the instructor of the situation as far in advance as possible. For unanticipated or emergency absences when advance notification to an instructor is not possible, the student should contact the instructor as soon as possible by email, or by contacting the main office that offers the course. When the student is unable to make direct contact with the instructor and is unable to leave word with the instructor’s department because of circumstances beyond the student’s control, and in cases of bereavement, the student or the student’s representative should contact the Office of the Dean of Students.

Grief Absence Policy

Purdue University recognizes that a time of bereavement is very difficult for a student. The University therefore provides the following rights to students facing the loss of a family member through the Grief Absence Policy for Students (GAPS). GAPS Policy: Students will be excused for funeral leave and given the opportunity to earn equivalent credit and to demonstrate evidence of meeting the learning outcomes for misses assignments or assessments in the event of the death of a member of the student’s family.

Violent Behavior Policy

Purdue University is committed to providing a safe and secure campus environment for members of the university community. Purdue strives to create an educational environment for students and a work environment for employees that promote educational and career goals. Violent Behavior impedes such goals. Therefore, Violent Behavior is prohibited in or on any University Facility or while participating in any university activity.

Students with Disabilities

Purdue University is required to respond to the needs of the students with disabilities as outlined in both the Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1990 through the provision of auxiliary aids and services that allow a student with a disability to fully access and participate in the programs, services, and activities at Purdue University. If you have a disability that requires special academic accommodation, please make an appointment to speak with me within the first three (3) weeks of the semester in order to discuss any adjustments. It is important that we talk about this at the beginning of the semester. It is the student’s responsibility to notify the Disability Resource Center (http://www.purdue.edu/drc) of an impairment/condition that may require accommodations and/or classroom modifications.

Emergencies

In the event of a major campus emergency, course requirements, deadlines and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances beyond the instructor’s control. Relevant changes to this course will be posted onto the course website or can be obtained by contacting the instructors or TAs via email. You are expected to read your @purdue.edu email on a frequent basis.

Nondiscrimination

Purdue University is committed to maintaining a community which recognizes and values the inherent worth and dignity of every person; fosters tolerance, sensitivity, understanding, and mutual respect among its members; and encourages each individual to strive to reach his or her own potential. In pursuit of its goal of academic excellence, the University seeks to develop and nurture diversity. The University believes that diversity among its many members strengthens the institution, stimulates creativity, promotes the exchange of ideas, and enriches campus life.

Purdue University prohibits discrimination against any member of the University community on the basis of race, religion, color, sex, age, national origin or ancestry, marital status, parental status, sexual orientation, disability, or status as a veteran. The University will conduct its programs, services and activities consistent with applicable federal, state and local laws, regulations and orders and in conformance with the procedures and limitations as set forth in Executive Memorandum No. D-1, which provides specific contractual rights and remedies.

Schedule

The first class (23 August) will be rescheduled as the professor is on travel.

A tentative list of lectures follows. This list will evolve throughout the course.

  1. 25-Aug – Course syllabus discussion, Course overview,
  2. 30-Aug – Review of matrix computations: norms, linear systems, condition numbers
  3. 1-Sep – Review of matrix computations: sparse matrices, their storage and operation
  4. 6-Sep – Review of matrix computations: stationary iterative methods for sparse linear systems
  5. 8-Sep – Review of matrix computations: Krylov methods for large linear systems and eigenvalues
  6. 8-Sep – Makeup Review of network computations: connected components, shortest paths, minimum spanning trees
  7. 13-Sep – Matrix based network computations: degrees, triangles, and Reachability.
  8. 15-Sep – Markov chains
  9. 20-Sep – Markov chains
  10. 22-Sep – Markov chains
  11. 27-Sep – Network centrality
  12. 29-Sep – PageRank
  13. 4-Oct – PageRank
  14. 6-Oct – Localized centrality algorithms
    11-Oct – No class
  15. 13-Oct – PageRank 18-Oct – Rescheduled
  16. 20-Oct – PageRank
  17. 25-Oct – Spectral graph theory
  18. 27-Oct – Spectral graph theory
  19. 1-Nov – Spectral graph theory
  20. 3-Nov – Spectral graph theory
  21. 8-Nov – Jen Neville
  22. 10-Nov – Alex Pothen
  23. 15-Nov – Student presentations (30 mins each)
  24. 17-Nov – Reschedule
  25. 22-Nov – Student presentations (30 mins each)
  26. 24-Nov – No class (Thanksgiving)
  27. 29-Nov – Student presentations (30 mins each)
  28. 1-Dec – Student presentations (30 mins each)
  29. 6-Dec – Student project presentations (12 mins each)
  30. 8-Dec – Student project presentations

Makeup classes

Currently, the instructor is planning to miss two classes: 23 August and 8 November. These classes will be rescheduled. The tentative makeup times are September 1st from 11:45am-1pm and November 17th from 11:45-1pm. For these classes, the instructor will provide a pizza lunch.

Let the instructor know if these times will not work for you on the introductory survey

Changes

This syllabus is subject to change. Updates will be posted on the course website.