Microsoft Word - xb 陈兴蜀.doc

Size: px

Start display at page:

Download "Microsoft Word - xb1506-23 陈兴蜀.doc"

瑕侑夏
7 years ago
Views:

1 第 44 卷第 6 期电子科技大学学报 Vol.44 No.6 15 年 11 月 Journal of Unversty of Electronc Scence and Technology of Chna Nov. 15 面向人人网的用户信息采集及拓扑结构测量研究陈兴蜀, 尹雅丽, 李卫, 王文贤, 王海舟 ( 四川大学计算机学院成都 665) 摘要以人人网为例, 研究社交网站数据采集技术, 并对其网络拓扑结构进行详细研究结果表明 :1) 人人网的分布不同于一般社交网络符合的幂律分布, 更倾向于具有指数分布特征, 且其度分布具有一定的重尾特性, 在小范围内出现了类似小变量饱和现象, 并且出现双峰现象 ;) 人人网符合小世界特性 ;3) 人人网具有同配性, 高的节点倾向于与高度节点连接 ;4) 用户状态数照片数和访客数没有明显的正相关特性研究成果对于进一步了解社交网络的拓扑结构特征具有重要意义, 为后续实现资源监管跨社交网站的数据挖掘奠定了基础关键词主动测量 ; 聚集系数 ; 网络拓扑结构 ; 小世界网络中图分类号 TP393.8 文献标志码 A do:1.3969/j.ssn Measurement Study of Topologes Characterstcs for Renren Socal Networkng System CHEN Xng-shu, YIN Ya-l, LI We, WANG Wen-an, and WANG Ha-zhou (College of Computer, Schuan Unversty Chengdu 665) Abstract In ths paper, takng as Renren for eample, the socal networkng ste s data collecton technology s studed. The collected data s used to study Renren s topologcal structure. The results show that, 1) dfferent from general socal networks power-law dstrbuton, the node degree dstrbuton of Renren tends to follow an eponental dstrbuton; Renren s degree dstrbuton has some heavy-taled feature, and there s a saturaton phenomenon of small varables on a small scale; t also presents the double peak phenomenon; ) Renren has a smaller average shortest path length and a larger clusterng coeffcent, whch means the small world characterstcs; 3) Renren shows the assortatvty, whch means the node wth hgh degrees s nclned to connecton to the nodes wth hgh degree; 4) No obvous postve correlaton s found n status number, photos number and the vstors number of Renren users. The results are of great sgnfcance for the further understandng of the Renren and other socal networks topology structure, and they wll lay a foundaton for resources supervson and cross-socal network ste s data mnng. Key words actve measurement; clusterng coeffcent; network topology; small-world networks 随着互联网技术的快速发展, 以新浪微博腾讯 QQ 空间人人网等为代表的社交网络发展壮大, 吸引着越来越多的用户但是由于这一类自媒体普泛化传播快等特点, 使得一些不法分子有机可乘, 利用社交网络发布不良信息, 对网民造成不良的引导作用其中以人人网为代表的社交网站具有以下特点 :1) 用户群虽然在近年来扩展到每一个人, 但是主要用户仍为大学生, 由于这类群体的特殊性, 容易被不法分子利用 ;) 具有传播快用户多等特点 ;3) 现有的社交网站只有针对浏览对象 ( 包括隐私设置访问浏览权限 ) 的安全设置, 没有针对内容安全的审查机制因此对发布信息的采集以及其合法性检测对于舆情监控和信息安全等都具有十分重要的意义本文以人人网为例, 分析其网站结构特点, 研究社交网站的数据采集技术, 以网络爬虫为基础, 通过设计主题网络爬虫, 实现对特定网页的定向抓取, 用正则表达式匹配出所需信息, 存入数据库, 用于后续分析, 进而实现对网站的监管本文实现了人人网数据采集系统, 并分析了人人网的网络拓扑结构目前, 国内外针对社交网站的研究主要集中在社交网络的拓扑分析 [1] 用户行为特征分析 [-3] 社交网络中的信息传播安全隐私问题网络拓扑演化模型 [4] 用户影响力度量以及社交网络盈利模式收稿日期 : ; 修回日期 : 基金项目 : 国家科技支撑计划 (1BAH18B5); 国家自然科学基金 (617447) 作者简介 : 陈兴蜀 (1969 ), 女, 教授, 博士生导师, 主要从事信息安全云计算安全等方面的研究.

