什么是图论模型？它的起源是什么？

　　图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。

　　图论模型就是用图（点和边构成的抽象图形）来描述事物之间关系。图论模型G=<V,E,R>，是一个三元组，用于描述事物之间的关系。所有事物的集合V是图论模型中的顶点，事物之间的联系用一条边表示，所有这些联系构成图论模型的边集合E，R则是定义在V x V上的二元关系，是集合V x V的笛卡尔积。

主要内容：三元闭包关系的强度及其与网络结构的关系

一、图论

1、图：包含一组元素以及他们之间连接关系的集合

（1）节点（vertex，node，point）

边（链接，连接，关系，联系；edge，link，tie）

邻居

（2）常用的图：合作图、即时通信图、信息链接图

（3）有向图（节点、有向边）、无向图

2、图的同构：画法不同，但本质上（结构上）相同

节点的连接关系比节点的位置更重要。

题目下面哪些图是同构的？

题目

3、路径、最短路径、距离、圈

①路径：一个节点序列的集合，且序列中任意两个相邻节点都有一条边相连。

两点之间可有多条路径。

路径的长度：一条路径所包含的边数

②最短路径-->又叫两点之间的距离

③距离-->最短路径的长度

题目下图中节点A和节点B之间的距离是多少？

④圈

环状结构；至少三条边，起点与终点相同，所有节点均不重复。

部署网络的一个原则：要求每条边都至少在一个圈里（为了保证连通性，带来冗余）。eg：ARPANET的每条边都在圈里

4、连通性

（1）连通图：一个图中任意两点间有路径相通；每条边都在一个圈里。

（2）非连通图

（3）连通分量

若图G的节点子集满足：①连通性：子集中任意两个节点间均有路径相连；②独立性：该子集不是其他满足条件1的子集的一部分；则称G的节点子集是连通分量

题目下面指出的哪些节点集合不对应这个6节点图的一个连通分量？

（4）超大连通分量（giant component）

非形式化地对于包含其中大部分节点的连通分量的称谓。

Q：全世界友谊图是否为连通图？A：即使本身不具备联通性，其中的连通分量也是巨大的。

5、距离与广度优先搜索法

深度搜索和广度搜索的算法复杂度相同，但是深度搜索用的多，因为广度搜索对存储的要求高，一层中节点太多。

广度优先：从一个节点开始，沿着相连的边，将图的节点一一列举。

二、弱联系和强联系

1、三元闭包（triadic closure）

在一个社交圈内，如果两个互不认识的人有了一个共同的朋友，则他们将来成为朋友的可能性会提高。

三元闭包是社交网络演化的基本结构性原因。

三语闭包产生的原因：机会、信任、动机

三元闭包原理扩展：

①“量”的方面

两个人的共同朋友越多，他们成为朋友的可能性越高

②“质”的方面

两个人与共同朋友的关系越密切，则他们成为朋友的可能性越高。

2、聚集系数

节点A的聚集系数：A的任意两个朋友彼此也是朋友的概率

总对数=节点的度（节点度-1）/2

聚集系数就是三元闭包在一个节点上的属性测度，表示“凝聚力”的大小

聚集系数随时间的变化体现了三元闭包对网络结构的影响趋势。节点附近的三元闭包过程越强，其聚集系数就越大。

题目

3、三元闭包原理的大数据验证

（1）三元闭包原理的表达（定量）

最初表述：如果两个互不认识的人有了一个共用朋友，则他们在未来成为朋友的可能性增加。

转变成：两个互不认识的人的共同朋友数越多，则他俩在未来成为朋友的可能性越大。

（2）验证数据：电子邮件网络≈社会网络

（3）考察网络的演化：考察两个相继的网络快照

考察三元闭包现象的测度：当前共同朋友数与后来成为朋友的概率关系。

得到一个图-->找不连接的边-->计算不连接节点他们的共同朋友-->过一定的时间再做。

题目

4、弱联系的力量

（1）桥：一张图中，已知A和B相连，若去掉连接A和B的边，会导致A和B属于不同的连通分量，则该边称为桥。（断开就不通）

（2）捷径（local bridge）：若边A-B的端点A和B没有共同朋友，则称边A-B为捷径。（断开距离>2）

（3）跨度：没有捷径时的距离。

如果A和B的跨度>2，则A和B之间的边是捷径。

跨度很大的捷径的作用类似于桥。

通过捷径联系的人更可能为你提供工作信息。（找工作问题的第一个解释）

5、强三元闭包

捷径很大程度上可能是弱联系

考虑社交网络中关系的强度-->边的属性

边属性的一种测度：强-弱（强度可以使连续变量）

（1）强三元闭包原理（架设）：如果A-B和A-C之间的关系为强联系，则B-C之间形成边的可能性应该很高

若A有两个强联系邻居B和C，但B-C之间没有任何关系（s或w，即strengh或weak），则称节点A违背了强三元闭包原理。反之，则称A符合强三元闭包原理。

（2）在一定条件下：捷径-->弱联系

若节点A符合强三元闭包，且至少有两个强联系邻居，则与A相连的任何捷径必定是弱联系。

（假设A-B是s，而A有个强联系邻居C，即A-C为s，那么根据强三元闭包，一段时间后B-C会有联系，A-B的跨度为2，与捷径的定义矛盾）

连接关系：强联系、弱联系

