Show The Graduate Center Menu

Graph And Social Network Analysis


A graph has nodes and edges which connect some pairs of nodes. The edges

can be directed or undirected. Graph theory has broad application to areas

of physics, chemistry, communication science, biology, electrical engineering,

operations research, psychology, linguistics, and social networks.

Course Description

The course rst studies fundamental concepts in graph theory including data

structures that can represent graphs. Concepts include ows and connectiv-

ity (e.g., Mengers theorem), planarity (coloring), Eulerian and Hamiltonian

graphs. Then the course studies fundamental concepts, metrics, and algo-

rithms associated with Social Networks.

Topic Lists


  •  Graphs and subgraphs
  •  Connected graphs
  •  Trees

Flows and Connectivity

  •  Non-separable graphs
  •  Flows in networks
  •  Edge and Vertex Connectivity

Graph Representation and Algorithms.

  •  Adjacency matrix and adjacency-linked lists
  •  Dijkstra's Shortest Path Algorithm

Planarity and the Four-Colour

Independent Sets

Cliques and Quasi Cliques


Eulerian and Hamiltonian Cycles

Vertex and Edge Covers

Dominating Sets

Random Network Models

Social Network Analysis

  •  Types of Social Networks
  •  Homophily
  •  Multiplexity
  •  Mutuality/Reciprocity
  •  Propinquity
  •  Bridges
  •  Degree Centrality
  •  Betweenness Centrality
  •  Closeness Centrality
  •  Network Reach
  •  Network Integration
  •  Boundary Spanners
  •  Peripheral Players
  •  Density
  •  Structural Holes
  •  Tie Strength
  •  Communities

Learning Objectives

Students will be able to

Formally apply graph-theoretic terminology and notation

Apply theoretical knowledge acquired to solve practical graph problems

Understand and apply social network analysis techniques


There will be two exams to assess understanding of the theoretical concepts

of Graph Theory: a Midterm (30%) and a Final (30%). There will be Home-

work and Programming Projects (30%) to assess knowledge of algorithms.