|
Computer Science 496
Special Topics in Computer Science:
Complex Networks - Analysis and Applications
|
Fall 2017
|
General Information | Schedule and
Assignments | Project Page | Announcements
EVOLVING: CHECK BACK FOR UPDATES
The reading for a class should be completed before class.
Important dates:
Wed. Oct 18: 5 minute project proposals by students in
class
MOVED Wed.
Oct 25 - Fri. Oct 27: take-home midterm exam window -
details to follow
Wed. Nov. 8 - Fri. Nov 10:
take-home midterm exam window - details to follow
Wed. Dec 6 - Fri. Dec 8: take-home second exam
window - details to follow
We will find a time some late in reading period or the
beginning of Exams Period for Project Presentations
Tues. Jan 16 Dean's Date, written project report due
WEEK 0
Wed. Sept 13: Introduction
to Network Science
- Class presentation slides (pdf): Introduction
- Reading:
- Assignment 0 (not graded
but necessary) will be posted on Piazza. Due Wed. Sept. 20.
WEEK 1
Mon. Sept 18: Review of graph
concepts
- No class presentation slides
- Reading:
Wed. Sept 20: Network properties
- Class presentation slide: Seyi
Lawal case study
- Reading:
-
Newman, Networks:
an Introduction: Chapter 7 (Measures and Metrics),
Sections 7.1; 7.6; 7.9; 7.10;
7.12: only subsections 7.12.1 thru 7.12.3; 7.13
It is not necessary to work through the
derivations, just understand the concepts and
techniques.
WEEK 2
Mon. Sept 25: Network
properties continued : new properties and betweenness
Wed. Sept 27: No Class
WEEK 3
Mon. Oct. 2: PageRank and other
global link metrics
- Class presentation slide:
global link metrics
- Reading:
-
Rajaraman, Anand;
Leskovec,
Jure; Ullman, Jeffrey
D, Mining
of Massive Data Sets, Chapter
5: Sections 5.1 and 5.5. You can download a pdf file
(2.9 MB) of the latest version of the book ( March 2014 as of
this writing) from the book site. Safari books online offers
the earlier printed version (Cambridge
University Press. 2011) here.
I recommend the latest version.
- Also of interest, original papers:
- (HITS algorithm) Kleinberg, Jon, Authoritative
sources in a hyperlinked environment, Journal of the
ACM, Vol. 46, No. 5(Sept. 1999), pp.604-632.
(Earlier versions appeared in Proc. 9th ACM-SIAM Symposium on Discrete Algorithms,
1998 and as IBM Research Report RJ 10076, May 1997.)
- (PageRank algorithm) Page, Larry and Sergey Brin, R.
Motwani, T. Winograd, The PageRank Citation Ranking:
Bringing Order to the Web, Stanford
Digital Library Technologies Project TR, Jan. 1998.
(Early version: L. Page. PageRank: Bringing order to the web.
Stanford Digital Libraries Working Paper 1997-0072, Stanford
University, 1997. )
Wed. Oct 4: Homophily
Note: we will start by going around to discuss
your thoughts on your projects
- Class notes: homophily
- Reading:
- Review section 7.13 of Newman
WEEK 4
Mon. Oct
9: Visualization
algorithms
- Reading (originally assigned for Oct 4.):
Wed. Oct 11: Random Graphs
- Reading:
- Barabasi, Network
Science, Chapter 3: all regular sections plus
"Advanced Topics" sections 3.14 "Giant Component" and 3.16
"Fully Connected Regime"
- Recommended reading:
WEEK 5
Mon. Oct 16:
Scale-free Networks
Wed. Oct
18: 5
minute project proposals by students in class; continuing
Scale-free Networks
- Reading
- Barabasi, Network
Science, Chapter 4:
Sections 4.7-4.9 and Advanced Topics Sections 4.11 and
4.12. Just get the main ideas of the Advanced Topics
Sections.
- Recommended reading:
WEEK 6
Mon. Oct 23:
Clustering Overview
- Class Slides: Clustering
Overview
- Reading
- Barabasi, Network
Science, Chapter 9, Section 9.1 (Introduction)
- Introduction to Information Retrieval *: Chapter 17
Introduction, Sections 17.1, 17.2 and 17.5
- Recommended reading:
- Introduction to Information Retrieval *, Sections
17.3 and 17.4
* Manning, Christopher D.; Raghavan, Prabhakar; Schutze,
Hinrich, Introduction to
Information Retrieval, Cambridge University
Press, 2008, reprinted 2009. The above link is to the
website for the book, which contains, among other things, links
to complete html and pdf (6.6 MB) versions. The Safari books
online version is available here.
Wed. Oct 25:
Hierarchical Agglomerative Clustering
October 28 - November 5 fall break
WEEK 7
Mon. Nov. 6:
Hierarchical Divisive Clustering
Wed. Nov.
8: Clustering by iterative improvement, with
betweenness; evaluating clusters
Wed. Nov. 8 - Fri. Nov 10: take-home midterm exam
WEEK 8
Mon. Nov. 13:
Spectral Clustering background
- Reading
-
Newman Chapter 6, Section 6.13; Chapter 11 Sections 11.5 and
11.8
Wed. Nov.
15: Spectral clustering, overlap clusters, Gephi's
algorithm
- Reading
- Barabasi, Chapter 9, Section 9.5 Overlapping
Communities
- Newman, Chapter 11, Section 11.9 Division
into more than two groups
WEEK 9
Mon. Nov. 20: Growing
networks: preferential attachment
Wed. Nov. 22: Thanksgiving
holiday break
WEEK 10
Mon. Nov. 27:
Preferential attachment simulation; other network
models
Wed. Nov. 29: Epidemic
modeling
- Reading
- Barabasi,
Chapter 10, Sections 10.1-10.4
WEEK 11
Mon. Dec. 4: Epidemic modeling:
networks
- Reading
-
Barabasi, Chapter 10, Sections 10.5-10.8
Wed. Dec. 6: Epidemic
modeling: vaccinating; Network robustness: cascading failures
- Reading: none assigned for today
Wed.
Dec 6 - Fri. Dec 8: take-home
second exam window
WEEK 12
Mon. Dec. 11: Network
Robustness: Percolation model
- Reading
- Barabasi,
Chapter 8, Sections 8.1 - 8.3, 8.10 (Advanced topic 8A)
- Also
of interest:
- Barabasi,
Chapter 8, Section 8.11(Advanced topic 8B) contains the
derivation of the Molloy-Reed Criterion, which I sketched
today
Wed. Dec. 13: Network
Robustness: other topics; Closing remarks
- Reading
- Barabasi,
Chapter 8, Sections 8.4-8.8 ( 8.5, 8.6 presented 12/6)
READING
PERIOD
Project
Report due
5:00 pm Dean's Date, Tuesday Jan. 16, 2018
by CS Dropbox submission.
last revised Mon Dec 11 17:42:24 EST 2017
Copyright
2017
Andrea S. LaPaugh
topological
overlap example; overview
of efficient hierarchical agglomerative algorithm, also
see slides posted for Nov. 6.