\$30.00

Category:

## Description

Social Networks

This project is a programming assignment in C which aims to find influencer peaople in a

social graph. Your program will read a data file containing a list of people names and the friendness they have. You will build a graph from the given data file. The vertices of the graph will be the people and there will be an edge between each person who have a friendness relationship.

You will process the graph and make the necessary calculations. The output of your program will be

1. a representation of the graph you generated (can be viewed like adjacency matrix) and

1. the centrality degrees .

The input will be in the following format:

Cem; Ayşe, Ferit, Dundar

Ayşe; Cem, Ferit, Dundar, Belma

Belma; Ayşe, Dundar, Edip

Edip; Belma, Dundar, Gamze

Dundar; Ayse, Belma, Cem, Ferit, Gamze, Edip

Gamze; Dundar, Edip, Ferit, Halit

Ferit; Ayşe, Cem, Dundar, Gamze, Halit

Halit; Ferit, Gamze, Ilke

Ilke; Halit, Jale

Jale; Ilke

1. (25 points) The output of your program must be in the following form:

As the output, the resulting graph can be displayed using either of the following formats:

The first 2 rows have been done for you:

1

 Cem Ayşe Belma Edip Dundar Gamze Ferit Halit Ilke Jale Cem 0 1 0 0 1 0 1 0 0 0 Ayşe 1 0 1 0 1 0 1 0 0 0 Belma Edip Dundar Gamze Ferit Halit Ilke Jale

2

b)Build your graph and calculate the following values, Degree centrality(20 points), Closeness centrality(20 points), Betweenness centrality(20 points).

Example:

Degree centrality: Degree centrality of a node refers to the number of edges attached to the node. In order to know the standardized score, you need to divide each score by n-1 (n = the number of nodes). Since the graph has 7 nodes, 6 (7-1) is the denominator for this question.

 Node Score Standardized Score 1 1 1/6 2 1 1/6 3 3 3/6 = 1/2 4 2 2/6 = 1/3 5 3 3/6 = 1/2 6 2 2/6 = 1/3 7 2 2/6 = 1/3

Closeness centrality: You need to calculate the inverted score after you count the total number of steps to a node. In order to know the standardized score, you need to divide a score by (n-1), then take inverse. Note that the most central node is node 4 while the most central node for degree centrality is node 3 and 5.

3

 Node Score Standardized Score 1 1/16 6/16 = 3/8 2 1/16 6/16 = 3/8 3 1/11 6/11 4 1/10 6/10 = 3/5 5 1/11 6/11 6 1/15 6/15 = 2/5 7 1/15 6/15 = 2/5

Betweenness centrality: To calculate betweenness centrality, you take every pair of the network and count how many times a node can interrupt the shortest paths (geodesic distance) between the two nodes of the pair. For standardization, I note that the denominator is (n-1)(n-2)/2. For this network, (7-1)(7-2)/2 = 15. Note that node 5 has a little smaller centrality score that node 3 and 4 because the connection between node 6 and 7 reduces the controllability of node 5.

Betwennes Centrality:

 ( ) = ( ) ≠ ≠

Where, ( ) is the betwenness centarlity of node V, is the number of shortest paths between all source and target pairs, ( ) is the number of shortests paths between all source and target pairs those pass through from node V.

4

 Source Target Intermedia Nodes Path 1 2 3 1-3-2 1 3 – 1-3 1 4 3 1-3-4 1 5 3,4 1-3-4-5 1 6 3,4,5 1-3-4-5-6 1 7 3,4,5 1-3-4-5-7 2 3 – 2-3 2 4 3 2-3-4 2 5 3,4 2-3-4-5 2 6 3,4,5 2-3-4-5-6 2 7 3,4,5 2-3-4-5-7 3 4 – 3-4 3 5 4 3-4-5 3 6 4,5 3-4-5-6 3 7 4,5 3-4-5-7 4 5 – 4-5 4 6 5 4-5-6 4 7 5 5-6-7 5 6 – 5-6 5 7 – 5-7 6 7 – 5-7
 1 = 0 2 = 0 3 = 9/15

5

 4 = 9/15 5 = 8/15 6 = 0 7 = 0

After making standardization (n-1)(n-2)/2=15

 1 = 0 2 = 0 3 = 9 = 0.04 225 4 = 9 = 0.04 225 5 = 8/225=0.035 6 = 0 7 = 0

c)(15 points) What do you think about the information flow on this graph? What do you think the most powerful/critical node of this graph?,nk that this is a centralized graph? Why, why not?Do you think that

For PROJECT SUBMISSON:

1 page report + Code (by email also with hard copy to department secretary)

(name_surname.docx) both by email (cse225.marmara.2018 at gmail dot com )with the code by the deadline and 1 page report submission to department secretary.

with the following contents

REPORT:

b)

Source Degree Centrality Closeness Centrality Betwenness Centrality

6

1

2

3

4

5

6

7

Betwennes Centrality

 Source Target Intermedia Nodes Path 1 2 1 3 1 4 1 5 1 6 … …

CODE:

Code (name_surname.c)

When I run the code, the output format will be the same as in the report.

I will review and run your code and compare the results of the output with the results in the report.

If I get different results, you will fail the course and have dicisplinary penalty.

7

Ref: http://www.sscnet.ucla.edu/soc/faculty/mcfarland/soc112/cent-ans.htm

The main goal of this project is to be familiar with Graphs. So, you need to use Graph data structure.

CODE SUBMISSION:

You should use the following email address in order to submit your code:

cse225.marmara.2018 at gmail dot com.

8