社会关系网络分析基础理论：现状与展望

邓小龙，李欲晓，曾　洁

(1.北京邮电大学 可信分布式计算与服务教育部重点实验室,北京 100876；2.北京邮电大学 科学技术发展研究院,北京 100876)



社会关系网络分析基础理论：现状与展望

邓小龙1，李欲晓1，曾洁2

(1.北京邮电大学 可信分布式计算与服务教育部重点实验室,北京 100876；2.北京邮电大学 科学技术发展研究院,北京 100876)

摘要：针对关系结构、网络群体、网络信息这3个社会关系网络核心点，总结了社会关系网络的基本概念、分类、组成要素、社会关系网络分析的统计特性指标、社团结构划分算法等5个方面的主要问题和研究现状，并对未来与公共安全紧密相关的社会关系网络上的结构特性判别、多语言复杂情感环境下社会关系网络中信息语义和倾向性判别，以及社会关系网络信息传播过程中心理互动规律等方面的发展趋势进行了展望。

关键词：社会关系网络；分类；组成要素；统计特性指标；社团结构划分；个体及群体互动

随着互联网在全球快速发展和社会信息化进程加速，互联网、手机等新媒体承载终端快速普及，极大方便了人们之间的信息传递和分享。这种社交网络具体应用形式反映了人与人之间的本质社会关系，是人与人之间真实社会关系网络在多种信息媒体上的具体投影和多维度展现。

同时，随着当代信息化、全球化进程的进一步加速以及全球恐怖主义活动的进一步升温，大数据[1]、移动互联网、云计算等新技术也不断出现，以社交网络具体应用形式为代表的社会关系网络正深刻影响人们的生活方式和公共安全，因此对近年来蓬勃发展的社会关系网络分析的相关理论进行细节梳理，可以对未来科学界对社会关系网络这一重要社会形态的发展趋势进行把握，并对社会关系网络分析有着积极的推动和促进作用。当前已有社会关系网络分析的相关基础理论主要有：①社会关系网络基本概念及其与复杂网络的关系；②社会关系网络分类；③社会关系网络组成要素；④社会关系网络分析统计特性指标；⑤社会关系网络社团结构划分算法；⑥社会关系网络个体及群体互动。

1社会关系网络基本概念及其与复杂网络的关系

1.1社会关系网络的基本概念

对于社会关系网络的定义，刘军[2]指出社会关系网络是社会行动者及其之间关系的集合，罗家德[3]指出社会关系网的相关理论是一个“中层理论”，有一组分析社会现象的概念，包括社会关系、社会网、关系强度、关系内涵、网络结构、信任、社会资本、情感支持、人际影响等。

而近年来随着互联网的兴起和美国Facebook、国内开心网、校内网等“在线社交网络”理念风靡全球，研究者更多地从在线社交网络的角度去考虑社会关系网络，有学者[4-5]指出在线社交网络是一种在信息网络上由社会个体集合及个体间连接关系构成的社会性结构，包含关系结构、网络群体与网络信息3个要素。其中，社交网络的关系结构是社会个体成员之间通过社会关系结成的网络系统。个体也称节点，可以是组织、个人、网络ID 等不同含义的实体或虚拟个体；而个体间的相互关系可以是亲友、动作行为、收发消息等多种关系。

从社会关系网络形式化定义而言，社会关系网络可以抽象为一个由结点以及结点之间的边组成的图结构：G=(V，e)，其中V为网络中的节点集合，e为边的集合。节点的个数N=|V|，边的条数L=|e|。

在研究社会关系网络的相关特性时，图结构一般分为有向图、无向图、无权图、有权图。如果在图G中，只考虑结点和结点之间是否有边存在，而不考虑边权重，这时将图G称为无权图，可以用N×N的邻接矩阵A来描述图G，对于∀vi,vj∈V，如果两个结点之间存在边连接，则∃eij∈e，Aij=1，否则Aij=0。而对于有权图G=(V,e)，如果定义边eij的权重为wij(wij属于权重集合W并且wij为有效数值，一般为整数或者实数)，则邻接矩阵中表示边eij的元素Aij=wij。

