University Graph Analysis

University Graph Analysis with Writeup #

A mathematical and visual analysis of a graph representing the relationships between members of a university faculty.

.rmd knitted with execution results available for download here

Plotting the Graph#

Start by adding the required packages.

1
# install required libraries
2
if (!require("igraph")) {
3
    install.packages("igraph")
4
    library(igraph)
5
}

1
## Loading required package: igraph

1
##
2
## Attaching package: 'igraph'

1
## The following objects are masked from 'package:stats':
2
##
3
##     decompose, spectrum

1
## The following object is masked from 'package:base':
2
##
3
##     union

1
if (!require("igraphdata")) {
2
    install.packages("igraphdata")
3
    library(igraphdata)
4
}

1
## Loading required package: igraphdata

1
## Warning: package 'igraphdata' was built under R version 4.3.2

Then, we can get our data from the ‘igraphdata’ package for use with ‘igraph’

1
# load the data into 'UKfaculty' variable
2
data(UKfaculty, package="igraphdata")
3
# listen to the warning given
4
G = upgrade_graph(UKfaculty)

The data ‘UKfaculty’ consists of 81 nodes, each representing a person at a UK university.

Each node has a ‘Group’ attribute, which is an integer id for their school affiliation.

There are a total of 817 edges, each with a weight.

The weight of each edge represents the ‘closeness’ of the friendship between two faculty members, so lower ‘weight’ means the two are better friends.

Each edge is directed, since a friendship could be one-sided.

It would be helpful to encode more information into the graph, instead of just nodes and edges.

Lets encode the ‘Group’ attribute into the vertices’ color.

1
# loop through all the vertices
2
for(i in c(1:length(V(G)))){
3
  # set the vertex color based on 'Group'
4
  if(V(G)[i]$Group == 1){
5
    V(G)[i]$color = "white"
6
  } else if(V(G)[i]$Group == 2){
7
    V(G)[i]$color = "lightgreen"
8
  } else if(V(G)[i]$Group == 3){
9
    V(G)[i]$color = "lightblue"
10
  } else if(V(G)[i]$Group == 4){
11
    V(G)[i]$color = "lightpink"
12
  }
13
}

After that, we can plot the graph.

1
plt = function(G, log=TRUE){
2
  # reduce the margin size
3
  par(mar=c(0,0,0,0)+.1)
4

5
  # consistent graph generation
6
  # doesn't change community structure for later analysis
7
  set.seed(7881954)
8
  # plot the graph with some layout changes to prevent it from being a ball of vertices on top of each other.
9
  plot(G, layout=layout_with_fr(G), # use force-directed graph drawing to minimize crossing edges, and place similar edge lengths nearby
10
       asp=1, edge.arrow.size=0.5, edge.arrow.width=1, vertex.size=10, # now some coloring to encode more info into the graph
11
       vertex.color=V(G)$color, vertex.label.color="black")
12
  # create a legend for the different node colors/groups
13
  if(log){
14
    legend(x = 1, y = 1.1, xjust = 0.5, ncol = 2, c("Group 1", "Group 2", "Group 3", "Group 4"),
15
        pch = 21, , pt.cex = 1.5,
16
        col = "black", pt.bg = c("white", "lightgreen", "lightblue", "lightpink"))
17
  }
18
}

1
plt(G)

Analyzing Plotted Graph#

From this graph, we can see three general communities form based on the faculty members ‘Group’ attribute.

While there are friendships between groups, its clear to see that in general the members of one group are more friendly with other members of their group, instead of members of another group.

Additionally, we can see that the members of Group 1 and Group 2 are much closer to the members of their own group, compared to the members of Group 3 which are not as close with each other.

Next we can see that in general, Group 1 and Group 2 are much more friendly with the members of the other group (Group 2 and Group 1 respectively) than they are with members of Group 3.

Also, members of Group 4 are friendly enough with Group 1 (and vice versa) for Group 4 to be included in Group 1’s ‘community’.

