社会网络是人们通过各种关系建立起来的联系，并通过成员之间的交互作用形成的一种网络化结构. 社交网络为人们建立和维持各种社会关系提供了便利. 人际关系为信息交流提供一个有效的渠道，让知识、想法或私人信息更好地传播. 社会网络研究最先使用这一方法，用中心性（centrality）指标对节点重要性进行量化. 在这里，节点的重要性可以理解为该节点对其他节点或整个网络的影响. 中心度（degree centrality）是指采用定量方法对每个节点处于网络中心地位的程度进行刻画，从而描述整个网络是否存在核心，以及存在什么样的核心. 中心度的主体对象可以是网络中的节点、边、局域社团甚至是整个网络.

公司或企业的中心人物对公司的影响颇大. 国内外已有众多对社交网络和中心度算法的研究. 但是以往的中心度算法，只考虑单一的度量标准，没有考虑多种中心度的共同影响. 这种考虑在某些时候是不全面的，没有考虑网络规模，没有显示不同地区的文化差异，更不能横向比较. 由于权值可以显示出网络中节点的重要性，因此加权网络结构是非常实用的. 本文考虑各种中心度的共同影响，提出加权中心度算法，以刻画社交网络的中心性，力求更全面、更完善地对比分析不同文化环境下的网络中心性. 此外，由于实验采用真实的大数据，因此使用Spark集群并行计算来提高处理数据的效率.

本文内容如下组织. 第1节给出本文的相关工作. 第2节给出中心性的主要定义. 第3节给出算法和实验设计. 第4节给出实验中的重要环节——参数调优. 最后是结语部分.

1 相关工作

各学科领域对中心度算法的研究由来已久. 下面将从公司中心人物的重要性、现有社交网络研究、加权算法这3方面介绍本文的相关工作.

公司或企业的中心人物对公司的影响颇大. Larcker等^[1]论证了公司的中央委员会获得风险校正后更高的股票收益，可以归因于更大的信息访问. Hwang等^[2]发现如果公司董事会成员个人连接到首席执行官，则有更高的首席执行官薪酬、更低的支付功能敏感度和成交量敏感度. 首席执行官的社会关系会使得董事会成员监督的有效性降低^[2-3]. Ishii等^[4]研究发现首席执行官与广泛的个人网络不太可能取消收购，即使收购公告的市场反应是负面的. Faleye等^[5]研究发现，大多数独立董事会成员都被认为是“密集监测员”的董事会，这显示出卓越的监测绩效. Suri等 ^[6]应用游戏理论中心来研究网络中的影响传播，使用top-k算法来识别网络中k个最有影响的节点.

国内外已有众多对社交网络和中心度算法的研究. 在国内，郑巍^[7]利用节点网络中心度和共同邻居数来计算2个节点的相似性，即共同邻居数越多、共同邻居的网络中心度越高，则两个节点的相似度越高. 李明雪^[8]选取了度中心性、介数中心性、离心率中心性3个指标，用于构建不确定性证据合成的指标集，使用主观贝叶斯方法对证据集合进行合成，从而得到社会网络内节点的中心性排名. 郭静^[9]研究的基于社交网络传播的信息聚散结构，使人们传播和获取信息的能力得到了提高，从而加速了人际交流和信息流通. 在国外，Jackson^[10]使用在社交网络中个人节点的链接到其他个人节点的链接形式. 网络中的每个节点的位置不是随机的，网络强大的人可能会更好地获取信息. Cai等^[11]认为网络位置很重要. 网络的中心，而不是边缘，可以为个体提供更多的信息获取和控制信息流动.

权值可以显示出网络中节点的重要性，加权网络结构非常实用. 李静茹等^[12]将无权网络中的主分量中心性应用于加权社交网络，提出基于链接强度矩阵的加权中心性度量法. 刘欣等^[13]根据社交网络的特点，采用基本的中心性指标加权来度量节点的自身影响力，并考虑信息在网络中的动态传播来度量其潜在影响力. 王晓彤等^[14]提出了一种新的微博用户影响力度量模型——UIRank模型. 它以用户之间的交互行为作为切入点，根据用户不同行为的权重差异确定用户间UIRank值的分配比例. 林穗等^[15]针对在线广告投放中对实时性和高精确度的要求，提出了将线性模型结合Spark技术应用在广告投放系统中，并从数值特征、迭代和步长等方面对模型进行优化. 曾碧等^[16]针对移动机器人在室内环境下自主导航过程中的走廊识别问题，提出一种改进的走廊识别算法. 陆靖桥等^[17]提出非微博网络应采用度和介数攻击策略，而微博网络应采用度和紧密度攻击策略. 还有，广为人知的PageRank算法 ^[18]是研究用户影响力的一种基本方法，该算法通过网页的链接结构来度量网页的重要性. Triangle Counting^[19]用于计算网络聚集系数和传递性的重要步骤，可识别重要角色.

