5225 Assignment 1 Notebook

library(igraph)
setwd("~/Desktop/2017 semester 2/self/R")

Question 2

create the graph

g<-graph.formula(1-2,1-3,2-3,2-4,2-7,3-4,3-6,3-7,3-8,3-9,3-10,4-8,4-9,5-6,5-8,5-7,6-7,6-8,6-9,6-10,7-8,7-9,8-9,8-10)
V(g)

+ 10/10 vertices, named, from 1085e9b:
 [1] 1  2  3  4  7  6  8  9  10 5 

E(g)

+ 24/24 edges from 1085e9b (vertex names):
 [1] 1--2  1--3  2--3  2--4  2--7  3--4  3--7  3--6  3--8  3--9 
[11] 3--10 4--8  4--9  7--6  7--8  7--9  7--5  6--8  6--9  6--10
[21] 6--5  8--9  8--10 8--5 

plot(g)

2.1

neighbors(g,"3")

+ 8/10 vertices, named, from 1085e9b:
[1] 1  2  4  7  6  8  9  10

neighbors(g,'5')

+ 3/10 vertices, named, from 1085e9b:
[1] 7 6 8

2.2

cliques(g, min = 2)

[[1]]
+ 2/10 vertices, named, from 1085e9b:
[1] 8 5

[[2]]
+ 2/10 vertices, named, from 1085e9b:
[1] 3 8

[[3]]
+ 2/10 vertices, named, from 1085e9b:
[1] 2 3

[[4]]
+ 2/10 vertices, named, from 1085e9b:
[1] 8 9

