2014年《计算机学报》

主要内容：从测量角度对在线社会网络的拓扑结构、用户行为和网络演化等方面进行了综述，总结了常见的测量方法和典型的网络拓扑参数，着重介绍了用户行为特征、用户行为对网络拓扑的影响以及网络的演化。

主要结论：好友少的用户的交流范围集中在小部分好友，而好友多的用户联系的好友更均匀；用户之间的交互减小了在线社会网络的聚类系数，使网络结构更松散；边的生成受优先链接和临近偏倚的共同影响；小社团倾向于和大社团合并，大社团倾向于分裂为两个规模相当的小社团等。

论文简介

出处、上课讲过的，之前基础上拓展（交互）

一、应用

wiki的用户，用户编辑同一个页面；万维网中的页面，通过嵌入的超链接相互连接

互联网上的社会网络统称为社会媒体网络SMN（Social Media Network）

Facebook、Twitter、新浪微博、人人网等社交网站SNS（Social Network Site）

社交网站强调用户的直接参与，用户可以建立单向或者双向的好友关系，

基于SNS而形成的用户网络或是真实社会网络的虚拟映射，或是互联网用户自发形成的在线网络．这个网络不再像 wiki一样需要通过进一步抽象而构成用户之间的连接，而是存在用户之间的直接交互。

社交网站用户构成的社会媒体网络称为在线社会网络，或在线社交网络OSN（Online Social Network）

在线社会网络的测量与分析是指通过采集、整理OSN的原始数据，利用复杂网络、社会网络和数据挖掘的理论方法和技术，挖掘和提取OSN的结构特征和用户行为特性。

二、在线社会网络的测量方法

简要介绍一些典型的数据集，总结３种常用的测量方法。

1、典型的社会网络数据集

①加州大学欧文分校（University of California，Irvine.UCI）网络组，关于Facebook的测量数据：http://odysseas.calit2.uci.edu/wiki/doku.php/public:online_social_networks/

②Twitter的测量数据：http://twitter.mpi-sws.org/

③斯坦福大学网络分析项目组（Stanford Network Analysis Project，SNAP）：http://snap.stanford.edu/

SNAP收集了大约５０个大型网络的数据，这些网络的规模（节点数和边数）从数万到几千万不等：

2、常见的测量方法

OSN的主动测量方法主要有以下几种：网络爬虫、抓取数据包、采集日志。

（1）网络爬虫

①以图遍历的方式，以用户为中心，以好友关系为线索遍历好友关系网．虽然这种方法的逻辑结构简单，但其工作量大、数据形式单一、局限性较大．采集的数据往往是静态的，无法用来分析OSN的动态行为。

②通过API采集（调用）用户数据，这些数据较简洁，也会包含一些动态信息，但数据获取范围仍受API本身的限制

（2）抓取数据包

通过在网关抓取（HTTP）数据包、解 析包头，可以获得丰富的实时信息。但是必须得到ISP或网络运营机构的支持，解析包的工作也非常繁琐，对于认识 OSN 的拓扑特征较局限。

一些常用的包分析工具有Wireshark、Sniffer Pro、Bro IDS。

网络爬虫和抓包是互补的测量方法，分别呈现了OSN 的静态和动态特征。

（3）采集日志

较便捷的测量方法，但是需要得到SNS服务商的协助，由他们直接提供原始日志。

微博API：https://open.weibo.com/wiki/%E5%BE%AE%E5%8D%9AAPI

社交网络聚合器（Social network aggregation）：同时采集多个SNS的用户数据，用户可在该网站同时登陆多个 SNS帐号，这种混合数据便于对不同OSN进行比较。

例如：Hootsuite，Taggbox和FriendFeed

http://en.wikipedia.org/wiki/Social_network_analysis_software/

三、常见的社会网络分析工具

社会网络分析SNA （Social Network Analysis）软件，以邻接表或邻接矩阵的方式输入原始网络，可以计算简单的网络拓扑参数，如聚类系数、度分布等，也可以直观地展示网络结构。一些SNA软件可以进行预测分析，包括：①基于连接等网络现象预测个人层面的输出（称为同伴影响或传染建模）；②基于个人层面的现象预测连接或三元组的形成等网络输出（称为同质性模型）；③基于网络现象预测其它网络现象，比如根据0时刻某一个三元组的形成预测1时刻某个连接的形成。

SNA软件通常包括基于图形用户接口（Graphical User Interfaces，GUIs）的包或为编程语言设计的API．常见的 GUI包 有NetMiner、UCINet、Pajek、GUESS、ORA和Cytoscape。商业用户的GUI包有Orgnet、Keyhubs和KXEN。其它SNA平台，比如IdiroSNAPlus，定位于电信和在线游戏等有大规模数据分析需求的企业。

常见的 SNA脚本工具有 NetMiner（python）、statnet组件包（R）、igraph（R与python）、Networkx库（python）以及c++中大规模网络分析的SNAP包。

微软开发的NodeXL是一款基于Microsoft Office Excel的社会网络分析工具，容易上手，功能较强大。

常见的SNA软件

四、在线社会网络的拓扑结构

*****怎样把现象转变为定量的描述*********

