SEO外包平台,我们为您提供专业的企业网站SEO整站优化外包服务 SEO设置

SEO外包平台

专注于企业网站SEO整站优化外包服务

【论文阅读】在线社会网络的测量与分析

作者:jcmp      发布时间:2021-05-11      浏览量:0
2014年《计算机学报》主要内容:从测量

2014年《计算机学报》

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

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

论文简介

出处、上课讲过的,之前基础上拓展(交互)

一、应用

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

互联网上的社会网络统称为社会媒体网络SMN(Social Media Network)。

Facebook、Twitter、新浪微博、人人网等社交网站SNS(Social Network Site)。

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

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

社交网站用户构成的社会媒体网络称为在线社会网络,或在线社交网络OSN(Online Social Network)。

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

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

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

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收集了大约50个大型网络的数据,这些网络的规模(节点数和边数)从数万到几千万不等:

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的社会网络分析工具,容易上手,功能较强大。

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

1、静态拓扑结构

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

(1)平均路径长度

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

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

(2)聚集系数

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

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

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

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

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

(3)对称性与度分布

完全随机网络的度分布近似为Poisson分布,其形状在远离峰值处呈指数下降,这类网络也成为均匀网络(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:活动网络中节点的入度、出度分布都呈幂律形式,且二者分布相似。

③活动网络和好友关系网的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个超家族。这些研究表明,相同类型的网络不仅具有相同的网络模体,而且各个模体在网络中也具有相似的相对重要性。另外,一个网络超家族中可能包含规模差异很大、功能极其不同的网络。

最后要有思考