三元闭包

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
薄荷讨论 | 贡献2020年11月30日 (一) 00:53的版本 (薄荷移动页面三元闭包三元闭包 Triadic closure
跳到导航 跳到搜索

三元闭包 Triadic closure社会网络 social network理论中的一个概念,最早由德国社会学家格奥尔格·西梅尔 Georg Simmel在其1908年的著作《社会学:社会形式的调查 Sociology: Investigations on the Forms of Sociation》中提出。[1]三元闭包指的是由A,B,C三个节点 node所组成的三元组的一种性质,即如果A-B和A-C之间存在强联系,则B-C之间也仅存在强联系。[2] 这一性质过于极端,以至于它难以在规模较大、结构复杂的网络中被满足,然而在理解网络与网络预测等方面,它却是一种十分有用的对现实的简化。[3]


历史

马克·格兰诺维特 Mark Granovetter在1973年发表的《强联系的力量 The Strength of Weak Ties》 一文使得三元闭包性质变得流行。 [4] 在这一文章中,他综合了弗里茨·海德 Fritz Heider于1946年提出的认知平衡 cognitive balance理论以及Georg Simmel对社会网络的理解。 一般而言,认知平衡是指两个个体对同一事物具有产生相同感觉的倾向。 如果三个个体所组成的三元组没有闭合,那么与同一个体联系的其余两个个体均将想要闭合这一三元组,进而在关系网络中形成闭包。


测量

最常见的测量一张的三元闭包性质的两种方法(排名不分先后)是采用该图的聚集系数 clustering coefficient传递性 transitivity


聚集系数

测量三元闭包是否出现的方法之一是聚集系数,如下所示:


[math]\displaystyle{ G =(V,E) }[/math]无向简单图 undirected simple graph(即,没有自环 Self-loops多重边 multiple edges的图),其中[math]\displaystyle{ V }[/math]顶点集,[math]\displaystyle{ E }[/math]集。 另外,令[math]\displaystyle{ N = |V| }[/math][math]\displaystyle{ M = |E| }[/math]分别表示图[math]\displaystyle{ G }[/math]中顶点和边的数量,并令[math]\displaystyle{ d_i }[/math] 表示顶点[math]\displaystyle{ i }[/math]


我们可以通过边集[math]\displaystyle{ ((i,j),(j,k),(i,k)) }[/math],将由顶点[math]\displaystyle{ i }[/math],[math]\displaystyle{ j }[/math][math]\displaystyle{ k }[/math]组成的三元组定义为一个三角形。


我们也可以将顶点[math]\displaystyle{ i }[/math]所涉及的三角形的数量定义为[math]\displaystyle{ \delta(i) }[/math],并且由于每个三角形都被计数了三次,我们可以将图[math]\displaystyle{ G }[/math]中三角形的个数表达为[math]\displaystyle{ \delta (G) = \frac{1}{3} \sum_{i\in V} \ \delta (i) }[/math]


假设三元闭包性质成立,则一个三元组仅需要两条强联系便可形成三角形。 因此,在三元闭包性质成立的前提下,顶点[math]\displaystyle{ i }[/math]所涉及的理论三角形的数量为[math]\displaystyle{ \tau(i) = \binom{d_i}{2} }[/math],假设[math]\displaystyle{ d_i \ge 2 }[/math]。我们可以表示[math]\displaystyle{ \tau(G) = \frac{1}{3} \sum_{i\in V} \ \tau(i) }[/math]


现在,对于具有[math]\displaystyle{ d_i \ge 2 }[/math]的顶点,顶点[math]\displaystyle{ i }[/math]的聚集系数是其拥有的三角形的占比,即[math]\displaystyle{ \frac{\delta(i)}{\tau(i)} }[/math]。 因此,图[math]\displaystyle{ G }[/math]的聚集系数[math]\displaystyle{ C(G) }[/math][math]\displaystyle{ C(G)=\frac {1}{N_2} \sum_{i \in V,d_i \ge 2}c(i) }[/math]给出,其中[math]\displaystyle{ N_2 }[/math]是度至少为2的顶点数量。


传递性

测量三元闭包是否出现的另一方法是传递性,定义为[math]\displaystyle{ T(G)= \frac{3\delta(G)}{\tau(G)} }[/math]


形成及其影响

在一个信任网络中,三元闭包性质的出现往往是由于传递性。如果节点A信任节点B,并且节点B信任节点C,则节点A将具有信任节点C的基础。在社会网络中,强三元闭包 strong triadic closure性质的出现往往是由于节点A与节点C拥有共同邻居节点B,在此情况下,节点A与节点C相遇的机会将会增加,进而至少产生一条弱联系。此外,由于两段分离的关系所带来的潜在压力,节点B也具有将节点A和节点C聚在一起的动机。[3]


遵循此原理的网络将高度互连且具有极高的聚集系数。 与此相反,不遵循该原理的网络的连通性则较差,且一旦包含负面关系,网络则可能会变得较不稳定。


三元闭包是分析网络如何随时间演变的一个良好模型。简单图论倾向于在某个时点分析网络,而应用三元闭包原理则可以预测网络中联系的形成,以及网络连通性的发展。[3]


在社会网络中,三元闭包将促进合作行为,但是在新联系是通过现存联系而产生的情况下,平均而言个体所拥有的合作伙伴相对数量将小于个体在总体中随机选择合作伙伴时所拥有的合作伙伴相对数量。这一现象的产生可以从结构与信息两个角度进行解释。基于结构角度而言,网络具有高度聚集性的倾向。基于信息角度而言,我们通常假设,相较于随机的陌生人,个体对朋友的朋友有所了解。


强三元闭包性质和局部桥

强三元闭包性质指,如果一个节点与两个邻居具有强联系,则这些邻居之间必须至少有一条弱联系。另一方面,当某节点在两个互不相连的邻居间充当中间人 Gatekeeper时,则将产生局部桥 local bridge。在遵循强三元闭包性质的网络中,局部桥涉及的节点之间的联系必然至少包括一条弱联系。


反证法

假设节点B是节点A和C之间的局部桥,则所涉及的节点之间没有弱联系。 如果B与A和C之间均具有强联系,则根据强三元闭包性质的定义,节点A和C之间将形成弱联系。但是,这与B是局部桥的事实相矛盾。 因此,局部桥涉及的至少一个节点需要是弱联系,以防止三元闭包的产生。[3]


参考文献

  1. Georg Simmel, originator of the concept: "Facebook" article at the New York Times website. Retrieved on December 21, 2007.
  2. Working concept of triadic closure: book review of Duncan Watts' "Six Degrees: The Science of a Connected Age" at the Serendip (Bryn Mawr College) website. Retrieved on December 21, 2007.
  3. 3.0 3.1 3.2 3.3 Easley, D, & Kleinberg, J. (2010). Networks, crowds, and markets: reasoning about a highly connected world. Cornell, NY: Cambridge Univ Pr.
  4. Granovetter, M. (1973). "The Strength of Weak Ties" , American Journal of Sociology, Vol. 78, Issue 6, May 1360-80.



本中文词条由信白 参与编译, Alienxj 审校,薄荷编辑,欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。