this assignment is to implement graph-based data analysis functions that could be used to identify influencers

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Assignment 2

Social Network Analysis

Aims

• To implement graph-based data analysis functions to mine a given social network

• To give you further practice with C and data structures (Graph ADT)

Introduction

The main focus of this assignment is to implement graph-based data analysis functions that could be used to identify influencers, followers and communities in a given social network.

Setting Up

Change into the directory you created for the assignment and run the following command:

unzip /web/cs2521/22T1/ass/ass2/downloads/files.zip

If you're working at home, download files.zip by clicking on the above link and then unzip the downloaded file.

This bundle of files includes the files you need to implement, as well as a few completed ADTs that you may use, some testing programs/scripts and sample graphs.

We have provided complete implementations of the Graph and Priority Queue ADTs. You may use these ADTs for any parts of the assignment as long as you do not modify them.

Part 1 - Dijkstra's Algorithm

In order to discover influencers, we need to repeatedly find shortest paths between pairs of nodes. Your task is to implement a variant Dijkstra's algorithm to discover the shortest paths from a given source node to all other nodes in the graph. The algorithm has one important additional feature: if there are multiple shortest paths from a source node to another node, it keeps track of all of them by allowing each node to have multiple predecessors. In the code, this is achieved by each node having a linked list of predecessors (see Dijkstra.h). Each predecessor list must be in ascending order.

In the following example, while discovering shortest paths from node 0, we find that there are two possible shortest paths from node 0 to node 1 (0 -> 1 and 0 -> 2 -> 1), so node 1 has two possible predecessors: node 0 and node 2, as shown below.

 

Source node: 0

  Distances

    0: 0

    1: 2

    2: 1

  Predecessors

    0: NULL

    1: [0] -> [2] -> NULL

    2: [0] -> NULL

 

Source node: 1

  Distances

    0: 2

    1: 0

    2: 3

  Predecessors

    0: [1] -> NULL

    1: NULL

    2: [0] -> NULL

 

Source node: 2

  Distances

    0: 3

    1: 1

    2: 0

  Predecessors

    0: [1] -> NULL

    1: [2] -> NULL

    2: NULL

 

What you need to do:

Complete the file Dijkstra.c that implements all the functions declared in Dijkstra.h.

Part 2 - Centrality Measures for Social Network Analysis

Centrality measures play a very important role in analysing a social network. For example, nodes with higher betweenness often correspond to influencers in a social network. Your task is to implement two well-known centrality measures for a given directed weighted graph.

Closeness Centrality

The closeness centrality of a node x is calculated as the reciprocal of the sum of the lengths of the shortest paths between node x and all other nodes y (y≠x) in the graph. Generally closeness is defined as below:

C(x)=1∑yd(y,x)

where d(y,x) is the shortest distance between vertices x and y.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of