1.2与复杂网络的关系

复杂网络的概念和定义模型涵盖社会关系网络的相关定义，复杂网络是指近年来在规模日益增大的万维网、电信网、移动通讯网络中可获得的社会关系网络数据，而这些社会关系网络数据由于规模过于庞大使得人们无法通过传统的技术和方法进行管理和运作，并且这些网络都具有某些共同的性质，比如“整体稀疏，局部密集；顶点度数服从幂率分布的无尺度特性[6]。再如，依据GIRVAN等[7]的观点，现实网络中的复杂网络大致分为4类：社会关系网络、信息网络、技术网络和生物网络。这4种网络的网络结构形式各不相同，彼此描述的系统内涵各异，其节点和边的定义差别也很大，但其却具有一些相同的特征：节点度服从幂律分布，群聚系数高，节点间平均路径距离小，因此研究者常使用复杂网络的相关概念和模型对社会关系网络进行研究。

2社会关系网络分类

通常而言，社会关系网络中往往表现为线上群体和线下群体两种模式，线上社会关系网络群体为在互联网媒体中所反映出来的社会关系群体，即在论坛、社交网络、即时通信工具中联系紧密的社会关系群体。依据2008年12月欧盟关于社会计算的研究报告《Key areas in the public sector impact of social computing》，在线社会关系网络群体可分为4类：①即时消息类应用，即通过在线实时通信平台进行交互的社会关系网络，如MSN、QQ、AIM、飞信、微信等；②在线社交类应用，即通过在线社交关系进行沟通的社会关系网络，如Facebook、Google+、人人网、开心网、QQ空间等；③微博类应用，即双向短信息发布平台进行沟通的社会关系网络，如Twitter、新浪微博、腾讯微博、网易微博、搜狐微博等；④共享空间等其他类应用，即通过其他可以相互沟通但结合不紧密的Web2.0应用进行交流的社会关系网络，如论坛、博客、BBS、视频分享、社会书签、在线购物等。

而线下社会关系网络群体是通过传统的互联网非实时方式进行沟通和交流的社会关系网络，如邮件网络、语言沟通网络、手机呼叫网络、手机短消息网络等，强调通过传统的面对面沟通或书信等方式进行沟通。

3社会关系网络组成要素

通过对社会关系网络的组成要素进行逻辑抽象，可以发现社会关系网络通常由点、关系、角色和演化4个核心组成要素构成。

(1)点：社会关系网络中的点是发生联系的事物。对于社会网络而言，点是行动者，可以是任何一个社会单位或社会实体。它既可以是一个教育机构如教研室、学院、学校；也可以是一个村落、组织、城市、国家；还可以是一个微博账号、一个Facebook账号等。关于点的信息既可以是动态的，也可以是静态的。

(2)关系：关系是社会关系网络中点与点之间的联系。关系常常代表具体的联络内容或者现实中发生的实质性关系。关系有多种表现，首先，点与点之间的关系类型多样，可以是朋友关系、上下级关系、国际贸易关系、城市距离关系等。其次，两个点之间的关系还有可能是“多元关系”。例如两个学生之间可能同时存在同学关系、友谊关系、恋爱关系和上下级关系。对多元关系网络的研究，是当前社会关系网络分析中最具潜力的前沿领域。再次，两个点之间的关系还具有显式和隐式(比如微博用户的关注关系)、双向和单向、强和弱等区别。除此之外，研究者还广泛研究了关系的特征，比如互惠性、传递性、同质性、异质性等。

(3)角色：角色是社会关系网络中的点在某个特定的关系中所具有的责任或任务。比如在某个社会团体中，可能领导者与下级联系的频度较高，通过统计该社会团体两两之间的通信强度发现该领导者处于整个社会团体的“核心”，这种核心地位可以体现该领导者的“领导角色”。此外，还可以发现和统计其他角色，并分析这些角色之间关系的强度，如新浪微博中微博账号之间的“粉丝”关系和相关“意见领袖”角色的发现和识别。

