Syllabus for 22C:196 Social Networks: Models, Algorithms, and Applications

Instructors: Sriram V. Pemmaraju and Alberto M. Segre
SVP Coordinates: 101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
AMS Coordinates: 14D MLH, alberto-segre@uiowa.edu, 319-335-1713
Office Hours: SVP: TBA and AMS: by appointment
Course webpage: www.cs.uiowa.edu/~sriram/196/spring12

In this course we will study the common set of tools and techniques that have emerged over the last decade or so for the modeling and analysis of social, technological, and biological networks and the processes that interact with these networks. The main themes of the course include (i) random graph models for real-world networks, (ii) the spread of information, disease, influence, etc., on networks, (iii) models and algorithms for web search and sponsored search, and (iv) game-theoretic approach to interaction on networks. The course aims to bring together advances from different disciplines: computer science, mathematics, statistics, physics, economics, and sociology and present them in a manner that students with basic CS background and some mathematical maturity can appreciate.

Prerequisite
Undergraduate algorithms (22C:31 or equivalent) and a probability and statistics course (equivalent of 22C:120 or 22C:130). If you do not have these prerequisites, but still want to take the course, please talk to one of the instructors.

Textbook
Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg, Cambridge University Press, 2010.

We will follow this textbook closely for some topics. For other topics, we will use material from the following excellent book: Networks: An Introduction by Mark Newman, Oxford University Press, 2010.

Besides these books we will study a number of papers during the semester. These appear under "Bibliography" in the "List of Topics" document (see below).

List of Topics
See List of Topics for a tentative plan for the course. This is subject to change based on time constraints and student interest.

Grading
Plus/Minus grading will be used for the course. There are two components that will determine your grade.

• Scribe Notes: 30% Two students will be assigned to be "scribes" for each week. The "scribes" will be responsible for taking careful notes in the two lectures for that week, typing these up into a latex document, and submitting them to the instructors by the end of Monday of the following week. The "scribes" should make sure that the notes are typo-free and coherent and can serve as a good reference for what transpired in class during that week. Scribe notes will be posted on the course page as soon as they become available. Depending on how many students eventually enroll in class, each student will be a "scribe" for 2-3 weeks. We will publish a "scribe" schedule on the course webpage.

• Paper: 70% Each student is responsible for a substantial research paper that will be developed over the course of the semester. We will run the paper submission and evaluation process in the style of a typical CS conference. About 3 weeks into the semester you will enter into a "contract" with the instructors on the topic of your research paper and the conference or journal your paper is targeted for. Your target conference or journal will dictate the style and size of your paper. Soon we will post a candidate list of topics that interest us. You can choose one of these or make a pitch for a topic not on the list. About 7 weeks into the semester you will submit a first draft of your paper to the instructors for review. You will have 3 weeks to respond to the instructors reviews and about 10 weeks into the semester you will be required to submit an anonymous research paper for double-blind reviewing by a panel of your classmates. Assuming a review panel of size 3 for each paper, each student will have to serve on review panels for 3 papers. You will then have the last 4 weeks of the semester to respond to the reviews your paper received and submit a final version of your paper on the last day of classes. During the finals week we will run a "conference" in which you will make a 10 minute presentation on your paper.

  During the semester you will graded on various aspects of this process including of course the quality of your paper and presentation, but also on the quality of your reviews and how you responded to constructive criticism of your paper. Ideally, the research paper that will emerge from this process will be submitted to an actual conference during or immediately after the semester. Just as in a typical conference there will be no opportunity to make late submissions.

Course Home
This course is run by the Computer Science department which is part of the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

Students with disabilities
We would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact us as soon as you can.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone the work of someone else as your own. This also applies to code or other material that you might find on the internet. If you are unclear about what constitutes academic dishonesty contact your professor or consult the policy in the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Student Complaints
If you have any complaints or concerns about how the course is being run please feel free to come by and talk to us. Since one of the instructors is the department chair, you should see Prof. Jim Cremer (101P MacLean Hall, 319-321-1893, james-cremer@uiowa.edu), if you have concerns about the course that you do not feel comfortable discussing with the instructors. Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

Classroom Etiquette
Showing up to class late, leaving your cell phone ringer on, etc. can be quite distracting to the instructor and fellow students. If you are in class, it is your responsibility to pay attention and to make sure that you are not doing anything that makes it harder for fellow-students to pay attention. When disruptive activity occurs, a University instructor has the authority to determine classroom seating patterns and to request that a student exit immediately for the remainder of the period. One-day suspensions are reported to appropriate departmental, collegiate, and Student Services personnel (Office of the Vice President for Student Services and Dean of Students).

University Statement on Sexual Harassment
Sexual harassment subverts the mission of the University and threatens the well-being of students, faculty, and staff. All members of the UI community have a responsibility to uphold this mission and to contribute to a safe environment that enhances learning. Incidents of sexual harassment should be reported immediately. See the UI Comprehensive Guide on Sexual Harassment for assistance, definitions, and the full University policy.

Reacting Safely to Severe Weather
In severe weather, class members should seek appropriate shelter immediately, leaving the classroom if necessary. The class will continue if possible when the event is over. For more information on Hawk Alert and the siren warning system, visit the Public Safety web site.