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

生活也是大事业

阿波的学习、工作和生活

 
 
 
 
 

日志

 
 
关于我

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

文章分类

《社会网络分析法》读书笔记(三)“密度”  

2010-04-20 00:04:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

继续。

前面已经介绍了“社会网络分析”所涉及的数据形式(发生阵与邻接阵),下面开始引入与图论相关的一些概念,以展示“网络”的特点。

简单地说,一个图由“点”与“线”组成,其中的点可以理解为网络中的个体,而线则是网络中的关系,由于表述习惯的原因,下文涉及到这些概念时不加区别。

我们称两个个体是“邻接的”(adjacent),是指这两个点之间有线相连,等价地,是指在邻接阵中的相应位置上元素为1。而一个个体的“邻域”,是指与该个体相邻接的所有个体构成的集合。某个体的邻域中的点的数目,称为这个个体在这个网络中的“度数”(degree)。

形象地说,度数就是这个点引出来的线的条数。反映在数据上,某个个体的度数就是邻接阵中这个个体所对应的行的行和或者列的列和(考虑到对称性)。

在图中,一个线路(walk)是指由一系列首尾相连的线构成的集合。当一个线路中不存在重复的点和线时,将其称为一个“途径”(path)。一个途径中的线的条数,称为这个途径的“长度”(length)。

形象地说,从一个点到另一个点之间用线相连接的路径就是一个线路。而当这个路径中不存在回头路时,则称其为一个途径。显然地,两点之间可能存在不止一条的途径,我们称其中长度最短的一条途径为“捷径”,而捷径的长度则称为这两点之间的“距离”(distance)。

注:上述定义的前提是“无向图”。在有向图的情形下,需要进行一定的推广。简单地说是将度数分为“点入度”与“点出度”,分别对应了箭头的两种方向,可以从字面上进行理解。相应地,点入度是邻接阵中的列和,而点出度则是邻接阵中的行和。涉及到途径时,相关定义也变得更加严格,仅当所有线的箭头方向一致时可以将两点之间的线路称为途径(即只能由一点指向另一点),当无法满足这个条件时,途径退化为半途径(semi-path)。由于我本人比较偷懒,后面的笔记中也尽量不涉及有向图的情形。与此同时,多值图也是本人尽量避免涉及的特殊情形。事实上,多值图可以通过简单的阈值处理转化为二值图。即便在研究过程中对线的多重性有所关注,也可以进行一系列简单的推广得到关于多值图的若干初等结论。

 

在定义了图中的基本元素后,下面引入社会网络分析中的第一个重要概念:密度(density)。

抽象地说,一个图的密度就是对这个图的完备性的一种测度。而所谓完备性,则是指这个图中各点之间邻接的程度。一个完备的图是指图中各点两两邻接。

也就是说,网络的密度在一定程度上表征着这个网络中关系的数量与复杂程度。在一个密度为1的网络中,每个个体都与其他所有个体产生关系。相反地,在一个密度为0的网络中,不存在个体与个体之间的关系(此时似乎很难再将其称为一个网络)。

在对网络密度进行具体定义的过程中,需要从两个角度进行衡量:图的内含度以及图中各点的度数总和。

“各点度数总和”很好理解,度数和越大,则关系数量越多。

而“内含度”则重点关注了图中的孤立点,也就是不与任何点相邻接的点。内含度的常见定义是“非孤立点数与总点数之比”,孤立点越多,内含度越小,图的密度也就越小。

综合考虑上述因素,一般将图的密度定义为“图中实际存在的线的条数/图中理论上最多可能产生的线的条数”。当图中点的个数为n时,密度可以表示为l/[n(n-1)/2]。其中分子l是图中实际存在的线的条数,是所有点度数总和的一半,也就是邻接阵中所有元素总和的一半。而分母可以用简单的排列组合方法计算得到。

这个密度的定义是合理而自然的。在这个定义下,完备图的密度为1。

需要注意的是,在实际研究过程中,问题往往不会这样简单。如果更严格地考虑密度的定义,“图中理论上最多可能产生的线的条数”并不能简单地从每点相连的假设推导出来,而是与问题的具体背景有关。一般地,“实际最多线数”总是小于“理论最多线数”的,换句话说,密度为1的网络基本不存在(有研究指出在实际网络中能够发现的最大的密度是0.5)。这与网络的规模有关,也与问题中的“关系”的性质有关。忽视这个因素并不会影响对某个图的密度的判断,但是却会导致我们难以比较不同图的密度大小。事实上,当考虑网络规模的影响时,我们通常认为每个个体的度数具有一个上限,于是网络中的“实际最多线数”等于这个上限与网络规模的乘积(除以2),从而使得大图的密度往往会小于小图的密度。书中似乎阐述的不是很清楚,需要进一步学习。

另外,与我们在统计学中所学习的一样,在社会网络分析中也存在着如何用样本密度来估计总体密度的问题。这种估计往往转化为对密度定义中分子的估计,也就是对所有点度数总和的估计,并可以进一步地转化为对所有点的平均度数的估计。当然,更直观的方法是对整体网络进行随机抽样,研究若干个较小的子图,并用这些子图的密度的平均值作为对整体网络的密度的估计。这里的一个结论是:对100000人组成的网络进行分析时,可以考虑从中抽取五个100人的样本,也可以考虑从中抽取两个200人的样本,都可以得到比较可靠的估计。

 

总而言之,密度是社会网络分析中的一个重要测度,并且具有容易计算的特点。但是,密度的简单定义也导致其容易受到网络的规模以及网络中关系的性质的影响,导致其无法对不同网络之间密度的差异进行很客观的衡量。因此,在具体使用过程中,如果能够与网络的规模及网络的内含度等其他测度一起表示出来,网络的密度会具有更明显的参考价值。

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

历史上的今天

评论

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

页脚

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