The Ohio State University
Department of Computer Science and Engineering

CSE 5245: Introduction to Network Science  

Spring 2015, TTH 2:20-3:40,  Cockins Hall 312

http://www.cse.ohio-state.edu/~srini/674


Description

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:

Instructors: Dr. Srinivasan Parthasarathy, DL 691, srini@cse.ohio-state.edu;

Teaching Assistant: Aniket Chakrabarti, DL 686, chakraba@cse.ohio-state.edu;

  
Office Hours and Locations: 

Srinivasan Parthasarathy  TBD T-TH @ 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)

Approximate Reading Plan (to be revised)

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 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.

Lab Assignment 1. Due Tuesday Feb 2 2016 11:59PM.  Example python file.

Lab Assignment 2. Due Tuesday Feb 16 2016 11:59PM

Proposals Due:  Wednesday March 2nd 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 take-home 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 29 (first presentation): RolX: structural role extraction & mining in large graphs, Keith Henderson et al. KDD 2012.  To be presented by Browning-Moosavi-Sun.

March 29 (second presentation):  Detecting Change Points in large Scale Structure of Evolving Networks. Peel et al. ArXiV 2014. To be presented by Bao-Guan-Wang.

March 31 (first presentation): Community Detection for Hierarchical Image Segmentation, Arnaud Browet et al. Combinatorial Image Analysis 2011. To be presented by Liang-Liu-Jacobs.

March 31 (second presentation): Ranking based clustering of heterogeneous information networks with star network schema, Y. Sun et al et al. KDD 2009.  To be presented by Bandyopadhyay-Vedhula-Voytovich.

April 5 (first presentation): Basketball teams as strategic networks. J. Fewell et al. PLOS (one), 2012. To be presented by Gupta-Khan-Witt

April 5 (second presentation): Multiplex networks in metropolitan areas: generic features and local effects, Strano et al. Royal Society Interface 2015. To be presented by Indukuri-Rao-Tankasala

April 7 (first presentation): Structural Inference in Uncertain Networks. T. Martin et al. ArXiV 2015. To be presented by Ramachandran-Kaushik-Wakefield.

April 7th (second presentation): A Spin Glass Model for Semi-Supervised Community Detection. E. Eaton et al. AAAI 2012. To be presented by Bakshi-Kumchum-Madley.

 

S. Parthasarathy

March 2016