BBM462 Spring 2023

BBM462 Social and Economic Networks

Hacettepe University, Spring 2023.
Lectures: ??:40 - ??:30 PM, Xday.

Instructor: Lale Özkahya, (ozkahya@cs.hacettepe.edu.tr).
Communication: Over Piazza. Office hours: By appointment.

Resources

Resources:

Review of Linear Algebra, Probability, and Proof Techniques.
Networks: An Introduction by M.E.J. Newman. (available online via our library)
Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg.
Network Science by Albert-László Barabási.
Sample Exams: 2023

Coursework

Midterm Exam (25%)
Course Project (35%)
The topic of this project is of your choosing but must be related to the class. You can work individually or in groups of two (the scope of the project should be scaled according to the group size). We will be looking for two key pieces in the course project: (i) some theoretical or mathematical discussion of a numerical method or algorithm; (ii) some software implementation of a method or algorithm. The project will be split into three components: a proposal, a progress report, and a final report, worth 5%, 10%, and 15% of the final grade, respectively.
Final Exam (40%)

Tentative Submission Schedule

Project Proposal: March, ...
Progress Report: April, ...

Class schedule

This schedule is tentative and subject to change. Readings are mainly from Newman, and Easley-Kleinberg's books.

Module 1: Introduction to Social Network Analysis

Week 1

Introduction: Slides 1 2
Topics: Fundamentals of Networks, Review of Graphs
Readings:

Chapters 1 and 2 in Easley-Kleinberg's book.
Chapter 6 in Newman's book.

Week 2

Measures and Metrics for Networks: Slides
Topics: Centrality Measures, Similarity, Homophily
Readings:

Chapter 7 in Newman's book.

Week 3

Motifs and Structural Roles in Networks: Slides
Topics: Network Motifs, Graph Features in Network Analysis
Readings:

Milo, Shen-Orr, Itzkovitz, Kashtan, Chklovskii, Alon. Network Motifs: Simple Building Blocks of Complex Networks
Wernicke, Sebastian. Efficient Detection of Network Motifs
Henderson, Gallagher, Eliassi-Rad, Tong, Basu, Akoglu, Koutra, Faloutsos, Li. RolX: Structural Role Extraction & Mining in Large Graphs

Week 4

Community Structure: Slides
Topics: Strong and Weak Ties in Social Networks, Finding Communities in Networks
Readings:

Chapter 3 in Easley-Kleinberg's book.
Chapter 4 and 14 in Newman's book.
The Strength of Weak Ties by Granovetter, 1973.
Community detection in graphs by S. Fortunato, Arxiv 2009.
Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach by Yang and Leskovec, 2013.
Fast unfolding of communities in large networks by Blondel, Guillaume, Lambiotte, Lefebvre, 2008.

Week 5

The structure of real-world networks, Network Search: Slides
Topics: The Bow-Tie Structure of the Web, PageRank, Link Analysis
Readings:

Chapter 10 and 18 in Newman's book.
Chapter 13 and 14 in Easley-Kleinberg's book.

Week 6

The Small-world Phenomenon: Slides
Topics: Six Degrees of Separation, The Watts-Strogatz model, Decentralized Search
Readings:

Chapter 20 in Easley-Kleinberg's book.

Week 7

(Special Topic) Classification Problems on Graphs and Node Embeddings: Slides 1 and 2
Topics: Node-level and Graph-level Features, Link Prediction, Random Walk Approaches, Graph Embedding
Readings:

Graph Embedding Techniques, Applications, and Performance: A Survey by P. Goyal and E. Ferrara, 2017.