Large-Scale Social and Complex Networks

Project 1: Random Graphs and Random Walks

Content

• Generate large random networks using Erdős–Rényi (ER) model and Preferential Attachment (PA) model.
• Analyze community structure of large networks, including Giant Connected Component (GCC) size and modularity.
• Modify preferential attachment model to penalize the age of a node in large random graph.
• Implemente random walk on large random network to simulate Google’s PageRank algorithm.

Project 2: Social Network Mining

Content

• Explore structural properties of undirected social network (Facebook dataset) using connectivity and degree distribution.
• Explore structural properties of personalized network of core nodes using Fast-Greeedy, Edge-Betweenness, and Infomap community detection algorithms.
• Explore characteristics of nodes in the personalized networks using Embeddedness and Dispersion.
• Implement friend recommendation in personalized networks using neighborhood-based measures, including common neighbor measure, Jaccard measure, and Adamic-Adar measure, and evaluate with average accuracy measure.
• Explore the community structure of directed social network (Google+ dataset), defined by homogeneity and completeness.

Project 3: Reinforcement Learning (RL) and Inverse Reinforcement Learning (IRL)

Content

• Model the environment of the agent by Markov Decision Process (MDP).
• Implement value iteration algorithm of Reinforcement Learning (RL).
• Implement the IRL algorithm using Linear Programming (LP) formulation.
• Evaluate the performance of IRL algorithm by comparing the extracted reward function and optimal policy map with ground truth.

Project 4: Graph Theory and Algorithms

Content

• Construct a correlation graph using correlation coefficient computed among stock-return time series data.
• Extract the Minimum Spanning Tree (MST) of the correlation graph and interpret it.
• Predict the market sector of an unknown stock, and evaluate the performance using sector clustering in MST.
• Simulate the influence of traffic block on the flow between certain places, and estimate how many roads could be blocked before paralyzing the traffic in Los Angeles area.