2 中心性的定义

目前常用的中心度度量指标有：节点中心度（de- gree centrality）、接近中心度（closeness centrality）、介数中心度（betweenness centrality）、特征向量中心度（eigenvector centrality）和三角计数（triangle counting）等.

节点中心度（以下简称中心度）测量网络中一个节点与所有其他节点相联系的程度，是最基本的中心性度量. 对于一个拥有g个节点的无向图，节点i的中心度是i与其他g-1个节点的直接联系总数，用公式表示为

${C_D}({N_i}) = \sum\limits_{j = 1}^g {{x_{i{\rm{ }}j}}} (i \ne j).$

(1)

其中，C _D (N _i )表示节点i的中心度， $\sum\limits_{j = 1}^g {{x_{ij}}} $ 用于计算节点i与其他g-1个节点j（i≠j，即排除i与自身的联系）之间的直接联系的数量. 简单地说，C _D (N _i )的计算将节点i在网络矩阵中对应的行或列所在的单元格值累加.

介数中心度表示社会网络中经过某节点的最短路径的比例. 公式为

${C_{_B}}(v) = \sum\limits_{s \ne v \ne t} {\frac{{{\delta _{st}}(v)}}{{{\delta _{st}}}}} .$

(2)

其中， ${\delta _{st}}$ (v)表示从s到t的最短路径中经过节点v的路径数量， ${\delta _{st}}$ 表示从s到t的最短路径数.

接近中心度描述网络节点间在最短路径上的距离，它利用计算节点v _i 与其他节点v _j 的最短距离之和的倒数来描述度量指标. 公式为

${C_c}({v_i}) = \frac{{n - 1}}{{\sum\nolimits_{j \ne i}^n {g({v_i}} ,{v_j})}}.$

(3)

其中，g(v _i , v _j )是v _i 与v _j 的最短路径距离.

特征向量中心性被用于刻画通过高度值的邻接点获得的间接影响力. 如果一个节点的度数很高，说明这个节点有较高的中心性. 但是如果一个节点的度数不是很高，但是它与一个有很高度值的节点邻接，那么这个节点的中心性应该也不会很低. 著名的PageRank算法是类似于特征向量中心度的算法. PageRank的定义为

${\rm{PageRank}}\left( {{p_i}} \right) = \frac{{1 - q}}{N} + q\sum\limits_{{p_j}} {\frac{{{\rm{PageRank}}\left( {{p_j}} \right)}}{{L\left( {{p_j}} \right)}}} .$

(4)

此外，还有三角中心性度量. 它在社交网络分析中是非常有用的. 假如在公司里面，你认识两个人，而这两个人相互认识，那么这就可以组成一个三角形. 本文主要考虑了多种中心度，分别计算了度中心性、三角计数和PageRank值.

3 实验 3.1 数据描述

本文使用真实的社交网络数据库Boardex，由合作单位香港大学提供. BoardEx是全球领先的人脉资本管理数据库（网址http://corp.boardex.com）. 它提供重要商业应用所需的精准数据，Boardex的数据库记载了逾60万名商界人士间的相互关系，它可以提供一个人的教育背景、被雇佣经历和与高管之间的联系，当然也有年龄性别等个人信息. 该数据库造价高昂，目前还没有计算机领域的文章使用过它. 目前已经得到香港大学提供的基础数据约600 G，其中使用到的单个表文件最大5 G.

由于需要处理大数据，因此使用Spark平台. Apache Spark（网址http://spark.apache.org/）是一种新兴的通用数据处理引擎，专门用于商用计算集群的内存计算. 当单机无法处理大数据的时候，利用集群并行计算的能力，在多台机器上同时处理数据，这样处理数据的效率将大大提高，而且伴随集群节点数量的增加，计算速度也会相应的加快. 本文利用3台台式机进行集群，每个机器内存分布16 GB，处理器为4，硬盘2 TB，集群环境是Spark On Yarn，其中，Hadoop版本：2.7.0；Java版本：1.8；Scala版本：2.11.8；Spark版本：Spark-2.0.0-bin-hadoop2.7.

Spark集群规划如表1所示.

以下是集群部署：

1) Spark集群所有节点部署Java，配置环境变量（/etc/profile）并source生效，如下：

export JAVA_HOME=/usr/lib/jvm/jdk

export JRE_HOME=${JAVA_HOME}/jre

export PATH=$PATH:$JAVA_HOME/bin

export CLASSPATH=./:$JAVA_HOME/lib:$JAVA_HOME/jre/lib

2) Spark集群所有节点部署Scala

Scala部署好之后，配置环境变量并source生效，如下：

export SCALA_HOME=/usr/lib/jvm/scala