布不同于一般社交网络符合的幂律分布, 更倾向于具有指数分布特征, 且其度分布具有一定的重尾特性, 在小范围内出现了类似小变量饱和现象, 并且出现双峰现象 ;) 人人网符合小世界特性 ;3) 人人网具有同配性, 高的节点倾向于与

2 第 6 期陈兴蜀, 等 : 面向人人网的用户信息采集及拓扑结构测量研究 99 研究等方面文献 [5] 从测量角度对在线社会网络的拓扑结构用户行为和网络演化等方面进行了综述, 总结了常见的测量方法和典型的网络拓扑参数, 着重介绍了用户行为特征用户行为对网络拓扑的影响以及网络的演化文献 [] 基于人人网用户主页的行为记录数据, 对个体行为和群体互动行为的时间统计特性进行实证研究 ; 并针对人人网群体互动行为设计了社交驱动系数影响下的兴趣驱动模型文献 [3] 分析社交网络中的用户行为, 总结出了 SNS 中的用户行为图谱, 研究了社交网络中的用户影响力模型文献 [6] 把 OSN 的聚类系数与用不同算法生成的网络聚类系数进行对比, 发现 OSN 的聚类系数要远大于理论模型的聚类系数文献 [7] 通过对 Facebook 的用户交互, 提出社会关系加强模型来量化人际关系指标相比以上的研究工作, 本文采用申请应用的方式获得了人人网提供的 API, 通过调用 API 接口快速高效地获取用户的完整的好友关系, 该方法能有效解决通用网络爬虫抓取信息时存在的数据采集不完整等问题基于采集的数据, 对人人网网络拓扑结构进行详细研究, 包括了人人网网络拓扑的聚集系数同配系数平均最短路径长度平均度和度分布和小世界特性本文的研究成果对进一步分析社交网络的用户行为网络拓扑结构具有重要意义, 为跨社交网站的数据挖掘研究奠定了良好基础 1 人人网数据采集系统通过对人人网网站结构分析, 发现该网站用户个人资料 ( 包括基本信息学校信息联系方式 ), 用户好友关系及用户状态等数据具有重要价值而获取这些信息首先需要用户 ID, 然后根据 ID 采集每个用户的信息其次, 针对话题, 一般以话题标题的小写字母表示, 并作为该话题的唯一标识, 因此采集前需要采集话题的名字, 然后根据该名字 ( 话题 ID) 采集该话题的具体内容和评论该系统由用户 ID 和用户好友关系采集模块用户个人资料和状态采集模块话题 ID 采集模块话题评论内容采集模块和数据存储模块 5 部分组成用户行为分析.1 用户主页信息统计分析本文统计了两个数据集的好友数和访客数的关系, 数据集 1(data1): 目前采集到的所有数据中好友数在 1~1 的个用户 ; 数据集 (data): 不限制好友数的个用户统计其好友数和访客数的关系, 数据集的统计结果如图 1 所示访客数好友数图 1 用户好友数和访客数关系从图 1 可以看出用户好友数在 ~ 5 时, 访客数主要集中在 1 以下, 当用户好友数大于 5 时, 访客数分布无特定规律数据集 1 的统计结果和图 1 类似, 该数据集主要用于与文献 [] 的测量结果进行对比分析图 1 可知, 用户好友数和访客数没有明显的正相关特性, 而文献 [] 通过统计 7 个好友数在 1~1 的用户的好友数和访客数的关系, 发现其存在一定的正相关特性本文得出的结论与文献 [] 不同, 可能的原因是文献 [] 的数据集太小, 导致得到了完全不同的相关特征另外, 对用户状态数照片数和访客数也进行了统计, 发现统计结果都集中在一个范围内, 没有如文献 [] 所显示的明显的正相关特性. 用户行为特征分析对爬取的个用户 ID 进行统计, 其中由于用户设置了权限, 或者账号已被注销等因素无法获取主页数据有的 ID 有 1 88 个, 占总用户的.954% 采集用户个人资料时, 对 5 61 个数据集进行统计, 发现填写了个人资料的用户只有 37 个, 只占总数的 4.3%, 说明大多数用户不愿意公开自己的隐私信息, 而这部分信息恰好是利用价值最高的, 对于这部分数据, 人人网可以采取一定的激励机制, 促使用户完善信息, 用户个人资料的完整性是后续数据挖掘中的关键 3 网络拓扑结构分析 3.1 和度分布是指与该节点相关联的边的条数 [4] 在现实网络中, 两种分布比较常见 : 一种是指数分布, 另一种是幂律分布 [1] 人人网中是指某一用户的好友个数为描述人人网的度