Finally, there are some outliers: like node 62, which is more friendly with Groups 1 and 4 than with their own group (Group 3), and node 11 which isn’t part of their groups community, only having 2 distant friendships.

Mathematical Analysis#

Now that we’ve analyzed the graph’s structure when plotting it, it’s time to perform some mathematical analysis on it’s structure.

First, lets start with the graph’s center, AKA the list of nodes in G with the lowest eccentricity (radius).

1
# init list
2
center = list()
3
# loop through all nodes
4
for(i in V(G)){
5
  # if current node has lowest possible eccentricity in G
6
  if(eccentricity(G)[i] == radius(G)){
7
    # it's a center node, add to list
8
    center[length(center) + 1] = i
9
  }
10
}
11
# the number of center nodes is
12
length(center)

1
## [1] 61

1
# the center nodes are:
2
# to print w/out weird [[i]] stuff
3
for(i in c(1:length(center))){
4
  print(center[[i]])
5
}

1
## [1] 1
2
## [1] 2
3
## [1] 4
4
## [1] 5
5
## [1] 6
6
## [1] 7
7
## [1] 9
8
## [1] 10
9
## [1] 12
10
## [1] 13
11
## [1] 15
12
## [1] 17
13
## [1] 18
14
## [1] 19
15
## [1] 20
16
## [1] 21
17
## [1] 22
18
## [1] 23
19
## [1] 25
20
## [1] 26
21
## [1] 27
22
## [1] 29
23
## [1] 31
24
## [1] 32
25
## [1] 33
26
## [1] 34
27
## [1] 35
28
## [1] 37
29
## [1] 38
30
## [1] 39
31
## [1] 41
32
## [1] 42
33
## [1] 43
34
## [1] 44
35
## [1] 46
36
## [1] 48
37
## [1] 49
38
## [1] 50
39
## [1] 51
40
## [1] 52
41
## [1] 54
42
## [1] 55
43
## [1] 57
44
## [1] 58
45
## [1] 60
46
## [1] 61
47
## [1] 62
48
## [1] 64
49
## [1] 65
50
## [1] 68
51
## [1] 69
52
## [1] 70
53
## [1] 71
54
## [1] 72
55
## [1] 74
56
## [1] 75
57
## [1] 76
58
## [1] 77
59
## [1] 79
60
## [1] 80
61
## [1] 81

1
# with an eccentricity/radius of
2
radius(G)

1
## [1] 3

So there’s a total of 61 center nodes, each with an eccentricity of 3.

That means that 61 people in the faculty have at most 3 degrees of separation from all the other faculty members.

In terms of the relationships defined by the edges: for any faculty member that is also a center node, the list of the center node’s friends, the friends of the center node’s friends, and the friends of the friends of the center node’s friends all combined will be the set of all faculty members.

1
max(eccentricity(G))

1
## [1] 4

Since the max eccentricity is 4, for all 81 nodes there will be at most 4 degrees of separation from all the other faculty members.

Next we can look at betweenness, a centrality measure for graphs.

Betweenness for a vertex ‘v’ is calculated as the sum of fractions, where each fraction is the sum of shortest paths from vertex ‘s’ to ‘t’ (s != v != t) that pass through vertex ‘v’, divided by the sum of shortest paths from ‘s’ to ‘t’ that don’t pass through ‘v’.

Overall, this gives a measure of what vertices are included in more shortest paths compared to others, giving a measure of what vertices are near the ‘center’ of the graph.

1
# order returns indices
2
# pass these indices to V(G) to sort V(G) by betweenness descending
3
V(G)[order(betweenness(G, normalized = TRUE, directed=TRUE), decreasing = TRUE)]

1
## + 81/81 vertices, from 6f42903:
2
##  [1] 37 62  5  2 29 38 17 72 58 10 54 52 69 77  1 48 75  6  9 35 27 49  7 24 51
3
## [26] 22 53 70  4 40 42 21 57 39 31 46 61 15 13 55 80 67 28 43 20 79 81 68 25 34
4
## [51] 59 30 12 66 33 16 19 76 56 64 65 47  3 26 50 45 44 23 41 71  8 11 14 18 32
5
## [76] 36 60 63 73 74 78

