第九讲 图与网络模型 —— 竞赛图与社会网络

数学建模 讲义 NUDT 2023SP

---

---

9.1 竞赛图模型

• 在有向图中，给每条边指定一个方向，得到的图称为 竞赛图（Tournament）.
• 只计胜、负，没有平局的循环比赛 (tournament) 的结果都可以用竞赛图表示.

---

例：循环比赛的名次

• $N$ 支球队进行循环赛，每场比赛必须分出胜负，没有平局. 如何根据比赛结果排出各队名次？
• 竞赛图模型：用节点表示球队，两个节点之间的边表示两个球队进行了一场比赛，边的方向表示胜负，从胜的一方指向败的一方

---

方案一：按胜负场次排序

• 胜场数 = 结点的出度
• 负场数 = 结点的入度
• $\boxed{\begin{array}{c|cccccc} \text{队伍编号} & 1 & 2 & 3 & 4 & 5 & 6 \\\hline \text{胜场数} & 4 & 3 & 3 & 2 & 2 & 1\\ \text{负场数} & 1 & 2 & 2 & 3 & 3 & 4 \end{array}}$
• 存在并列的情况，无法得到完全的排序

---

方案二：查找完全路径

• 从图中找一条经过所有节点的路径，由这条路径确定球队之间的排序关系（完全路径）
• 存在的问题：结果可能不唯一
• 例如：312456，124563

---

三个结点的竞赛图

---

四个结点的竞赛图

---

竞赛图的分类

• 4 个顶点以上的竞赛图相对更复杂，但仍然可以分为 3 种类型：
  
  1. 可唯一排序：有唯一的完全路径
  2. 无法排序：双向连通竞赛图（存在方向相反的完全路径）
  3. 可部分排序：存在局部相反的完全路径

---

竞赛图的性质

任意一个包含 $n$ 个顶点的竞赛图都有以下性质：

1. 必存在完全路径

2. 若存在唯一的完全路径，则由完全路径确定的顶点的顺序，与按得分多少排列的顺序一致

   • 注：不允许平局，得分为严格大小关系

   • 解决本例中问题的关键是双向连通竞赛图的名次排序

---

双向连通竞赛图的名次排序

• 建立邻接矩阵 $\boldsymbol{A}=[a_{ij}]_{n\times n}$
  
  • 其中 $a_{ij}=\begin{cases} 1 & (i,j)\in E\\ 0 & (i,j)\notin E \end{cases}$
• 双向连通图的邻接矩阵中不存在全为 0 的行，也不存在除对角线元素外全为 1 的行.

---

结点总得分

$$\boldsymbol{s}=\begin{bmatrix} 2 \\ 2 \\ 1 \\ 1 \end{bmatrix}=\boldsymbol{A}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}$$

• 本例中，由 $\boldsymbol{s}$ 无法排出全部名次.

---

多级得分向量

• 记 $\boldsymbol{s}^{(1)}=\boldsymbol{s}$，称为 1 级得分向量
• 进一步计算 2 级得分向量：$\boldsymbol{s}^{(2)}=\boldsymbol{A}\cdot \boldsymbol{s}^{(1)}={(3,2,1,2)}^{\mathrm{T}}$
  
  • 代表某球队所战胜的各个球队的 1 级得分之和
• 依此类推，$k$ 级得分向量：$\bbox[yellow]{\boldsymbol{s}^{(k)}=\boldsymbol{A}\boldsymbol{s}^{(k-1)}=\boldsymbol{A}^k \boldsymbol{e}}$
  
  • $\boldsymbol{e}=[1\;\;1\;\;1\;\;1]^{\mathrm{T}}$.
• $k$ 越大，$\boldsymbol{s}^{(k)}$ 作为排序依据越合理

---

持续观察迭代的结果（归一化后）

---

结果的收敛性

• 结点规模 $n\geq 4$ 的双向连通竞赛图均为素阵，即：存在正整数 $r$，使得 $\boldsymbol{A}^r$ 中的元素均大于零
• Perron-Frobenius定理[1]：素阵 $\boldsymbol{A}$ 的最大特征根为正单根 $\lambda$，对应正特征向量 $\boldsymbol{s}$，且 $\lim\limits_{k\to \infty}\dfrac{\boldsymbol{A}^k \boldsymbol{e}}{\lambda^k}=\boldsymbol{s}$
• 对于前例中的竞赛图有 $\lambda=1.4,\; \boldsymbol{s}={(0.323,0.280,0.167,0.230)}^{\mathrm{T}}$
  
  • 最终排名：$1,2,4,3$

---

邻接矩阵的性质

