论文部分内容阅读
摘 要 对网络的基本性质的探测是对网络深入研究的基本模式和前提条件，文章对社会网整体网的几种属性展开阐述和分析，为整体网的理解和探索提供启发式信息。
关键词 中心性；凝聚子群；小世界模型
中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2014）15-0035-01
PageRank算法简单描述如下：u是一个网页，F（u）是页面u指向的网页集合，B（u）是指向u的网页集合，N（u）=|F（u）| 是u指向外的链接数，c是规范化因子（一般取0.85）。
那么网页u的PageRank值可以利用下面的公式计算：
该算法的矩阵描述形式为：
设A为一个方阵，方阵A的行和列对应网页集的网页。如果网页u有指向网页v的一个链接，即存在社会网中的“引用”关系，则Au，v=1/N（v），否则Au，v=0。设R是对应网页集的PageRank值向量，则有R=cAR，可得R为A的特征根为C的特征向量。而在实际操作中，最终的PageRank值往往可以通过求最大特征根的特征向量得到。
社会网属性的浅析：宏观来说，PageRank是在对社会网基础分析上对其特有属性深入研究创造的算法，因此对网络中的属性分析的了解是重要的。在分析网络中节点的影响力的案例中，笔者给出以下几种属性研究，对得到精确的影响力相对值有较好的启发性。
1 中心性
1）点度中心度（Degree of Centrality）。点度中心度说明了与节点v相连接的总的个数，这也反应了节点v与其他节点连接的能力。在有向网络中，节点之间的连接存在“连接”和“被连接”的关系，所以每个节点的度数可分为点入度和点出度；具体得讲，微博的转发与被转发存在方向性，这样就需要出度和入度的区别；而在合著者网络中，忽略点的有向性又往往能提高计算的效率。在具体计算中，点度中心度可分为绝对中心度和相对度数中心度，后者主要是为了使数据更具有可比性而改进的算法[4]。
2）中间中心度（Between Centrality）。当两个点之间的联系需要通过另外一个点的联系才能达成，那么这个“另外一个点”具有一定的中间中心度，中间中心度测量一个节点控制资源的路径的能力。当这个点相对于其他点之间最短路径时必须经过的点，那么这个点的中间中心度就相对地高；一个节点具有很高的中间中心度，并不代表这个节点有很高的点度中心度。如节点a与节点b组成合著者网络，而节点a与节点c的合著者网络必须要有节点b的支持才能构建，那么节点b就有较高的中间中心度。具有中间中心度的节点，往往因为其所具有的“中介”能力，即使只有较低的点度中心度，也能其处于网络的中心。
3）接近中心度（Closeness Centrality）。接近中心度描述了一个节点与其他节点接近的程度。如果一个节点与网络中其他所有节点都有很近的距离，那么这个节点就有较高的接近中心度。接近中心度度量了一个节点所具备的得到很高的点度中心度的潜力。如节点v与节点a，b，c三个节点都没有连接，但与a b，c相连的节点都有联系，那么说明节点v具有成为核心点的潜力。但往往接近中心度越大时，说明这个节点越不是网络的中心点。
2 凝聚子群
在对节点在网络中的关系研究层面上，除了中心度以外，还有网络中的子群体（subgroups）之间的联系，在某些情况下，我们可以通过研究节点之间联系的紧密程度来确定子群体，也就是凝聚子群。对于凝聚子群的研究往往集中在网络中凝聚子群的种类以及凝聚子群内节点之间的联系等。对于凝聚子群的定义，尚未有一个权威的解释，但从大体上讲“凝聚子群是满足集中条件的一个行动者子集合，即在此集合中的行动者之间具有相比其他行动者有较强、直接而且密集、频繁和积极的关系”[5]。在此基础上，可以从以下四个角度对凝聚子群进行拆分。
1）关系的互惠性。
2）子群成员之间的接近性或者可达性。
3）子群内部成员之间关系的频次（也就是节点的度数）。
4）子群内部成员之间的关系密度相对于内、外部成员之间的关系的密度。
建立在关系互惠性上，可以构建派系。严格地讲，派系内的所有节点都相互连接，这样才能使互惠的程度达到最大化；基于可达性和接近性基础上的凝聚子群可以分为n-派系（n-cliques），通过设定一个临界值n作为凝聚子群成员之间距离的最大值。假设n=2，节点v与节点a相连，而节点a与节点b相连，那么节点v和节点b之间的距离为2，则符合2-派系的要求，v， a， b可归为一个派系；反之，当节点w与节点v相连，节点b与节点w之间的距离为3，则不符合2-派系的定义，那么节点w将不属于这个派系。
建立在节点度数的凝聚子群则更多地被广泛应用。如k-丛（k-plex）和k-核（k-core），k-丛要求该子群中所有点的度数都必须大于等于（n-k）值（假设n为网络的规模），而k-核则要求要求该子群中所有点的度数都必须大于等于k；无论是k-丛还是k-核，都要比n-派系子群更具有稳健性，更能体现凝聚力的思想。
3 小世界模型
小世界模型（Small World Model）揭示了网络中节点之间联系的高度重叠性。小世界模型的基本显示模型是随机的密友网络，结论是世界上任何人都只需要大概6步就能够建立连
接[6]，在一个巨大而且稀疏的网络中，节点极度分散，不存在核心点，但网络是高度聚类的情况下，小世界的效应是明显的。而在大多数情况下，小世界模型尤其适合社会网的分析，如互联网、电网、社交网络等。对小世界模型性质的分析已有大量文献参阅，如果能准确区别一个网络是否属于小世界模型，那么就能判断这个网络是否符合小世界模型的性质，在此基础上可继承大量可参考性质。现定义L为网络中节点之间最小距离的平均值，L由如下公式计算得出：
其中，dij代表节点i和节点j之间的最小距离，n为网络的规模。当L值相对得小的时候，就可以确定这个网络是否符合小世界模型。对于相对较小的L值判断，有如下三个条件：
1）总体规模n是固定的。
2）节点的平均度数因此也是固定的，其值大于1，并且远小于n。
3）网络之内节点之间必须可通过一定的距离建立联系，即不存在完全隔离的节点。
通过中心性、凝聚子群和小世界模型的分析，能够在一定程度上建立对社会网的基本认知，对指标的理解是深入研究网络并对网络做出准确预测的判断的必要条件。
参考文献
[1]蔡建超，蔡明.搜索引擎PageRank算法研究[J].计算机应用与软件，2008（09）.
[1]刘军著.社会网络分析导论[M].社会科学文献出版社，2004.
关键词 中心性；凝聚子群；小世界模型
中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2014）15-0035-01
PageRank算法简单描述如下：u是一个网页，F（u）是页面u指向的网页集合，B（u）是指向u的网页集合，N（u）=|F（u）| 是u指向外的链接数，c是规范化因子（一般取0.85）。
那么网页u的PageRank值可以利用下面的公式计算：
该算法的矩阵描述形式为：
设A为一个方阵，方阵A的行和列对应网页集的网页。如果网页u有指向网页v的一个链接，即存在社会网中的“引用”关系，则Au，v=1/N（v），否则Au，v=0。设R是对应网页集的PageRank值向量，则有R=cAR，可得R为A的特征根为C的特征向量。而在实际操作中，最终的PageRank值往往可以通过求最大特征根的特征向量得到。
社会网属性的浅析：宏观来说，PageRank是在对社会网基础分析上对其特有属性深入研究创造的算法，因此对网络中的属性分析的了解是重要的。在分析网络中节点的影响力的案例中，笔者给出以下几种属性研究，对得到精确的影响力相对值有较好的启发性。
1 中心性
1）点度中心度（Degree of Centrality）。点度中心度说明了与节点v相连接的总的个数，这也反应了节点v与其他节点连接的能力。在有向网络中，节点之间的连接存在“连接”和“被连接”的关系，所以每个节点的度数可分为点入度和点出度；具体得讲，微博的转发与被转发存在方向性，这样就需要出度和入度的区别；而在合著者网络中，忽略点的有向性又往往能提高计算的效率。在具体计算中，点度中心度可分为绝对中心度和相对度数中心度，后者主要是为了使数据更具有可比性而改进的算法[4]。
2）中间中心度（Between Centrality）。当两个点之间的联系需要通过另外一个点的联系才能达成，那么这个“另外一个点”具有一定的中间中心度，中间中心度测量一个节点控制资源的路径的能力。当这个点相对于其他点之间最短路径时必须经过的点，那么这个点的中间中心度就相对地高；一个节点具有很高的中间中心度，并不代表这个节点有很高的点度中心度。如节点a与节点b组成合著者网络，而节点a与节点c的合著者网络必须要有节点b的支持才能构建，那么节点b就有较高的中间中心度。具有中间中心度的节点，往往因为其所具有的“中介”能力，即使只有较低的点度中心度，也能其处于网络的中心。
3）接近中心度（Closeness Centrality）。接近中心度描述了一个节点与其他节点接近的程度。如果一个节点与网络中其他所有节点都有很近的距离，那么这个节点就有较高的接近中心度。接近中心度度量了一个节点所具备的得到很高的点度中心度的潜力。如节点v与节点a，b，c三个节点都没有连接，但与a b，c相连的节点都有联系，那么说明节点v具有成为核心点的潜力。但往往接近中心度越大时，说明这个节点越不是网络的中心点。
2 凝聚子群
在对节点在网络中的关系研究层面上，除了中心度以外，还有网络中的子群体（subgroups）之间的联系，在某些情况下，我们可以通过研究节点之间联系的紧密程度来确定子群体，也就是凝聚子群。对于凝聚子群的研究往往集中在网络中凝聚子群的种类以及凝聚子群内节点之间的联系等。对于凝聚子群的定义，尚未有一个权威的解释，但从大体上讲“凝聚子群是满足集中条件的一个行动者子集合，即在此集合中的行动者之间具有相比其他行动者有较强、直接而且密集、频繁和积极的关系”[5]。在此基础上，可以从以下四个角度对凝聚子群进行拆分。
1）关系的互惠性。
2）子群成员之间的接近性或者可达性。
3）子群内部成员之间关系的频次（也就是节点的度数）。
4）子群内部成员之间的关系密度相对于内、外部成员之间的关系的密度。
建立在关系互惠性上，可以构建派系。严格地讲，派系内的所有节点都相互连接，这样才能使互惠的程度达到最大化；基于可达性和接近性基础上的凝聚子群可以分为n-派系（n-cliques），通过设定一个临界值n作为凝聚子群成员之间距离的最大值。假设n=2，节点v与节点a相连，而节点a与节点b相连，那么节点v和节点b之间的距离为2，则符合2-派系的要求，v， a， b可归为一个派系；反之，当节点w与节点v相连，节点b与节点w之间的距离为3，则不符合2-派系的定义，那么节点w将不属于这个派系。
建立在节点度数的凝聚子群则更多地被广泛应用。如k-丛（k-plex）和k-核（k-core），k-丛要求该子群中所有点的度数都必须大于等于（n-k）值（假设n为网络的规模），而k-核则要求要求该子群中所有点的度数都必须大于等于k；无论是k-丛还是k-核，都要比n-派系子群更具有稳健性，更能体现凝聚力的思想。
3 小世界模型
小世界模型（Small World Model）揭示了网络中节点之间联系的高度重叠性。小世界模型的基本显示模型是随机的密友网络，结论是世界上任何人都只需要大概6步就能够建立连
接[6]，在一个巨大而且稀疏的网络中，节点极度分散，不存在核心点，但网络是高度聚类的情况下，小世界的效应是明显的。而在大多数情况下，小世界模型尤其适合社会网的分析，如互联网、电网、社交网络等。对小世界模型性质的分析已有大量文献参阅，如果能准确区别一个网络是否属于小世界模型，那么就能判断这个网络是否符合小世界模型的性质，在此基础上可继承大量可参考性质。现定义L为网络中节点之间最小距离的平均值，L由如下公式计算得出：
其中，dij代表节点i和节点j之间的最小距离，n为网络的规模。当L值相对得小的时候，就可以确定这个网络是否符合小世界模型。对于相对较小的L值判断，有如下三个条件：
1）总体规模n是固定的。
2）节点的平均度数因此也是固定的，其值大于1，并且远小于n。
3）网络之内节点之间必须可通过一定的距离建立联系，即不存在完全隔离的节点。
通过中心性、凝聚子群和小世界模型的分析，能够在一定程度上建立对社会网的基本认知，对指标的理解是深入研究网络并对网络做出准确预测的判断的必要条件。
参考文献
[1]蔡建超，蔡明.搜索引擎PageRank算法研究[J].计算机应用与软件，2008（09）.
[1]刘军著.社会网络分析导论[M].社会科学文献出版社，2004.