So using betweenness as a centrality measure, the ‘center’ of the graph is node 37.

That means that node 37 is in the most shortest paths from any other two nodes.

In the context of the faculty members, since node 37 is in more shortest paths, this means that node 37 probably has ‘closer’ (lower edge weight) friendships with other faculty members in general, or that their collection of friends are ‘closer’ comparatively.

Next, we can look at closeness, another centrality measure.

Closeness for a vertex ‘v’ is the mean distance between ‘v’ and all other vertices that ‘v’ is connected with.

1
# order returns indices
2
# pass these indices to V(G) to sort V(G) by closeness descending
3
V(G)[order(closeness(G, mode="all", normalized = TRUE), decreasing = TRUE)]

1
## + 81/81 vertices, from 6f42903:
2
##  [1] 37 62 54  9 10 29  5 38 18  2  7 40 58 77 55 79 52 69 16 20 32 35 34 23 49
3
## [26] 57 70 27 61 17 22 48  6 51 42 65 15 41  4 39 76 26 72 43 80 60 59 81  1 21
4
## [51] 24 28 44 13 53 67 33 45 75 31 12 68  8 25 64 19 14 50 66  3 30 47 78 11 56
5
## [76] 63 74 36 71 46 73

Here we can see that node 37 is also the graphs ‘center’ when using closeness as a centrality measure.

This tracks with what we concluded when measuring betweenness.

With betweenness we concluded that node 37 was in the most shortest paths between any two nodes, then it follows that the path from most nodes to node 37 will be the shortest path, leading to node 37 having the ‘closest’ mean distance between itself and any other vertex.

Next let’s look at periphery.

The periphery of our graph is the nodes that have the maximum eccentricity.

1
# graph vertices whose eccentricity is the max value for G
2
V(G)[eccentricity(G)==max(eccentricity(G))]

1
## + 20/81 vertices, from 6f42903:
2
##  [1]  3  8 11 14 16 24 28 30 36 40 45 47 53 56 59 63 66 67 73 78

In the context of the faculty members, a person on the periphery of the graph would be someone who isn’t as ‘friendly’ and whose friends would be less ‘friendly’

Next let’s look at the graph’s girth.

The girth of a graph is the length of the shortest possible cycle.

This most likely will be 2 for the faculty graph, so long as there are two people who are mutually friends

1
girth(G)

1
## $girth
2
## [1] 3
3
##
4
## $circle
5
## + 3/81 vertices, from 6f42903:
6
## [1]  4  1 36

I have no idea why it says 3, since this can easliy be shown as incorrect.

As we can see from the following:

1
E(G)[.from(1)]

1
## + 6/817 edges from 6f42903:
2
## [1] 1->62 1->45 1->36 1->61 1-> 4 1->44

1
E(G)[.to(1)]

1
## + 9/817 edges from 6f42903:
2
## [1] 62->1 61->1 38->1  4->1 45->1 81->1 52->1 44->1 36->1

In ‘G’ there are the edges ‘1->4’ and ‘4->1’, meaning the shortest cycle in ‘G’ is of length 2 not 3.

So the girth of ‘G’ is 2, and there is at least one mutual friendship among the faculty members.

Now lets look at the degree distribution of our graph.

The degree distribution does exactly what you’d expect, it creates a distribution based on the percentage chance that any given vertex will have the associated degree.

1
dd = degree_distribution(G)*100
2
plot(dd, ylab="% Chance for Degree", xlab="Vertex Degree")

1
as.data.frame(dd)