模型文献 [3] 分析社交网络中的用户行为, 总结出了 SNS 中的用户行为图谱, 研究了社交网络中的用户影响力模型文献 [6] 把 OSN 的聚类系数与用不同算法生成的网络聚类系数进行对比, 发现 OSN 的聚类系数要远大于理论模型的聚

3 93 电子科技大学学报第 44 卷分布, 本文使用和幂律函数对几组数据集进行拟合拟合函数为 : b y = a (1) t1 t t3 1 3 y = Ae + A e + Ae + y () 式中, 式 (1) 为, 式 () 为对 4 组数据 ( 分别含有个节点个节点个节点和 85 1 个节点 ) 进行拟合, 选取其中两组拟合结果如图图 3 所示分布 a. 线性坐标分布分布 4 6 a. 线性坐标分布 1 1 b. 双对数坐标图个节点的度分布图对 4 组数据进行和拟合得到的参数分别如表 1 表所示表 1 拟合效果和参数表 b. 双对数坐标图个节点的度分布图数据组别 b 参数值 ( y = a ) R a b data data data data 数据组别表拟合效果和参数表 t1 参数值 ( y = Ae t + Ae t3 + Ae + y ) 1 3 R y A t 1 1 A t A t 3 3 data data data data 由表 1 表可以看出 : 对数据进行拟合得到的拟合优度分别为 : ; 对数据进行拟合得到的拟合优度分别为 : 从两个表的数据可以看出, 随着节点数的增多, 拟合优度值 R 有增长的趋势但是数据经过拟

双对数坐标图 3 85 1 个节点的度分布图对 4 组数据进行和拟合得到的参数分别如表 1 表所示表 1 拟合效果和参数表 1 1 1 b. 双对数坐标图 57 733 个节点的度分布图数据组别 b 参数值 ( y = a ) R a b data1-1 31 746.

