社交网络中个体价值分析

王志斌，黄　蔚

(华北计算技术研究所信息技术应用系统部，北京　100083)

社交网络中个体价值分析

王志斌，黄蔚

(华北计算技术研究所信息技术应用系统部，北京100083)

社交网络中个体价值分析，就是利用网络爬虫抓取社交网络中数据，对数据过滤分析，抽象成图结构，发现排名最高的节点（个体）。本文基于PageRank算法模型，应用“黄金分割线”方法和“二八定律”对其进行改进，并用在社交网络中，定义以人为核心的个体价值，这样PageRank模型就有了新的应用领域，同时也有了一个新的名字“PeopleRank”。本文将复杂的社交网络抽象成一种图结构，图中节点代表用户，图中边的链入链出代表了用户之间的“粉丝”和“关注”关系。利用“PeopleRank”模型，构建矩阵，对矩阵进行迭代计算，最后得到一个收敛的结果，根据结果的大小确定在社交网络中个体的重要性。

社交网络；个体价值；PeopleRank；

本文著录格式：王志斌，黄蔚. 社交网络中个体价值分析[J]. 软件，2016，37（8）：120-124

0　引言

随着互联网蓬勃发展，社交网络改变了人们的生活方式。如今人们会更多的利用社交网络，获取信息和分享信息。通过社交网络，我们每个个体，都成为了网络的中心。我们的生活半径，被无限放大，根据“六度理论”，我们通过6个朋友关系，就可以认识世界上任何一个人。如何从庞大的社交网络中分析出个体的价值。

为了解决上述复杂的问题，本文把PageRank这个抽象的算法模型，应用到了社交网络中，定义以人为核心的个体价值，同时在新的应用领域中也赋予了其新的名字PeopleRank。本文利用当下流行的大数据分析工具hadoop和spark针对实际例子，对其建模进行了设计与实现，具有较强的现实价值与意义。

1　相关概念介绍

1.1社交网络介绍

社交网络是一个系统：第一、系统中的主体是用户（User），用户可以公开或半公开个人信息；第二、用户能创建和维护与其他用户之间的连接（或朋友）关系及个人预分享的内容信息（如日志或照片等）；第三、用户通过连接（或朋友）关系能浏览和评价朋友分享的信息。

社交网络与传统的Web网络最大不同之处在于：传统的Web网络的主体是内容信息，依靠内容信息组织在一起，呈现给用户；而社交网络的主体是人，依靠人与人之间的朋友关系组织在一起。社交网络必须具备三项基本功能，即允许用户创建和维护朋友关系；上传自己预分享的内容信息；浏览其他用户分享的内容信息。但这三项功能在不同的社交网站上的体现形式可能存在较大差异，如Facebook 只允许用户遍历三层朋友关系，而人人网则没有这个限制。

1.2社交网分类

社交网络按照其功能属性，大致可以把社交网络分为如下类别：

交友网络；这类社交网络是现实社交圈子的映射，其朋友关系的真实性和关系维护的便捷性吸引了大量用户的参与。这类网站国际上比较流行的有facebook、cyworld和myspace等；国内比较流行的有renren网和开心网。除此之外，面向商务人士的xing和linkedin、婚恋交友网也属于此类网络。

博客网络；博客站点提供的最基本功能是博客的发布和用户关注服务，用户之间的关注关系就形成了社交网络。博客网络一般是有向网络，即用户A关注用户B的博客，但用户B未必关注用户A的博客。较大的博客站点有Google blogger、Microsoft live spaces、twitter、新浪博客、腾讯Qzone、Live Journal、Twitter和Follow5等。

媒体分享网络；这类网络主要用于用户发布、共享和检索媒体资源，如视频、图片或书签等。这些站点降低了信息发布的门槛，吸引大量用户参与进来。此类站点除了提供资源发布和共享服务外，也提供交友服务。这些站点上的用户形成的社交网络一般也是有向网络。

较大的站点有视频分享网站爱奇艺和优酷土豆、图片分享网站、网络书签站点CiteULike和delicious等。

