-
Notifications
You must be signed in to change notification settings - Fork 43
/
11 Directed network and hypergraph.Rmd
107 lines (79 loc) · 5.1 KB
/
11 Directed network and hypergraph.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
---
title: "有向网络和超图 2020213053010刘佳怡"
author: "刘佳怡"
date: "2021/10/20"
output: word_document
---
```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
```
## 一、有向网络
1、有向网络
（1）定义
有向网络或有向图：是指每条边都有一个方向即一个顶点指向另一个顶点的网络。这些边本身称为有向边，可以用带着箭头的线表示。
（2）性质
一般来说,有向网络的邻接矩阵是不对称的。如果我们愿意,我们可以把无向网络看作是有向网络,其中每条无向边都被替换成两条在同一对顶点之间方问相反的有向边。这样的网络的邻接矩阵是对称的,并且与原始的无向网络完全相同。
（3）举例
图一：
例如，图一小网络的邻接矩阵为：
（3）注意
像无向网络一样,有向网络可以有多重边和自边,它们分别用大于1的元素和非零对角元素在邻接矩阵中表示。然而,有向网络中的自边是通过将邻接矩阵的对角元素设为1来表示的,而不是像无向网络中的自边是2。
2、无环有向网络
（1）定义
有向网络中的环是由边组成的闭合环路,每个边上的箭头指向环路的同一方向。然而,有些有向网络没有环,这些被称为无环网络。
注意：一条自边即一条连接顶点和自身的边——被认为是一个循环,因此一个非循环网络也没有自边。
如图3：
（2）举例：
非循环有向网络的经典例子是论文的引用网络,当你写一篇论文时,你只能引用另一篇已经写过的论文,这意味着在一个引文网络中,所有的有向边都指向时间上的倒退。
3、共引和文献耦合
（1）由来与联系
有时为了分析,我们会将一个有向网络转换成一个无向网络。使一个有向网络变为无向的一个简单方法就是完全忽略边的方向,这种方法在某些情况下是可行的,但不可避免地会出现一些关于网络结构的问题。一种更复杂的方法是使用“共引”或“文献耦合”,这两种不同但却相关的思想。
（2）共引：在一个有向引文网络中，一个节点表示一篇文章，如果文章i引用了文章j，那么就有一条从节点i指向节点j的有向边。两篇文章的共引就是指同时引用这两篇文章的其他文章的数量。
我们可以构造无向的共引网络如下：如果两篇文章被至少一篇其他文章同时引用，那么在对应的两个节点之间就有一条无向边。
（3）文献耦合：在引文网络中，两篇文章的文献耦合就是指这两篇文章的参考文献中的相同文章的数目，也就是同时被这两篇文章引用的其他文章的数目。
可以定义有向的引文网络所对应的无向的文献耦合网络如下：如果两篇文章至少有一篇相同的参考文献，那么在对应的两个节点之间就有一条边。
##二、有向网络简单示例
```{r}
rm(list=ls())
library(igraph)
#1.用igraph创建图表
g<- graph(c(1,2, 1,8,1,9,1,10,2,4,2,5,2,6,2,3,3,7,3,11,3,10,3,1), directed=T)
com = walktrap.community(g, steps = 6)
V(g)$sg = com$membership + 1
V(g)$color = rainbow(max(V(g)$sg))[V(g)$sg]
plot(g, layout=layout.fruchterman.reingold,edge.color = grey(0.4),edge.arrow.mode = ">",vertex.size =20,
vertex.color = V(g)$color)
```
```{r}
rm(list=ls())
library(igraph)
library(plyr)
#1.用igraph创建图表
g<- graph(c(1,2,1,3,1,4,2,3,2,4,3,4,4,2), directed=T)
com = walktrap.community(g, steps = 6)
V(g)$sg = com$membership + 1
V(g)$color = rainbow(max(V(g)$sg))[V(g)$sg]
plot(g, layout=layout.fruchterman.reingold,edge.color = grey(0.4),edge.arrow.mode = ">",vertex.size =20,
vertex.color = V(g)$color)
pr<-page.rank(g)$vector
df<-data.frame(Object=1:4,PageRank=pr)
arrange(df,desc(PageRank))
```
## 三、超图
（1）定义
在某些类型的网络中,连边一次连接两个以上的顶点。例如：我们可能想要创建一个社交网络,代表一个更大的社区中的家庭。家庭中可以有两个人以上,在这样的家庭中表示家庭关系的最好方法是使用一种广义的边连接两个以上的顶点。这样的边称为超边,具有超边的网络称为超图。
（2）性质
超图的本质特征在于它的超边，它可以连接两个以上的结点(包括两个)。按这样的意义来说，我们所熟悉的普通图只是超图的一个特例而已，而超图则定义了一个更加宽泛的图。
（3）举例
通过用平面点识别超图的顶点，以及通过识别包含这些边缘的顶点的连接域的边，可以在平面中表示超图。
例如：可以表示超图H与一组顶点$V={v1…v6}$和边缘家族
$E={E1={v1}, E2={v1,v3}, E3={v1,v2,v3},E4=E5={v2,v4}, E6={v3,v4,v5},E7=∅}$
如图4所示：
##四、参考文献
[1]Albert-Laszlo Barabasi.Network Science[M].2014
[2]汪小帆，李翔，陈关荣.网络科学导论[M].2012
[3]维基百科 https://encyclopediaofmath.org/wiki/Hypergraph