export PATH=.:$SCALA_HOME/bin:$PATH

3) 配置Spark目录下conf/spark-env.sh

export JAVA_HOME=/usr/lib/jvm/jdk

export SCALA_HOME=/usr/lib/jvm/scala

export SPARK_MASTER_IP=10.21.63.46

export SPARK_WORKER_MEMORY=10g

export HADOOP_CONF_DIR=/usr/lib/jvm/hadoop/etc/hadoop

export master=spark://Master:7077

export SPARK_EXECUTOR_MEMORY=5g

export SPARK_DRIVER_MEMORY=4g

export SPARK_MASTER_OPTS="-Dspark. deploy.defaultCores=3"

export HADOOP_HOME=/usr/lib/jvm/hadoop

export SPARK_WORKDER_CORES=2

对于Boardex数据库，选取美国、英国、欧洲和其他国家4个地区的社交网络数据. 在构建计算加权中心度的函数之前，先利用Spark进行个人中心度的一些基本计算. 根据这些基本数据，来选取加权函数的形式和进行参数调优.

在进行实验之前，先对数据进行预处理. 选取4个区域上市公司的首席技术官（chief technology officer，简称CTO）和首席信息官（chief information officer，简称CIO）的相关数据，并且剔除数据集中的不完整样本. 数据集中各字段描述如表2所示.

3.2 实验设计

本文对真实的社交网络计算PageRank、三角计数、度中心性. 首先，分别计算所有个体连接在这个庞大网络的中心度，通过加权算法来避免单个中心度的不足. 其中，PageRank值反映节点的重要程度. 三角计数表明在社交网络中拥有越多的三角形，其联系也就越紧密. 度中心性是在网络分析中刻画节点中心性的最直接度量指标. 本文研究的是在不同区域、不同文化环境下的网络中心度，因此对一个区域的人员中心度取平均值可得到区域的中心度. 表3给出在数据集中4个区域的人口数及中心度平均值.

根据以上实验的基本数据，可以构建以下线性加权中心度公式W，W ₁，W ₂，W ₃，W ₄.

$\begin{array}{l}W = {\left( \alpha \right._1} \times {\rm{PageRank}}\_{\rm{ave}} + \\[8pt]\;\;\;\;\;\;\;\;{\alpha _2} \times {\rm{TriangleCounting}}\_{\rm{ave + }}\\[8pt]\;\;\;\;\;\;\;\;{\alpha _3} \times {\rm{Degree}}\_\left. {{\rm{ave}}} \right)/\left( {\gamma \times {\rm{People}}\_{\rm{num}}} \right).\end{array}$

(5)

$\begin{array}{l}{W_1} = ({\alpha _1} \times 0.460\;618\;36 + {\alpha _2} \times 11.565\;860\;37{\rm{ + }}\\[7pt]\;\;\;{\alpha _3} \times 5.594\;858\;2)/(\gamma \times 221\;051).\end{array}$

(6)

$\begin{array}{l}{W_2} = ({\alpha _1} \times 0.232\;620\;636 + {\alpha _2} \times 3.162\;462\;857{\rm{ + }}\\[7pt]{\rm{ }}{\alpha _3} \times 3.830\;903\;186)/(\gamma \times 43\;413).\end{array}$

(7)

$\begin{array}{l}{W_3} = ({\alpha _1} \times 0.259\;913\;793 + {\alpha _2} \times 3.020\;783\;509{\rm{ + }}\\[7pt]{\rm{ }}{\alpha _3} \times 3.648\;860\;293)/(\gamma \times 47\;249).\end{array}$

(8)

$\begin{array}{l}{W_4} = ({\alpha _1} \times 0.256\;820\;14 + {\alpha _2} \times 2.085\;386\;334{\rm{ + }}\\[7pt]{\rm{ }}{\alpha _3} \times 3.281\;072\;336)/(\gamma \times 181\;882).\end{array}$

(9)

${W_5} = ({W_1} + {W_2} + {W_3} + {W_4})/4.$

(10)

$\begin{array}{l}{\rm{fun}} = \min (({({W_1} - {W_5})^2} + {\rm{ }}{({W_2} - {W_5})^2} +\\[7pt]{({W_3} - {W_5})^2} + {\rm{ }}{({W_4} - {W_5})^2})/4).\end{array}$

(11)

方程W表示线性加权中心度函数的基本形式，其中α ₁、α ₂、α ₃分别表示3种中心度的权值，γ表示人口总数的权值. 根据W，W ₁是美国区域的加权中心度，W ₂是英国区域的加权中心度，W ₃是欧洲区域的加权中心度，W ₄是其他国家的加权中心度. W ₅则是所有区域的加权中心度的平均值. 函数fun是最小平方误差函数. 它的构建表明，尽管不同区域的加权中心度不同，但是可以通过调整线性权，使得总中心度理念是一致的，或者误差尽可能最小化. 针对本文所选用的数据集，计算3个中心度平均值的核心代码请见附录部分.