结构关系：捷径、非捷径

三元闭包将连接关系和结构关系连接起来了。

（两人的关系强度如何，与两人是否有共同好友相关，但不等价）捷径意味着没有共同朋友，强度为“弱”。

（3）统计推论：共同朋友越多，关系强度越高

6、邻里重叠度

（1）社交网络中，桥、捷径一般不存在-->邻里重叠度（Neighborhood Overlap）

①捷径是邻里重叠度为0的边

②可以把邻里重叠地很低的边粗略的视为捷径

③一种很好的从二到多的数学抽象的例子

目标3：弱联系起到将包含大量强联系的紧密社区连接起来的作用。（方法：从强度最强的关系边开始，按强度的降序逐渐删边；从强度最弱的关系边，按强度的升序，逐渐删除边。发现：从弱的开始删，网络崩的快）

（2）社交网络实验

Facebook的三种连接：相互连接、单向连接、保持关系。

社交网络中好友数目：尽管一个用户可声明关注大量（几百）其，但实际关注的大约在50以下，而真正有联系的则更少，在20以下。

社会网络是用弱系连起来的若干紧密群体。

7、结构洞

（1）嵌入性：一条边的嵌入性为其两个端点共同的邻居数

①嵌入性就是邻里叠度的分子

②捷径就是嵌入性0的边

③嵌入性越大的边相互间的信任就越强；嵌入性越强的边社会资本也越多

节点A：

①聚集系数较高（7/10）

②A关联的边多数具有较大的嵌入性

③处于一个相对比较诚实可信的群体

节点B：

①聚集数较（2/10）

②他关联的边多数具有较小的嵌入性

③结构洞： 两个没有紧密联系的节点集合之间的“空地”

节点B具有的优势：

①信息优势： 可以较早地获得网络中多个互不交叉部分的信息

②创新优势： 处在捷径的一端对创造性有放大功能

③权力优势：所处位置具有某种社交“把关”的机会

启示：有效破坏网络的连通性（以最快最小的代价）：破坏处于结构洞位置的节点或捷径（关键连接）

（2）数字大炮（一种DDoS）（攻的是路由器的BGP协议）

边界网关协议（BGP）

主要用于两个自治系统（AS）间交换路由信息

使用矢量路径机制，路由信息格式：<目的站， AS有序列表（由AS构成的路径） >

UPDATE报文：（发生时机：发生变化时，发送UPDATE报文）

“数字大炮”攻击示意：

攻击的基本原理：

数字大炮的攻击步骤：

① 构建僵尸网络（可预先构建）

② 启动僵尸网络中的计算机之间流量发送，建立它们之间的“路径地图” （拓扑发现），找到众多路共用的连接（关键链路）（可预先构建）

③ 由僵尸网络对关键链路两端路由器BGP协议发动ZMW攻击，使得关键链路处于断开状态

④ 附近路由器会对此作出回应，发送BGP更新消息

⑤ 很短的时间之后，这两个被切断的路由器可能会重新连接，并发送BGP更新信息

⑥ 不断重复（3） ~（5），最后互联网上每一台路由器都会接收到超出自身处理能力的更新消息，从而导致互联网瘫痪

数字大炮的攻击效果：

选好节点，靠网络自身的扩散功能。实验不错，但是实际中很难。这几年很少用，DDoS多用放大协议，即受到的包不大，但是会回过来一个很大的包。

（3）如何找到重要的边

①桥，捷径，邻里叠度很低的边，……

②许多节点之间的最短路径都要经过它

8、介数

节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例。

边介数定义为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。

（本课中，后面说的介数，都是指最短路径数）

（1）介数：一条边承载的一种“流量”

①两个节点A和B，设想1个单位的流量从A到B，均分到它们之间所有的最短路径上

②K条路径，则每条路径上分得1/k，

③若一条边被m条路径共用，则在它面流过m/k

④所有节点对都考虑后，一条边上的累记流量就是它的介数（betweenness）

（2）破坏连通性

①Girvan-Neman方法： 逐步删除高介数边

（3）介数计算的一种方法-->广度搜索

路径的数目从上往下算

下图：因为A给每个人都发了一个单位流量（可以想数据包），所以每个节点都会留下1个单位流量

介数：很适合描述实际网络中，承载流量的边的信息

三、回顾总结

忠诚的子集是指在一个有向图中，存在一个子集，其中每个节点都指向该子集中的至少一个节点。换句话说，如果一个节点在该子集中，那么该节点指向的所有节点也必须在该子集中。这个子集被称为忠诚的，因为其中的节点会相互支持并共同参与某项活动或决策，而不会被其他节点所影响或干扰。忠诚的子集在图论和计算机科学中具有重要的应用，例如在分布式系统中的一致性协议和社交网络中的社区发现。

图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。

述

图G=(V,E)是一个二元组(V,E)使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认V∩B=Ø。集合V中的元素称为图G的定点(或节点、点)，而集合E的元素称为边(或线)。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

图论

图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。

折叠编辑本段起源

众所周知，图论起源于一个非常经典的问题--柯尼斯堡(Konigsberg)问题。

1738年，瑞典数学家欧拉( Leornhard Euler)解决了柯尼斯堡问题。由此图论诞生。欧拉也成为图论的创始人。

1859年，英国数学家汉密尔顿发明了一种游戏:用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即"绕行世界"。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。