1. Course Information
- Lecture Times: Tuesday (Periods 2–3) and Thursday (Period 3)
- Classroom: Sophie Barat Hall B346
2. Instructor and TAs
Instructor
- Name: Prof. O-Joun Lee
- Office: Michael Hall T404
- Email: ojlee@catholic.ac.kr
- Website: NS Lab @ CUK Website
- Office Hours: TBA (by appointment or specify times)
3. Course Description
This course provides an in-depth exploration of the techniques and algorithms used to analyze and mine large-scale graphs and networks. Students will learn about:
- Various types of graph data and their unique challenges in storage and processing
- Core graph mining techniques (e.g., graph traversal, centrality measures, community detection)
- Real-world applications including social network analysis, fraud detection, and recommendation systems
By the end of the semester, students will be able to:
- Represent and store complex graph data efficiently
- Apply key graph mining algorithms to extract meaningful insights
- Utilize programming tools (e.g., Python’s NetworkX) for hands-on graph analysis and visualization
4. Course Materials
-
Lecture Notes & Assignments:
Materials are updated weekly on the course’s online learning platform (or the GitHub repository linked below). -
Practice & Assignments Repository:
https://github.com/stars/NSLab-CUK/lists/graph-mining
5. Tentative Schedule
| Week | Topics | Key Concepts & Activities |
|---|---|---|
| 1 | Introduction to Graph Mining | - Overview of graph mining - Types of graphs & applications - Basic graph concepts - Sample Code: Simple graph creation with NetworkX |
| 2 | Graph Representation and Storage | - Adjacency list & matrix - Sparse matrix representations - Graph databases - Sample Code: Converting NetworkX graph to a sparse matrix |
| 3 | Centrality Measures | - Degree, Betweenness, Closeness, Eigenvector centrality - PageRank - Sample Code: Calculating centralities in NetworkX |
| 4 | Graph Visualization | - Visualization techniques (spring-embedded, circular, etc.) - Tools (Gephi, Cytoscape) - Sample Code: Visualizing graphs in NetworkX |
| 5 | Community Detection | - Definitions, properties - Clustering (k-means, hierarchical) - Modularity & Louvain - Sample Code: Louvain community detection |
| 6 | Link Prediction | - Positive vs. negative links - Common neighbors, Jaccard coefficient - Sample Code: Predicting links in NetworkX |
| 7 | Subgraph Mining | - Frequent Subgraph Mining (FSM) - Algorithms (gSpan, FSG) - Sample Code: Mining frequent subgraphs with gSpan |
| 8 | Mid-term Exam | - Covers Weeks 1–7 |
| 9 | Graph Kernels | - Overview of graph kernels - Weisfeiler-Lehman (WL) - Sample Code: WL relabeling process |
| 10 | Node Classification | - Feature extraction - Classifiers (SVM, RF) - Sample Code: Node classification with SVM |
| 11 | Social Network Applications | - Community detection & link prediction in social networks - Sample Code: Analyzing a social network in NetworkX |
| 12 | Transportation Network Applications | - Shortest path algorithms - Centrality measures - Sample Code: Shortest path in a transportation network |
| 13 | Web Graph Applications | - Web graph crawling - Web graph analysis - Sample Code: Crawling & analyzing a web graph |
| 14 | Additional Topics & Wrap-Up | - Graph matching & other advanced techniques - Important graph metrics - Future directions |
| 15 | (Open/Review Week)* | - (Optional: Project presentations, guest lectures, or review) |
| 16 | Final Exam | - Covers Weeks 1–14 |
* Week 15 may be used for additional review, presentations, or extra content at the instructor’s discretion.
6. Assignments & Practices
- Assignments: Practice materials and problem sets will be posted on the GitHub repository. Please submit all solutions via the course’s online platform by the stated deadlines.
Late Submission Policy
- Assignments submitted after the deadline are capped at a grade of B (8 points).
- Failure to submit or excessively late submissions may result in F (0 points) for that assignment.
7. Evaluation
| Component | Percentage |
|---|---|
| Attendance | 10% |
| Assignments | 30% |
| Mid-term Exam | 30% |
| Final Exam | 30% |
Grading Scale
- A : 80–100
- B : 60–80
- C : < 60
- F : Absence from exams
(Note: Exact cutoff points for letter grades may be adjusted slightly at the instructor’s discretion.)
8. Academic Integrity & Plagiarism
- Policy: Plagiarism or any form of academic dishonesty (e.g., copying code or solutions without proper citation) will not be tolerated.
- Consequences: Violations may result in penalties up to and including failing the assignment/exam or the entire course.
- Guidelines:
- Complete your own work.
- Properly cite any external sources.
- If you have questions on citation or collaboration policies, consult the instructor or TAs in advance.
9. Exams
- Mid-term Exam (Week 8): Details will be announced in class.
- Final Exam (Week 16): Comprehensive exam covering all course topics.
- Make-Up Policy: Make-up exams will only be given under exceptional circumstances with proper documentation.
10. Contact & Office Hours
- Instructor Office Hours: TBA. Students may schedule an appointment via email if they need additional time or have specific concerns.
- TA Office Hours: TBA. All TAs will be available for help with assignments, project work, or any course-related questions.
Note: This syllabus may be subject to minor updates. Any changes will be announced via the course’s online platform or email. Students are responsible for staying informed of any modifications.