[[5]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 8 9

[[6]]
+ 2/10 vertices, named, from 1085e9b:
[1] 3 9

[[7]]
+ 2/10 vertices, named, from 1085e9b:
[1] 8  10

[[8]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3  8  10

[[9]]
+ 2/10 vertices, named, from 1085e9b:
[1] 3  10

[[10]]
+ 2/10 vertices, named, from 1085e9b:
[1] 1 2

[[11]]
+ 3/10 vertices, named, from 1085e9b:
[1] 1 2 3

[[12]]
+ 2/10 vertices, named, from 1085e9b:
[1] 1 3

[[13]]
+ 2/10 vertices, named, from 1085e9b:
[1] 6  10

[[14]]
+ 3/10 vertices, named, from 1085e9b:
[1] 6  8  10

[[15]]
+ 4/10 vertices, named, from 1085e9b:
[1] 3  6  8  10

[[16]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3  6  10

[[17]]
+ 2/10 vertices, named, from 1085e9b:
[1] 6 9

[[18]]
+ 3/10 vertices, named, from 1085e9b:
[1] 6 8 9

[[19]]
+ 4/10 vertices, named, from 1085e9b:
[1] 3 6 8 9

[[20]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 6 9

[[21]]
+ 2/10 vertices, named, from 1085e9b:
[1] 6 8

[[22]]
+ 3/10 vertices, named, from 1085e9b:
[1] 6 8 5

[[23]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 6 8

[[24]]
+ 2/10 vertices, named, from 1085e9b:
[1] 6 5

[[25]]
+ 2/10 vertices, named, from 1085e9b:
[1] 3 6

[[26]]
+ 2/10 vertices, named, from 1085e9b:
[1] 4 9

[[27]]
+ 3/10 vertices, named, from 1085e9b:
[1] 4 8 9

[[28]]
+ 4/10 vertices, named, from 1085e9b:
[1] 3 4 8 9

[[29]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 4 9

[[30]]
+ 2/10 vertices, named, from 1085e9b:
[1] 2 4

[[31]]
+ 3/10 vertices, named, from 1085e9b:
[1] 2 3 4

[[32]]
+ 2/10 vertices, named, from 1085e9b:
[1] 4 8

[[33]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 4 8

[[34]]
+ 2/10 vertices, named, from 1085e9b:
[1] 3 4

[[35]]
+ 2/10 vertices, named, from 1085e9b:
[1] 7 6

[[36]]
+ 3/10 vertices, named, from 1085e9b:
[1] 7 6 9

[[37]]
+ 4/10 vertices, named, from 1085e9b:
[1] 7 6 8 9

[[38]]
+ 5/10 vertices, named, from 1085e9b:
[1] 3 7 6 8 9

[[39]]
+ 4/10 vertices, named, from 1085e9b:
[1] 3 7 6 9

[[40]]
+ 3/10 vertices, named, from 1085e9b:
[1] 7 6 8

[[41]]
+ 4/10 vertices, named, from 1085e9b:
[1] 7 6 8 5

[[42]]
+ 4/10 vertices, named, from 1085e9b:
[1] 3 7 6 8

[[43]]
+ 3/10 vertices, named, from 1085e9b:
[1] 7 6 5

[[44]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 7 6

[[45]]
+ 2/10 vertices, named, from 1085e9b:
[1] 7 9

[[46]]
+ 3/10 vertices, named, from 1085e9b:
[1] 7 8 9

[[47]]
+ 4/10 vertices, named, from 1085e9b:
[1] 3 7 8 9

[[48]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 7 9

[[49]]
+ 2/10 vertices, named, from 1085e9b:
[1] 2 7

[[50]]
+ 3/10 vertices, named, from 1085e9b:
[1] 2 3 7

[[51]]
+ 2/10 vertices, named, from 1085e9b:
[1] 7 8

[[52]]
+ 3/10 vertices, named, from 1085e9b:
[1] 7 8 5

[[53]]
+ 3/10 vertices, named, from 1085e9b:
[1] 3 7 8

[[54]]
+ 2/10 vertices, named, from 1085e9b:
[1] 7 5

[[55]]
+ 2/10 vertices, named, from 1085e9b:
[1] 3 7

max_cliques(g, min = 2)

[[1]]
+ 3/10 vertices, named, from 1085e9b:
[1] 1 2 3

[[2]]
+ 3/10 vertices, named, from 1085e9b:
[1] 2 3 4

[[3]]
+ 3/10 vertices, named, from 1085e9b:
[1] 2 3 7

[[4]]
+ 4/10 vertices, named, from 1085e9b:
[1] 4 3 9 8

[[5]]
+ 4/10 vertices, named, from 1085e9b:
[1] 5 7 8 6

[[6]]
+ 4/10 vertices, named, from 1085e9b:
[1] 10 3  8  6 

[[7]]
+ 5/10 vertices, named, from 1085e9b:
[1] 6 3 9 8 7

clique_num(g) #the size of the largest clique

[1] 5

2.2 yc

list_clique=max_cliques(g,min=2)
mc <- lapply(mc, function(x) { V(g)$name[x] })
mc<-max_cliques(g, min = 4, max = NULL, subset = NULL, file = "output_clique.csv" )
result=unlist(lapply(1:length(list_clique),FUN=function(x){
  if(sum(c('8','9') %in% names(list_clique[[x]]))==2) 
    return(x) 
  }) ) 
for (i in result) cat(names(list_clique[[i]]),"\n")

4 3 9 8 
6 3 9 8 7 

2.3

get.adjacency(g)

10 x 10 sparse Matrix of class "dgCMatrix"

   [[ suppressing 10 column names '1', '2', '3' ... ]]

                      
1  . 1 1 . . . . . . .
2  1 . 1 1 1 . . . . .
3  1 1 . 1 1 1 1 1 1 .
4  . 1 1 . . . 1 1 . .
7  . 1 1 . . 1 1 1 . 1
6  . . 1 . 1 . 1 1 1 1
8  . . 1 1 1 1 . 1 1 1
9  . . 1 1 1 1 1 . . .
10 . . 1 . . 1 1 . . .
5  . . . . 1 1 1 . . .

2.4

### Snowball Sampling
s1=c('3','8')
get.edges(g,E(g));

      [,1] [,2]
 [1,]    1    2
 [2,]    1    3
 [3,]    2    3
 [4,]    2    4
 [5,]    2    5
 [6,]    3    4
 [7,]    3    5
 [8,]    3    6
 [9,]    3    7
[10,]    3    8
[11,]    3    9
[12,]    4    7
[13,]    4    8
[14,]    5    6
[15,]    5    7
[16,]    5    8
[17,]    5   10
[18,]    6    7
[19,]    6    8
[20,]    6    9
[21,]    6   10
[22,]    7    8
[23,]    7    9
[24,]    7   10

h=g;
V(h)$prop='pop'; 
V(h)$prop[which(names(V(h)) %in% s1)]='sample'
target=NULL
for (item in s1){ 
  target=c(target,names(neighbors(h,item))) 
}
V(h)$prop[which(names(V(h)) %in% target)]='sample'
V(h)$color=ifelse(V(h)$prop=='sample','red','grey')
plot(h)

2.5

target=names(V(g))
source='6'
target=target[-which(target %in% source)]
dist=NULL 
for (item in target){dist=c(dist,length(get.shortest.paths(g,source,item)$vpath[[1]]))}
1/(mean(dist))

[1] 0.4285714

Question 3

3.1

polbooks<-read_graph("polbooks.gml", format = "gml")

3.2

summary(polbooks)

IGRAPH f179825 U--- 105 441 -- 
+ attr: id (v/n), label (v/c), value (v/c)

is.directed(polbooks)

[1] FALSE

is.simple(polbooks)

[1] TRUE

is.connected(polbooks)

[1] TRUE

igraph::gsize(polbooks)

[1] 441

igraph::gorder(polbooks)

[1] 105

3.3

Induced-Subgraph Sampling

set.seed(42)
g=induced.subgraph(polbooks,sample(V(polbooks),40)) 
plot(g,vertex.size=8,vertex.label=NA)

3.4

library("poweRlaw")
library("ggplot2")
g <-read_graph("polbooks.gml", format = "gml")
gd <- degree(g)
g_dhist<- as.data.frame(table(gd))
g_dhist[,1] <- as.numeric(g_dhist[,1])
ggplot(g_dhist, aes(x = gd, y = Freq))+
  geom_point()+
  scale_x_continuous("Degree")+
  scale_y_continuous("Frequency")+
  ggtitle("Degree Distribution of Polbooks data (log-log)") +
  theme_bw()