1
##          dd
2
## 1  0.000000
3
## 2  0.000000
4
## 3  1.234568
5
## 4  0.000000
6
## 5  1.234568
7
## 6  1.234568
8
## 7  3.703704
9
## 8  0.000000
10
## 9  3.703704
11
## 10 2.469136
12
## 11 8.641975
13
## 12 2.469136
14
## 13 6.172840
15
## 14 7.407407
16
## 15 3.703704
17
## 16 2.469136
18
## 17 1.234568
19
## 18 2.469136
20
## 19 2.469136
21
## 20 4.938272
22
## 21 4.938272
23
## 22 2.469136
24
## 23 3.703704
25
## 24 0.000000
26
## 25 3.703704
27
## 26 1.234568
28
## 27 3.703704
29
## 28 2.469136
30
## 29 1.234568
31
## 30 2.469136
32
## 31 1.234568
33
## 32 0.000000
34
## 33 0.000000
35
## 34 1.234568
36
## 35 0.000000
37
## 36 3.703704
38
## 37 1.234568
39
## 38 2.469136
40
## 39 2.469136
41
## 40 1.234568
42
## 41 0.000000
43
## 42 0.000000
44
## 43 0.000000
45
## 44 1.234568
46
## 45 1.234568
47
## 46 0.000000
48
## 47 0.000000
49
## 48 0.000000
50
## 49 0.000000
51
## 50 0.000000
52
## 51 0.000000
53
## 52 0.000000
54
## 53 0.000000
55
## 54 0.000000
56
## 55 1.234568
57
## 56 0.000000
58
## 57 0.000000
59
## 58 0.000000
60
## 59 0.000000
61
## 60 0.000000
62
## 61 0.000000
63
## 62 0.000000
64
## 63 1.234568

Note: degree_distribution starts at degree 0, so % chance of degree ‘deg’ is dd[deg+1]

From this we can see several things:

Faculty members have the highest chance of being friends with 10 people.

1
V(G)[degree(G) == 10]

1
## + 7/81 vertices, from 6f42903:
2
## [1] 30 32 36 53 56 65 81

There is no faculty member with no friends.

1
V(G)[degree(G) == 0]

1
## + 0/81 vertices, from 6f42903:

The highest number of friends any faculty member has is 62.

1
max(degree(G)) == 62

1
## [1] TRUE

1
V(G)[degree(G) == max(degree(G))]

1
## + 1/81 vertex, from 6f42903:
2
## [1] 29

The lowest number of friends any faculty member has is 2.

1
min(degree(G)) == 2

1
## [1] TRUE

1
V(G)[degree(G) == min(degree(G))]

1
## + 1/81 vertex, from 6f42903:
2
## [1] 11

Now lets look at graph density.

Graph density measures how many edges are there in the graph compared to how many there could possibly be.

With our graph of order 81 (number of vertices), it could have a total of 6480 edges (# vertices * (# vertices -1))

So our graph density is:

1
graph.density(G)

1
## [1] 0.1260802

So that means, that of all the possible friendships all the faculty members could make with each other, only around 12.6% of them exist.

Now let’s look at the density of the different groups in the faculty

1
s1 = induced_subgraph(G, V(G)$Group==1, impl="create_from_scratch")
2
plt(s1,FALSE)

1
graph.density(s1)

1
## [1] 0.3001894

1
s2 = induced_subgraph(G, V(G)$Group==2, impl="create_from_scratch")
2
plt(s2,FALSE)

1
graph.density(s2)

1
## [1] 0.3561254

1
s3 = induced_subgraph(G, V(G)$Group==3, impl="create_from_scratch")
2
plt(s3,FALSE)

1
graph.density(s3)

1
## [1] 0.2807018

1
s4 = induced_subgraph(G, V(G)$Group==4, impl="create_from_scratch")
2
plt(s4,FALSE)

1
graph.density(s4)

1
## [1] 1

From this, we can see that each group in the faculty is tighter knit than the faculty as a whole.

Relatively, there are more friendships within a group than in the faculty as a whole.

Additionally, Group 4 has the highest friendship density, but with only two members, that isn’t particularly notable.

The group with the second highest friendship density is Group 2, with around a 35.6% friendship density.

University Graph Analysis with Writeup#

Plotting the Graph#

Analyzing Plotted Graph#

Mathematical Analysis#

University Graph Analysis with Writeup #