4 第 6 期陈兴蜀, 等 : 面向人人网的用户信息采集及拓扑结构测量研究 931 合得到的拟合优度在.9 附近, 最高的也只有.94 ; 而经过拟合得到的拟合优度 R 都大于.9, 且随着节点数的增多, 越接近 1 说明人人网的分布符合幂律分布的程度比较低, 它更倾向于符合指数分布, 且呈指数衰减趋势从图中可以看出, 在双对数坐标系下, 人人网分布具有幂律分布的重尾特征, 但是幂律分布的程度比较低且图中出现了类似小变量饱和现象, 即网络中较小强度节点的强度分布是接近饱和的并且在小范围内形成了类似文献 [4,8] 所发现的双峰现象文献 [8] 提出, 这种新的多峰分布对网络可靠性有一定的影响, 更统一的连接分布可能会保存网络处理随机节点故障的能力, 减少对高度连接节点的依赖性 3. 聚集系数集聚系数 (clusterng coeffcent) 用于描述一个节点邻居之间的相互连接的紧密程度, 即网络的集团化程度, 是网络拓扑的另一个重要参数 [4] 节点的簇系数 c 描述的是网络中与该节点直接相连的节点之间的连接关系, 即与该节点直接相邻的节点间实际存在的边数目占最大可能存在的边数的比例, C e 的表达式为 C =, 式中 k 表示节点的度, k ( k 1) e 表示节点的邻接点之间实际存在的边数, 网络的聚集系数 C 为所有节点聚集系数的算术平均值, 计算公式为 [1] : 不同网络人人网 ER 网络 1 N C N = 1 C = (3) 参数表 4 小世界特性对照表式中, N 为网络节点数对人人网的聚集系数进行计算, 得到表 3 所示的结果, 节点数的聚集系数分别为 : 可以看出, 随着数据集的增大, 聚集系数有降低的趋势, 但是整体水平仍然比较高文献 [9] 指出, 网络同时具有较小的平均路径长度和较大的集聚系数, 这类网络称为小世界网络因此, 聚集系数也是体现小世界特性的一个参数表 3 人人网用户平均最短路径长和聚集系数比较数据集边数平均最短路径长聚集系数 data data data data data 小世界特性小世界特性是指一个网络如果它具有较短的平均路径长度 ( 有文献指出同时具有较大聚集系数 [9] ), 那么这个网络称为小世界网络 [1] 平均最短路径长度是指网络中所有节点对之间最短路径的平均值, 通常以节点间的跳数作为度量来计算, 平均最短路径长度的计算公式为 [4] : 1 l = dj N( N 1) (4) j 式中,N 为网络中 ; d j 为节点和节点 j 之间的最短路径长度对人人网的几组数据的平均最短路径长度进行计算, 得到表 3 所示结果聚集系数平均最短路径边数聚集系数平均最短路径边数表 3 分别代表由个节点的平均最短路径长度和聚集系数, 其中平均最短路径长度分别为 : , 最大为 7, 最小为由上述结果可看出, 随着节点数的增多, 平均最短路径长有升高的趋势, 但是最高也在 6~7 左右, 说明人人网在一定范围内符合六度分隔理论, 且数据集越大, 越接近真实水平表 4 表示在相同节点数和平均顶点度的情况下随机网络 (ER: random network) 和人人网的聚集系数平均最短路径长和边数对照情况由表 4 中数据可以看出, 同样情况下, 人人网和随机网络 (ER) 的平均最短路径长差别不大, 但是人人网的聚集系数要远远大于随机网络的聚集系数由此说明, 人人网具有较小平均最短路径长和较大聚

且图中出现了类似小变量饱和现象, 即网络中较小强度节点的强度分布是接近饱和的并且在小范围内形成了类似文献 [4,8] 所发现的双峰现象文献 [8] 提出, 这种新的多峰分布对网络可靠性有一定的影响, 更统一的连接分布可能会

