查看“︁集聚系数”︁的源代码

在[[图论]]中，'''集聚系数'''（也称'''群聚系数'''、'''集群系数'''）是用来描述一个[[图]]中的[[顶点 (图论)|顶点]]之间结集成团的程度的系数。具体来说，是一个点的邻接点之间相互连接的程度。例如生活社交网络中，你的朋友之间相互认识的程度<ref name=wangxt>{{Cite journal
 | author = 王冰、修志龙、唐焕文
 | title = 基于复杂网络理论的代谢网络结构研究进展
 | year = 2005
 | issue = No.6
 | url = http://www.ebiotrade.com/emagazine/content/3/2005_6_25_6/4324FE4C-BBED-4051-BFC8-947ACF8FA13F/pdf/2005-6Vol.25-3.pdf
 | journal = 《中国生物工程杂志》
 | volume = 25-3
 | pages = 10–14
 | access-date = 2011-04-20
 | archive-date = 2018-10-01
 | archive-url = https://web.archive.org/web/20181001220250/http://www.ebiotrade.com/emagazine/content/3/2005_6_25_6/4324FE4C-BBED-4051-BFC8-947ACF8FA13F/pdf/2005-6Vol.25-3.pdf
 | dead-url = yes
 }}</ref>。有证据表明，在各类反映真实世界的网络结构，特别是[[社交网络]]结构中，各个结点之间倾向于形成密度相对较高的网群<ref>{{Cite journal
 | author = P. W. Holland and S. Leinhardt
 | title = ''Transitivity in structural models of small groups''
 | year = 1971
 | journal = Comparative Group Studies
 | volume = 2
 | pages = 107–124
}}</ref><ref name=WattsStrogatz1998>{{Cite journal
 | author = D. J. Watts and Steven Strogatz
 | title = ''Collective dynamics of 'small-world' networks''
 | url = http://tam.cornell.edu/tam/cms/manage/upload/SS_nature_smallworld.pdf
 | journal = [[Nature (journal)|Nature]]
 | volume = 393
 | pages = 440–442
 | doi = 10.1038/30918
 | pmid = 9623998
 | issue = 6684
 | date = June 1998
 | access-date = 2011-04-20
 | archive-date = 2012-01-05
 | archive-url = https://web.archive.org/web/20120105224315/http://tam.cornell.edu/tam/cms/manage/upload/SS_nature_smallworld.pdf
 | dead-url = no
 }}</ref>。也就是说，相对于在两个节点之间随机连接而得到的网络，真实世界网络的集聚系数更高。

集聚系数分为整体与局部两种。整体集聚系数可以给出一个图中整体的集聚程度的评估，而局部集聚系数则可以测量图中每一个结点附近的集聚程度。

==基础概念==
集聚系数主要是描述图（或者称为网络）的特性。一个图 ''G'' 是由一些[[顶点 (图论)|顶点]] ''V'' 和顶点与顶点之间的一些连线（称为边）''E'' 构成。两个相连的顶点也称为邻接点。比如在一群人中，将每个人用一个点表示，如果两人之间认识，就将对应的两点连起来。这样就构成了一个图。有的图是有方向的，比如在同样一群人中，如果一人甲欠另一人乙的钱，就连一条从
甲至乙的线，这样就构成了一个[[有向图]]。

==整体集聚系数==
整体集聚系数的定义建立在闭三点组（邻近三点组）之上。假设图中有一部分点是两两相连的，那么可以找出很多个“三角形”，其对应的三点两两相连，称为闭三点组。除此以外还有开三点组，也就是之间连有两条边的三点（缺一条边的三角形）。这两种三点组构成了所有的[[连通]]三点组。整体集聚系数定义为一个图中所有闭三点组的数量与所有连通三点组（无论开还是闭）的总量之比（也有定义为这个值的三倍，使得在[[完全图]]中的整体集聚系数等于1）。最早尝试测量这个系数是在1949年[[罗伯特·邓肯·路斯]]和[[阿尔伯特·D·佩里]]合作的一篇论文中<ref>{{Cite journal
 | author = R. D. Luce and A. D. Perry
 | title = ''A method of matrix analysis of group structure''
 | year = 1949
 | journal = Psychometrika
 | volume = 14
 | pages = 95–116
 | doi = 10.1007/BF02289146
 | issue = 1
| pmid=18152948
}}</ref>。