• $\boldsymbol{A}^k$ 的元素 $a_{ij}^{(k)}$ 表示由顶点 $i$ 到 顶点 $j$ 长度为 $k$ 的路径条数
  
  • 例：$\boldsymbol{A}^3$ 中 $a_{ii}^{(3)}$ 表示包含节点 $i$ 的长度为 $3$ 的路径条数
  • 例：$\dfrac{1}{3}\sum\limits_{i=1}^na_{ii}^{(3)}$ 表示图中包含的“三角”的数量
• $\boldsymbol{S}=(\boldsymbol{I}-\boldsymbol{A})^{-1}=\sum\limits_{k=0}^{\infty}\boldsymbol{A}^k$ 中的元素 $s_{ij}$ 表示由顶点 $i$ 到 $j$ 的所有路径的总数.
• 图中没有有向圈当且仅当 $\boldsymbol{I}-\boldsymbol{A}$ 可逆.

---

传球问题

甲乙丙丁四人传球 6 次，问最终回到甲手里共有多少种传法？

• $\boldsymbol{A}=\begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}$，$\boldsymbol{A}^6=\begin{bmatrix} 183 & 182 & 182 & 182 \\ 182 & 183 & 182 & 182 \\ 182 & 182 & 183 & 182 \\ 182 & 182 & 182 & 183 \end{bmatrix}$

---

例：6 支球队的循环赛

• $\boldsymbol{s}^{(1)}={(4,3,3,2,2,1)}^{\mathrm{T}}$
• $\boldsymbol{s}^{(2)}={(8,5,9,3,4,3)}^{\mathrm{T}}$
• $\boldsymbol{s}^{(3)}={(15,10,16,7,12,9)}^{\mathrm{T}}$
• $\boldsymbol{s}^{(4)}={(38,28,32,21,25,16)}^{\mathrm{T}}$
• $......$
• $\boldsymbol{s}={(0.238,0.164,0.231,0.113,0.150,0.104)}^{\mathrm{T}}$
• $\lambda=2.232$
• 最终排名：$1,3,2,5,4,6$.

---

9.2 网页排序模型 PageRank

---

World Wide Web

• 将互联网上所有页面 (web page) 按照超链接关系建立网络
• 结点为页面
• 有向边代表页面之间的链接关系
  
  • 若 A 页面上有一条链接指向 B 页面，则它们之间的边从 A 指向 B

---

网站排名

问题：可否基于网络中的连接关系，给出互联网上页面（网站）的排名？

• 直接使用竞赛图模型，存在两个问题：
  
  1. 网络不一定是竞赛图，因为页面（网站）之间的超链接可能是双向的
  2. 互联网中页面（站点）之间的连接关系不能用胜负关系来解释，实际意义并不一样

---

PageRank

• PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results.
• It is named after both the term "web page" and co-founder Larry Page.
• PageRank is a way of measuring the importance of website pages.
• According to Google:
  
  • PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.

---

模型的基本假设

• 假设 1：页面的得分由用户根据超链接网络的结构访问页面的概率决定
• 假设 2：用户在选择下一个要访问的页面时，不考虑其过去浏览过哪些页面，也与当前页面的内容无关
  
  • 用户的下一个选择，取决于其个人的兴趣和当前页面包含的超链接
  • 对于任一个页面，从其他页面指向其的边越多，则用户去往该页面的的可能性越大
• 本质上，超链接网络的结构决定了用户从一个网站（状态）转换为另外一个网站（状态）的概率

---

转移矩阵

• 设图的邻接矩阵为 $\boldsymbol{G}=[g_{ij}]_{n\times n}$
• 用户从页面 $i$ 转移到页面 $j$ 的概率为 $\bbox[yellow]{a_{ij}=\dfrac{1-d}{n}+d\dfrac{g_{ij}}{c_i}}$
  
  • $c_i=\sum\limits_{j=1}^ng_{ij}$：页面 $i$ 的出边数量
  • $\dfrac{1-d}{n}$：基本转移概率，表示用户访问任意一个网站的概率
  • 加权系数 $d$：用户浏览页面的过程中有 $d$ 的比例由页面沿着超链接进行跳转，在 PageRank 模型中，通常取 $\bbox[yellow]{d=0.85}$
• 记 $\boldsymbol{A}=[a_{ij}]_{n\times n}$，称 $\boldsymbol{A}^{\mathrm{T}}$ 为该网络中的 转移矩阵 (Transition Matrix)

---

PageRank 的定义