5 93 电子科技大学学报第 44 卷集系数, 人人网符合小世界特性另外, 从边数增长的速度来看, 随着节点数的增多, 边数增长越来越缓慢, 说明人人网中用户呈一定的社团化社团化是指一组节点, 这组节点构成一个连通子图, 它们之间的连接要密于它们与外界节点的连接 [5] 即用户更倾向于与一个范围内的人联系, 而范围之间联系就不那么密切 3.4 同配性无标度性质和同配性说明社交网络中有一些紧密连接的度较大的核心, 它们把整个网络连接起来, 度较小的节点分布在网络的边缘 [5] 分析网络的同配性, 对于揭示网络自身组织结构与形成机制有着重要意义, 也可以进一步量化社交网络的度相关性同配性的计算公式为 : M jk M ( j + k ) r = (5) M ( j + k ) M ( j + k) 式中, j 和 k 分别为第条边的两个端点的度, = 1,,, M,M 为网络边数 ; 1 r 1 该系数描述网络中的节点和与其度相同的节点连接的倾向性 ; 若 r >, 网络是同配的 (assortatve), 表示节点倾向于和与其度相同的节点连接 ; 若 r <, 网络是异配的 (dsassortatve), 表示节点倾向于和与其度相异的节点连接文献 [11] 测得人人网同配系数为.15 本文通过 4 组数据集计算人人网的同配系数, 结果如表 5 所示表 5 同配系数数据集节点数同配系数 data data data data 由表 5 结果可以看出, 人人网同配系数 r >, 最大为.833 3, 最小为.541 9, 说明人人网是同配的也从另一个方面反映了人人网的无尺度特性随着数据集越大, 同配系数有减小的趋势, 但是越来越接近真实水平 4 总结本文分析了从网网站特点, 探索了用户模拟登陆过程, 为了解决好友关系获取的完整性, 通过调用人人网 API 的方式获得完整好友关系 ; 设计并实现了数据采集系统, 采集用户主页数据好友关系用户状态个人资料话题 ID 和话题评论详细研究了网络拓扑结构, 包括人人网网络拓扑的聚集系数同配系数平均最短路径长度平均度和度分布以及小世界特性得出以下结论 : 1) 人人网分布不同于一般社交网络服从幂律分布, 而是更符合指数分布特点 ; 且出现了类似小变量饱和现象, 并且在小范围内形成了双峰现象 ; ) 人人网具有较小的平均最短路径长和较大的聚集系数, 符合小世界特性 ; 3) 计算得出人人网同配系数大于, 说明人人网具有同配性, 高的节点倾向于与高度节点连接 ; 4) 通过分析人人网用户主页信息, 发现其用户状态数照片数和访客数主要集中在一个范围内, 没有明显的正相关特性本文的研究成果对进一步分析社交网络的用户行为网络拓扑结构具有重要意义, 为跨社交网站的数据挖掘研究奠定了良好基础后续的工作主要包括 : 首先, 针对采集的大量数据, 进行文本分析, 挖掘关于用户信息的一些更深层的东西, 如可以根据人人网用户信息的真实性和用户群的特殊性研究用户的专业和用户行为的特点, 实现跨社交网站的数据挖掘 ; 其次, 可对该采集系统进行扩展, 通过设置配置参数来实现针对不同社交网站的信息定向抓取, 提高其通用性参考文献 [1] 陈兴蜀, 郝正鸿, 王海舟, 等. PP 网络电视拓扑测量方法研究与特性分析 [J]. 四川大学学报 : 工程科学版, 1, 44(3): CHEN Xng-shu, HAO Zheng-hong, WANG Ha-zhou, et al. Measurng and characterzng topologes of PP IPTV[J]. Journal of SChuan Unversty (Engneerng Scence Edton), 1, 44(3): [] 尤婷. 社交网站用户行为特征及其内在机制研究以人人网为例 [D]. 北京 : 北京邮电大学, 1. YOU Tng. The research on socal-networkng users behavor characterstcs and nteror mechansm: Take renren.com for eample[d]. Bejng: Unversty of Posts and Telecommuncatons, 1. [3] 邓夏伟. 基于社交网络的用户行为研究用户行为分析与用户影响力建模 [D]. 北京 : 北京交通大学, 1. DENG Xa-we. User behavor analyss based on socal network servce-user behavor analyss and user nfluence modelng[d]. Bejng: Bejng Jao tong Unversty, 1.

4 同配性无标度性质和同配性说明社交网络中有一些紧密连接的度较大的核心, 它们把整个网络连接起来, 度较小的节点分布在网络的边缘 [5] 分析网络的同配性, 对于揭示网络自身组织结构与形成机制有着重要意义, 也可以进一步

