The Ohio State
University
Department of Computer Science and Engineering
CSE 5245: Introduction to Network Science
Spring 2018, TTH
2:20-3:40, DL480
Introduction to Network Science; Global and Local Network
Measures; PageRank; Community Discovery
Algorithms; Network Models; Understanding the role of network analysis
in Web and Social network applications
Level
and Credits
Prerequisites:
Please note that inspite of the title word
“Introduction” this will be a somewhat advanced class involving
paper readings. Ideally students
should be completely comfortable with topics covered in the following courses:
- Discrete
Mathematics and Linear Algebra
- Databases
- Algorithms
- Data Mining
Instructors:
Dr. Srinivasan Parthasarathy, DL 691, srini@cse.ohio-state.edu;
Teaching
Assistant: Yu Wang, DL 686, wang.5205@osu.edu;
Office Hours and Locations:
Srinivasan Parthasarathy,
Thursdays 1-2 PM, Fridays by appointment
Yu Wang, Tuesdays 1-2 PM; Wednesdays 11-12 (noon), or
Mondays by appointment
Objectives
·
Familiarity with network science as a discipline
·
Mastery over major macro- and micro- metrics used to
describe various networks.
·
Mastery over key community discovery algorithms
·
Familiarity with generative models for networks and various
network analysis tools.
·
Mastery of the role of network science in WWW and social
network applications
Texts
(for reading, free for OSU students)
- First five chapters of the book by
D. Easley and J. Kleinberg.
Tentative
Grading Plan (Subject to revision)
Assignments and Annotated
Bibliographies
|
35%
|
Midterm I: TBD
|
25%
|
Project and Final
Presentation: TBD
|
40%
|
Lecture
Notes (note I will be using the blackboard liberally)
·
Minwise Hashing
(adapted from authors of MMD book, from DM class) – standalone lecture,
something we will use later – covered by TA.
·
Lecture 1 (adapted from various authors –
citations in slides)
·
Lecture 2
·
Lecture 3 (adapted from various authors)
·
Lecture 4 (community discovery). Adapted from: http://arxiv.org/abs/0906.0612 .
·
Lecture 5 (graph models)
·
Lecture 6 (an introduction to cascades)
Homework and Lab Assignments: Given the hands-on, problems
assigned for this course project grading will be based on effort, novelty, of
approach and clarity of analysis. Reports should be concise and to the point and bereft of
spelling and grammatical errors. Also a site of
interest in general for this class is kdnuggets.com
. You can use any publicly available software for these assignments or
choose to implement your own.
1.
Reading
and summarization assignment (individual): Read and
summarize the following two papers (which follow along with the lectures). Each
summary should be about a page
in length (11 point font) and should concisely articulate the key points of the
paper and a critical reflection of the paper in today’s day and age
– applies specifically to the second paper). See additional notes on what constitutes
a good summary below. (Due
date: January 30 2018, in class)
2.
Lab
assignment (team
of two) (Due date: February 4 2018, via submit cmd)
3.
Assignment
3 (individual): All exercises from the Easley-Kleinberg book (Due date: Feb20th in class)
Exercises: 2.5.1, 2.5.2, 3.7.2, 3.7.3, 3.7.4, 3.7.5, 5.6.1, 5.6.2 and 5.6.3
Extra credit: 2.5.3, 5.6.4
4.
Lab
assignment (team
of two) (Due date March 11 th (extended) 2018, via submit cmd)
Paper Readings and Summaries: Each group will introduce a topic (30 minute
presentation followed by 10 minutes of Q&A). We will discuss 2 papers per
class. Each group will have to explain and defend what the paper says, as well
as present weaknesses and shortcomings as theysee
fit. The rest of the class will be expected to contribute to the discussion as
well, and there will be some points assigned for class participation. Ideally,
criticisms should be constructive in nature, including the identification of
alleviating solutions. Once a paper has been discussed in class you will be expected
to compile an annotated bibliography covering all eight papers and submit this
to me by the end of the semester. This part of the task (annotated
bibliography) is an individual assignment and serves as a take-home final exam
(to be turned in the week of finals week). The best time to compile this is
to do it as soon as possible after the discussion in class. That is when you
will have all the points covered in class. Feedback forms to help you with this process can be
downloaded here
[The presentation elements of the feedback forms help with peer
evaluation].
Paper Presentation Schedule:
S. Parthasarathy
January
2018