4 参数调优

本文利用Matlab Version：8.0.0.783（R2012b）软件计算线性加权函数中的α ₁、α ₂、α ₃、γ等权重系数. 在此处选取fminunc函数，用来求解多变量函数的最小化. 选取不同的权值初始值，来获得使得函数fun最小的最优调整值. 参数调优过程见表4.

Matlab过程如下：

x0=[1, 1, 1, 1]；%各变量的初始值

[x, fval, exitflag, output, grad, hessian]=minunc(fun, x0).

在以上过程中，exitflag为退出标志. 当它大于0时表示函数收敛于x，即函数具有收敛性. 实验过程中，exitflag均等于1，这表明fun函数是收敛的. 根据表4可知，4个区域之间的方差最小值都接近于0，fun函数的最小值接近于0. 这表明通过调整权值，不同区域的加权中心度的误差很小. 而且，通过权值的大小，可以看到不同的中心度度量标准对加权中心度的影响是不同的. 例如，当函数取最小值时6.677 3e^–10，平均PageRank的权值为0.003 9，平均三角计数的权值为0.047 8，平均中心度的权值为0.0647，人口总数的权值为–0.116 4. 这是因为，不同区域代表了不同的文化环境，因而使得各种中心度度量标准的作用产生差异. 物理意义：PageRank值表示人脉的重要程度；三角计数表示小圈子的个数；度中心性表示认识人的总数.

5 结论

本文提出社交网络中加权中心度的思想，并在真实数据库上进行应用. 通过计算在社交网络上的个人中心度、PageRank值、三角计数，得到一个地区的线性加权平均中心度. 调整权值，可以使得不同区域的加权中心度的误差尽可能小，并且不同的中心度度量标准对加权中心度有不同影响. 本文方法是加权社交网络和大数据应用的一次良好结合，对金融智能、中心性分析、数据分类和兴趣推荐等方面的研究都有重要的现实意义.

在接下来的工作中，还需要进一步的改进和完善，体现在两个方面：（1）目前工作采用线性加权，未来可尝试其他类型的加权中心度函数，例如非线性函数，可能会得到更好的拟合数据；（2） 目前工作采用地区分类，未来可尝试其他数据分类，例如年龄、性别和职业角色等.

附录：

(1) 计算Degree

import org.apache.spark.graphx.GraphLoader

// 加载边

val graph = GraphLoader.edgeListFile(sc,"/repeat/row/ ciocto/followers.txt")

//运行图的度数

val degrees=graph.degrees

// 使用用户名加入图的度数

val users = sc.textFile("/repeat/row/ciocto/users.txt").map { line =>

　val fields = line.split("\t")

　(fields(0).toLong, fields(1))

}

val degreesByUsername = users.join(degrees).map {

　case (id, (username, degrees)) => (id, degrees)

}

// 打印结果

println(degreesByUsername.collect().mkString("\n"))

// 保存结果

degreesByUsername.saveAsTextFile("/abe/rowdegree.txt")

(2) 计算PageRank

import org.apache.spark.graphx.GraphLoader

//加载边

val graph = GraphLoader.edgeListFile(sc,"/repeat/uk/ ciocto/followers.txt")

//运行PageRank

val ranks = graph.pageRank(0.0001).vertices

// 使用用户名加入图的PageRank

val users = sc.textFile("/repeat/uk/ciocto/users.txt").map { line =>

　val fields = line.split("\t")

　(fields(0).toLong, fields(1))

}

val ranksByUsername = users.join(ranks).map {

　case (id, (username, rank)) => (id, rank)

}

// 打印结果

println(ranksByUsername.collect().mkString("\n"))

// 保存结果

ranksByUsername.saveAsTextFile("/ab/ukdegree.txt")

(3) 计算Triangle Counting

import org.apache.spark.graphx.{GraphLoader, PartitionStrategy}

// 按照规范顺序加载边缘, 并将图形划分为三角形计数

val graph = GraphLoader.edgeListFile(sc,"/repeat/row/ ciocto/followers.txt", true).partitionBy(Partit

ionStrategy.RandomVertexCut)

// 找到每个顶点的三角形计数

val triCounts = graph.triangleCount().vertices

// 使用用户名加入三角形计数

val users = sc.textFile("/repeat/row/ciocto/ users.txt").map { line =>

　val fields = line.split("\t")

　(fields(0).toLong, fields(1))

}

val triCountByUsername= users.join(triCounts).map { case (id, (username, tc)) =>

　(id, tc)

}

// 打印结果

println(triCountByUsername.collect().mkString("\n"))

// 保存结果

triCountByUsername.saveAsTextFile("/repeatresult/row/ciocto")