即时通信网络；即时通信系统是一种实时交流工具，系统中的每个用户都有自己的联系人（或好友）列表。根据用户之间的好友关系可以构建即时通信系统中的社交网络。有代表性的即时通信系统有MSN、QQ和微信等。

除了上述网络以外，某些BBS（如天涯社区）和协同编辑站点（如百度百科）等也增加了关注或好友功能，这些站点上的用户之间也可组成社交网络。

上述站点所提供的服务之间有互补和重叠之处，如视频分享网络优酷上的用户也可以指定自己的好友；Facebook和人人网上的用户也可以发布自己的微博客，这使得我们很难在社交网络的分类上给出严格的划分。

1.3黄金分割

黄金分割线是一种古老的数学方法，黄金分割的创始人是古希腊的毕达哥拉斯，他在当时十分有限的科学条件下大胆断言：一条线段的某一部分与另一部分之比，如果正好等于另一部分同整个线段的比即0.618，那么，这样比例会给人一种美感。后来，这一神奇的比例关系被古希腊著名哲学家、美学家柏拉图誉为“黄金分割律”。

1.4二八定律

二八定律又名80/20定律、帕列托法则（定律）也叫巴莱特定律、最省力的法则、不平衡原则等，被广泛应用于社会学及企业管理学等。

1897年，意大利经济学者帕累托偶然注意到19世纪英国人的财富和收益模式。在调查取样中，发现大部分的财富流向了少数人手里。同时，他还从早期的资料中发现，在其他的国家，都发现有这种微妙关系一再出现，而且在数学上呈现出一种稳定的关系。于是，帕累托从大量具体的事实中发现：社会上20%的人占有80%的社会财富，即：财富在人口中的分配是不平衡的。

同时，人们还发现生活中存在许多不平衡的现象。因此，二八定律成了这种不平等关系的简称，不管结果是不是恰好为80%和20%（从统计学上来说，精确的80%和20%出现的概率很小）。习惯上，二八定律讨论的是顶端的20%。而非底部的80%。人们所采用的二八定律，是一种量化的实证法，用以计量投入和产出之间可能存在的关系。[5]

2　社交网络中个体价值分析

2.1算法模型

2.1.1PageRank算法介绍

PageRank是Google专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page和Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。

我们将Web做如下抽象：第一将每个网页抽象成一个节点；第二如果一个页面A有链接直接链向B，则存在一条有向边从A到B（多个相同链接不重复计算边）。因此，整个Web被抽象为一张有向图。PageRank算法是基于这样一种背景思想：被用户访问越多的网页更可能质量越高，而用户在浏览网页时主要通过超链接进行页面跳转，因此我们需要通过分析超链接组成的拓扑结构来推算每个网页被访问频率的高低。最简单的，我们可以假设当一个用户停留在某页面时，跳转到页面上每个被链页面的概率是相同的。

总而言之，一个页面的“得票数”由所有链向它的页面的重要性来决定，指向一个页面的超链接相当于给该页投一票。一个页面的PageRank是由所有链向它的页面（“链入页面”）的等级指标经过递归算法得到的。一个有较多链入链接的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。也就是说从许多优质的网页链接过来的网页，必定还是优质网页。

2.1.2PeopleRank算法介绍

基于PageRank的理论，我们以每个微博账户的“关注”为链出链接，“粉丝”为链入链接，我们把这种以人为核心的关系，叫PeopleRank。

1. PeopleRank之二八定律和黄金分割线

本文对数据进行抽象，并且构建图，图中有n个节点，假设起初图中每个节点的权值都是1。统计图中节点的“入度”，按照“入度”从大到小进行排名，遇到“入度”相同的按照“出度”从小到大进行排名，拿到排名最高的20%的节点。这20%的节点按照黄金分割比例进行切分，0.618这部分节点起始权值分别加(1-0.618)*0.8*1/n，(1-0.618)这部分节点的起始权值分别加0.618*0.8*1/n。

2. PeopleRank假设条件：

1）“明星”假设：本文假设“粉丝”数量多的前20%的人为“明星”人员。“明星”就应该产生传递大权值，在迭代计算开始时根据算法，它们会获得较高的权值。

2）数量假设：如果一个用户节点接收到的其他用户“关注”的数量越多，那么这个用户越重要。也就是说他的“粉丝”数量越多，这个用户越重要。