(4)演化：在现实网络当中，有些网络是相对静态的，如蛋白质网络、Internet的物理层网络。而对大多数网络来说，其拓扑结构[8-10]会随着时间而发生明显的变化，如每个人所处的朋友圈在不同时期会有所不同。而当网络的拓扑结构发生变化时，网络中的点、关系和角色都有可能发生变化，变化的过程称之为演化。以往的研究方法主要从整个网络或某个特定时间快照出发，关注网络全局特征在不同时间点上的变化，近年来，许多基于网络演化的分析方法被应用于各种社会关系网络当中[11-13]。这些方法中，利用图来描述某一特定时间(如一天或一个月等)的网络快照，基于这些图序列，社会关系网络的动态特性就能够被刻画出来[14-15]，如图1所示。

图1　社会关系网络组成要素

4社会关系网络分析统计特性指标

社会关系网络分析中的统计特性指标是针对具体社会关系网络数据进行分析和统计的重要统计维度，结合近年来相关研究中涉及到的社会关系网络的统计特性指标，可大致分为宏观性指标和微观性指标两大类。

(1)宏观性指标。宏观性指标侧重于从社会关系网络的整体角度去度量某个网络的性质和特征，这些指标[16-21]主要包括网络度分布指数、平均路径长度、反向平均路径长度、图聚类系数、最大连通子图大小、网络Q值、结构模块性、网络结构熵、网络容量等。

(2)微观性指标。微观性指标侧重于从网络的局部刻画社会关系网络的相关统计特性，主要分为4大类：点、边、模体[22]以及社团。各分类包括的统计特性指标[23-27]如下：

点：点-度、点-强度、点-介数、点-聚类系数、点-中介中心性、点-度中心性、点-接近中心性等。

边：边-方向、边-权、边-介数等。

模体：Z-score(表示每个子图的统计重要作用)、重要性剖面(significance profile)等。

社团：社团统计指标又分为3类，即社团基本统计指标、单条件指标和多条件指标。基本统计指标包括社团节点个数、社团内边数等；单条件统计指标由社团基本统计指标中的一项复合而成，主要有模块度(社团内部模块度)、模块度比例、社团内点的度和、社团边界边数等。多条件统计指标由社团基本统计指标的多项复合而成，主要有导电率、扩展率、内部边密度、截边率、规范截边率、MAX-ODF、Average-ODF、Flake-ODF等。

5社会关系网络社团结构划分算法

研究人员发现许多实际的社会关系网络是由若干个局部密集的“社团”(社团也被称作虚拟社区、虚拟社团等)所构成的。每个社团内部的结点之间的连接相对紧密,社团之间的连接相对来说比较稀疏。这些社团结构代表了网络中具有相同兴趣偏好的团体或联系紧密的结构，例如科学研究中的某一活跃领域和分支；万维网中主题相近的一组网页；对某一类话题比较感兴趣的微博用户账号、Twitter用户账号等。由于社会关系网络中的社团结构和网络功能有着紧密的关系，例如鲁棒性、高传播速度等，因此发现网络的社团结构是揭示网络结构和功能之间关系的重要基础。

目前已有的社团结构发现算法旨在揭示出网络中真实存在的网络簇结构，已被广泛应用于恐怖组织识别、组织结构管理等具体的社会关系网络分析[28-29]，以及Web社区挖掘和基于主题词的Web文档聚类[30-32]和搜索引擎[33-35]等众多领域。社会关系网络中社团结构的划分算法大致分为以下3类：

(1)基于优化的划分方法。基于优化的划分方法主要分为谱方法[36]和局部搜索方法，其中谱方法N-Cut(normal cut)[40]和A-Cut(average cut)具有严密的数学理论,但是针对网络的社团划分,谱方法不具备自动识别网络社团总数的能力，而现实中的网络往往包含多个网络社团,谱方法的递归二分策略不能保证得到的网络划分是最优的多网络社团结构。局部搜索方法部分主要基于目标函数、候选解的搜索策略和最优解的搜索策略，通过判断目标函数的某些局部最优值来选取相应的搜索策略。有代表性的局部搜索算法有Kernighan-Lin算法(简称KL算法)[37]、FastGN算法[38]和Guimera-Amaral算法(简称GA算法)[39]。KL算法需要先验知识(如社团的个数或社团的平均规模)，并且该算法对初始解异常敏感，不好的初始解将导致缓慢的收敛速度和较差的最终解。FastGN算法在社团规模较大时准确度不高，而GA算法时间复杂度太高，需要的计算时间较长。

