社交网络的结构支撑理论.pdf

第37卷第4期
计算机
Vol 37 No 4
2014年4月
CHINESE JOURNAL OF COMPUTERS
Apr.2014
社交网络的结构支撑理论
韩毅”许进”方滨兴”周斌”贾焰
(北京大学计算机科学与技术系北京100871)
2)(国防科学技术大学计算机学院长沙410073
8)(北京电大学计算机学院北京100876)
摘要社交网络分析是近年来的研究热点之一,常见的分析方法包括度分布分析、个体排名、社区发现、模式发
现等.文中,作者认为一个人的社会地位其所在的网络结构共有紧密的联系,而这种网络结构对成员社公地位的
影响稈度是可以被表示和量化的.文中通过分析社交刚络的链接结构,将社交?络中个体与个体间的依赖关系从
般社会关系中抽取出米,提出了一种基于依赖模型的支持力衡量方法,并基于此给出了一种高效的计算最只支
持力的节点计算方法?此外,基于上述模型,设计了一种基于依赖关系的支撑结构模型及其计算方法,用于刻画社
交络中特定节点的影响力米源.作者在大规模的其实数据环境下对模型和算法的正确性:、效率和仲缩性进行了
验证
关键词社交网络;依赖度;支持力:社区发现
中图法分类号TP391
DOI号10.3724/SP.J.1016.2014.00905
Structural Supportiveness Theory on Social Networks
HAN Yi2 XU Jin FANG Bin-xing2zhou Bin?JIA Yan'
1)(Debartmenl o/ Computer Science, Peking Universily, Beijing 100871)
)(College of Computer, National University of Defense Technology, Changsha 410073)
5( School of Computer, Beijing University of Posts and Telecommunications, Beijing 100876)
Abstract Social network analysis has been studied extensively from variable angles such as
degree distribution analysis, social entity ranking, community extraction, and pattern discovery,
etc. In this paper, we consider a person's social status is highly related with the network struc-
ture which he/she locates in, and such impact from network structure to entities 'social status
can be modeled and mcasured. Wc cxtract the dependencies from ordinary relations by analyzing
the link structure. We also propose a "supportiveness"model based on dependency model. We
exploit a supportiveness-based entity ranking scheme, and efficient algorithms are developed to
compute the top-n most supportive entities. Moreover, we extend the supportiveness analysis to
community extraction, and develop feasible solutions to identify the most supportive groups of
entities. The empirical study conducted on a large real data set indicates that the supportiveness
measures are interesting and meaningful, and our methods are effective and efficient in practice.
Keywords social nctwork; dependency; supportiveness; community cxtraction
收稿凵期:2013-06-21;最终修改稿收到凵財:2014-01-24.本课题得到国家“九七三”重点基础研究发展规刘项∏基金(2013CB329601,
2013CB329602)、国家白然科学基金(61372191,91124002,61133010,61033003)、博十后科学基金(2013T60037,2012M520114)资助
韩毅,屴,1982年生,博士,高级工程师,中国计算机学会(CCF)会员,主要研究方向为信息网络分析、数据挖掘、信息安全. E-mail
yihan@pku.edu.cn.许进,男,1959年生,博十,教授,主要研究领域为图论、DNA计算机和信息安全等.方滨兴?男,1960年生,博十
教授,中国工稈院院十,主要研究领域为信息网络分析、信息安全和网络安全等,周斌,男,1971年生,博十,教授,主要研究领域为信作息
网络分析和数据挖掘等.贾焰,女,1960年生,博十,教授,主要研究领域为信息网络分析、数据挖掘、信息安全