假设有图<math>G=(V,E)</math>，其中<math>V=\left\{v_1, v_2, \cdots, v_n \right\}</math>表示[[顶点 (图论)|顶点]]的集合，<math>E = \left\{e_{ij} : (i, j) \in S \subset \left[ 1, \cdots , n \right]^2 \right\}</math>表示边的集合（<math>e_{ij}</math> 表示连接顶点 <math>v_i</math> 和 <math>v_j</math> 的边）。

每一个[[顶点 (图论)|顶点]]连接的顶点有多有少，用 ''L''(''i'') 表示与顶点 <math>v_i</math> 相连的边的集合：
: <math>L(i) = \left\{ v_j : e_{ij} \in E \land e_{ji} \in E \right\}</math>

''L''(''i'')  里的边的数量就是顶点 <math>v_i</math> 的度，记作 <math>k_i</math> ：<math>k_i = |L(i)|</math>。

如果用 <math>C_{total}(G)</math> 表示整体集聚系数，用 <math>G_{\triangle}</math> 表示图中闭三点组的个数，<math>G_{\land}</math> 表示其中开三点组的个数，那么：
: <math>C_{total}(G) = \frac{3 \times G_{\triangle} }{3 \times G_{\triangle} + G_{\land} }</math>

使用 <math>k_i</math> 来表示的话，也可以写成：
: <math>C_{total}(G) = \frac{3 \times G_{\triangle} }{\sum_{i=1}^n \binom{k_i}{ 2}}</math><ref>{{Cite journal
 | author = N. Eggemann and S.D. Noble
 | url = http://bura.brunel.ac.uk/bitstream/2438/3831/1/Fulltext.pdf
 | title = ''The clustering coefficient of a scale-free random graph''
 | date = 2009-11-03
 | journal = Discrete Applied Mathematics
 | volume = 159
 | pages = 953-965
 | doi = 10.1016/j.dam.2011.02.003
 | issue = 10
 | access-date = 2011-04-20
 | archive-date = 2017-08-13
 | archive-url = https://web.archive.org/web/20170813045838/http://bura.brunel.ac.uk/bitstream/2438/3831/1/Fulltext.pdf
 | dead-url = no
 }}</ref>

== 局部集聚系数 ==
[[Image:Clustering coefficient example.svg|thumb|right|150px|局部集聚系数：蓝点有三个邻接点（白点）。如果三个白点都相互连接（上图），那么蓝点的集聚系数是3÷3=1；如果只有两点之间相连（中图，只有一条边），那么集聚系数是<math>\scriptstyle \frac{1}{3}</math>；如果没有两点是相连的，那么集聚系数就是0。]]

对图中具体的某一个点，它的局部集聚系数 <math>C(i)</math> 表示与它相连的点抱成[[團 (圖論)|团]]（[[正则图|完全子图]]）的程度。{{le|邓肯·J·瓦兹|Duncan J. Watts}}与[[斯蒂芬·斯特罗加茨]]在1998年发表的一篇论文中首次引入了这个概念，用以判别一个图是否是[[小世界網路|小世界网络]]<ref name=WattsStrogatz1998 />。

图中的一个[[顶点 (图论)|顶点]] <math>v_i</math> 的局部集聚系数 <math>C(i)</math> 等于所有与它相连的顶点之间所连的边的数量，除以这些顶点之间可以连出的最大边数<ref name=zrz>{{Cite journal
 | author = 章忠志、荣莉莉、周涛
 | title = 一类无标度合作网络的演化模型
 | url = http://www.sysengi.com/qikan/manage/wenzhang/2005110055.pdf
 | journal = 《系统工程理论与实践》
 | volume = 11
 | pages = 55–60
 | date = 2005年11月
 | access-date = 2011-04-20
 | archive-date = 2018-09-29
 | archive-url = https://web.archive.org/web/20180929071921/http://www.sysengi.com/qikan/manage/wenzhang/2005110055.pdf
 | dead-url = no
 }}</ref>。一般来说，对于无向图，这个最大边数等于 <math>\scriptstyle \frac{k_i(k_i - 1)}{2}</math>；对于有向图，由于每两个顶点之间可以连两条边（不同方向），最大边数等于 <math>k_i(k_i - 1)</math>。这时候的 <math>k_i</math> 表示的是指向顶点 <math>v_i</math> 的边与从顶点 <math>v_i</math> 指出去的边的总数。同时，对于有向图，要注意边 <math>e_{ij}</math> 与边 <math>e_{ji}</math> 是不一样的。