(2)启发式划分方法。典型的启发式划分算法有MFC(maximum flow community)算法、HITS(hyperlink induced topic search)算法[40]、GN算法、CPM(clique percolation method)算法和FEC(finding and extracting communities)算法[41]等，这类算法的共同特点是:基于某些直观的假设来设计启发式算法,对于大部分网络,其能够快速地找到最优解或者近似最优解,但无法从理论上严格保证其对任何输入网络都能找到令人满意的解。

(3)其他划分方法。比较著名的有基于节点间相似度的算法，根据网络拓扑结构定义,如基于结构全等的相关系数(correlation coefficient)算法[42]、基于随机游走的相似度算法[43]和节点聚类中心度(clustering centrality)算法[44]等。

基于以上对社团划分方法的分类，可以得到基于优化的划分方法和启发式划分方法都存在一些各自的缺陷,比如基于优化的方法计算时间比较长，复杂度比较高，而启发式划分方法难以从理论上保证对输入的任何网络都有较满意的解。

6研究展望

当前在上述几个核心问题上的研究工作都面临着社会关系网络的具体形态快速发展所带来的新问题，也意味着每个方向上都有不少的挑战。面对快速发展的各种社会关系网络具体形态，笔者认为以下几个方面的研究将是未来社会关系网络的研究核心。

(1)新生形态社会关系网络的结构特性研究。随着各种新生形态的社会关系网络承载形式的快速发展，如开心网、新浪微博、Twitter、微信、腾讯QQ群等，深刻反映在线社会关系的社交网络等产品和服务快速进入人们的视野和生活，但是这些新生态社交网络产品所反映出社会网络的结构特性又各有区别。因此，如何针对快速发展的新生形态社会关系网络产品，构建合适、准确的网络模型来统计和模拟其性能，并对其结构特性进行精准的研究，准确评估个体的影响力，制定合理的管理策略，是非常值得研究的科学问题。

(2)多语言、复杂情感环境下社会关系网络中信息语义、倾向性的多维判别。当今互联网上承载的社会关系网络的相关应用，早已跨越了国界、种族和语言的界限，同时随着后Web 2.0时代的来临，用户在网络上所表达的语义、情感也是逐渐倾向于褒义贬义混用、褒义贬义替换使用、多语言杂糅和多个情感、情绪的混合，这就给抓取互联网信息后用户信息的语义判别、情感倾向性判别增加了难度和噪声。因此，如何在全球化背景下快速、准确地判断用户语义信息中所表达的真实目的和相关言论，对于智能化判别技术而言，存在巨大的挑战。

(3)社会关系网络中信息产生、传播过程的个体、群体心理互动规律研究。社会关系网络中的信息传播过程涉及传播个体、群体的心理互动规律、信息传播模式、个体群体观点博弈等多个复杂过程，涉及到心理学、计算机以及管理学等多个学科，信息在社会关系网络中的传播(特别在非常规突发事件中)具有传播方向、传播内容、传播变异的多个不确定性，因此如何将机器学习、人工智能等技术与传统的心理学、管理学理论相结合，构建社会关系网络中个体、群体在信息传播过程中心理、行为等诸多要素的互动规律，是当前很多学者重点关注的热点研究问题。

7结论

随着全球信息化、工业化进程的加速和互联网的快速发展，以在线社会关系网络为代表的社交网络的相关应用正在迅速而深刻地改变着人们的生活，笔者从社会关系网络的基本概念、社会关系网络的分类、组成要素模型、分析统计特性指标、社团结构划分算法、个体与群体互动规律等5个方面展开讨论，详细研究和分析了当前在社会关系网络方面已有的最近研究成果，以及未来发展趋势和主要研究方向。总之，社会关系网络方面的研究处于快速发展和变化当中，尚有诸多问题亟待解决。

参考文献：