6 第 6 期陈兴蜀, 等 : 面向人人网的用户信息采集及拓扑结构测量研究 933 [4] 姜志宏. 大规模 PPTV 系统测量与建模研究 [D]. 长沙 : 国防科学技术大学, 11. JIANG Zh-hong. Research on modelng and measurement of large scale PP TV systems[d]. Changsha: Natonal Unversty of Defense Technology, 11. [5] 徐恪, 张赛, 陈昊, 等. 在线社会网络的测量与分析 [J]. 计算机学报, 14, 37(1): XU Ke, ZHANG Sa, CHEN Hao, et al. Measurement and analyss of onlne socal networks[j]. Chnese Journal of Computers, 14, 37(1): [6] MISLOVE A, MARCON M, GUMMADI K P, et al. Measurement and analyss of onlne socal networks[c]// Proceedngs of the 7th ACM SIGCOMM conference on Internet measurement. [s.l.]: ACM, 7: 9-4. [7] WILSON C, BOE B, SALA A, et al. User nteractons n socal networks and ther mplcatons[c]//proceedngs of the 4th ACM European Conference on Computer Systems. [s.l.]: ACM, 9: [8] MATEI R, IAMNITCHI A, FOSTER I. Mappng the Gnutella network[j]. Internet Computng,, 6(1): [9] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用 [M]. 北京 : 清华大学出版社有限公司, 6. WANG Xao-fan, LI Xang, CHEN Guan-rong. Comple networks theory and ts applcaton[m]. Bejng: Tsnghua unversty press co, LTD, 6. [1] NEWMAN, MARK E J. The structure and functon of comple networks[j]. SIAM Revew, 3, 45(): [11] JIANG J, WILSON C, WANG X, et al. Understandng latent nteractons n onlne socal networks[j]. ACM Transactons on the Web (TWEB), 13, 7(4): 18. 编辑蒋晓 ( 上接第 9 页 ) [1] KABBUR S, HAN E H, KARYPIS G. Content-based methods for predctng web-ste demographc attrbutes [C]//1 IEEE 1th Internatonal Conference on Data Mnng (ICDM). Sydney: IEEE Press, 1: [11] BREESE J S, HECKERMAN D, KADIE C. Emprcal analyss of predctve algorthms for collaboratve flterng[c]//proceedngs of the Fourteenth Conference on Uncertanty n Artfcal Intellgence. San Francsco: Morgan Kaufmann Publshers Inc, 1998: [1] SU X, KHOSHGOFTAAR T M. A survey of collaboratve flterng technques[eb/ol]. [ ]. hndaw.com/journals/aa/9/ [13] SARWAR B, KARYPIS G, KONSTAN J, et al. Applcaton of dmensonalty reducton n recommender system-a case study[r]. Mnneapols: Dept of Computer Scence Unv of Mnnesota,. [14] KOREN Y. Factorzaton meets the neghborhood: a multfaceted collaboratve flterng model[c]//proceedngs of the 14th ACM SIGKDD Internatonal Conference on Knowledge Dscovery and Data Mnng. New York: ACM Press, 8: [15] PRYOR M H. The effects of sngular value decomposton on collaboratve flterng[r]. Hanover: Dartmouth College, [16] GOLUB G H, VAN LOAN C F. Matr computatons[m]. Maryland: Johns Hopkns Unversty Press, 1. [17] JOACHIMS T. Makng large scale SVM learnng practcal[r]. Dortmund: Unverstat Dortmund,1999. [18] LECHEVALLIER Y, SAPORTA G. Blum MGB choosng the summary statstcs and the acceptance rate n appromate Bayesan computaton[c]//proceedngs of Computatonal Statstcs. Herdelberg: Sprnger, Physca Verlag, 1: 编辑蒋晓

计算机学报, 14, 37(1): 165-188. XU Ke, ZHANG Sa, CHEN Hao, et al. Measurement and analyss of onlne socal networks[j]. Chnese Journal of Computers, 14, 37(1): 165-188.

何秋琳张立春视觉学习研究进展视觉注意视觉感知

何秋琳张立春视觉学习研究进展视觉注意视觉感知第卷第期年月开放教育研究何秋琳张立春华南师范大学未来教育研究中心广东广州随着图像化技术和电子媒体的发展视觉学习也逐步发展为学习科学的一个研究分支得到研究人员和教育工作者的广泛关注基于此作者试图对视觉学习