没有合适的资源?快使用搜索试试~ 我知道了~
首页图论基础与应用:从欧拉到现代网络科学
图论基础与应用:从欧拉到现代网络科学
需积分: 9 0 下载量 173 浏览量
更新于2024-07-09
收藏 2.27MB PDF 举报
图论与网络模型是数学和计算机科学中的核心领域,它研究的对象是通过节点(通常表示事物)和边(代表事物间的特定关系)连接起来的图形结构。图论的历史可以追溯到18世纪,以莱布尼茨的位置分析方法为基础,欧拉的贡献尤为显著。他的工作不仅涉及著名的柯尼斯堡七桥问题,也就是欧拉路径问题,还提出了关于凸多边形顶点、棱和面之间关系的Euler公式,这是拓扑学的基石。 1736年,欧拉关于七桥问题的论文开启了图论的大门,这个问题后来扩展到了寻找连通无回路的路径,即哈密顿路径问题。随后,Cayley的研究从微分学的角度转向了树形图的研究,这在化学中尤其重要,因为有机分子常具有树状结构。他对树的计数理论的发展,以及Pólya和De Bruijn的工作,共同奠定了图论计数理论的基础。 1860年至1930年间,Jordan和Klein等数学家进一步深化了图论的研究,他们不仅关注了更复杂的网络模型,还探讨了网络的结构性质,如连通性、度分布、中心性等。这些概念对于理解实际生活中的网络现象至关重要,如互联网、社交网络、生物网络(如蛋白质相互作用网络、神经网络)等。 图论不仅应用于数学理论,也在计算机科学中扮演着核心角色。它是算法设计、数据结构、网络优化、无线通信、人工智能等领域的重要工具。例如,在路由算法中,图论帮助寻找最短路径;在社交网络分析中,理解节点间的连接模式有助于预测信息传播和社区结构;在机器学习中,图神经网络用于处理非结构化的数据。 图论与网络模型是现代科学技术中的一个关键分支,它通过抽象的图形模型揭示了复杂系统内部的规律和结构,对信息技术的进步产生了深远影响。无论是解决实际问题还是推动理论发展,图论都发挥着不可替代的作用。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/20439259/bg7.jpg)
周吕文 数模教材: 图论与网络 第 7 页, 共 38 页
对于边上赋权的图或网络, 也可以用类似邻接矩阵的 n × n 矩阵表示. 此时一条弧所对应的
元素不再是 1, 而是相应的权而已. 如果网络中每条弧赋有多种权, 则可以用多个矩阵表示这些
权.
顶点的度和中心度
在图论中, 对于无向图 G, 顶点 v ∈ V (G) 的度 (degree) 定义为: G 中与 v 关联的边数 (每
个环算作两条边), 记作 d
G
(v) 或 deg(v). 如果 d
G
(v) 是奇数, 称 v 是奇顶点 (odd point); 如果
d
G
(v) 是偶数, 称 v 是偶顶点 (even point). 对于顶点的度, 有以下性质
2
• 所有顶点的度之和等于两倍的边数, 即
v∈V
d(v) = 2|E|.
• 任意一个图的奇顶点的个数是偶数.
对于有向图, 顶点的度又可细分为出度 (outdegree) 和入度 (indegree):
• 出度: 以某顶点为弧尾, 起始于该顶点的弧的数目称为该顶点的出度. 顶点 v 的出度记作
d
−
(v) 或 deg
−
(v). 例如对于图15中的 D 图, 顶点 x 的出度为 d
−
(x) = 3.
• 入度: 以某顶点为弧头, 终止于该顶点的弧的数目称为该顶点的入度. 顶点 v 的入度记作
d
+
(v) 或 deg
+
(v). 例如对于图15中的 D 图, 顶点 x 的入度为 d
+
(x) = 2.
对于有向图, 所有顶点的出度和必然等于所有顶点的入度和, 且等于弧数, 即
v∈V
d
−
(v) =
v∈V
d
+
(v) = |A|.
在网络, 特别是社会网络的分析中, 经常用到中心度 (Centrality) 的概念来描述个人或者组
织在社会网络中具有的权力, 或者说居于的中心地位, 对于信息在整个网络中如何传播, 以及传
播效果都有十分重要的意义. 最常见的度量节点的中心度的方式有点度中心度, 接近中心度, 中
间中心度和特征向量中心度. 下面我们给出这四种中心度的定义 [17, 18], 并以图16所示的社交
网络加以说明:
• 点度中心度 (Degree Centrality): 点度中心度是最常见, 也是最简单的方法. 在无向图
中, 用一个节点的度数来衡量点度中心度. 在有向图中, 可以用节点的入度表示点度中心
度. 在很多情况下, 无向图中的边可以认为是双向的. 因此无论是无向图还是有向图, 顶点
v 的点度中心度 C
D
(v) 可以统一表示为:
C
D
(v) = d
+
(v)
我们称 C
D
(v) 为绝对点度中心度, 相应的标准化中心度为 C
D
(v)/(|V | − 1).
在社会网络中, 一个用户与其他很多用户有直接联系, 该用户就处在中心地位. 即朋友越
多, 越显示出来节点的重要性. 在图16中, 节点 Dave 的好友数最多, 有 6 个人, 所以他成
为了点度中心度最高的节点. 真实的社交网络中, 点度中心度高的那些人一般都是公众人
物, 有较大的知名度.
• 接近中心度 (Closeness Centrality): 在连通图中, 可以用顶点间的最短路径来衡量顶点
间的距离. 定义顶点 v 与其它所有顶点的距离和的倒数为其接近中心度, 即
C
C
(v) =
1
u∈V
d(u, v)
我们称 C
C
(v) 为绝对接近中心度, 相应的标准化中心度为 C
C
(v) · (|V | − 1). 显然, 如果节
点到图中其它节点的最短距离都很小,那么我们认为该节点的接近中心度较高. 这个定义
2
对于这些性质, 我们不作证明, 有兴趣的同学参看专门的图论教材 [16].
7
![](https://csdnimg.cn/release/download_crawler_static/20439259/bg8.jpg)
周吕文 数模教材: 图论与网络 第 8 页, 共 38 页
其实比点度中心度从几何上更符合中心度的概念, 因为到其它节点的平均最短距离最小,
意味着这个节点从几何角度看是处于图的中心位置.
在社会网络中, 当用户越是离其他人近, 则在传播信息的过程中越是不依赖其他人. 因为
一个非核心成员必须通过其它人才能传播信息, 容易受制于其它节点. 在图16中, Fanny
和 Garth 虽然好友数不如 Dave, 但他们到其它所有节点的最短距离是最小的. 直观上说,
Dave 虽然好友数多, 但离图的右半部分的节点更加的远. 真实的社交网络中, 接近中心度
高的节点一般扮演的是八婆的角色. 他们并不是明星, 但是乐于在不同的人群之间传递消
息.
• 中间中心度 (Between Centrality): 定义顶点 v 作为其它两个节点间最短路径的中间点
的频率为该顶点的中间中心度. 即
C
B
(v) =
s=v=t∈V
σ
st
(v)
σ
st
其中 σ
st
表示的是节点 s 和 t 之间的最短路径的数量, 而 σ
st
(v) 是最短路径中经过节点 v
的数量. 计算网络中任意两个节点的所有最短路径, 如果这些最短路径中有很多条都经过
了某个节点, 那么就认为这个节点的中间中心度高.
在社会网络中, 如果一个用户处在许多交往网络的路径上, 则认为此人处于重要地位, 因
为该人具有控制他人交往的能力, 其他人的交往需要通过该人才能进行. 因而中间中心度
测量的是用户对资源信息的控制程度. 在图16中, Hale 就是中间中心度最高的节点,因为
Ike 和 Jane 到其它节点的路径都需要经过 Hale.
• 特征向量中心度 (Eigenvector Centrality): 特征向量中心度是衡量网络上节点的影响
力的重要指标. 一个节点的特征向量中心度等于与其相邻节点的中心度线性叠加. 特征向
量中心度的思想是: 与高中心度节点相邻对自身中心度的提升贡献要比与低中心度节点相
邻大.
C
E
(v) = x
v
=
1
λ
u∈M(v)
x
u
=
1
λ
u∈V
a
vu
x
u
其中 M (v) 是节点 v 的相邻节点集, λ 为常数 (特征值). (a
vu
) 为邻接矩阵. Google 非常
有名的网页排序算法 PageRank[19] 就是特征向量中心度的一种变种.
图16列出了各节点的四种中心度. 关于图16节点中心度的计算, 在本章中的第3节 (第10页) 中将
给出相关程序.
Dave
Fanny
Andre
Betty
Garth
Carol
Ed
Hale
Ike
Jane
C
D
C
C
C
B
C
E
Andre 0.444 0.529 0.023 0.125
Betty 0.444 0.529 0.023 0.125
Carol 0.333 0.500 0.000 0.102
Dave 0.667 0.600 0.102 0.171
Ed 0.333 0.500 0.000 0.102
Fanny 0.556 0.643 0.231 0.142
Garth 0.556 0.643 0.231 0.142
Hale 0.333 0.600 0.389 0.070
Ike 0.222 0.429 0.222 0.017
Jane 0.111 0.310 0.000 0.004
图 16: 社交网络及其标准化中心度, 图片的原型来自 [20]
8
剩余37页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/4262e1effd9b4c3ebd2636479b814bfe_weixin_53173985.jpg!1)
刘乐彬
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述:模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成:理论与算法
- 基于语义元的相似度计算方法研究:改进与有效性验证
- 网格梯度多密度聚类算法:去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型:有效提升系统状态预测
- 煤矿安全评价:信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN:统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)