第四部分重要内容：OSN的拓扑结构和用户行为对网络拓扑的影响

①OSN是小世界网络，具有较短的平均路径长度和较大的聚类系数。

②OSN是无标度网络，度分布呈幂律形式。

③大部分OSN是同配网络，度较大的节点倾向于与度较大的节点相连。OSN中有一些紧密连接的度较大的节点，他们把整个网络连接起来，度较小的节点分布在网络边缘。

④OSN用户的好友关系并 不代表他们之间活跃的交互，好友关系网中存在大量的静默边和非活跃用户。用户的不可见行为（如浏览网页）减小了网络的聚类系数，使网络结构变得松散，也增加了平均路径长度，使网络的连接性能变差。

⑤OSN用户的交互行为具有相互性。好友少的用户其交流对象集中在少部分好友，而好友多的用户联系的好友更多更均匀。

⑥OSN中的传递模体占很大比例，广播性和汇聚型模体也占较大比例。

1、静态拓扑结构

首先介绍一些常见的拓扑参数，然后总结OSN 在这些参数上的额表现，最后考察用户的交互行为对OSN拓扑结构的影响。

（1）平均路径长度

网络具有小世界性。如果对于固定的节点点平均度<k>，平均路径长度L的增加速度至多与网络规模N的对数成正比，即。

与web相比，OSN的平均路径长度和直径都很短。

（2）聚集系数

在好友关系网中，一个人的好友很可能彼此也是好友，这就是网络的聚类特征。

好友关系网是无权网络，带权网络的聚类系数公式为

把OSN的聚类系数与用不同算法（参考文献27、28中，幂律随机图）生成的网络聚类系数进行对比，发现OSN的聚类系数远大于理论模型的聚类系数。说明在OSN中 ，人们更喜欢通过共同好友相互认识。

此外，对于小出度的节点，其聚类系数更高，说明：拥有较少好友的用户紧密的链接在一起。

如果一个网络有较短的平均路径长度和较高的聚类系数，则其为小世界网络，所以OSN是典型的小世界网络。

（3）对称性与度分布

OSN的拓扑结构具有对称性symmetry。对称性是指一个有向图中，边的方向是双向的。例如在YouTube中，有79.1%的好友关系是双向的。这说明用户之间倾向于相互关注。这种对称性与线下社会网络中的情形类似。

完全随机网络的度分布近似为Poisson分布，其形状在远离峰值<k>处呈指数下降，这类网络也成为均匀网络（homogeneous network）。

（4）同配性

大多数情况下，OSN的同配系数r都大于0，比如人人网的同配系数为0.15，Facebook为0.17，Flickr为0.202，LiveJournal为0.179，这一特征把OSN从其他幂律网络中区别开来。Web和Internet的同配系数都小于0，分别为-0.067和-0.189。但这并不表示所有OSN都是同配的。

无标度性质和同配性说明OSN中有一些紧密连接的度较大的核心，它们把整个网络连接起来，度较小的节点分布在网络的边缘。

与同配系数相似的另一个参数是平均邻居连接数。当节点度大于100时，人人网用户的与节点度之间呈正相关性，即度较大的节点倾向于与度较大的节点连接，这与OSN的同配性一致。

（5）k-核与核数

同配性使OSN形成了一个“核心”：核心在网络连接中起重要作用，移去核心，网络会变得支离破碎；核心的直径很小，用k-核描述核心。

用在web使用过的图分析方法，挖掘OSN中的核心，

SCC指网络中的最大连通子图，当移去10%度较大的节点时，网络会分裂成上百万个非常小的SCC，所以网络是由这10%的核心节点连接而成。此结论的另一个证据是：随着移去度较大的节点，网络的平均路径长度回逐渐增加。

2、用户之间的动态交互对拓扑结构的影响

问题：用户之间建立好友关系之后，是否经常联系呢？很有可能A与B建立好友关系之后少有联系，但C和D虽然不是好友却经常交流．因此有必要研究用户的交互行为对网络拓扑结构的影响。

本文把所有基于用户交互行为而非好友关系建立起来的网络统称为活动网络，其拓扑结构称为活动拓扑结构。

定义活动网络，如果节点i到j的一条有向边表示i对j的一个行为（eg留言），有向边的权值表示该行为的强度。活动网络不是好友关系网的子集，因为非好友的用户之间仍可以交互。对研究信息在OSN中的传播更有意义。

（1）活动拓扑与静态拓扑的比较

以用户之间的留言为实例研究活动网络：虽然互动网络是有向、甲醛的网络，但其与好友关系网的结构特征相似。eg：活动网络中节点的入度、出度分布都呈幂律形式，且二者分布相似。

当仅考虑对称边时，活动网络比好友关系网更具同配性

①以用户之间的留言为实例研究活动网络：虽然互动网络是有向、甲醛的网络，但其与好友关系网的结构特征相似。eg：活动网络中节点的入度、出度分布都呈幂律形式，且二者分布相似。

