The Ohio State
University
Department of Computer Science and Engineering
CSE 5245: Introduction to Network Science
Spring 2015, TTH
2:203:40, Cockins Hall 312
http://www.cse.ohiostate.edu/~srini/674
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.ohiostate.edu;
Office Hours and Locations:
Srinivasan Parthasarathy TBD TTH @
DL691;
Aniket Chakrabarti, TBD MW @DL686=
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: (to be added during the quarter). Given the
handson, 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.
Proposals Due:
Wednesday March 2^{nd} 2016 by 5PM (sent to TA).
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 takehome
final exam (to be turned in by April 19. 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].
March 31 (first presentation): Community
Detection for Hierarchical Image Segmentation, Arnaud Browet
et al. Combinatorial
Image Analysis 2011. To be presented by LiangLiuJacobs.
April 5 (first presentation): Basketball
teams as strategic networks. J. Fewell et al. PLOS (one), 2012. To be
presented by GuptaKhanWitt
April 7 (first presentation): Structural
Inference in Uncertain Networks. T. Martin et al. ArXiV 2015. To be presented
by RamachandranKaushikWakefield.
S. Parthasarathy
March
2016