[1]王元卓,靳小龙,程学旗.网络大数据：研究与展望[J].计算机学报,2013,36(6):1125-1138.

[2]刘军.整体网分析讲义:UCINET软件实用指南[M].上海:上海人民出版社,2009:32-98.

[3]罗家德.社会网络分析讲义[M].北京:社会科学文献出版社,2010:101-123.

[4]PALLA G,BARABASI A L,VICSEK T.Quantifying social group evolution[J].Nature,2007,446(7136):664-667.

[5]KUMAR R,NOVAK J,TOMKINS A.Structure and evolution of online social networks[C]∥Link Mining: Models,Algorithms and Applications.New York :Springer New York,2010:337-357.

[6]BARABASI A L,BONABEAU E.Scale-free networks [J].Scientific American,2003(288):60-69.

[7]GIRVAN M,NEWMAN E J.Community structure in social and biological networks [J].PNAS,2002,99(12):7821-7826.

[8]ONNELA J P ,SARAMAKI J,HYVONEN J,et al.Structure and tie strengths in mobile communication networks[J].PNAS,2007,104(18):7332-7336.

[9]NEWMA M E J.Coauthorship networks and patterns of scientific collaboration [J].PNAS,2004,101(s1):5200-5205.

[10]HOPCROFT J,KHAN O,KULIS B,et al.Tracking evolving communities in large linked networks [J].PNAS,2004,101(s1)：5249-5253.

[11]SUN J M,FALOUTSOS C,PAPADIMITRIOU S,et al.GraphScope: parameter-free mining of large time-evolving graphs[C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]: ACM,2007:687-696.

[12]KUMAR R,NOVAK J,TOMKINS A.Structure and evolution of online social networks[C]∥Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]: ACM,2006:611-617.

[13]ASUR S,PARTHASARATHY S.An event-based framework for characterizing the Evolutionary behavior of interaction graphs [C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]: ACM,2007:913-921.

[14]BERGE W,TANYA Y,SAIA J.A framework for analysis of dynamic social networks[C]∥Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.[S.l.]:ACM,2006:523-528.

[15]LESKOVEC J,KLEINBERG J,FALOUTSOS C.Graphs over time: densification laws,shrinking diameters and possible explanations[C]∥Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.[S.l.]:ACM， 2005:177-187.

[16]REKA A,HAWOONG J.Error and attack tolerance of complex networks [J].Nature,2000(406):378-382.

[17]BOGUNA M,PASTOR-SATORRAS R.Epidemic spreading in correlated complex networks [J].Physical Review E,2002,66(7):7104-7106.

[18]ALBERT R,BARABASI A L.Statistical mechanics of complex networks[J].Review of Modern Physics,2001,74(1):47-97.

[19]NEWMAN M E J.Finding community structure in networks using the Eigenvectors of matrices [J].Physical Review E,2006,74(3):6104-6107.

[20]SOLE R V,VALVERDE S.Information theory of complex networks: on evolution and architectural constraints[J].Lecture Notes in Physics,2004(650):189-210.

[21]PROKOPENKO M,WANG P.Self-organizing hierarchies in sensor and communication networks[J].Artificial Life,2005(11):407-426.

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

[23]DOROGOVTSEV S N ,MENDES J F F.The shortest path to complex networks [J].Am J Med Genet,2004(71):47-53.

[24]NEWMA M E J.Who is the best connected scientist: a study of scientific coauthorship networks [J].Lecture Notes in Physics,2004(650):337-370.

[25]FREEMAN L C.A set of measures of centrality based on betweenness [J].Sociometry,1977(40):35-41.

[26]CHRISTINE K,MARTIN B.Identification of influencers-measuring influence in customer networks [J].Decision Support Systems Archive,2008(10):233-253.

[27]LESKOVEC J,KEVIN J.Empirical comparison of algorithms for network community detection[C]∥Proceedings of the 19th International Conference on World Wide Web.[S.l.]:[s.n.],2010:631-640.

[28]PALLA G,DERENYI I.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[29]TYLER J R,WILKINSON D M.Email as spectroscopy: automated discovery of community structure within organizations[C]∥Proc of the 1st Int’l Conf on Communities and Technologies.Dordrecht: Kluwer Academic Publishers,2003:81-96.