• 记 $\boldsymbol{x}=[x_1\;x_2\;...\;x_n]^{\mathrm{T}}$，其中 $x_k$ 表示网页 $k$ 被访问的概率
  
  • 则：$x_k=\sum\limits_{j=1}^na_{jk}x_j,\;k=1,...,n.$ 或 $\bbox[yellow]{\boldsymbol{x}=\boldsymbol{A}^{\mathrm{T}}\boldsymbol{x}}$
• 上式说明，转移矩阵 $\boldsymbol{A}^{\mathrm{T}}$ 的特征值 $1$ 对应的归一化特征向量即为网页被访问的概率向量，其中的每个分量值被称为每个网页对应的 PageRank.
• 定理： 对于转移矩阵 $\boldsymbol{A}^{\mathrm{T}}$，存在唯一的 主特征值（最大特征值）为 $1$，且该特征值对应的特征向量各分量均非负.

---

例：求给定网络中每个结点的 PageRank

邻接矩阵

$$\boldsymbol{G}=\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

---

状态转移矩阵

$$\boldsymbol{A}=\begin{bmatrix} 0.025 & 0.875 & 0.025 & 0.025 & 0.025 & 0.025 \\ 0.025 & 0.025 & 0.450 & 0.450 & 0.025 & 0.025 \\ 0.025 & 0.025 & 0.025 & 0.308 & 0.308 & 0.308 \\ 0.875 & 0.025 & 0.025 & 0.025 & 0.025 & 0.025 \\ 0.025 & 0.025 & 0.025 & 0.025 & 0.025 & 0.875 \\ 0.875 & 0.025 & 0.025 & 0.025 & 0.025 & 0.025 \end{bmatrix}$$

---

计算矩阵 $\boldsymbol{A}$ 的特征值 $1$ 所对应的特征向量，并归一化后得到各网页的 PageRank

$$(0.2675,0.2524,0.1323,0.1697,0.0625,0.1156)$$

---

缺陷与问题

• PageRank 的主要缺点在于旧的页面的排名往往会比新页面高.
  
  • 因为即使是质量很高的新页面也往往不会有很多外链，除非它是某个已经存在站点的子站点.
  • 因此 PageRank 还需要与多项算法或启发信息结合以保证其结果的准确性（权威性）.
• 例如，PageRank 常常对维基百科页面给与更大的偏好，在条目名称的搜索结果中，维基百科页面经常在大多数页面甚至所有页面之前.
• 例如：处罚恶意提高网页 PageRank 的行为（搜索引擎优化，Search Engine Optimization）
  
  • 如何区分正常的链接和不正常的链接，仍然是 Google 的核心商业机密
  • 在Google的链接规范中清楚地说明了哪些是属于违反规范的行为

---

9.3 基于网络的学术评价模型

• 问题：如何评价学者的学术影响力？

---

观察与假设

• 发表论文数量越多、质量越高的影响力越大
• 与影响力越大的人关系越密切的影响力也越大
  
  • 学者之间合作发表文献可以反映学者交流的广泛程度和学术影响力
  • 一些交流广泛的学者往往被业界所熟识，也在业界具有较大的影响力

---

Paul Erdős

• an extraordinarily prolific Hungarian-Jewish mathematician who published more than 1,500 papers before his death in 1996.
  
  • 当代发表最多数学论文的数学家之一，也是全世界和各种各样不同国籍的数学家合作发表论文最多的人.
• Believing that the meaning of life is to “prove and conjecture,” Erdös spent almost all of his time on the road, attending meetings, visiting any of his hundreds of collaborators and working 20-hour days in constant pursuit of mathematical progress.
  
  • “对我来说，研究数学就像呼吸一样自然.”

---

Erdős 数

• Erdős 数（缩写：EN）：根据与 Paul Erdős 合作的紧密程度计算的一个数.
  
  • Erdős 自己为 0，与其直接合作的作者的 EN 为 1，而与这些作者合作过的作者的 EN 为 2，依次类推.
  • 数越小意味着影响力越大.

---

---

问题描述

• 现有一个 511 人的与 Erdős 直接合作的学者的数据集合，数据中给出了这 511 人之间是否合作发表文献的关系，
• 请依据此合作关系建立评价学者学术影响力的数学模型，要求该模型中应该排除 Erdős 所造成的影响.

---

问题分析

1. 与影响力相关因素
   
   • Erdős 数
   • 与 Erdős 合作的次数，进一步可以利用其它指标，比如
   • H 指数
   • 论文引用总次数
   • 其它的评价指标
2. 学者之间的合作关系如何反应到学者影响力中？

---

合作网络

