更改

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

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

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

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

全局集聚系数的定义是:

全局集聚系数的定义是:

<math>C = \frac{\mbox{number of closed triplets}}{\mbox{number of all triplets (open and closed)}}</math>.

 

:<math>C = \frac{\mbox{number of closed triplets}}{\mbox{number of all triplets (open and closed)}}</math>.

 

闭合三联体的数目在文献中也被称为3×三角形，所以:

闭合三联体的数目在文献中也被称为3×三角形，所以:

<math>C = \frac{3\times (\mbox{number of triangles)}}{\mbox{number of all triplets}}</math>.

:<math>C = \frac{3\times (\mbox{number of triangles)}}{\mbox{number of all triplets}}</math>.

Opsahl 和 Panzarasa (2009)提出了加权网络的一般化，<ref>{{Cite journal

Opsahl 和 Panzarasa (2009)提出了加权网络的一般化，<ref>{{Cite journal

==局部聚集系数==

==局部聚集系数==

图中某顶点(节点)的局部集聚系数量化了其邻居节点相互聚集构成团(完全图)的程度。 Duncan J. Watts 和 Steven Strogatz 在1998年引入该测量方法来确定一个图是否构成小世界网络。

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

 

一个图 G=(V,E)，形式上由一组节点和节点之间的连边组成。 边连接节点。一个节点<math>v_{i}</math> 的邻域<math>N_{i}</math>被定义为其紧邻的节点，具体如下:

一个图 G=(V,E)，形式上由一组节点和节点之间的连边组成。 边连接节点。一个节点<math>v_{i}</math> 的邻域<math>N_{i}</math>被定义为其紧邻的节点，具体如下:

<math>N_{i}=\{v_{j}:e_{ij}\in E\lor e_{ji}\in E\}.</math>

 

:<math>N_{i}=\{v_{j}:e_{ij}\in E\lor e_{ji}\in E\}.</math>

 

我们将 <math>k_{i} </math>定义为节点的个数，|<math>N_{i}</math>| 为邻域，<math>N_{i}</math>为邻域节点数目。

我们将 <math>k_{i} </math>定义为节点的个数，|<math>N_{i}</math>| 为邻域，<math>N_{i}</math>为邻域节点数目。

一个节点<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/>

<math>C_i = \frac{|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.</math>

 

:<math>C_i = \frac{|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.</math>

 

无向图的<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>边可以存在于邻域内的顶点之间。因此，无向图的局部集聚系数可以定义为

<math>C_i = \frac{2|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.</math>

 

:<math>C_i = \frac{2|\{e_{jk}: v_j,v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.</math>

 

设<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个顶点的子图(不一定是诱导的)的个数，其中一条边与两条边相关。 那么我们也可以将集聚系数定义为

<math>C_{i} = \frac{\lambda_G{(v)}}{\tau_G{(v)}}.</math>

 

:<math>C_{i} = \frac{\lambda_G{(v)}}{\tau_G{(v)}}.</math>

 

易证明前面的两个定义是相同的，因为

易证明前面的两个定义是相同的，因为

<math>\tau_G(v) = C({k_i},2) = \frac{1}{2}k_i(k_i-1).</math>

 

:<math>\tau_G(v) = C({k_i},2) = \frac{1}{2}k_i(k_i-1).</math>

 

如果所连接的每个邻居也连接到邻近的每个其他节点<math>v_{i}</math>，则这些测量值为1; 如果没有任何节点<math>v_{i}</math>连接到所连接的任何其他节点<math>v_{i}</math>，则这些测量值为0。

如果所连接的每个邻居也连接到邻近的每个其他节点<math>v_{i}</math>，则这些测量值为1; 如果没有任何节点<math>v_{i}</math>连接到所连接的任何其他节点<math>v_{i}</math>，则这些测量值为0。

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

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

作为全局聚类集聚系数的代替，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>

<math>\bar{C} = \frac{1}{n}\sum_{i=1}^{n} C_i.</math>

 

:<math>\bar{C} = \frac{1}{n}\sum_{i=1}^{n} C_i.</math>

 

值得注意的是，该度量将更多权重放在低度节点上，而传递性比率将更多权重放在高度节点上。 事实上，每个局部聚类分数由<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>延展。

如果图有一个小的平均最短路径长度与网络中节点数量的自然对数<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&ndash;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&ndash;48 | issue = 1 | doi = 10.1016/j.socnet.2007.04.006}}</ref>和 Opsahl (2009).<>重新定义了二部图(也称为双模网络)

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&ndash;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&ndash;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&ndash;38 | doi = 10.1016/j.chaos.2017.12.007|arxiv= 1706.07322 |bibcode= 2018CSF...107...26C }}</ref>

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&ndash;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> .

提出了另一种加权有向图网络的推广概念。默认情况下，这个公式不适用于具有孤立顶点的图; 参见 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 />

==参考链接==

==参考链接==

<references />

<references />

'''''本中文词条由[[Gravity PHY]]用户参与编译，  刘佩佩 用户审校，欢迎在讨论页面留言'''''。

 

 

本中文词条由[[用户:Gravity PHY|Gravity PHY]]参与编译，[[用户:苏格兰|苏格兰]]审校，[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。

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

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