3）质量假设：用户P的“粉丝”质量不同，质量高的“粉丝”，关注用户P，能给用户P传递更多的权重。所以越是质量高的“用户”关注用户P，则用户P越重要。例如：李开复“关注”了用户P，或名人关注了用户P和一个“僵尸”关注了用户P相比，他们质量是不一样的，李开复关注用户P得到的PeopleRank的值越高。

3. 衡量PeopleRank的3个指标：

1）粉丝数，用户P的“粉丝”数量越多，这个用户越重要。

2）粉丝是否有较高PeopleRank值，PeopleRank值也就是一个重要性值。

3）粉丝关注了多少人，也就是关注用户P的人，还关注了其他多少人。因为粉丝关注人的时候要把他的权重进行传递。一个粉丝只关注了一个人，他就将自身的权重百分之百传给这个人，如果这个粉丝关注了n个人，那么他传给每个人的权重就是1/n乘以权重值。

2.1.3PeopleRank算法原理

PeopleRank算法建立在随机冲浪者模型上，其基本思想是：社交网络中主体的重要性排序是由主体间的链接关系所决定的，算法是依靠主体间的链接结构来评价每个主体的等级和重要性，一个主体的PR值不仅考虑指向它的链接主体数，还有指向它的主体本身的重要性。

PeopleRank具有两大特性：第一、PR值的传递性，主体A指向主体B时，A的PR值也部分传递给B。第二、重要性的传递性，一个重要主体比一个不重要主体传递的权重要多。

PeopleRank算法将社交网络看成一个图(Graph)。图的节点是用户，图中的边是用户之间的链接。PeopleRank会计算出用户的重要程度，并且给出排名。

算法计算公式：

