$30
CSE2046-Social Networks Assingment 4Solved
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) 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
b)Build your graph and calculate the following values, Degree centrality Closeness centrality , Betweenness centrality
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
CBe,ennes (1)
=
0
CBe,ennes (2)
=
0
CBe,ennes (3)
=
9/15
CBe~iennes (4)
=
9/15
CBeiennes (5)
=
8/15
CBe~iennes (6)
=
0
CBeiennes (7)
=
0
After making standardization (n-1)(n-2)/2=15
CBe~iennes (1)
CBeiennes (2)
=
=
0
0
9
= 0.04
CBeiennes (3)
=
225
9
= 0.04
CBeiennes (4)
=
225
CBe~iennes (5)
=
8/225=0.035
CBe~iennes (6)
=
0
CBeiennes (7)
=
0
c)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