用数学公式表达的话，无向图中一[[顶点 (图论)|顶点]] <math>v_i</math> 的局部集聚系数是：
: <math>C(i) = \frac{2 \Big | \Big \{ e_{jk} : v_j,v_k \in L(i), e_{jk} \in E \Big \} \Big | }{k_i(k_i-1)} .</math>
因为边 <math>e_{ij}</math> 和边 <math>e_{ji}</math> 指的是同一条边。有向图中一[[顶点 (图论)|顶点]] <math>v_i</math> 的局部集聚系数是：
: <math>C(i) = \frac{ \Big | \Big \{ e_{jk} : v_j,v_k \in L(i), e_{jk} \in E \Big \} \Big |  }{k_i(k_i-1)}.</math>

在无向图 <math>G</math> 中，如果设一个顶点 <math>v_i \in V </math> 的相连闭三角数为<math>\lambda_G(v_i)</math>，也就是 <math>G</math> 中所有的包括了 <math>v_i</math>  的闭三点组（三点中连有三条边）的数目；再设 <math>v_i</math>  的相连开三角数为 <math>\tau_G(v_i)</math>，也就是 <math>G</math> 中所有的包括了 <math>v_i</math> ，并且满足两条边都与 <math>v_i</math> 相连的开三点组（三点中恰好连有两条边）。这时，顶点 <math>v_i</math>  的局部集聚系数也可以表示为：

: <math>C(i) = \frac{\lambda_G(v_i)}{\tau_G(v_i) + \lambda_G(v_i)}.</math>
很容易证明两种表示方法是等价的。实际上，计算 <math>\lambda_G(v_i)</math> 时候的每一个闭三点组，除 <math>v_i</math> 外的另外两点都是 <math>v_i</math> 的邻接点，并且他们相连。计算 <math>\tau_G(v_i)</math> 时候的每一个开三点组，除 <math>v_i</math> 外的另外两点也都是 <math>v_i</math> 的邻接点，并且他们不相连。所以：
: <math>\tau_G(v_i) + \lambda_G(v_i) = C({k_i},2) = \frac{1}{2}k_i(k_i-1).</math>

可以看出，一个[[顶点 (图论)|顶点]] <math>v_i</math> 的局部集聚系数 <math>C(i)</math> 总是在0与1之间。 <math>C(i)</math> 越接近1，表示 <math>v_i</math> 的“邻居”们越是“抱成一团”，接近完全图。<math>C(i)</math> 越接近0，说明它的邻居们“老死不相往来”，整个结构接近[[树 (图论)|树状]]。

==平均集聚系数==
知道了一个图里的每一个[[顶点 (图论)|顶点]]的局部集聚系数后，可以计算整个图的平均集聚系数。这个概念也是瓦兹和斯特罗加兹在1998年的论文中引入的<ref name=WattsStrogatz1998 />，具体来说就是所有顶点的局部集聚系数的[[算术平均数]]：
: <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) = \frac{1}{n}\sum_{i=1}^{n} \frac{\lambda_G(v_i)}{\tau_G(v_i) + \lambda_G(v_i)}</math>
: 而<math>C_{total}(G) =  \frac{\sum_{i=1}^{n} \lambda_G(v_i)}{\sum_{i=1}^{n}\left( \tau_G(v_i) + \lambda_G(v_i) \right)}</math>

一个图（或称为网络）被叫做[[小世界網路|小世界网络]]，如果它的平均集聚系数远大于一个在同样的[[顶点 (图论)|顶点]]集合上构造的[[随机图]]的平均集聚系数，并且它的[[距离 (图论)|平均最短路径长度]]和这种[[随机图]]基本相同。

在更为广泛的[[加权网络]]<ref>{{Cite journal
 | author = A. Barrat and M. Barthelemy and R. Pastor-Satorras and A. 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
}}</ref>和[[二部图]]<ref>{{Cite journal
 | author = M. Latapy and C. Magnien and N. 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>中，也可以引进类似于集聚系数的概念。

==参见==
*[[正则图]]
*[[ER随机图]]

==参考来源==
{{reflist}}

[[category:图论]]
[[Category:复杂网络]]