上述公式里，p1,p2,p3...pn代表n个不同的用户，M(i)是“关注”pi的所有用户的集合，L(j)是pj用户的粉丝数。d (0

2.2构造算法实例

2.2.1PeopleRank算法模型

以4个节点的数据为例。

1. 起始权值确认：1、2、3、4节点权值分别为1、1、1、1.1236

1）ID=1的节点链向2,3,4节点，所以一个用户从ID=1的节点关注2,3,4的概率各为1/3。

2）ID=2的节点链向3,4节点，所以一个用户从ID=2的节点关注3,4的概率各为1/2。

3）ID=3的节点链向4节点，所以一个用户从ID=3的节点关注4的概率为1。

4）ID=4的节点链向2节点，所以一个用户从ID=4的节点关注2的概率为1.1236。

图1　4个节点图

2. 构造邻接表：

3. 构造邻接矩阵(方阵):

列：源节点

行：目标节点

4. 转换为概率矩阵(转移矩阵)

5. 阻尼系数概率矩阵

增加阻尼系数后，ID=1的节点，就有值了PR(1)=(1-d)/n=(1-0.85)/4=0.0375，即无外链节点的最小值。

6. 实现矩阵的迭代计算

结果说明：

1）ID=1的节点，PR值是最小，因为没有指向ID=1的节点。

2）ID=2的节点，PR值是0.3738930，权重很高，因为1和4都指向2，4权重较高，并且4只有一个链接指向到2，权重传递没有损失。

3）ID=3的节点，PR值是0.2063759，虽有1和2的指向了3，但是1和2还指向的其他节点，权重被分散了，所以ID=3的节点PR并不高。

4）ID=4的节点，PR值是0.3822311，权重最高，因为被1,2,3都指向了。

2.2.2PeopleRank算法实例

1. 测试数据集：weibo.csv

数据集说明：25个用户，66个关系，关注和粉丝的关系。第一列为用户ID，第二列也是用户ID。第一列用户，关注了第二用户。

2. 用R语言构建PeopleRank的算法原型

1）构建邻接矩阵。

2）变换概率矩阵。

3）递归计算矩阵特征值。

4）标准化结果。

5）对结果排序输出。

6）R语言算法模型。

用户18有4个粉丝为别是6,7,10,19（粉丝数）。4个粉丝的PeopleRank排名，是3,5,8,20（粉丝是否有较高PeopleRank值）。粉丝的关注数量，是6,3,2,1（粉丝关注了多少人）。因此，通过对上面3个指标的综合打分，用户18是评分最高的用户。

3　结束语

本文将PageRank模型应用于社交网络，定义以人为核心的个体价值。本文以微博数据为例，基于PageRank模型给微博中每个用户进行行评分。传统的评分规则是，第一简单求和：评分=关注数+粉丝数+微博数，第二加权求和：评分=a*关注数+b*粉丝数+c*微博数。和这两种传统方法相比，基于PageRank的模型评分结果，更符合我们的评分标准了。并且本文用到了大数据分析工具hadoop和spark，能满足对海量数据的计算需求。

今后还有许多后续工作，将在以下方面做进一步的研究：

（1）目前PeopleRank模型只进行了起始节点权值确定。没有对整个迭代过程进行考虑。还可以把黄金分割和二八定律用到迭代过程中，或者通过部分关系明确的数据（相当于一个图中的子图）得到一部分训练集，然后一步一步加入所有数据，直到计算完图中所有节点为止，但是考虑还不是很成熟，是接下来要研究的重点；

（3）本文没有跟踪用户的行为，进行数据分析判断用户的倾向，这将导致对用户的排名不完全符合实际情况。

[1] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters.

[2] S. Brin, L. Page, ‘The Anatomy of a Large-Scale Hypertextual Web Search Engine’.

[3] Wang S, Liu Z, Sun Q, Zou H, Yang F. Towards an accurate evaluation of quality of cloud service in service-oriented cloud computing. Journal of Intelligent Manufacturing, 2014, 25(2): 283-291.

[4] Jon M. Kleinberg, ‘Authoritative sources in a hyperlinked environment’, Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.

[5] (美)克里斯·安德森 译者: 乔江涛. 长尾理论: 中信出版社, 2006年12月

[6] 张振华, 刘瑞芳. 微博社交网络中面向机构的用户挖掘[J].软件, 2013, 34(1): 121-124.

[7] 山名早人, 近藤秀和, 「解说: 搜索引擎Google」(概要), 信息处理42卷8号(2001年8月), pp.775-780.

[8] 赵佳男. 基于社交网络(SNS)的非正式学习模式的研究[J].软件, 2014, 35(4): 175-177, 180.

[9] 刘耀庭: 社会关系网络结构研究[D]. 浙江. 浙江大学, 2008.

[10] 张晨辰， 赵方. 社交网络服务系统核心功能的设计与实现[J]. 软件, 2013, 34(12): 92-98.

[11] 李冠辰. 一个基于hadoop的并行社交网络挖掘系统[J]. 软件, 2013, 34(12): 127-131.

[12] 刘华婷, 郭仁祥, 姜浩. 关联规则挖掘Apriori算法的研究与改进[J]. 计算机应用与软件, 2009(1): 146-149.

[13] 王珊, 王会举, 覃雄派等. 架构大数据: 挑战、现状与展望[J]. 计算机学报, 2011, (10): 1741-1752.

[14] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京:清华大学出版社, 2006.

Analysis of Individual Value in Social Networks

WANG Zhi-bin, HUANG Wei
(Application System Department, North China Institute of Computing Technology, Beijing, China)

The analysis of individual value in the social network is to use the web crawler to grab the data in the social network, to filter the data, to abstract the graph structure, and to find the highest ranking node (individual). This paper is based on PageRank algorithm, using the golden section line method” and the “Pareto Law” and is used in the social network. Based on the definition to the individual value of human as the core, this model can used in the new fields, and it is called “PeopleRank”. In this paper, the complex social network is abstracted into a graph structure, and the nodes in the graph represent the users, and the edges of the graph represent the relationship between the “fans” and“concerns”. Using the “PeopleRank” model, the matrix is constructed, and the matrix is calculated iteratively. Finally, a convergent result is obtained. According to the obtained results, the importance of the individual in the social network can be determined.

SNS (Social Networking Services); Individual values; PeopleRank

TP391

A

10.3969/j.issn.1003-6970.2016.08.026

王志斌(1989-），男，硕士研究生，大数据。

通讯联系人： 黄蔚，研究员级高级工程师，大数据。