• 网络中的一个结点代表一位学者
• 结点之间是否有边取决于两位作者是否合作发表过学术文献（不考虑合作次数）
• 合作网络是一个无向图，共计 511 个结点，180000 条边

---

学术影响力的评价要素

• 假设：
  
  1. 合作者越多的学者影响力越大；
  2. 与 Erdős 合作次数越多的作者越重要；
  3. 与越重要的人合作，说明该学者也越重要；
• 指标 I：与 Erdős 合作的次数 $C_i^a=\dfrac{n\cdot n_i}{\sum\limits_{i=1}^nn_i}$
  
  • $n_i$ 为学者 $i$ 与 Erdős 合作的次数
• 指标 II：特征向量度量 $C_i^e=\sum\limits_{j}a_{ij}C_j^e$

---

---

指标合成

• 方法一：理想点法，定义指标理想点 $(iC_e,iC_a)$，按点与理想点的欧式距离进行排序
  
  • $D(i)=\sqrt{(C_i^e-iC_e)^2+(C_i^a-iC_a)^2}$
• 方法二：加权平均
  
  • $P(i)=\alpha C_i^e+(1-\alpha)C_i^a$

---

9.4 社会网络与社会网络分析

• 社会网络（Social network）：节点通常是个人或组织，边的连接则反映出结点的某种社会关系（例如：价值观、理想、观念、兴趣爱好、友谊、血缘关系、共同厌恶的事物、冲突或贸易）
• 相对于经典的图模型，社会网络往往规模更大，结构也更加复杂的
• 社会网络的研究重点，主要是通过对网络结构的量化分析，来推断网络整体的宏观特性（如连通性、鲁棒性、关键节点、演化规律等）

---

社会网络分析

• 一项热门的研究，在现代社会学、人类学、社会语言学、地理、社会心理学、通信研究、信息学、历史学、社会分析、探勘、组织研究、经济学，以及生物学等领域有广泛应用
• 常用的度量指标：分支度、点度（Degree）、密度（Density）、派别（Clique）、亲密度中心性（Closeness Centrality）、中介度中心性（Betweeness Centrality）、丛聚系数（Clustering Coefficient）

---

艺术品拍卖网络

• 利用网络分析来考察艺术家在博物馆展览中一起展出时产生的网络.
• 这种网络已被证明会影响艺术家在历史和历史叙事中的认可度，甚至有时直接决定了艺术家的个人成就.
• 也有研究探讨了艺术家的网络分组如何影响单个艺术家的拍卖业绩.
• 艺术家的商业价值已被证明在与更高地位的团簇相关联时有可能得到提高.

---

犯罪网络

• 在犯罪学和城市社会学中，人们对犯罪行为人之间的社会网络给予了很大关注.
• 例如，谋杀案可以被看作是帮派之间的一系列交流.
• 谋杀的发生可以被视为从单一来源向外的扩散，因为较弱的帮派没有能力杀死较强帮派的成员作为报复，但必须实施其他暴力行为以保持其实力的声誉.
• 以此为基础，来识别网络中需要重点打击的对象或研究犯罪活动的扩散规律.

---

人口学

• 在人口学中，对社会网络的研究带来了新的抽样方法，用于估计和接触难以统计的人口（例如，无家可归者或静脉注射毒品者）.
• 例如，受访者驱动抽样是一种基于网络的抽样技术，它依赖于调查的受访者推荐更多的受访者.

---

语言和语言学

• 对语言和语言学的研究，特别是进化语言学，侧重于语言形式的发展和变化、声音或词语的转移，通过社会互动的网络从一个语言系统转移到另一个语言系统.
• 社会网络在语言转变中也很重要，因为一群人在他们的日常使用引入或启用某类语言是语言转变的驱动力.
• 这可能是通过语言创新的社会传播发生的，也可能是通过与同龄人的交流获得第二语言.

---

社会网络分析平台与工具

腾讯 Plato

• 开源地址：https://github.com/tencent/plato
• 高效地支撑腾讯超大规模社交网络图数据的各类计算
• 已开源：图特征、结点中心性指标、社团识别、图表示学习、聚类算法、BFS

---

Apache Spark GraphX

• API for graphs and graph-parallel computation
• 支持的算法：PageRank、LabelPropagation、SVD++、Triangle Count

---

课后思考

（$\star\star\star$）检索阅读一篇使用网络方法研究学者间合作的论文（注意必须是在正式学术刊物上发表的），简述其建模的主要思路、模型的假设与参数、模型使用的数学表达式的含义，以及论文得到的主要结果. 在文字介绍的基础上，使用计算机仿真，复现论文中的至少 2 个实验结果. 注意：提交作业时，须附上所介绍论文的原文.