登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

生活也是大事业

阿波的学习、工作和生活

 
 
 
 
 

日志

 
 
关于我

江浙沪,数学系,天蝎座O型,懒洋洋,傻乎乎

文章分类

《社会网络分析法》读书笔记(五)“凝聚子群”  

2010-05-07 01:05:58|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天把论文送审,算是告一段落。所以继续写读书笔记。

社会网络分析的一块重要内容是探索网络中可能存在的凝聚子群,形象地说就是寻找网络中的小团体,较为正式的名称是“派系”(cliques)。与“派系”相似的定义包括“子群”、“聚类”、“成分”与“圈子”等等,这些定义大同小异,基本可以从字面上进行理解。

 

一、成分

初步的探索是寻找网络中自然存在的子图。通常将网络中最大的关联子图定义为“成分”,成分内部的各点之间必然有一条途径相连,而成分之外的点与成分内部的点没有联系,这是“最大”性质的体现,即不能给某个成分加入新的点而使其成为新的成分。成分的概念似乎与马尔科夫链理论中的连通集有些相似之处,也与可达性有一定关系。

由成分的定义可以看出,一个网络可能由“若干个规模不同的成分”及“不属于其中任一成分的若干个孤立点”构成。通常用某种生成树的回朔算法寻找图中的成分。

成分是图的一个最基本的组成元素,成分与成分之间不存在联系,因此可以将眼光从大范围的图转向小范围的成分,探索成分的内在结构。关于成分的内在结构有两个概念:环成分及结群。

1.环成分

环是网络中的一个循环的途径,通常将长度为k的循环途径称为k环。其中的k作为阈值,根据研究兴趣决定,一般情况下我们研究较短的环(3环或4环)。环与环之间可以通过桥线相连接。若干个环相互交叉,就构成了环成分。举例如下。

《社会网络分析法》读书笔记(五)“凝聚子群” - 皮皮米菲兔 - 生活也是大事业

这个网络(成分)本身不是环成分,但其中包含了两个环成分:{A,B,C,D}与{E,F,G,J,I,H}。BE是一条桥线。移除图中的桥线,可以得到相应的环成分。

环成分不必须是成分,一个环成分可以与另一个环成分相连(如上述例子),也可以与一些非环成分的点相连,根据这些点的不同性质可以将它们分为:悬挂点,桥点,孤立树,孤立点。

2.结群

结群的概念来源于图中的切割点。当移除图中某个点会导致增加图的成分时,将这个点称为切割点。由定义来看,切割点往往处于某种中枢的位置,起到轴心的作用。不存在切割点的关联子图被称为“结群”knot。从某种角度来看,一个切割点划分了两个成分,这两个成分(加上切割点)成为两个结群。因此,切割点其实是若干结群的交叉点。

一个成分可以表示成一系列结群的叠加,结群内部各成员之间互相交往,结群之间通过切割点产生联系。切割点代表的成员在网络中成为明显的局部中心,而结群内部的交往通常表现出高效及高弹性,因为结群中各个成员的交互不需要依赖某个特殊的人物。这似乎可以看作“去中心化”的某种理论依据。

关于结群的简单例子如下所示。

《社会网络分析法》读书笔记(五)“凝聚子群” - 皮皮米菲兔 - 生活也是大事业

其中{A,B,C}及{B,D,E,F}是两个结群,而B是相应的切割点。

 

除了研究成分的内在结构,研究者们还对“寻找成分的边缘及核心”很感兴趣。通常采用嵌套的手段实现这种搜索。

《社会网络分析法》读书笔记(五)“凝聚子群” - 皮皮米菲兔 - 生活也是大事业

具体的嵌套模式可以分为两类:依据点的度数(K核),依据线的重数(M核)。

k-K核:每个点的度数不小于k。

m-M核:每条线的多元度不小于m。

初始的简单成分为:1-K核,1-M核。

去掉某些点,得到:2-K核,2-M核。

······

定义所谓的k剩余集合,即属于k-K核且不属于(k+1)-K核的点。也就是从k-K核变化为(k+1)-K核过程中被去掉的那些点。类似地可以定义m剩余集合。

上述过程构造了一个“核塌缩序列”,序列中每个数值为相应的剩余集合的点数。这个序列的稳定性从某个角度衡量了成分的密集性。若“核塌缩序列”的波动较大,则表明成分中存在紧密区域。这种塌缩序列可以用两个例子来说明。

例1.K核

《社会网络分析法》读书笔记(五)“凝聚子群” - 皮皮米菲兔 - 生活也是大事业

例2.M核

《社会网络分析法》读书笔记(五)“凝聚子群” - 皮皮米菲兔 - 生活也是大事业

 

总地来说,成分、环成分、结群及嵌套是对密度的补充,是描述网络性质的重要手段。

在描述网络的过程中,应当综合考虑的因素主要有:网络总体密度,成分的数量与规模,成分的密度,成分的嵌套结构,核塌缩序列。

 

二、派系

派系与成分不同,它要求所有点都互相邻接,且不被更大的派系所包含。正式的定义为:派系就是图中最大的完全子图(或完备子图)。

令U为无向图G的顶点的子集,当且仅当对于U中的任意点u 和v,(u,v)是图G的一条边时,U定义了一个完全子图(complete subgraph)。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在G的一个更大的完全子图中时,它是图G的一个完备子图。最大的完备子图是具有最大尺寸的完备子图。

派系的定义较为严格,在实际的社会网络中往往很难找到标准的派系,因此放宽一些条件,得到了派系的两种推广:n派系,k丛。

n派系不要求所有点之间都直接相邻接,而是接受间接联系,但要求任意两点之间的距离不大于n。显然地,3派系比2派系松散。n派系在使用中具有一定的局限性,主要包括:n大于2时,很难给出社会学解释;n派系的一些途径中的中介点可能不在派系中;(直径大于n)。对此进行一定的约束,要求直径不大于n,即得到n宗派(n-clan)的定义。

k丛(k-plex)则从另一个角度进行推广。N个点的k丛中,每个点至少与(N-k)个点相邻接。

1丛就是1派系。

2丛可以不是2派系。

3派系可以不是3丛。

k丛概念似乎比n派系概念更体现凝聚力思想,更符合对派系的想象。

 

社会网络中的派系往往存在各种各样的重叠,派系的重叠程度是对派系之间距离的一种测度,并由此引出社会圈的概念。

通常可以根据派系的重叠情况将若干派系逐步地合并为社会圈。一个典型做法的步骤如下。

(1)找到一些三人组(规模为3的派系)

(2)若两个派系的2/3成员相同,则合并为一个圈

(3)若又有1/3的重叠,则进一步合并为圈(重叠层次较低)

其中2/3和1/3的选取仅依据常识或直觉。

  评论这张
 
阅读(2404)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018