Created Date: 2020-03-08 16:14:53
Last Upgraded Date: 2020-03-08 19:40:00

Networks, Crowds, and Markets: A Book by David Easley and Jon Kleinberg

网络与图论

无处不在的网络

从差序格局到社会网络

费孝通（1947，1985：23）：源与众

（中国人的社会关系）好像是把一块石头丢在水面上所发生的一圈圈推出去的波纹。每个人，都是他社会影响所推出去的圈子的中心，被圈子的波纹做推及的，就发生联系。每个人在某一时间某一地点所动用的圈子是不一定相同的。

林南（2004：37）：网络

一个特定的网络可以自然地形成，也可以有对一个特定的共同关注的焦点或关注一种资源利益的社会性建构

在自然界，网络同样无处不在

C.S.Elton（1927），在生态系统中，物种之间的”吃“与”被吃“也是一个网络，食物链是自然生态系统稳定的重要机制
一些自然资源之间的关系，如水的转化关系，也是一个网络……

甚至可以说，网络是自然世界生发演变的机制之一

形形色色的网络

1979年12月ARPA计算机网

交通运输网，邮政网，电话通信网，计算机网，互联网，万维网
社会关系网，产品供销网，金融借贷网
智能电网，无线网，传感网，物联网
神经网，生物代谢网，食物链（网）
攻守同盟网，恐怖主义网络
……
人人网，新浪微博网，QQ，…，团购网

不同类型网络的依存

互联网（Internet）——物理的、技术的
万维网（World Wide Web）——基于互联网的信息网络
人人网——基于万维网的在线社会（社交）网络（Online Social Network，OSN)
社会关系网，与地域相关（尤其在古代），地域上的相邻或相近，见面的机会多，建立关系的可能性就大，随着交通工具的发达，社会关系的地域范围扩大

ICT技术发展的影响

催化了各种网络的发展
规模变大，范围变广
新型网络的涌现，如兴趣网
ICT技术的发展使分析和理解大规模网络的结构与演变成为可能
行为（痕迹）数据（para data）与网络的运行伴生
海量数据（大数据，big data）分析的能力（计算设施，算法工具）
以社会网络分析为例，从前的分析能力限制在上百个节点，现在可以分析上亿个节点的网络
今天，人们很难想象一个不在网络中的个体能怎样工作和生活，一个没有网络的世界又会是怎样的世界

小结

”网络“并不是今天才出现的现象，自然界原本就有，人类社会自古也有
对人类社会而言，凡是有人群的时间与空间，就有网络
网络不仅无处不在，而且形形色色
ICT环境的发展，使人群之间的网络现象及其意义更加凸显
计算能力的发展，使得针对网络现象的可计算性越来越强，进而使得对人群的行为及其与网络之间互动的可预测性也越来越有意义

网络与图

节点（vertex，node，point）
边（连接，链接，关系，练习；edge，link，tie）

图=事物+联系

同构：画法不同，但本质上（结构上）相同

小结

图是网络结构信息的抽象，表达的是网络中各种事物之间的关系。
这里所说的”图“，不同于日常生活中看到的”图像“，尽管图常常也可以被画出来，呈现出一种图像的形式。
同一个图，可能有多种不同的画法。也就是说，同一个图可能呈现出不同的图像形式。

路径与连通

路径、最短路径、距离

连通、连通分量（节点之间存在路径；不包含在其他的连通分量中）

二部图与广度优先搜索

一个图是二部图的充分必要条件是它没有长度为奇数的圈。

图上的广度优先搜索（遍历）

从一个节点开始，沿着相连的边，将图的节点一一列举出来的以一种过程（算法）。

从任何节点开始，在广度优先搜索（遍历）过程中，一旦发现同一层的节点之间有边，则图中一定存在长度为奇数的圈。

小结

许多社会现象或状态的结构，都呈现出二部图的形式。
是否有长度为奇数的圈，是判断一个图是否为二部图的充分必要条件。
广度优先搜索（遍历），是考察一个图是否存在长度为奇数的圈的有效方法（算法）。

三元闭包与聚集系数

不仅要考虑一个时刻（”快照“）上的状态，还要研究随时间发生的变化（内部原因 vs 外部原因）。

三元闭包

社会网络演化的基本结构性原因（Anatole Rapoport，1953）
三元闭包（闭合）如果两个互不相识的人有了一个共同的朋友，则他们俩将来成为朋友的可能性提高
机会（opportunity）？信任（trust）？动机（incentive）？
林南（2004：37）
一个特定的网络可以自然地形成，也可以有对一个特定的共同关注的焦点或关注一种资源利益的社会性建构。

聚集系数

某个节点的重要性——结构洞

对节点属性刻画的一种方式

