更改

聚类系数 (查看源代码)

2020年5月23日 (六) 07:38的版本

大小无更改、 2020年5月23日 (六) 07:38

无编辑摘要

第1行：第1行：

{{#seo:

|keywords=聚类系数,图论,节点

−

|description=小世界网络,~~全局聚集系数~~,~~局部聚集系数~~

+

|description=小世界网络,全局聚类系数,局部聚类系数

}}

−

~~图论中，聚集系数用于衡量节点聚集的程度。~~ 有证据表明，大多数现实世界的网络中，特别是在社交网络中，节点倾向于创建相对紧密联系的群体; 这种可能性往往大于在两个节点之间随机建立关系的平均概率(Holland 和 Leinhardt，1971; <ref name=HollandLeinhardt1971>{{Cite journal

+

图论中，聚类系数用于衡量节点聚集的程度。有证据表明，大多数现实世界的网络中，特别是在社交网络中，节点倾向于创建相对紧密联系的群体; 这种可能性往往大于在两个节点之间随机建立关系的平均概率(Holland 和 Leinhardt，1971; <ref name=HollandLeinhardt1971>{{Cite journal

| author = P. W. Holland and S. Leinhardt

| title = Transitivity in structural models of small groups

第28行：第28行：

}}</ref>

)。

−

==~~全局聚集系数~~==

+

==全局聚类系数==

−

~~全局集聚系数以节点三重性~~ triplets为基础。一个三元组是由两个(开三元组)或三个(闭三元组)无向联系相连接的三个节点。因此，一个三角形图包括三个闭合的三联体，每个节点中心为一个(注意，这意味着三角形中的三联体来自节点的重叠选择)。 ~~全局集聚系数是三联体总数除以闭合三联体~~(或3 x 三角形)的个数。 Luce和Perry(1949年)第一次尝试对其进行测量。 <ref>{{Cite journal

+

全局聚类系数以节点三重性 triplets为基础。一个三元组是由两个(开三元组)或三个(闭三元组)无向联系相连接的三个节点。因此，一个三角形图包括三个闭合的三联体，每个节点中心为一个(注意，这意味着三角形中的三联体来自节点的重叠选择)。全局聚类系数是三联体总数除以闭合三联体(或3 x 三角形)的个数。 Luce和Perry(1949年)第一次尝试对其进行测量。 <ref>{{Cite journal

| author = R. D. Luce and A. D. Perry

| title = A method of matrix analysis of group structure

第41行：第41行：

| pmid=18152948

}}</ref>这个度量概括了整个网络(全局)中的集群，并可应用于无向和有向网络(通常称为传递性，见 Wasserman 和 Faust，1994，第243页。<ref>Stanley Wasserman, Katherine Faust, 1994. ''Social Network Analysis: Methods and Applications.'' Cambridge: Cambridge University Press.</ref>

−

~~全局集聚系数的定义是~~:

+

全局聚类系数的定义是:

第65行：第65行：

}}</ref>和一种双模式网络(包括二进制和加权)。

−

==~~局部聚集系数~~==

+

==局部聚类系数==

[[File:Clustering_coefficient_example.svg.png|200px|right|thumb|无向图上的示例局部聚类系数。将蓝色节点的局部聚类系数计算为其实际邻居之间的连接比例与所有可能连接的数量之比。在图中，蓝色节点具有三个邻居，它们之间最多可以有3个连接。在图的顶部，实现了所有三个可能的连接（黑色的粗线段），局部聚类系数为1。在图的中间部分，仅实现了一个连接（黑色的粗线），而缺少2个连接（红色虚线），则局部簇系数为1/3。最终，蓝色节点的邻居之间没有任何可能的连接被实现，从而产生了局部聚类系数值0。]]

−

图中某顶点(节点)~~的局部集聚系数量化了其邻居节点相互聚集构成团~~(完全图)的程度。[[邓肯·沃茨 Duncan J Watts]]和[[斯蒂文·斯特罗加茨 Steven H. Strogatz]]在1998年引入该测量方法来确定一个图是否构成[[小世界网络]]。

+

图中某顶点(节点)的局部聚类系数量化了其邻居节点相互聚集构成团(完全图)的程度。[[邓肯·沃茨 Duncan J Watts]]和[[斯蒂文·斯特罗加茨 Steven H. Strogatz]]在1998年引入该测量方法来确定一个图是否构成[[小世界网络]]。

第79行：第79行： −

一个节点<math>v_{i}</math>~~的局部集聚系数~~<math>C_{i}</math>由邻域内节点之间的连边除以它们之间可能存在的连边数量的比例给出。对于有向图，<math>e_{ij}</math>不同于<math>e_{ji}</math> ，因此对于每个邻域<math>N_{i}</math> ，邻域内的节点之间可能存在<math>k_{i}(k_{i}-1)</math>链(<math>k_{i}</math>是一个顶点的邻域数)。 ~~因此，有向图的局部集聚系数为~~<ref name=WattsStrogatz1998/>

+

一个节点<math>v_{i}</math>的局部聚类系数<math>C_{i}</math>由邻域内节点之间的连边除以它们之间可能存在的连边数量的比例给出。对于有向图，<math>e_{ij}</math>不同于<math>e_{ji}</math> ，因此对于每个邻域<math>N_{i}</math> ，邻域内的节点之间可能存在<math>k_{i}(k_{i}-1)</math>链(<math>k_{i}</math>是一个顶点的邻域数)。因此，有向图的局部聚类系数为<ref name=WattsStrogatz1998/>

第85行：第85行： −

无向图的<math>e_{ij}</math>和<math>e_{ji}</math>被认为具有相同的性质。因此，如果一个顶点有<math>v_{i}</math>邻域， <math>k_i</math>~~边可以存在于邻域内的顶点之间。因此，无向图的局部集聚系数可以定义为~~

+

无向图的<math>e_{ij}</math>和<math>e_{ji}</math>被认为具有相同的性质。因此，如果一个顶点有<math>v_{i}</math>邻域， <math>k_i</math>边可以存在于邻域内的顶点之间。因此，无向图的局部聚类系数可以定义为

第91行：第91行： −

设<math>\lambda_G{(v)}</math>是无向图<math>G</math>上的三角形个数<math>v \in V(G)</math>。也就是说，<math>\lambda_G{(v)}</math>是 <math>G</math>的3条边和3个节点的子图的个数，其中一个是<math>v</math>。设<math>\tau_G{(v)}</math>是<math>v \in V(G)</math>上的三倍数。即，<math>\tau_G{(v)}</math>具有2条边和3个顶点的子图(不一定是诱导的)的个数，其中一条边与两条边相关。 ~~那么我们也可以将集聚系数定义为~~

+

设<math>\lambda_G{(v)}</math>是无向图<math>G</math>上的三角形个数<math>v \in V(G)</math>。也就是说，<math>\lambda_G{(v)}</math>是 <math>G</math>的3条边和3个节点的子图的个数，其中一个是<math>v</math>。设<math>\tau_G{(v)}</math>是<math>v \in V(G)</math>上的三倍数。即，<math>\tau_G{(v)}</math>具有2条边和3个顶点的子图(不一定是诱导的)的个数，其中一条边与两条边相关。那么我们也可以将聚类系数定义为

第107行：第107行：

===网络整体聚类水平===

−

~~作为全局聚类集聚系数的代替，Watts~~ 和 Strogatz <ref name=WattsStrogatz1998/>将所有顶点局部聚类系数的平均值作为网络整体聚类水平<math>n</math> :<ref>{{Cite book|last= Kemper |first=Andreas|title=Valuation of Network Effects in Software Markets: A Complex Networks Approach|publisher=Springer|year=2009|isbn=9783790823660|page=142|url=https://books.google.com/books?id=isdza0IiXbUC&pg=PA142}}</ref>

+

作为全局聚类聚类系数的代替，Watts 和 Strogatz <ref name=WattsStrogatz1998/>将所有顶点局部聚类系数的平均值作为网络整体聚类水平<math>n</math> :<ref>{{Cite book|last= Kemper |first=Andreas|title=Valuation of Network Effects in Software Markets: A Complex Networks Approach|publisher=Springer|year=2009|isbn=9783790823660|page=142|url=https://books.google.com/books?id=isdza0IiXbUC&pg=PA142}}</ref>

第113行：第113行： −

值得注意的是，该度量将更多权重放在低度节点上，而传递性比率将更多权重放在高度节点上。事实上，每个局部聚类分数由<math>k_{i}(k_{i}-1)</math>~~的加权平均数模型与全局聚类集聚系数模型是相同的。~~

+

值得注意的是，该度量将更多权重放在低度节点上，而传递性比率将更多权重放在高度节点上。事实上，每个局部聚类分数由<math>k_{i}(k_{i}-1)</math>的加权平均数模型与全局聚类聚类系数模型是相同的。

如果图有一个小的平均最短路径长度与网络中节点数量的自然对数<math>\ ln{{N}}</math>一起延展<ref>http://networksciencebook.com/4#ultra-small</ref>，那么这个图被认为是小世界。例如，随机图是小世界图，而格子图不是，无标度图通常被认为是超小世界图，因为它们的平均最短路径长度随<math>\ln{\ln{N}}</math>延展。Barrat 等人提出了广义的加权网络(2004) ，<ref>{{Cite journal | first1= A. |last1= Barrat |first2= M. |last2= Barthelemy |first3= R. |last3= Pastor-Satorras |first4= A. |last4= Vespignani | title = The architecture of complex weighted networks | year = 2004 | journal = Proceedings of the National Academy of Sciences | volume = 101 | pages = 3747–3752 | doi = 10.1073/pnas.0400087101 | issue = 11 | pmid = 15007165 | pmc = 374315 | bibcode=2004PNAS..101.3747B|arxiv = cond-mat/0311416 }}</ref>，Latapy 等人(2008)<ref>{{Cite journal | first1 = M. |last1= Latapy |first2= C. |last2= Magnien |first3= N. |last3= Del Vecchio | title = Basic Notions for the Analysis of Large Two-mode Networks | year = 2008 | journal = Social Networks | volume = 30 | pages = 31–48 | issue = 1 | doi = 10.1016/j.socnet.2007.04.006}}</ref>和 Opsahl (2009)重新定义了二部图(也称为双模网络)。Fagiolo (2007)<ref>{{Cite journal | first1= G. |last1= Fagiolo | title = Clustering in complex directed networks | year = 2007 | journal = Physical Review E | volume = 76|issue= 2 Pt 2 |pages= 026107 |doi= 10.1103/PhysRevE.76.026107 |pmid= 17930104 |citeseerx= 10.1.1.262.1006 }}</ref> , Clemente 和Grassi (2018)<ref>{{Cite journal | first1 = G.P. |last1= Clemente |first2= R. |last2= Grassi | title = Directed clustering in weighted networks: A new perspective | year = 2018 | journal = Chaos, Solitons & Fractals | volume = 107 | pages = 26–38 | doi = 10.1016/j.chaos.2017.12.007|arxiv= 1706.07322 |bibcode= 2018CSF...107...26C }}</ref>

提出了另一种加权有向图网络的推广概念。默认情况下，这个公式不适用于具有孤立顶点的图; 参见 Kaiser (2008)<ref>{{Cite journal | first= Marcus | last= Kaiser |title = Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks | year = 2008 | journal = New Journal of Physics | volume = 10 | pages = 083042 | issue = 8 | doi = 10.1088/1367-2630/10/8/083042|bibcode = 2008NJPh...10h3042K |arxiv = 0802.2512 }}</ref>和 Barmpoutis 等<ref name=BarmpoutisMurray2010>{{Cite arXiv | first1= D. |last1= Barmpoutis |first2=R. M. |last2= Murray | title = Networks with the Smallest Average Distance and the Largest Average Clustering | eprint = 1007.4031 | year = 2010 | class = q-bio.MN}}</ref> .

−

~~具有最大可能平均集聚系数的网络被发现具有模块结构，且不同节点之间存在尽可能小的平均距离。~~<ref name=BarmpoutisMurray2010 />

+

具有最大可能平均聚类系数的网络被发现具有模块结构，且不同节点之间存在尽可能小的平均距离。<ref name=BarmpoutisMurray2010 />

==参考链接==

薄荷

7,129

个编辑