以Cyworld（赛我网是韩国最大的社区网站）为例，当节点度k大于等于500时，knn呈发散趋势，且好友关系网更发散；当k小于等于30时，网络呈异配性；当时网络呈同配性。这说明网络中度较小的节点与度较大的节点之间是非对称的。大量节点都去关注“名人”节点，产生所谓的“名人效应”（celebrity effect）。特别对于微博等以弱关系尾注的社会网络，名人效应更明显。

③活动网络和好友关系网的k-核，有明显差别。活动网络和好友关系网的knn曲线在k<34时变化趋势相同，之后活动网络的k-核节点数下降的比好友关系网快。说明好友关系王忠含有不活跃（不联系）的边，而这些边把网络核心连接起来。

若好友留言是显式交互，则浏览页面是隐式的交互方式。根据人人用户访问记录，若定义访问他人主页次数为该用户的消费，则1％最流行的用户与1％消费最多的用户有9％的重叠，说明在人人网中有一部分非常流行且活跃的用户。一个有意思的现象是，陌生用户与好友访问个人主页的情况（累积分布）类似，这说明了隐式交互的重要性，因此仅考察好友关系网是不够的，陌生用户在OSN的构成中也非常重要。

以用户为节点，用户之间的浏览关系为有向边同样可以构造活动网络（隐式交互图），则这个活动网络与好友关系网的异同如下：

①度分布

隐式交互图的边数（240408）大于显式交互图（27347），隐式和显式交互图的边数都明显小于好友关系网（753279）．这说明人人网中有大量的不活跃用户，他们不浏览其他人的页面，也不与他人交互。尽管有这些不同，隐式交互图的度分布仍然呈幂律分布（入向幂指数为3.5，出向为3.39）

②聚类系数

由于人人网中有很多静默边的存在，隐式0.03和显式0.05交互图的聚类系数都小于好友关系网0.18。移除这些边导致邻居节点间的连接松弛，所以显式交互图比好友关系图小。因为很多陌生用户的访问使隐式交互图更加松散，聚类系数最小。

③同配性

由于很多用户访问流行用户，所以隐式交互图是异配的，r=-0.06；而好友关系图r=0.23和显式交互图r=0.05都有同配性。

这反驳先前关于活动网络比好友关系网更具同配性的说法。

④平均路径长度

隐式交互图的平均路径长度4.02介于显式交互图5.43和好友关系网3.64之间。由于平均节点度和度较大的节点数减少，整个网络的连接性能变差，中得到之隐式和显式交互图的平均路径长度增加。

（2）活动拓扑特征

①相互性reciprocity

把一堆用户之间的交互次数画成点状图，作图为用户间发消息与收消息的情况，取中值和对数后得到右图。

从图中可以看出明显的对称性，右图可以很好的用x=y来拟合。

相互性分为三类：相对的relative、绝对的absolute、定性的qualitative。因此活动网络中的相互性接近于绝对相互性。推测：绝对的相互性源于个体之间无差别的交互能力，在Cyworld中体现为用户可以无障碍的浏览他人的页面。

②差异性disparity

考察一个用户的交互对象在其好友上的分布。一个用户的好友数越少，他对待好友越平等，；反之，由于精力有限，他无法均匀地与所有好友交互。用户i的活动在其好友上的分布为

k为出度，kin为入度。Y（k）为所有出度为k的节点的Y（k,i）的平均值。如果一个节点的出向包的权值与其入向边的权值是可比的，则kY（k）~1；如果一个节点大部分的交互都位于一条出向边或入向边，则kY(k)~k。

k<=500时，kY(k)~k；当k>500时，kY(k)开始发散；当k达到1000时，kY(k)降为1，说明kY（k）~1。说明，一个好友数量少的用户，倾向于与少部分好友交互，而好友数量多（大于1000）的用户联系的好友更多而且更均匀。——与直观感觉相悖。

③网络模体（network motifs）

网络模体是指3个人之间13种可能的交互模式，或称为三元组重要性剖面。

一种基于网络模体的网络分类方法：一本思想：计算网络中13种网络模体的比例，并与其对应的随机化网络相比较，根据比较结果对网络进行分类。模体i的Z分数（Z-score）表示它在网络中所占的比例，定义为：

用模体探测工具FANMOD对Cyworld好友关系网进行模体分析：

分析结果：传递模体（9、10、12、13）所占的比例很大，而非传递模体（4、5、6）很少出现在Cyworld中。这些结果与其他社会网络的结果一致，模体1和模体2的正规化Z-score与我们期望的不同：

模体1是广播型（非传递），对应垃圾信息传播者spammer，一个用户给两个互补相识的人发消息，而没有得到回复；模体2是汇聚型（非传递），对应权威或者名人，两个互不相识的用户给一个用户发消息而没有得到回复。

我们可以根据TSP对网络进行分类，具有相似TSP的网络组成一个网络超家族superfamily。有人把19个不同类型的网络分成了4个超家族。这些研究表明，相同类型的网络不仅具有相同的网络模体，而且各个模体在网络中也具有相似的相对重要性。另外，一个网络超家族中可能包含规模差异很大、功能极其不同的网络。

TSP问题就是在一城市集合{A,B,C,…}中找出一个最短且经过每个城市各一次并回到起点的路径。（TSP旅行商问题）

最后要有思考