聚集系数
节点A的聚集系数 = 与A相邻的任意两个朋友之间也是朋友的概率 = 与A相邻的朋友对的个数/总
就是在三元闭包中，对一个节点属性的测度，表示”凝聚力“的大小。

小结

节点之间的关系，会随着时间的变化而发生变化，有些之前没有关系的节点之间，也可能出现边。
是否出现边，其中的一个机制，是结构性机制，即在三个点之间如果有两条边，则没有边的节点之间极有可能发展出边。
在一个网络结构中，某些位置的点是具有特殊意义的。
刻画一个网络结构中节点的属性，可以采用聚集系数。

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

准备工作

第一，将三元闭包原理最初的定性陈述转变成一种可以定量考察的表达；
第二，找到一种合适的社会网络数据。

三元闭包原理的两种表达

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

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

社会网络数据

电子邮件网络约等于社会网络
一所大学的两万多学生在一年里的通信关系数据；只关心谁和谁何时有过通信，不关心内容。

假设，网络中有100对节点，某一时刻之前没边，但分别恰好有5个共同的朋友。
如果，一个月内，其中有20对节点俩俩之前发生了通信，80对依然没有；就说，两个不相识但有5个共同朋友的人，在一个月内将成为朋友的概率为0.2。

”Empirical Analysis of an evolving social network“, Science 2006

数据验证过程

小结

以三元闭包原理的验证为例，我们看到了一种利用大数据分析，定量考察某些社会科学定性认识的方法。
其中有两个关键：将社会科学原理的定性描述，转化为便于定量分析的表述，形成数据指标（与共同朋友数对应的概率）；选择合适的数据，以及从原始数据中提炼出指标数据的方法。

强关系与弱关系

边的一种属性类型

以三节点关系为例
在A-B，A-C有关系且为朋友关系的条件下，B-C之间倾向于建立联系，显然A-B，A-C的关系与B-C建立关系的瞬间，是不一样的。

Granovetter（1973）提出了刻画边的属性的一种测度：强-弱。显然，这是一种简化的测度，强度是可以为连续变量的。

被动参与

Huberman et al.（2009）
三元闭包原理实际上暗含了一个随时间推移的可能
有的人会被动地加入某些网络
Huberman et al.（2009）对Teitter的研究表明，即时所有朋友的总数超过500，实际联系的总数也在10-20人之间；被动联系人的数量也不超过50人。

嵌入性：边的属性

嵌入性（Embedness）概念
Karl Polanyi（1944）《大转变》，行动嵌入制度
Granovetter（1985）在与经济学家的论战中，提出了经济行为与社会结构之间的关系问题，拓展了嵌入性概念，指出，经济行为是嵌入在社会结构之中的，是社会行为的一种
后来，这个概念的应用得到了极大的扩展，甚至被引入到了网络分析
网络分析，恰恰是Granovetter从他老师Harrison White（1967）那里得到的衣钵
抽象后的嵌入性
嵌入性 = 一条边两端共同的邻里数
嵌入性越强的边，相互之间的信任就越强。
嵌入性越强的边，社会资本也越多。

结构洞

结构洞概念
一个节点，移除该节点就会使网络变成多个连通分量的节点。
结构洞的意义——指其在结构位置上做具有的意义
了解3方面的信息；
处于捷径的一端，对其”长处“有放大影响；
对与其相邻的节点甚至具有”权利“；
冗余（凝聚力冗余和结构等位冗余）越小的结构洞，社会资本就越多。

小结

对网络中某个时点结构中的边的属性，可以用强弱进行测度。
边的属性可以用嵌入性来测度，嵌入性越强，社会资本越强。
点的属性除了聚集系数外，还有特殊的社会意义，即结构洞意义，冗余越小的结构洞，社会资本也越多。

弱关系与捷径

依三元闭包精神：如果一个节点A有两个强关系邻居B和C，则B和C不应该什么关系都没有。

强三元闭包原理

如果A和B、C之间的关系分别为强关系；则B和C之间形成边的可能性应该很高。进而，我们说：
若A有两个强关系邻居B和C，但B和C之间没有任何关系（s或w），则称节点A违背了强三元闭包原理；如果节点A没有违背强三元闭包原理，则称节点A符合强三元闭包原理。

捷径~弱关系？

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

捷径->弱关系：大数据验证

强三元闭包原理的精神
没有共同朋友->捷径->弱关系
定量化表述：共同朋友越多，关系强度越高
也就是，在社交网络中，我们预计看到人们关系的强度与共同朋友数正相关

小结

我们证明了，在一定条件下，社交网络中的捷径意味着弱关系。
这个结论的意义，在与它将来源于两个不同领域的概念巧妙地联系了起来，展示了学科交叉的魅力。