JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Course Objectives:

To explore the concept of Graphs and related algorithms. To learn new ways to model, store, retrieve and analyze graph-structured data. To be aware of advanced concepts in graph analytic techniques and its applications.

Course Outcomes

Upon the Successful Completion of the Course, the Students would be able to:

Explore the graph analytic techniques and its applications. Model a problem into a graph database and perform analytical tasks over the graph in a scalable manner. Apply Graph theoretical techniques in massive networks.

UNIT - I

Introduction and Application of Large-scale Graph: Characteristics, Complex Data Sources - Social Networks, Simulations, Bioinformatics; Categories- Social, Endorsement, Location, Co-occurrence graphs; Graph Data structures, Parallel, Multicore and Graph Algorithms

UNIT - II

Basic and Advanced Large-scale Graph Analysis: Parallel Prefix & List Ranking, Link Analysis, Page Ranking Algorithms; Parallel BFS, Spanning Tree, Connected Components, Minimum Spanning Tree Matroid Algorithms, Social Networking Algorithms.

UNIT - III

Dynamic Parallel Algorithms - Streaming Data Analysis -Data Structures for Streaming Data - Tracking Clustering Coefficients - Tracking Connected Components -Anomaly Detection, Massive-Graphs in Computational Biology, Genome Assembly.

UNIT - IV

Distributed Computation for Massive Data Sets: Spectral, Modularity-based Clustering, Random Walks; Large Graph Representation and Implementation- V-Graph Representation, Map Reduce, Surfer, Graph Lab.

UNIT - V

Advanced Topics: Power Law Distribution, Game-Theoretic Approach, Rank Aggregation and Voting Theory, Recommendation Systems, Social network analysis: case study ‐Facebook, LinkedIn, Google+, and Twitter.

Text Books:

Matthew O. Jackson, “Social and Economic Networks”, Princeton University Press, 2010. Stanley Wasserman, Katherine Faust, "Social Network Analysis: Methods and Applications”, (Structural Analysis in the Social Sciences), Cambridge University Press, 1995. Tanja Falkowski, "Community Analysis in Dynamic Social Networks", (Dissertation), University Magdeburg, 2009. M.Tech. (Data Science) II Year I Semester