Show The Graduate Center Menu

Graph-Based Analysis of Social Networks


Recent changes in the World Wide Web (WWW) facilitated media infor-
mation sharing among users, user-based content creation and remote collab-
oration. Social networks allow users to post public proles and share them
with friends, consequently creating virtual communities and networks. Post-
ing relevant media data (e.g., images, videos, music and text) in social media
sites forces an increase of multimedia data storage, communication and con-
sumption. Social media are concentrated on the creation and exchange of
user-generated content, allowing users to create, search, share, rate and ac-
cess multimedia data, thus creating a totally new media experience. This
course addresses these scientic and technological issues, that is, the con u-
ence of graph analysis, network theory, digital media, machine learning, and
big data analysis.

Course Description

Mathematical foundations of social media analysis, and a comprehensive in-
troduction to the use of graph theory in the study of social and digital media.
Study of the con uence of graph analysis, network theory, big data analy-
sis, and signal processing. Algebraic and combinatorial graph theory will be
particularly applied for the analysis of graphs, in social media studies. Tech-
niques such as spectral clustering, distributed tensor decomposition, match-
ing, and random walks will be discussed. As social media inherits strong
big data issues related to both size and content of the stored multimedia,
emphasis will be placed on the analysis of big data. Parallel and distributed
programming techniques to address graph partitioning problems (e.g., clus-
tering) will be discussed.

Topic Lists

Topics may include but won't be limited to:

  1. Graphs in Social and Digital Media
  •  Dominant social networking/media platforms
  •  Collecting data from social media sites
  •  Social media graphs (Facebook, Twitter, etc.)
  •  Graph storage formats and visualization
  •  Big data issues in social land digital media
      2. Mathematical Preliminaries: Graphs and Matrices
  • Adjacency, and Laplacian matrices
  • Review of relevant Graph Theoretical algorithms (e.g., Depth-first-search, Dijkstra's shortest path, minimum spanning trees,etc.)
  • Centrality, betweenness and closeness
      3. Algebraic Graph Analysis
  •  Spectral graph theory
  •  Similarity matrix and nearest neighbor graph
  •  Random graph generation and models
  •  Spectral graph generation
  •  Graph clustering
  •  Graph matching
  •  Spectral graph matching
  •  Random walks

Programming Assignment (spectral clustering, matching, or random
     4. Label Propagation and Information Diusion in Graphs

  • Graph construction approaches
  • Label inference methods
  • Social networks difusion models

     5. Graph-based Pattern Classication and Dimensionality Reduction
     6. Matrix and Tensor Factorization with Recommender System Applications
     7. Big Data Analytics of Social Networks
     8. Semantic Model Adaptation for Evolving Big Social Data
      (a) Parallel and Distributed Approaches for Big Data Analysis

  • Parallel probabilistic latent semantic analysis
  • Parallel spectral clustering
  • Distributed tensor decomposition

      (b) Applications to Evolving Social Data Analysis

  • Incremental label propagation
  • Incremental graph clustering in dynamic social networks

      (c) Programming Assignment (Parallel Probabilistic Latent Seman-
tics, Parallel Spectral Clustering, or Distributed Tensor Decom-

Learning Goals

The student must be able to demonstrate a working knowledge of the the-
oretical foundations of Graph Analytics by showing prociency in following

  • Theoretical methods to determine social in uence in media networks by application of known graph theoretical algorithms.
  • Graph partitioning (clustering) by application of spectral, matching, or random walks techniques.
  • Learn about social networks difusion models and dimensionality reduction methods.
  • Apply parallel/distributed techniques to handle big data problems. Besides clustering problems, partitioning of data to be distributed on a cluster of nodes to solve other graph theory algorithms will be investigated.


  • Programming exercises will be assigned to make sure students are capable of applying theoretical knowledge to implement algorithms for partitioning problems as well as implementation of parallel/distributed techniques to handle big data. 50 %
  • Midterm exam to demonstrate prociency in but not limited to tech-
    niques to measure social in uence, and partitioning methods for clus-
    tering problems. 25%
  • Final exam to demonstrate knowledge in but not limited to graph difus-
    sion models, dimensionality reduction methods, and parallel/distributed
    partitioning problems of large graphs. 25%