[30]FLAKE G W,LAWEWNCE S,GILES C L,et al.Self-organization and identification of web communities [J].IEEE Computer,2002,35(3):66-71.

[31]LI X,LIU B,YU P S.Discovering overlapping communities of named entities[C]∥Proc of the 10th European Conf on Principles and Practice of Knowledge Discovery in Databases.Berlin: Springer-Verlag,2006:593-600.

[32]INO H,KUDO M.Partitioning of web graphs by community topology[C]∥Proc of the 14th Int’l Conf on World Wide Web.New York: ACM,2005:661-669.

[33]KLEINBERG J M.Authoritative sources in a hyperlinked environment [J].Journal of the ACM,1999,46(5):604-632.

[34]ALMEDIA R B,ALMEDIA V A F.A community-aware search Engine[C]∥Proc of the 13th Int’l Conf on World Wide Web.New York: ACM,2004:413-421.

[35]SIDIROPULOS A,PALLAIS G.Prefetching in content distribution networks via web communities identification and outsourcing[J].World Wide Web,2008,11(1):39-70.

[36]SHIGA M,TAKIGAWA I.A spectral clustering approach to optimally combining numerical Vectors with a Modular Network[C]∥Proc of the 13th ACM SIGKDD Int’l Conf on Knowledge Discovery and Data Mining.New York: ACM,2007:647-656.

[37]NEWMAN M E J.Detecting community structure in networks [J].European Physical Journal(B),2004,38(2):321-330.

[38]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):6133-6136.

[39]GUIMERA R,AMARAL L A N.Functional cartography of complex metabolic networks [J].Nature,2005,433(7028):895-900.

[40]KLEINBERG J M.Authoritative sources in a hyperlinked environment [J].Journal of the ACM,1999,46(5):604-632.

[41]YANG B,CHEUNG W K.Community mining from signed social networks [J].IEEE Trans on Knowledge and Data Engineering,2007,19(10):1333-1348.

[42]WASSEMAN S,FAUST K.Social network analysis [M].Cambridge: Cambridge University Press,1994:103-189.

[43]PONS P,LATAPY M.Computing communities in large networks using random walks [J].Lecture Notes in Computer Science,2005(3733):284-293.

[44]FORTUNATOS,LATORA V,MARCHIORI M.Method to find community structures based on information centrality [J].Physical Review E,2004,70(5):6104-6109.

DENG Xiaolong:Assistant Professor；Key Lab of Trustworthy Distributed Computing and Service of Education Ministry ,Beijing University of Post and Telecommunication,Beijing 100876,China.

[编辑：王志全]

文章编号：2095-3852(2016)01-0008-06

文献标志码:A

收稿日期：2015-10-26.

作者简介：邓小龙(1977-),男,湖北沙市人,北京邮电大学可信分布式计算与服务教育部重点实验室讲师；博士.

基金项目：十二五国家科技支撑计划资金资助项目 (2013BAH43F01) ；国家自然科学基金重大研究计划资金资助项目 (91124002).

中图分类号：C912.3;X915.2

DOI：10.3963/j.issn.2095-3852.2016.01.002

Social Network Analysis Basic Theory:Present and Future

DENG Xiaolong,LI Yuxiao,ZENG Jie

Abstract：With very fast developing speed of online social network users and their influence to our daily life,it is urgent for researchers to explore the essential scientific problem,investigate the disciplinary issues and common laws of social network,study the fundamental theory and basic approach to qualitatively or quantitatively researching on social network.And in recent years,researchers always focus on three components of relation structure,network group and network information to explore the essence of social network.To dealing the three essential components above,this paper analyzes and summary the related work of six aspects of social network such as basic concept,classification,components,statistical indicators,community detection algorithm in social network.It also looks ahead to the development trends of social network such as structure statistic analysis of new generation in social network,information semantic recognition and sentiment judgment in multilingual and complex sentiments environment,psychological interaction disciplines in information spreading process and so on.

Key words：social network; classification; components; statistical indicators; community detection; individuals and group interaction