图论基础
Huang Huilin
4/2/2022
安装包
# install.packages('sand')
# install.packages('igraph')
library(sand)
library(igraph)
?sand解决Rstudio不能显示中文的方法
library(showtext)
showtext_auto()创建网络图
无向图和有向图
library(igraph)
g<- graph_from_literal(1-2,1-3,2-3,2-4,3-5,4-5,4-6,4-7,5-6,6-7)
V(g)## + 7/7 vertices, named, from 8aa0f72:
## [1] 1 2 3 4 5 6 7E(g)## + 10/10 edges from 8aa0f72 (vertex names):
## [1] 1--2 1--3 2--3 2--4 3--5 4--5 4--6 4--7 5--6 6--7print_all(g)## IGRAPH 8aa0f72 UN-- 7 10 --
## + attr: name (v/c)
## + edges (vertex names):
## 1 -- 2, 3
## 2 -- 1, 3, 4
## 3 -- 1, 2, 5
## 4 -- 2, 5, 6, 7
## 5 -- 3, 4, 6
## 6 -- 4, 5, 7
## 7 -- 4, 6dg<-graph_from_literal(1-+2,1-+3,2++3)
par(mfrow=c(1,2))
plot(g,main="g:无向图")
plot(dg,main="dg:有向图")
dg<-graph_from_literal(Sam-+Mary,Sam-+Tom,Mary++Tom)
str(dg)## Class 'igraph' hidden list of 10
## $ : num 3
## $ : logi TRUE
## $ : num [1:4] 0 0 1 2
## $ : num [1:4] 1 2 2 1
## $ : num [1:4] 0 1 2 3
## $ : num [1:4] 0 3 1 2
## $ : num [1:4] 0 2 3 4
## $ : num [1:4] 0 0 2 4
## $ :List of 4
## ..$ : num [1:3] 1 0 1
## ..$ : Named list()
## ..$ :List of 1
## .. ..$ name: chr [1:3] "Sam" "Mary" "Tom"
## ..$ : Named list()
## $ :<environment: 0x7f9ba7356fe0>V(dg)$name<-c("Sam","Mary","Tom")
E(dg)## + 4/4 edges from b401a0c (vertex names):
## [1] Sam ->Mary Sam ->Tom Mary->Tom Tom ->Maryplot(dg,main="dg:有向图")
图的表示：邻接矩阵
as_adjacency_matrix(g)## 7 x 7 sparse Matrix of class "dgCMatrix"
## 1 2 3 4 5 6 7
## 1 . 1 1 . . . .
## 2 1 . 1 1 . . .
## 3 1 1 . . 1 . .
## 4 . 1 . . 1 1 1
## 5 . . 1 1 . 1 .
## 6 . . . 1 1 . 1
## 7 . . . 1 . 1 .get.adjacency(g)## 7 x 7 sparse Matrix of class "dgCMatrix"
## 1 2 3 4 5 6 7
## 1 . 1 1 . . . .
## 2 1 . 1 1 . . .
## 3 1 1 . . 1 . .
## 4 . 1 . . 1 1 1
## 5 . . 1 1 . 1 .
## 6 . . . 1 1 . 1
## 7 . . . 1 . 1 .as_adjacency_matrix(dg)## 3 x 3 sparse Matrix of class "dgCMatrix"
## Sam Mary Tom
## Sam . 1 1
## Mary . . 1
## Tom . 1 .get.adjacency(dg)## 3 x 3 sparse Matrix of class "dgCMatrix"
## Sam Mary Tom
## Sam . 1 1
## Mary . . 1
## Tom . 1 .图的运算：子图、导出子图、图的并、交、差、补
#子图和诱导子图
h<-induced_subgraph(g,1:5)
print_all(h)## IGRAPH 3797e7b UN-- 5 6 --
## + attr: name (v/c)
## + edges from 3797e7b (vertex names):
## [1] 1--2 1--3 2--3 2--4 3--5 4--5par(mfrow=c(1,2))
plot(g,main="g")
plot(h,main="h:induced subgraph of g")
#删减或增加节点
h<-g-vertices(c(6,7))
h1<-h+vertices(c(6,7))
g<-h1+edges(c(4,6),c(4,7),c(5,6),c(6,7))
par(mfrow=c(1,2))
plot(h,main="h")
plot(h1,main="h1")
h2<-graph_from_literal(4-6,4-7,5-6,5-7)
g<-union(h1,h2)
par(mfrow=c(1,3))
plot(h1,main="h1")
plot(h2,main="h2")
plot(g,main="g")
网络图的属性
节点、边、图的属性
#节点属性
plot(dg)
V(dg)$name## [1] "Sam" "Mary" "Tom"#添加节点所代表个体的性别
V(dg)$gender<-c("M","F","M")
V(dg)$gender## [1] "M" "F" "M"#边属性
plot(g)
is_weighted(g)## [1] FALSEwg<-g
E(wg)$weight<-runif(ecount(wg))
is_weighted(wg)## [1] TRUEg$name<-"Toy Graph"
plot(wg)
数据框：以Lazega律师数据为例
合作关系以边列表的形式被存储在数据框elist.lazega中， 节点属性被存储在数据框v.attr.lazega中
library(sand)
data(lazega)
print_all(lazega)## IGRAPH 3e8b2bf UN-- 36 115 --
## + attr: name (v/c), Seniority (v/n), Status (v/n), Gender (v/n), Office
## | (v/n), Years (v/n), Age (v/n), Practice (v/n), School (v/n)
## + edges (vertex names):
## V1 -- V17
## V2 -- V7, V16, V17, V22, V26, V29
## V3 -- V18, V25, V28
## V4 -- V12, V17, V19, V20, V22, V26, V28, V29, V31
## V5 -- V18, V24, V28, V31, V32, V33
## V6 -- V24, V28, V30, V31, V32
## V7 -- V2, V18
## V8 --
## V9 -- V12, V16, V29
## V10 -- V24, V26, V29, V31, V34
## V11 -- V17
## V12 -- V4, V9, V15, V16, V17, V19, V26, V29, V34
## V13 -- V31, V33
## V14 -- V16, V17, V25, V28, V30, V32
## V15 -- V12, V16, V19, V20, V22, V24, V26, V29, V32, V35, V36
## V16 -- V2, V9, V12, V14, V15, V17, V22, V26, V27, V29, V32, V34, V36
## V17 -- V1, V2, V4, V11, V12, V14, V16, V19, V22, V24, V25, V26, V28,
## V29, V34
## V18 -- V3, V5, V7, V28, V31, V32, V33, V35
## V19 -- V4, V12, V15, V17, V22, V24, V26, V28, V34, V35
## V20 -- V4, V15, V22, V26
## V21 -- V27
## V22 -- V2, V4, V15, V16, V17, V19, V20, V31, V32
## V23 --
## V24 -- V5, V6, V10, V15, V17, V19, V26, V31, V36
## V25 -- V3, V14, V17, V28, V35
## V26 -- V2, V4, V10, V12, V15, V16, V17, V19, V20, V24, V27, V32
## V27 -- V16, V21, V26
## V28 -- V3, V4, V5, V6, V14, V17, V18, V19, V25, V30, V31, V32, V35
## V29 -- V2, V4, V9, V10, V12, V15, V16, V17, V34
## V30 -- V6, V14, V28, V31
## V31 -- V4, V5, V6, V10, V13, V18, V22, V24, V28, V30, V32, V33, V35
## V32 -- V5, V6, V14, V15, V16, V18, V22, V26, V28, V31, V33, V35
## V33 -- V5, V13, V18, V31, V32
## V34 -- V10, V12, V16, V17, V19, V29
## V35 -- V15, V18, V19, V25, V28, V31, V32
## V36 -- V15, V16, V24g.lazega<-graph_from_data_frame(elist.lazega,
directed = "FALSE",
vertices=v.attr.lazega)
g.lazega$name <- "Lazega Lawyers"
plot(g.lazega,layout=layout_with_kk,vertex.color="green",
main="Lazega Lawyers")
vcount(g.lazega)## [1] 36ecount(g.lazega)## [1] 115vertex_attr_names(g.lazega)## [1] "name" "Seniority" "Status" "Gender" "Office" "Years"
## [7] "Age" "Practice" "School"图的基本概念
简单图：不存在自环和多重边的图
#判断图是否为简单图
is_simple(g)## [1] TRUEmg<-g+edge(2,3)
print_all(mg)## IGRAPH d448c4b UN-- 7 11 -- Toy Graph
## + attr: name (g/c), name (v/c)
## + edges (vertex names):
## 1 -- 2, 3
## 2 -- 1, 3, 3, 4
## 3 -- 1, 2, 2, 5
## 4 -- 2, 5, 6, 7
## 5 -- 3, 4, 6, 7
## 6 -- 4, 5
## 7 -- 4, 5is_simple(mg)## [1] FALSEpar(mfrow=c(1,2))
plot(g,main="简单图：g")
plot(mg,main="多重图：mg")
#将多重图转化为含权图
E(mg)$weight<-1
wg2<-simplify(mg)
is_simple(wg2)## [1] TRUEprint_all(wg2)## IGRAPH fe89b65 UNW- 7 10 -- Toy Graph
## + attr: name (g/c), name (v/c), weight (e/n)
## + edges (vertex names):
## 1 -- 2, 3
## 2 -- 1, 3, 4
## 3 -- 1, 2, 5
## 4 -- 2, 5, 6, 7
## 5 -- 3, 4, 6, 7
## 6 -- 4, 5
## 7 -- 4, 5E(wg2)$weight## [1] 1 1 2 1 1 1 1 1 1 1#输出某个节点的邻居节点
neighbors(g,5)## + 4/7 vertices, named, from 4c5bf7b:
## [1] 3 4 6 7#输出图的度序列
degree(g)## 1 2 3 4 5 6 7
## 2 3 3 4 4 2 2#有向图的入度和出度
plot(dg,main="dg")
degree(dg,mode="in")## Sam Mary Tom
## 0 2 2degree(dg,mode="out")## Sam Mary Tom
## 2 1 1
通路walk:图G中，从\(v_{0}\)到\(v_{l}\)的通路，是指一个节点和边交替的序列 \(\{v_{0},e_{1},v_{1},e_{2},...,v_{l-1},e_{l},v_{l}\}\),其中\(e_{i}\)的端点是 \(\{v_{i-1},v_{i}\}\).
迹trail:不存在重复边的通路walk.
路径path:不存在重复节点的通路walk.
回路circuit:起点和终点相同的迹称为回路.
环cycle:当起点和终点相同但其他所有节点都不同长度至少为3的通路，称为”环”. 不存在环的图称为“无环的”acyclic.
图G中，节点\(u\)和节点\(v\)之间如果存在一条walk,则称节点\(u\)和节点\(v\)是可达的。 若图G中任意两个节点均可达，则称图G是连通的。
plot(g)
#判断图是否连通
is_connected(g)## [1] TRUE#探寻图g的连通分支信息
clusters(g)## $membership
## 1 2 3 4 5 6 7
## 1 1 1 1 1 1 1
##
## $csize
## [1] 7
##
## $no
## [1] 1若图G的“基础图”(underlying graph,即从G中去除边的方向得到的图）是连通的，则称图为“弱连通”(weakly connected).
若任意两个节点\(u\)和\(v\)之间均存在有向walk,则称图为“强连通”.
plot(dg)
is_connected(dg,mode="weak")## [1] TRUEis_connected(dg,mode="strong")## [1] FALSEdiameter(g,weights=NA)## [1] 3特殊类型的图:完全图、环、树图、星图
DAG(directed acyclic graph)有向无环图：有向且不存在有向环的一类图.
g.full<- make_full_graph(7)
g.ring<-make_ring(7)
g.tree<-make_tree(7,children=2,mode="undirected")
g.star<-make_star(7,mode="undirected")
par(mfrow=c(2,2),mai = c(0.2, 0.2, 0.2, 0.2))
plot(g.full,main="完全图")
plot(g.ring,main="环")
plot(g.tree,main="树")
plot(g.star,main="星图")
par(mfrow=c(1,1))
plot(dg)
#判断图dg是否为有向无环图
is_dag(dg)## [1] FALSE二部图
g.bip<-graph_from_literal(actor1:actor2:actor3,
movie1:movie2,
actor1:actor2-movie1,
actor2:actor3-movie2 )
#判断节点类型
V(g.bip)$type<-grepl("^movie",V(g.bip)$name)
V(g.bip)$type ## [1] FALSE FALSE FALSE TRUE TRUEprint_all(g.bip,v=T)## IGRAPH d41e883 UN-B 5 4 --
## + attr: name (v/c), type (v/l)
## + vertex attributes:
## | name type
## | [1] actor1 FALSE
## | [2] actor2 FALSE
## | [3] actor3 FALSE
## | [4] movie1 TRUE
## | [5] movie2 TRUE
## + edges from d41e883 (vertex names):
## [1] actor1--movie1 actor2--movie1 actor2--movie2 actor3--movie2#节点子集的投影
proj<-bipartite_projection(g.bip)
print_all(proj[[1]])## IGRAPH 4b74b09 UNW- 3 2 --
## + attr: name (v/c), weight (e/n)
## + edges from 4b74b09 (vertex names):
## [1] actor1--actor2 actor2--actor3print_all(proj[[2]])## IGRAPH a261929 UNW- 2 1 --
## + attr: name (v/c), weight (e/n)
## + edge from a261929 (vertex names):
## [1] movie1--movie2par(mfrow=c(1,3))
plot(g.bip,layout=layout_as_bipartite,
vertex.color=c("green","red"))
plot(proj[[1]])
plot(proj[[2]])