CSE225-Project 3 Social Networks Solved

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 

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

b)    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 

 

 

a) (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: 

As an adjacency matrix: 

 

The first 2 rows have been done for you: 

 

 
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. 

 

 

 

 

 

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.

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
 

   

    

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

  

 

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