基于结构的社会网络分析

第３５卷　第４期 ２０１２年４月 计　　算　　机　　学　　报 ＣＨＩＮＥＳＥ　ＪＯＵＲＮＡＬ　ＯＦ　ＣＯＭＰＵＴＥＲＳ Ｖｏｌ．３５ Ｎｏ．４ Ａｐｒ．２０１２ 　 收稿日期：２０１１－０１－１１；最终修改稿收到日期：２０１２－０１－０４．窦炳琳，男，１９８０年生，博士研究生，主要研究方向为社会网络分析与社区识 别．Ｅ－ｍａｉｌ：ｂｉｎｇｌｉｎ．ｄｏｕ＠ｇｍａｉｌ．ｃｏｍ．李澍淞，男，１９８０年生，博士研究生，主要研究方向为舆论动力学和复杂系统仿真．张世永，男，１９５０ 年生，教授，博士生导师，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为计算机网络、信息安全、无线通信、移动计算． 基于结构的社会网络分析 窦炳琳　李澍淞　张世永 （复旦大学计算机科学技术学院　上海　２００４３３） 摘　要　互联网的发展和社交网站的流行为研究社会网络提供了大规模的实验平台．主要使用ＤＢＬＰ和Ｆａｃｅｂｏｏｋ 数据集构建网络，采取角色连接轮廓方法从结构上进行划分，发现它们属于外围串类型；验证了社会网络的一些统 计性质，比如无标度分布、稠化定律和直径缩减等；发现社会网络中存在紧密连接且直径较小的核心结构，规模中 等的社区主要呈现星型结构；基于事件框架研究了社会网络中社区结构的进化，发现社区间的融合很大程度上取 决于社区间直接连接的节点所构成网络的聚类系数，而社区的分裂则与该社区的聚类系数相关． 关键词　复杂网络；网络分类；网络性质；社区进化；社会网络 中图法分类号 ＴＰ３９３　　　ＤＯＩ号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１２．００７４１ Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋ　Ａｎａｌｙｓｉｓ　Ｂａｓｅｄ　ｏｎ　Ｓｔｒｕｃｔｕｒｅ ＤＯＵ　Ｂｉｎｇ－Ｌｉｎ　ＬＩ　Ｓｈｕ－Ｓｏｎｇ　ＺＨＡＮＧ　Ｓｈｉ－Ｙｏｎｇ （Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｆｕｄａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２００４３３） Ａｂｓｔｒａｃｔ　 Ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　Ｉｎｔｅｒｎｅｔ　ａｎｄ　ｔｈｅ　ｐｏｐｕｌａｒｉｔｙ　ｏｆ　ｓｏｃｉａｌ　ｓｉｔｅｓ　ｐｒｏｖｉｄｅ　ｔｈｅ　ｌａｒｇｅ－ｓｃａｌｅ ｅｘｐｅｒｉｍｅｎｔａｌ　ｐｌａｔｆｏｒｍ　ｆｏｒ　ｒｅｓｅａｒｃｈｉｎｇ　ｔｈｅ　ｓｔａｔｉｓｔｉｃａｌ　ｐｒｏｐｅｒｔｉｅｓ　ａｎｄ　ｓｔｒｕｃｔｕｒｅ　ｅｖｏｌｕｔｉｏｎ　ｏｆ　ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ．Ｔｈｉｓ　ｐａｐｅｒ　ｍａｉｎｌｙ　ｕｓｅｓ　ＤＢＬＰ　ａｎｄ　Ｆａｃｅｂｏｏｋ　ｄａｔａｓｅｔｓ　ａｎｄ　ｂｕｉｌｔ　ｔｈｅ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ． Ｗｅ　ｃｌａｓｓｉｆｙ　ｔｈｅｓｅ　ｎｅｔｗｏｒｋｓ　ｂｙ　ｕｓｉｎｇ　ｒｏｌｅ－ｔｏ－ｒｏｌｅ　ｃｏｎｎｅｃｔｉｖｉｔｙ　ｐｒｏｆｉｌｅｓ　ａｎｄ　ｆｏｕｎｄ　ｔｈａｔ　ｔｈｅｙ　ｂｅｌｏｎｇ ｔｏ　ｓｔｒｉｎｇｙ－ｐｅｒｉｐｈｅｒｙ　ｃｌａｓｓ．Ｗｅ　ｃｏｎｆｉｒｍ　ｔｈａｔ　ｔｈｅｙ　ｈａｖｅ　ｔｈｅｓｅ　ｐｒｏｐｅｒｔｉｅｓ，ｓｕｃｈ　ａｓ　ｆｒｅｅ－ｓｃａｌｅ　ｄｉｓｔｒｉ－ ｂｕｔｉｏｎ，ｄｅｎｓｉｆｉｃａｔｉｏｎ　ｌａｗ　ａｎｄ　ｓｈｒｉｎｋｉｎｇ　ｄｉａｍｅｔｅｒ．Ｗｅ　ｄｉｓｃｏｖｅｒ　ｔｈｅｒｅ　ｉｓ　ａ　ｓｍａｌｌ　ｃｏｒｅ　ｗｉｔｈ　ｈｉｇｈ　ｃｏｎ－ ｎｅｃｔｉｖｉｔｙ　ｉｎ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ，ａｎｄ　ｏｂｓｅｒｖｅｄ　ｔｈａｔ　ｍａｎｙ　ｍｉｄｄｌｅ－ｓｃａｌｅ　ｃｏｍｍｕｎｉｔｉｅｓ　ａｒｅ　ｃｏｍｐｏｓｅｄ　ｏｆ ｓｔａｒｓ．Ｗｅ　ｒｅｓｅａｒｃｈ　ｔｈｅ　ｅｖｏｌｕｔｉｏｎ　ｏｆ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｂａｓｅｄ　ｏｎ　ｅｖｅｎｔ　ｆｒａｍｅｗｏｒｋ　ａｎｄ　ｒｅｖｅａｌｅｄ ｔｈａｔ　ｔｈｅ　ｃｏｍｍｕｎｉｔｙ　ｍｅｒｇｅ　ｄｅｐｅｎｄｓ　ｌａｒｇｅｌｙ　ｏｎ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｃｏｅｆｆｉｃｉｅｎｔ　ｏｆ　ｔｈｅ　ｇｒａｐｈ　ｃｏｍｐｏｓｅｄ　ｏｆ ｎｏｄｅｓ　ｗｈｉｃｈ　ａｒｅ　ｄｉｒｅｃｔｌｙ　ｃｏｎｎｅｃｔｅｄ　ｂｅｔｗｅｅｎ　ｃｏｍｍｕｎｉｔｉｅｓ　ａｎｄ　ｔｈｅ　ｃｏｍｍｕｎｉｔｙ　ｓｐｌｉｔ　ｉｓ　ｒｅｌａｔｅｄ　ｔｏ　ｉｔｓ ｃｌｕｓｔｅｒｉｎｇ　ｃｏｅｆｆｉｃｉｅｎｔ． Ｋｅｙｗｏｒｄｓ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ；ｎｅｔｗｏｒｋ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｎｅｔｗｏｒｋ　ｐｒｏｐｅｒｔｙ；ｃｏｍｍｕｎｉｔｙ　ｅｖｏｌｕｔｉｏｎ； ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ １　引　言 社会网络是由节点和链接这些节点的边组成的 复杂结构，节点表示人，边表示人与人之间的各种社 会关系．像共作者网络、电子邮件网络和互联网社区 等都是社会网络的例子．随着Ｉｎｔｅｒｎｅｔ的快速发展 和各种社交网站的出现，许多大型社会网络的数据 可以从运营商或互联网上获得，而在此以前的调查 统计手段则对此显得力不从心．根据不同社会网络 的功能，可以简单地将它们划分为交友网络（如 Ｆａｃｅｂｏｏｋ、Ｍｙｓｐａｃｅ等）、媒体分享网络（如Ｙｏｕｔｕｂｅ、 Ｆｌｉｃｋｒ等）、博客网络（如ＬｉｖｅＪｏｕｒｎａｌ、Ｔｗｉｔｔｅｒ等）、 即时通信网络（如 ＭＳＮ、ＱＱ等）和ＢＢＳ论坛网络 （如天涯社区）等等．这些网络的注册用户数少则几 十万、多则几千万甚至上亿，为研究社会网络的结构 和性质提供了丰富的平台． ２０世纪６０年代，美国哈佛大学社会心理学家 Ｍｉｌｇｒａｍ提出了“六度分割”（ｓｉｘ　ｄｅｇｒｅｅ　ｏｆ　ｓｅｐａｒａ－ ｔｉｏｎ）推断，也就是说世界上任何两个人之间的平均 距离为６［１］．这被认为是社会网络的理论基础．随着 计算设备能力的大幅提升、网络的迅猛发展以及不 同学科的相互渗透，人们可以处理和比较规模巨大 且类型不同的实际网络数据以揭示网络共有的结构 特性．以１９９８年 Ｗａｔｔｓ和Ｓｔｒｏｇａｔｚ建立小世界网络 模型［２］、１９９９年Ｂａｒａｂｓｉ和 Ａｌｂｅｒｔ建立无标度网 络模型［３］为标志，人们对复杂网络的研究进入发展 和繁荣时期，也吸引了来自数学与系统科学、统计物 理、生命科学、信息科学、社会科学、经济金融等多个 领域的研究人员的关注．使用复杂网络理论对社会 网络进行分析主要关注个体间相互关联和作用的拓 扑结构，这也是理解社会网络性质和功能的基础．就 计算机领域而言，关于社会网络研究的文章在近几 年已经频繁出现于 ＶＬＤＢ、ＫＤＤ、ＷＷＷ、ＩＭＣ、ＩＣ－ ＤＭ、ＷＩ等国际会议上，一些针对社会网络的专题 研讨会也有举行，比如 ＷＯＳＮ（ＡＣＭ　ＳＩＧＣＯＭＭ Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｏｎｌｉｎｅ　Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋｓ）、ＳＮＳ（ＡＣＭ ＥｕｒｏＳｙｓ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋ　Ｓｙｓｔｅｍｓ）等． 社会网络的研究主要从两个方面考虑：社会网 络的静态性质和动态特征．对于它的静态性质研究 包括拓扑分析［４－５］、社区挖掘［６－７］、关键节点发现［８－９］ 等．随着时间的推移，社会网络中新节点会不断地 加入，节点间的链接也会形成，从而使得社会网络 具有动态特性．对于这方面的研究主要集中在社 会网络形成和社区进化［１０－１１］等方面．另外，社会网 络拓扑与其上动力学的相互作用也被人们所关注， 比如社会网络中的信息传播［１２－１３］等．本文主要的贡 献包括： （１）关于社会网络的类型．目前，通过同配性系 数对不同类型的网络进行分类，人们普遍认为社会 网络具有同配特性．然而，我们发现一些实际的社会 网络却是异配的．我们利用角色连接轮廓方法能够 对本文所研究的数据集进行一致划分，它本质上反 映的是网络内部结构特征． （２）关于社会网络的性质和结构．我们验证了 本文所研究数据集的度幂律分布、网络直径缩减以 及网络稠化的性质，发现这些网络中的社区大小服 从幂律分布，中等规模的社区主要呈现星型结构．另 外，我们发现社会网络中存在紧密连接且直径较小 的核心结构． （３）关于社会网络的进化．我们基于事件框架 研究了社会网络中社区结构的进化，使用神经网络 方法来判定主导社区间事件产生的结构条件．我们 发现社区间的融合很大程度上取决于社区间直接连 接的节点所构成的网络的聚类系数，而社区的分裂 则与这个社区的聚类系数相关． 本文第２节介绍相关工作和基本概念；第３节 介绍角色连接轮廓方法并对本文所使用的数据集进 行研究；第４节验证社会网络的一些性质并给出社 会网络的结构特征；第５节研究社会网络中社区进 化的结构条件和因素；最后给出本文的结论． ２　相关工作和基本概念 ２．１　相关工作 大体上来讲，复杂网络要研究的是各种看上去 互不相干但其实密切关联的形形色色网络之间的共 同属性和处理它们的普适性方法［１４］．人们已经提出 了许多描述网络拓扑的统计特征，包括度节点、平均 路径长度、聚簇系数、介数、同配系数等［１５］．许多研究 也发现了网络上的一些重要性质，比如度分布的幂律 特征、社区结构的存在、网络上的小世界现象等等［１６］． 研究网络的社区结构能够使人们理解系统的层 次和功能特性，有利于揭示出网络内部错综复杂的关 系．目前人们已经开发了大量的社区结构发现的方 法，可以参考文献［１４，１７］．这里简单介绍 Ｎｅｗｍａｎ 等人在社区发现领域中的贡献．Ｇｉｒｖａｎ和Ｎｅｗｍａｎ 提出了一种发现社区的ＧＮ算法［１８］，该算法已经成 为社区结构分析的标准算法．但是该算法在社区数 目未知的情况下不知道在哪一步终止分解．为了解 决这个问题，Ｎｅｗｍａｎ等人引入模块度（ｍｏｄｕｌａｒｉ－ ｔｙ）［１９］的概念来作为衡量网络划分质量的标准．鉴 于它独立于社区发现算法本身，之后人们利用各种 启发式方法对模块度进行优化，比如采用贪婪算法、 模拟退火算法、极值优化等．另外，ＧＮ算法具有较 高的时间复杂度，Ｎｅｗｍａｎ在ＧＮ算法的基础上提 出了一种快速算法（ＦＮ算法）［２０］．它实际上是基于 贪婪算法思想且与ＧＮ算法操作相反的一种凝聚方 法（ａｇｇｌｏｍｅｒａｔｉｖｅ　ｍｅｔｈｏｄ）．之后，Ｃｌａｕｓｅｔ、Ｎｅｗｍａｎ 和 Ｍｏｒｒｅ三人［２１］在ＦＮ算法基础上采用堆数据结 ２４７ 计　　算　　机　　学　　报 ２０１２年 4 高亮 4 高亮 4 高亮 4 高亮 4 高亮 4 高亮 构来计算和更新模块度（ＣＮＭ 算法），该算法的复 杂度已接近线性．本文采用该方法进行网络的社区 划分． 网络的形成是一个动态的过程而且是一直不断 变化的，对于它的研究有助于揭示网络性质的起源 并能够对其发展进行预测．因此，人们对网络结构演 化过程中展现出来的特性给予了极大的关注．Ｌｅｓｋ－ ｏｖｅｃ等人［２２］发现网络中边的数目相对于节点的数 目以超线性速度增长 （稠化定律，ｄｅｎｓｉｆｉｃａｔｉｏｎ ｌａｗｓ）；在许多情况下网络的有效直径随着网络的增 长是减小的（直径缩减，ｓｈｒｉｎｋｉｎｇ　ｄｉａｍｅｔｅｒｓ）．Ｍｉｓ－ ｌｏｖｅ等人［５］对多个在线社会网络进行了大规模的测 量研究和分析．Ｌｅｓｋｏｖｅｃ等人［４］研究了社会网络中 社区结构的统计属性．Ｓｈｉ等人［２３］研究了不同论坛 的数据集中用户行为的模式和产生这种模式的特征 因素．Ｆａｌｋｏｗｓｋｉ等人［２４］对社会网络中社区进化行 为进行了可视化分析．Ａｓｕｒ等人［２５］提出了个体和 社区在网络演化中的事件框架，研究了随时间增量 计算的个体稳定性、社会性、影响力以及社区流行性 的测量方法．与上述研究不同的是，本文在事件框架 的基础上探讨社区间相互作用的结构特征． ２．２　基本概念 通常情况下，在由代表实体的节点以及它们之 间交互的边构成的社会网络中，所有的节点和边都 来自于整个数据收集周期．这种方式导致节点出现 和个体交互时序信息的丢失．这里，我们给出一个社 会网络的动态模型，它是分时图的离散时间序列．而 分时图由特定时间点所观察到的节点以及它们交互 的边所构成．形式化的定义如下： 令Ｇｔ＝（Ｖｔ，Ｅｔ）表示时间点ｔ的分时图，其中， Ｖｔ表示在时间点ｔ出现的节点集合，Ｅｔ表示在时间 点ｔ 出现的边的集合，则分时图序列 ＧＲ 由Ｇ１， Ｇ２，…，ＧＴ构成；若Ｇ′ｉ＝（Ｖ′ｉ，Ｅ′ｉ）满足Ｖ′ｉ＝∪ ｉ ｋ＝１ Ｖｋ且 Ｅ′ｉ＝∪ ｉ ｋ＝１ Ｅｋ，则Ｇ′１，Ｇ′２，…，Ｇ′Ｔ称为累时图序列ＧＡ．令 Ｇ＝Ｇ′Ｔ，称为终图． 图１　分时图与累时图示意 对于网络结构的刻画人们已经提出了许多统计 特性，这里我们介绍３个基本的概念，包括平均路 径长度、聚类系数（ｃｌｕｓｔｅｒｉｎｇ　ｃｏｅｆｆｉｃｉｅｎｔ）和度分 布［１４］．网络中两个节点ｉ和ｊ之间的距离ｄｉｊ定义为 连接这两个节点的最短路径上的边的数目，网络平 均路径长度Ｌ则定义为任意两个节点之间距离的 平均Ｌ＝ １１ ２Ｎ （Ｎ＋１） ∑ ｉｊ ｄｉｊ；节点ｉ有ｋｉ个邻居节 点，这ｋｉ个节点之间实际存在的边数与其最多可能 存在的边数ｋｉ（ｋｉ－１）／２之比定义为节点ｉ的聚类 系数，即Ｃｉ＝ ２ｅｉ ｋｉ（ｋｉ－１） ，则整个网络的聚类系数为 Ｃ＝１Ｎ∑ｉ Ｃｉ；节点ｉ的度为ｋｉ，网络中节点的度的分 布函数Ｐ（ｋ）表示一个随机选定的节点的度恰好为 ｋ的概率． ３　社会网络的类型 ３．１　数据集 本文主要使用的两个数据集来自 ＤＢＬＰ计算 机科学文献库和Ｆａｃｅｂｏｏｋ社交网络． （１）ＤＢＬＰ数据集 ＤＢＬＰ① 提供在主要国际期刊和会议上公开发 表的计算机类文章的检索功能，它在学术界有着较 好的声誉和权威性．目前，ＤＢＬＰ收录的各类刊物达 到１４０多万种，并将ＸＭＬ格式的数据公开给研究 人员使用．本文选择从１９８６年到２００６年发表在８０ 种计算机各领域重要期刊上的所有文章作为基本数 据．将每一个作者作为一个节点，如果两个作者出现 在同一篇文章中则相对应的两个节点间存在一条无 向边．通过这种方式由在这２１年中所有出现的点 （８３９４３个节点）和边（１９０　３４２条边）构成ＤＢＬＰ共作 者网络．文中以年为单位构建ＤＢＬＰ分时图序列． （２）Ｆａｃｅｂｏｏｋ数据集 Ｆａｃｅｂｏｏｋ是一个著名的在线交友社会网络，注 册用户达５亿．本文使用的Ｆａｃｅｂｏｏｋ数据来自文献 ［２６］，他们收集了Ｆａｃｅｂｏｏｋ的Ｎｅｗ　Ｏｒｌｅａｎｓ区域中 的朋友关系网络．我们使用从２００７年１月１日～ ２００８年１２月３１日之间所涉及的６０　５６７位用户和 ５８３　７６６条连接来构建Ｆａｃｅｂｏｏｋ网络．文中以月为 单位构建Ｆａｃｅｂｏｏｋ分时图序列． 另外，文中用到的Ｅｎｒｏｎ数据集被美国联邦能 源监管委员会公开，由ＳＲＩ的ＣＡＬＯ项目收集并处 理，卡内·基梅隆大学的Ｃｏｈｅｎ为其建立了网站以 ３４７４期 窦炳琳等：基于结构的社会网络分析 ① ｈｔｔｐ：／／ｄｂｌｐ．ｕｎｉ－ｔｒｉｅｒ．ｄｅ／ 方便研究使用①．这个数据集中包含了５０万封电子 邮件．将邮件的地址作为节点，如果两个地址间有任 一电子邮件存在则建立一条无向边，这样构成的网 络有３６　６９２个节点以及３６７　６６２条边．Ｙｏｕｔｕｂｅ数 据集来自文献［５］，我们从中取２００７年１月１日～ ２００７年１月１５日的数据来构建网络，由３５　４６８个 节点和２６１　１９１条边组成． ３．２　社会网络的类型 Ｎｅｗｍａｎ将现实中的网络根据其自身的特性粗 略地归类为生物网络、技术网络、信息网络和社会网 络［１６］．网络的度相关性研究网络中给定具有特定度 的节点的邻居节点平均度分布情况，它可以用同配 性系数［２７］（Ａｓｓｏｒｔａｔｉｖｉｔｙ　Ｃｏｅｆｆｉｃｉｅｎｔ）加以刻画，即 ｒ＝ Ｍ －１∑ｉｊｉｋｉ－ Ｍ －１∑ｉ１２（ｊｉ＋ｋｉ［ ］） ２ Ｍ －１∑ｉ１２（ｊ ２ ｉ＋ｋ２ｉ）－ Ｍ －１∑ｉ１２（ｊｉ＋ｋｉ［ ］） ２， －１ｒ１． 其中，ｊｉ，ｋｉ分别表示第ｉ条边连接的两个节点的度， ｉ＝１，…，Ｍ，Ｍ 表示网络中的总边数．当ｒ＞０时表 示网络有正的度关联，即网络是同配的；当ｒ＜０ 时表示网络有负的度关联，即网络是异配的．如果网 络中节点间的度不具关联性，则有ｒ＝０．相关研究 表明，技术网络、生物网络和信息网络通常是异配 的，社会网络一般是同配的．然而，我们发现对于 一些在 线 社 会 网 络，比 如 瑞 典 的 婚 恋 交 友 网 Ｐｕｓｓｏｋｒａｍ（ｒ＝－０．０４８）［２８］、韩国最大的在线交友 网Ｃｙｗｏｒｌｄ（ｒ＝－０．１３）［２９］等，具有异配性．其原因 可能在于在线社会网络中每个人都有机会和具有较 高人气的角色建立联系．Ｈｕ等人［３０］的研究进一步 指出一些在线社会网络随着时间发展会从同配性过 渡到异配性，同样也存在度关联特征不随时间变化 的社会网络．这主要取决于社会网络所涉及的领域、 功能等自身特征．Ｓｚｅｌｌ等人［３１］也观察到了网络从同 配性到异配性的变迁过程．本文所使用的数据集 ＤＢＬＰ、Ｙｏｕｔｕｂｅ、Ｆａｃｅｂｏｏｋ和Ｅｎｒｏｎ的同配系数分 别为０．３７２、－０．０３３、０．１７７、－０．１１． 网络的度相关性同度分布、平均路径长度、聚簇 系数一样反映了网络的全局性质．这并不能体现出 网络内部的结构特性．人们普遍认为社会网络内部 存在有模块（模块（Ｍｏｄｕｌｅ）、社区（Ｃｏｍｍｕｎｉｔｙ）、组 （Ｇｒｏｕｐ）等表述在不引起歧义的情况下，本文将不 加区别地使用）结构［１８，３２－３３］，也就是说，模块内部节 点相互连接密集而模块间节点相互连接稀疏． Ｇｕｉｍｅｒａ等人［３４－３５］根据节点在模块内外的连接模式 将其分类为不同的角色，并在此基础上利用角色连 接轮廓（Ｒｏｌｅ－ｔｏ－ｒｏｌｅ　Ｃｏｎｎｅｃｔｉｖｉｔｙ　Ｐｒｏｆｉｌｅｓ，ＲＣＰ）将 具有模块性质的网络分为两种：串类 （ｓｔｒｉｎｇｙ－ ｐｅｒｉｐｈｅｒｙ　ｃｌａｓｓ）和多星类（ｍｕｌｔｉ－ｓｔａｒ　ｃｌａｓｓ），两者的 主要区别在于Ｕｌｔｒａ－ｐｅｒｉｐｈｅｒａｌ节点（节点角色Ｒ１） 间以及Ｃｏｎｎｅｃｔｏｒ　ｈｕｂｓ节点（节点角色Ｒ６）间的链 接模式不同．在串类网络中这些链接模式是高于平 均值的而在多星类网络中则相反．Ｇｕｉｍｅｒａ等人对 新陈代谢网络、蛋白质交互网络、航空交通网络以及 自治系统级别的Ｉｎｔｅｒｎｅｔ网络进行分析和归类．然 而，我们还不清楚社会网络所表现出来的内部特征， 因此划分社会网络的类别对于理解它们的拓扑结 构、功能属性具有十分重要的意义． 为了得到网络的ＲＣＰ需要采取以下３个步骤： （１）划分网络的模块结构． 目前，人们已经开发出多种网络模块划分的方 法［１７］．Ｇｕｉｍｅｒａ等人在文献［３４］中采用模拟退火 （Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌｉｎｇ，ＳＡ）算法来优化网络模块性 评价Ｑ函数．由于ＳＡ算法本身的特性，导致他们的 这种方法对初始参数非常敏感，且收敛速度缓慢．为 此，本文采用Ｃｌａｕｓｅｔ、Ｎｅｗｍａｎ和 Ｍｏｏｒｅ三人［２１］提 出的基于快速 Ｎｅｗｍａｎ算法和堆数据结构的新的 贪婪算法（ＣＮＭ算法），它具有接近线性的复杂度Ｏ （ｎｌｏｇ２　ｎ）．利用该算法，他们分析了具有超过４００ ０００个节点和２　０００　０００条边的Ａｍａｚｏｎ购书推荐网 络．用ＮＭ表示网络的模块数目． （２）指定每个模块的节点角色． Ｇｕｉｍｅｒａ等人利用两个参数ｚ和Ｐ 来决定模块 内每个节点的角色．节点ｉ的ｚ参数 ｚｉ＝ ｋｊｓｉ－〈ｋ ｊ ｓｉ 〉ｊ∈ｓｉ 〈（ｋｊｓｉ） ２ ｊ∈ｓｉ－ｋ ｊ ｓｉ 〉２ｊ∈ｓ槡 ｉ ， 其中：ｋｊｓｉ表示节点ｉ到其所在模块ｓ内其它节点的 连接数，ｓｉ表示节点ｉ所属的模块，〈…〉ｊ∈ｓ表示对模 块ｓ内所有节点的计算均值．节点ｉ的Ｐ 参数Ｐｉ＝ １－∑ ＮＭ ｓ＝１ ｋｉｓ Ｋ（ ）ｉ ２ ，其中Ｋｉ＝∑ ｓ ｋｉｓ是节点的度．ｚ参数表 示某节点与模块内其它节点的连接情况，Ｐ参数则 表示该节点如何连接到其它模块．根据节点参数ｚ 和Ｐ 的取值范围来确定节点的角色，如图２所示． 需要注意的是角色Ｒ４与Ｒ７在现实世界的网络中几 乎是不会存在的． ４４７ 计　　算　　机　　学　　报 ２０１２年 ① ｈｔｔｐ：／／ｗｗｗ－２．ｃｓ．ｃｍｕ．ｅｄｕ／～ｅｎｒｏｎ／ 图２　ｚ－Ｐ 坐标上的角色划分及其含义（角色划分的理论依据及其鲁棒性问题可以参考文献［３４－３５］的补充信息①） 　　（３）计算不同角色的节点间连接数目的Ｚ－Ｓｃｏｒｅ． 为了更好地统计不同角色间的连接数目，使用 节点数、边数、每个节点的度、网络的模块以及模块 间的连接数目都与实际网络相同的随机化网络来衡 量．将 Ｍａｒｋｏｖ－ｃｈａｉｎ　Ｍｏｎｔｅ　Ｃａｒｌｏ交换算法［３６］应用 到实际网络的模块内部以及模块与模块的节点之 间，来产生随机网络集合0．该算法重复随机选择连 接对（ａ，ｂ）和（ｃ，ｄ）并交换它们的一端成为（ａ，ｄ）和 （ｃ，ｂ）．它使得节点的角色在随机化网络中保持不变． 令ｒｉｊ和Ｒｉｊ分别表示实际网络与随机化网络中角色ｉ 与ｊ之间的连接数目，则有ｚｉｊ＝ ｒｉｊ－〈Ｒｉｊ〉0 〈Ｒ２ｉｊ〉0－〈Ｒｉｊ〉２槡 0 ． 根据所有角色对间的Ｚ－Ｓｃｏｒｅ 便可得到网络的 ＲＣＰ图． 我们利用上述方法分析了 ＤＢＬＰ、Ｙｏｕｔｕｂｅ、 Ｆａｃｅｂｏｏｋ和Ｅｎｒｏｎ等４个数据集，如图３所示． 图３　４个数据集上的Ｚ－Ｓｃｏｒｅ（（ａ）、（ｂ）引自文献［３５］，分别属于串类和多星类．（ｃ）、（ｄ）、（ｅ）、（ｆ）都属于串类） ①　相关文献补充信息的链接地址：ｈｔｔｐ：／／ｗｗｗ．ｎａｔｕｒｅ．ｃｏｍ／ｎａｔｕｒｅ／ｊｏｕｒｎａｌ／ｖ４３３／ｎ７０２８／ｓｕｐｐｉｎｆｏ／ｎａｔｕｒｅ０３２８８．ｈｔｍｌ；ｈｔｔｐ：／／ｗｗｗ．ｎａ－ ｔｕｒｅ．ｃｏｍ／ｎｐｈｙｓ／ｊｏｕｒｎａｌ／ｖ３／ｎ１／ｓｕｐｐｉｎｆｏ／ｎｐｈｙｓ４８９＿Ｓ１．ｈｔｍｌ ５４７４期 窦炳琳等：基于结构的社会网络分析 　　区分两种不同类型网络的关键在于它们角色连接 模式的差异，主要涉及到连接类型Ｒ１ －Ｒ１ 和Ｒ６ －Ｒ６． 空中交通网（ａ）与自治系统层的Ｉｎｔｅｒｎｅｔ拓扑（ｂ）属 于技术网络，度关联具有异配性．但是从角色连接 模式来看，它们有着显著的不同．图３（ａ）中，角色 Ｒ１ 之间连接Ｒ１ －Ｒ１ 的Ｚ－Ｓｃｏｒｅ（ＺａＲ１－Ｒ１）高于平均水 平（ＺａＲ１－Ｒ１０），角色Ｒ１ 与Ｒ２ 之间连接Ｒ１ －Ｒ２ 的 Ｚ－Ｓｃｏｒｅ（ＺａＲ１－Ｒ２）低于平均水平 （Ｚ ａ Ｒ１－Ｒ２ ０），这 导致较长的节点链．而图３（ｂ）中Ｒ１ －Ｒ１、Ｒ１ －Ｒ２的 Ｚ－Ｓｃｏｒｅ则与图３（ａ）相反，ＺｂＲ１－Ｒ１０且Ｚ ｂ Ｒ１－Ｒ２０． 这意味着网络中存在较多的星型结构．同时，考察 图３（ａ）与图３（ｂ）中心节点角色Ｒ６ 间的连接模式有 ＺａＲ６－Ｒ６０而Ｚ ｂ Ｒ６－Ｒ６０，与这两种网络的实际情况是 相符的．Ｉｎｔｅｒｎｅｔ的分层结构使得一个自治系统到 其它自治系统间存在较少的连接；对于空中交通网 络而言，一个国家或地区的交通枢纽则可能会存在到 其它国家或地区多个交通枢纽的多条航线．因此，将 空中交通网归为串类而Ｉｎｔｅｒｎｅｔ自治系统网络则属 于多星类． 考察图３中（ｃ）、（ｄ）、（ｅ）、（ｆ）的连接类型Ｒ１ －Ｒ１、 Ｒ１ －Ｒ２ 和Ｒ６ －Ｒ６，可以发现它们具有与图３（ａ）相似 的特征，即它们的ＺＲ１－Ｒ１０，ＺＲ１－Ｒ２０，ＺＲ６－Ｒ６＞０（其 中，ＺｃＲ６－Ｒ６＝０．９６，Ｚ ｅ Ｒ６－Ｒ６ ＝２．０１）．可以确定这些社 会网络属于串类（我们也研究了Ｆｌｉｃｋｒ、ＬｉｖｅＪｏｕｒ－ ｎａｌ、Ｏｒｋｕｔ、Ｗｉｋｉｐｅｄｉａ等社会网络，发现它们也表现 出了串类的性质，限于篇幅不再一一列出）．同时，利 用ＲＣＰ可以看到社会网络内部丰富的结构形式，这 与不同社会网络本身的功能有关．例如，共作者网络 ＤＢＬＰ有ＺｃＲ５－Ｒ５＞０和Ｚ ｃ Ｒ５－Ｒ６＞０，这是因为有影响 力的作者更愿意与自己水平相当的人合作；而视频 分享网络Ｙｏｕｔｕｂｅ有ＺｆＲ５－Ｒ５＜０和Ｚ ｆ Ｒ５－Ｒ６＜０，则说 明那些用户更多的是上传而不是分享视频． ４　社会网络的性质和结构 ４．１　社会网络的性质 近年兴起的复杂网络理论主要研究的内容之一 是揭示刻画网络系统结构的统计性质并给出度量这 些性质的合适方法．人们已经发现网络具有小世界、 无标度等特征，并利用度分布、平均路径长度、聚类 系数等统计手段［１５］．这里，我们从复杂网络的角度 来探讨ＤＢＬＰ和Ｆａｃｅｂｏｏｋ的性质．无标度分布广泛 存在于物理学、地球与行星科学、计算机科学、生物 学、人口统计学与社会科学、经济与金融学等众多领 域［３７］，它形式化地表示为Ｐ（ｋ）＝ｃｋ－α，其中ｋ表示网 络某特征的变量，ｃ为常数，α为幂指数．对于网络中 节点的度分布而言，其幂指数多在２～３的范围［３８］． 首先，考察两个数据集的度分布性质．需要说明 的是这里的网络是无向的，而且遗失某时间点之前 的数据对网络本身性质的影响可以忽略［２２］．从图４ 中可以看到，ＤＢＬＰ网络的度分布呈现幂律特征，幂 指数为２．７３２，拟合精确度 Ｒ－Ｓｑｕａｒｅ 为０．９９６７； Ｆａｃｅｂｏｏｋ网络的整体度分布介于指数分布和幂律 分布之间，而其尾部幂律特征较为明显（幂指数为 ２．９０５，拟合精确度为０．９８９６）．另外，使用ＣＮＭ 算 法对ＤＢＬＰ和Ｆａｃｅｂｏｏｋ划分社区并对其大小情况 进行统计，发现幂律分布同样存在，如图５所示． 图４　度分布 其次，研究两个网络平均距离随时间的变化，利 用有效直径（ｅｆｆｅｃｔｉｖｅ　ｄｉａｍｅｔｅｒ）［２２］的概念进行度 量．至少９０％的相互连接的节点对的距离最多不超 过ｄ，它的最小值即为有效直径．从图６中可以看 到，随时间的增加网络直径逐渐减小．在 ＤＢＬＰ网 络中，由于人为选择特定的刊物作为数据源以及计 算机各研究领域刚处于起步时期，导致网络的有效 直径在１９９０年以前有较大的变化而之后它呈现逐 ６４７ 计　　算　　机　　学　　报 ２０１２年 渐下降趋势．在Ｆａｃｅｂｏｏｋ网络中，这种特性从一开 始就很明显．网络有效直径减少的现象与网络中边 与节点的密度和增加速度相关．为此，我们讨论网络 中节点和边随时间变化的问题．从图７中可以看到， 网络中边Ｅ相对于节点Ｎ 呈现非线性增长，这意味 着网络平均度的增加．形式上，它服从幂律分布 （Ｅ∝Ｎβ）．ＤＢＬＰ网络中有β＝１．２８５，Ｒ ２＝０．９９９８； Ｆａｃｅｂｏｏｋ网络中有β＝１．６２６，Ｒ ２＝０．９９８７．因此，对 于上述两种性质，即社会网络的稠化定律（ｄｅｎｓｉｆｉ－ ｃａｔｉｏｎ　ｌａｗｓ）和直径缩减（ｓｈｒｉｎｋｉｎｇ　ｄｉａｍｅｔｅｒｓ），我 们在ＤＢＬＰ和Ｆａｃｅｂｏｏｋ网络中给予了验证． 图７　网络稠化 ４．２　社会网络的结构 在上一节中我们研究了社会网络的宏观性质， 它的微观结构将在本节中讨论． 首先，考察构成网络的社区规模随时间变化的 情况．利用ＣＮＭ算法对ＤＢＬＰ和Ｆａｃｅｂｏｏｋ网络的 多个时间点的累时图分别进行社区划分，并统计不 同大小的社区在网络中所占比重，如图８所示．图中 底部表示小规模的社区（几个节点），中间部分为中 等规模的社区（几十到几百个节点），顶部为较大规 模的社区（几百到几千个节点）．从网络的形成过程 来看，我们发现中等规模的社区所占比重在逐渐减 少，大规模的社区的情况与之相反；而小规模社区所 ７４７４期 窦炳琳等：基于结构的社会网络分析 占比重则基本保持不变．另外，计算中等规模社区的 同配性系数发现它们几乎都是负相关的，这说明在 这些社区中度较大的节点倾向于与度小的节点连 接；同时，对它们进行ＲＣＰ分析发现有９０．３％的社 区属于多星类．因此，这两个网络中中等规模的社区 大多数具有明显的星型结构特征． 图８　随时间变化的网络社区规模 其次，研究网络中是否存在具有较小直径且紧 密连接的核结构．我们首先从网络中移除所有度小 于１的节点，然后移除网络中所有度小于２的节点， 依次类推直到移除度小于某一设定值的所有节点． 通过这种方法来观察网络有效直径以及边 －节点比 值的变化，如图９所示．图９（ａ）中显示ＤＢＬＰ的有 效 直 径 下 降 了 ２８．９４％，Ｆａｃｅｂｏｏｋ 则 下 降 了 ２１．８５％；与之相反，图９（ｂ）中显示它们的边 －节点 比分别增长了３．２８倍和１．８８倍．这也就是说随着 外围节点或结构的移除，网络中节点间的有效距离 减少而网络中的边更加密集．我们也考察了在这一 过程中网络聚簇系数的变化，ＤＢＬＰ的聚簇系数由 ０．３７７４上升到了０．５１９６，Ｆａｃｅｂｏｏｋ的聚簇系数则 由０．４１０８达到０．６２１５．因此，可以认为有这样的核 结构存在于网络中，但是随着移除节点数目的增加 它变得不稳定，这一过程最终会导致核结构分解为 多个互不连通的社区．另外，我们考虑社区结构的传 导性（ｃｏｎｄｕｃｔａｎｃｅ）问题．它可以定义为一端在集合 内而另一端在集合外的连接数目与该集合所有连接 数目的比值．那么，获得大小为ｋ且具有最小传导性 的集合是一个较为困难的问题．我们使用 ＮＣＰ （Ｎｅｔｗｏｒｋ　Ｃｏｍｍｕｎｉｔｙ　Ｐｒｏｆｉｌｅ　ｐｌｏｔ）方法［４］来考察 ＤＢＬＰ和Ｆａｃｅｂｏｏｋ网络中具有不同ｋ值社区的传 导性，如图１０所示，图中曲线表示不同规模的社区 ８４７ 计　　算　　机　　学　　报 ２０１２年 所具有的最小传导性．从图中可以看到 ＤＢＬＰ和 Ｆａｃｅｂｏｏｋ中具有较好传导性的社区规模大致在 １０～１００个节点间而当社区规模较大时其传导性能 会变差．通过找到那些最小传导性的社区可以发现它 们多数位于网络边缘且与其它社区具有很少的连接． ５　社会网络的进化 对复杂网络不仅要研究网络的统计性质而且要 建立合适的模型来阐明它们产生的原理并预测网络 的行为．Ｂａｒａｂｓｉ和Ａｌｂｅｒｔ建立的ＢＡ无标度模型 利用增长（ｇｒｏｗｔｈ）和优先连接（ｐｒｅｆｅｒｅｎｔｉａｌ　ａｔｔａｃｈ－ ｍｅｎｔ）机制来解释网络连接度所具有的幂律形 式［３］．然而，它并不能反映实际网络的一些非幂律特 征，如指数截断（ｅｘｐｏｎｅｎｔｉａｌ　ｃｕｔｏｆｆ）、小饱和变量 （ｓａｔｕｒａｔｉｏｎ　ｆｏｒ　ｓｍａｌｌ　ｖａｒｉａｂｌｅｓ）等［１４］．随后，人们对 ＢＡ模型进行了扩展，提出了适应度模型［３９］、局域世 界模型［４０］、权重演化模型［４１］等．除了优先连接机制 外，自组织临界理论也可能是揭示幂律分布的动力 学原因之一．人们提出了一些自组织模型能够涌现 出网络的无标度结构［４２－４３］．然而这些模型并不能反 映网络具有的等级和模块化结构，为此，科研人员研 究了像“拷贝”模型（ｃｏｐｙｉｎｇ　ｍｏｄｅｌ）［４４］、ＪＧＮ（Ｊｉｎ， Ｇｉｒｖａｎ，Ｎｅｗｍａｎ）模型［４５］等网络社区生成和进化的 方法． 近年来，对于大规模社会网络的研究，人们发现 了它所具有的许多性质并开发了相应的模型．Ｌｅｓｋ－ ｏｖｅｃ等人给出一个称之为“森林火灾”模型（Ｆｏｒｅｓｔ Ｆｉｒｅ　Ｍｏｄｅｌ）来反映社会网络的社区结构、直径缩减 和稠化定律［４０］．随后，他们基于对几个社会网络时 序数据的观察，根据节点和边进入网络的时间顺序 构造了“微观进化”模型（Ｍｉｃｒｏｓｃｏｐｉｃ　Ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ）［１０］．Ｚｈｅｌｅｖａ等人［４６］在微观进化模型的基础 上提出了社会网络及其社区结构“共进化”模型（Ｃｏ－ ｅｖｏｌｕｔｉｏｎ　ｍｏｄｅｌ）．另外，ＭｃＧｌｏｈｏｎ等人［４７］研究了 网络中连通组件的进化特征并提出了“蝴蝶”模型 （Ｂｕｔｔｅｒｆｌｙ　ｍｏｄｅｌ）． 就社区结构的研究而言，学界主要集中于两个 方面：一是网络中社区结构的发现，目前已经有大量 的方法可以借鉴［１４，１７］；二是网络中社区结构的形成 与进化，主要关注网络中成员与社区之间的各种关 系［２３，４８］，而对于社区与社区的相互作用，就我们所 了解的知识而言，这方面研究还很少．Ａｓｕｒ等人提 出了一个事件框架（Ｅｖｅｎｔ－Ｂａｓｅｄ　Ｆｒａｍｅｗｏｒｋ）用于 刻画社区间的各种关系，然而他们的工作主要关注 个体的社会性、稳定性、影响力以及社区的受欢迎程 度等［２５］．与他们的工作不同，基于该框架本文侧重 于研究社区间的相互作用及结构影响． ５．１　事件框架 事件是当前图Ｇｔ中社区间的相互作用在邻接 后续图Ｇｔ＋１中的反映．文献［２５］中的基本事件包括 社区的融合（Ｍｅｒｇｅ）、分裂（Ｓｐｌｉｔ）、形成（Ｆｏｒｍ）、消 失（Ｄｉｓｓｏｌｖｅ）和保持（Ｃｏｎｔｉｎｕｅ）．本文着重研究影响 社区融合和分裂的结构特征．另外，本文根据社区中 成员数量的变化来判定各类事件的产生，不涉及具有 相同成员的社区在不同时间点它们之间关系的变化． 假定 图 Ｇｔ ＝ （Ｖｔ，Ｅｔ）划 分 成 ｍ 个 社 区 ｛Ｃ１ｔ，Ｃ２ｔ，…，Ｃｍｔ｝，其中第ｉ个社区Ｃｉｔ＝（Ｖｉｔ，Ｅｉｔ）且 有ＶｉｔＶｔ，ＥｉｔＥｔ．使用｜·｜表示集合的基，阈值φ 取０．５． 如果图Ｇｔ中的社区Ｃｉｔ与Ｇｔ＋１中的社区Ｃｋｔ＋１满 足Ｖｉｔ＝Ｖｋｔ＋１，则称社区保持． 如果图Ｇｔ中不存在任何社区Ｃｉｔ满足｜Ｖｉｔ∩ Ｖｋｔ＋１｜＞１，则有社区形成；如果图Ｇｔ＋１中不存在任何 社区Ｃｋｔ＋１满足｜Ｖｋｔ＋１∩Ｖｉｔ｜＞１，则有社区消失． 如果图Ｇｔ中社区Ｃｉｔ、Ｃｊｔ与Ｇｔ＋１中的社区Ｃｋｔ＋１ 满足 ｜ （Ｖｉｔ∪Ｖｊｔ）∩Ｖｋｔ＋１｜ ｍａｘ（｜Ｖｉｔ∪Ｖｊｔ｜，｜Ｖｋｔ＋１｜）＞φ 且有｜Ｖｉｔ∩Ｖｋｔ＋１｜＞ ｜Ｃｉｔ｜ ２ ，｜Ｖｊｔ∩Ｖｋｔ＋１｜＞｜ Ｃｊｔ｜ ２ ，则称社区Ｃｉｔ与Ｃｊｔ产生了 融合． 如果图 Ｇｔ中社区Ｃｉｔ与Ｇｔ＋１中的社区Ｃｊｔ＋１ 和Ｃｋｔ＋１ 满足 ｜ （Ｖｊｔ＋１∪Ｖｋｔ＋１）∩Ｖｉｔ｜ ｍａｘ（｜Ｖｊｔ＋１∪Ｖｋｔ＋１｜，｜Ｖｉｔ｜）＞φ 且有 ｜Ｖｊｔ＋１∩Ｖｉｔ｜＞｜ Ｃｊｔ＋１｜ ２ ，｜Ｖｋｔ＋１∩Ｖｉｔ｜＞｜ Ｃｋｔ＋１｜ ２ ，则社区 Ｃｉｔ产生了分裂． ５．２　社区进化的结构特征 研究社区动力学是社会网络分析的目标之一， 什么样的结构特征会影响社区的进化是我们关注的 焦点．本文使用的结构特征如下： 特征１．社区间的平均距离，指社区间所有节点 对最短路径和的均值； 特征２．社区间直接连接的节点数目以及它们 所构成的图的聚类系数； 特征３．每一社区中与另一社区直接连接的节 点数目以及它们所构成图的聚类系数； 特征４．社区中节点的数目和它的聚类系数． ９４７４期 窦炳琳等：基于结构的社会网络分析 为了判断哪些结构特征在社区进化中起主导作 用，我们将这些数据输入ＢＰ神经网络来进行评估． 把一段时间内社区进化中发生的事件划分为训练样 本和检验样本，通过控制不同结构特征的输入建立 多个神经网络，根据不同神经网络的预测精度决定 这些结构或它们的组合在社区进化中的影响力．我 们使用 Ｍａｔｌａｂ　７．８作为神经网络实现的工具，实验 环境为Ｉｎｔｅｌ　ＣＰＵ　３．２ＧＨｚ主频、４ＧＢ内存、Ｗｉｎ－ ｄｏｗｓ　７操作系统．所有神经网络都具有相同的三层 结构，学习算法使用ＬＭ算法．神经网络的输入层包 含９个神经元，对应于上述不同的结构特征；输出层 有１个神经元，传递函数使用线性函数．隐含层传递 函数使用ｓｉｇｍｏｉｄ，并根据经验公式Ｈ＝ Ｉ＋槡 Ｏ＋α 来确定隐含层神经元的个数，其中 Ｈ、Ｉ、Ｏ 分别为 隐含层、输入层和输出层的神经元个数，α为１～１０ 之间的常数．据此，神经网络隐含层的节点数可取 ５～１４，经反复实验后确定为１１，如表１所示（由于 训练网络达到目标误差所需的次数与初始权值有 关，表中给出的是１０次重新初始化权值后训练次数 的均值）．采用５０　０００个样例训练这样的神经网络 所需的平均时间为４５５．２ｓ，这对于文中的实验从效 率上讲是可行的． 表１　隐含层节点数的选择 隐含层节点数 训练次数 隐含层节点数 训练次数 ５　 ５５．３　 １０　 ４６．１ ６　 ５４．８　 １１　 ４２．９ ７　 ５２．２　 １２　 ４５．５ ８　 ５０．９　 １３　 ４８．２ ９　 ４８．６　 １４　 ５３．７ 为了评估不同神经网络的预测能力，我们使用 受试者操作特性（Ｒｅｃｅｉｖｅｒ　Ｏｐｅｒａｔｉｏｎ　Ｃｈａｒａｃｔｅｒｉｓ－ ｔｉｃ，ＲＯＣ）曲线［４９］，它能兼顾灵敏度（ｓｅｎｓｉｔｉｖｉｔｙ）和 特异性（１－ｓｐｅｃｉｆｉｃｉｔｙ）要求，以该曲线下面积（ｔｈｅ Ａｒｅａ　Ｕｎｄｅｒ　ＲＯＣ　Ｃｕｒｖｅ，ＡＵＣ）作为量化指标可以 直观有效地帮助比较不同分类器的性能．我们主要 讨论产生社区融合与分裂事件的特征条件．对于 ＤＢＬＰ和Ｆａｃｅｂｏｏｋ的数据集而言，我们得到了一致 的结论．限于篇幅，我们在下文中只具体讨论ＤＢＬＰ 数据的实验结果． ５．２．１　融　合 考察ＤＢＬＰ中从１９９６年到２００６年间的数据， 符合条件｜Ｖｉｔ∩Ｖｋｔ＋１｜＞｜ Ｃｉｔ｜ ２ 和｜Ｖｊｔ∩Ｖｋｔ＋１｜＞｜ Ｃｊｔ｜ ２ 的社区共计５７２２对，其中有７６８对社区产生了融 合．我们计算得到这些社区的特征数据，并使用 ４０００（包含５５０对产生融合的社区）对社区数据作为 神经网络的训练样本，其余数据作为检验样本，构造 了４个神经网络进行预测．这些特征对社区融合的 预测精度如图１１（ａ）所示． 图１１　不同社区结构特征的ＲＯＣ曲线及其ＡＵＣ值 从图１１（ａ）中可以看到，使用不同的特征对于 社区融合预测有较大差异．特征４、３、２的ＲＯＣ曲线 下面积分别为０．５５６３、０．６９２２和０．７１５０，而使用所 有特征进行预测的准确度则达到０．８３４９．也就是说 ＲＯＣ曲线越凸，其下面积也就越大，对系统的灵敏 度和特异度兼顾性越好，那么对应的网络结构预测 性能就越高．由此，我们可以认为特征２在社区融合 的过程中扮演着重要的角色．为了进一步验证特征２ 对社区融合的影响，我们在ＤＢＬＰ数据的５７２２对社 区中找到有直接连接的社区共计３７５１对，其中产生 融合的社区有４０９对．计算社区间直接连接节点和 边所构成的图的聚类系数，统计它们分别位于０～１ 平均划分的１０个区间内的对数以及产生融合的社 区的对数，近似地将两者之比作为社区融合的概率． 从图１２（ａ）中我们可以看到社区间的聚类系数增 加，则它们产生融合的机会越大．对Ｆａｃｅｂｏｏｋ数据 采用同样的方法进行考察可以得到同样的结果，如 图１１（ｂ）和１２（ｂ）所示． ０５７ 计　　算　　机　　学　　报 ２０１２年 图１２　聚类系数对社区融合概率的影响 ５．２．２　分　裂 从１９９６年到２００６年间的ＤＢＬＰ数据中，符合 条件｜Ｖｊｔ＋１∩Ｖｉｔ｜＞｜ Ｃｊｔ＋１｜ ２ 和｜Ｖｋｔ＋１∩Ｖｉｔ｜＞ Ｃｋｔ＋１ ２ 的 社区共计３８１１对，其中有４７５对社区由同一社区分 裂产生．同样使用神经网络对社区分裂进行预测，训 练样本为２５００对（其中包含３００对社区由同一社区 分裂而产生），其余数据作为检验样本． 表２　不同社区特征的ＡＵＣ值 ＤＢＬＰ　ＡＵＣ　 Ｆａｃｅｂｏｏｋ　ＡＵＣ 特征２　 ０．５１３８　 ０．６４４７ 特征３　 ０．６２２９　 ０．６１２３ 特征４　 ０．６７１０　 ０．７３９４ 所有特征 ０．７４５１　 ０．８０１６ 从表２ＤＢＬＰ　ＡＵＣ列中可以看到，使用特征４ 对社区的分裂进行预测有较高的精度．我们计算 ＤＢＬＰ数据中４７５个产生分裂社区的聚类系数，观察 聚类系数与社区分裂的关系．从图１３（ａ）中可以看到 社区的聚类系数越高，它产生分裂的可能性就越小． 同样，Ｆａｃｅｂｏｏｋ数据的实验结果在表２Ｆａｃｅｂｏｏｋ ＡＵＣ列和图１３（ｂ）中给出，可以看到其社区分裂也 与该社区的聚类系数密切相关． 图１３　聚类系数对社区分裂概率的影响 ６　结　论 本文研究了社会网络的类型、性质和社区进化 的结构特征．本文主要使用ＤＢＬＰ和Ｆａｃｅｂｏｏｋ数据 集构建网络，采用角色连接轮廓方法从结构上将它 们划分为外围串类型；本文验证了社会网络的无标 度分布、直径缩减和稠化性质，发现社会网络中社区 大小服从幂律分布，规模中等的社区主要呈现星型 结构；发现社会网络中存在紧密连接且直径较小的 核心结构；本文基于事件框架研究了社会网络中社 区结构的进化特征，发现社区间的融合很大程度上 取决于社区间直接连接的节点所构成网络的聚类系 数，而社区的分裂则与该社区的聚类系数相关．本文 的进一步工作是提出新的社区进化分析方法，深入 挖掘影响社区进化的结构特征，并建立相应的演化 模型． 社会网络是以人为中心构建的网络，与它相关 的研究成果对人们的工作生活有着潜在的影响．互 联网的发展和各种社交网站的出现也为我们提供了 实验平台，并为计算机相关学科的研究带来了新的 挑战和机遇．社会网络所表现出来的各种性质是如 何形成的，是否存在一个理论模型能够解释在个体 与个体交互中涌现出来的这些特征？不同的网络拓 １５７４期 窦炳琳等：基于结构的社会网络分析 扑结构与个体的行为如何相互产生影响？如何刻画 和控制信息在社会网络上的传播？等等，这些是需要 我们研究和解决的问题． 参 考 文 献 ［１］ Ｍｉｌｇｒａｍ　Ｓ．Ｔｈｅ　ｓｍａｌｌ－ｗｏｒｌｄ　ｐｒｏｂｌｅｍ．Ｐｓｙｃｈｏｌｏｇｙ　Ｔｏｄａｙ， １９６７，２（１）：６０－６７ ［２］ Ｗａｔｔｓ　Ｄ　Ｊ，Ｓｔｒｏｇａｔｚ　Ｓ　Ｈ．Ｃｏｌｌｅｃｔｉｖｅ　ｄｙｎａｍｉｃｓ　ｏｆ‘ｓｍａｌｌ－ ｗｏｒｌｄ’ｎｅｔｗｏｒｋｓ．Ｎａｔｕｒｅ，１９９８，３９３（６６８４）：４４０－４４２ ［３］ Ｂａｒａｂｓｉ　Ａ　Ｌ，Ａｌｂｅｒｔ　Ｒ．Ｅｍｅｒｇｅｎｃｅ　ｏｆ　ｓｃａｌｉｎｇ　ｉｎ　ｒａｎｄｏｍ ｎｅｔｗｏｒｋｓ．Ｓｃｉｅｎｃｅ，１９９９，２８６（５４３９）：５０９－５１２ ［４］ Ｌｅｓｋｏｖｅｃ　Ｊ，Ｌａｎｇ　Ｋ　Ｊ，Ｄａｓｇｕｐｔａ　Ａ，Ｍａｈｏｎｅｙ　Ｍ　Ｗ．Ｓｔａｔｉｓ－ ｔｉｃａｌ　ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｉｎ　ｌａｒｇｅ　ｓｏｃｉａｌ　ａｎｄ　ｉｎ－ ｆｏｒｍａｔｉｏｎ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１７ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ（ＷＷＷ）．Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ， ２００８：６９５－７０４ ［５］ Ｍｉｓｌｏｖｅ　Ａ，Ｍａｒｃｏｎ　Ｍ，Ｇｕｍｍａｄｉ　Ｋ　Ｐ，Ｄｒｕｓｃｈｅｌ　Ｐ，Ｂｈａｔｔａ－ ｃｈａｒｊｅｅ　Ｂ．Ｍｅａｓｕｒｅｍｅｎｔ　ａｎｄ　ａｎａｌｙｓｉｓ　ｏｆ　ｏｎｌｉｎｅ　ｓｏｃｉａｌ　ｎｅｔ－ ｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　ＡＣＭ　ＳＩＧＣＯＭＭ　Ｃｏｎｆｅｒｅｎｃｅ ｏｎ　Ｉｎｔｅｒｎｅｔ　Ｍｅａｓｕｒｅｍｅｎｔ　Ｃｏｎｆｅｒｅｎｃｅ （ＩＭＣ）．Ｓａｎ　Ｄｉｅｇｏ， Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，２００７：２９－４２ ［６］ Ｗａｋｉｔａ　Ｋ，Ｔｓｕｒｕｍｉ　Ｔ．Ｆｉｎｄｉｎｇ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｉｎ ｍｅｇａ－ｓｃａｌｅ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１７ｔｈ　Ｉｎｔｅｒｎａ－ ｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ （ＷＷＷ）．Ｂａｎｆｆ， Ａｌｂｅｒｔａ，Ｃａｎａｄａ，２００７：１２７５－１２７６ ［７］ Ｋｗａｋ　Ｈ，Ｃｈｏｉ　Ｙ，Ｅｏｍ　Ｙ　Ｈ，Ｊｅｏｎｇ　Ｈ，Ｓｕｅ　Ｍ．Ｍｉｎｉｎｇ　ｃｏｍ－ ｍｕｎｉｔｉｅｓ　ｉｎ　ｎｅｔｗｏｒｋｓ：Ａ　ｓｏｌｕｔｉｏｎ　ｆｏｒ　ｃｏｎｓｉｓｔｅｎｃｙ　ａｎｄ　ｉｔｓ　ｅｖａｌ－ ｕａｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　９ｔｈ　ＡＣＭ　ＳＩＧＣＯＭＭ　Ｃｏｎｆｅｒｅｎｃｅ ｏｎ　Ｉｎｔｅｒｎｅｔ　Ｍｅａｓｕｒｅｍｅｎｔ　Ｃｏｎｆｅｒｅｎｃｅ （ＩＭＣ）．Ｃｈｉｃａｇｏ， Ｉｌｌｉｎｏｉｓ，ＵＳＡ，２００９：３０２－３１４ ［８］ Ｗｈｉｔｅ　Ｓ，Ｓｍｙｔｈ　Ｐ．Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｅｓｔｉｍａｔｉｎｇ　ｒｅｌａｔｉｖｅ　ｉｍｐｏｒ－ ｔａｎｃｅ　ｉｎ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　９ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎ－ ｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ Ｍｉｎｉｎｇ（ＫＤＤ）．Ｗａｓｈｉｎｇｔｏｎ　Ｄ．Ｃ．，ＵＳＡ，２００３：２６６－２７５ ［９］ Ｌｉ　Ｙ　Ｍ，Ｌａｉ　Ｃ　Ｙ，Ｃｈｅｎ　Ｃ　Ｗ．Ｉｄｅｎｔｉｆｙｉｎｇ　ｂｌｏｇｇｅｒｓ　ｗｉｔｈ　ｍａｒ－ ｋｅｔｉｎｇ　ｉｎｆｌｕｅｎｃｅ　ｉｎ　ｔｈｅ　ｂｌｏｇｏｓｐｈｅｒｅ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１１ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｅｌｅｃｔｒｏｎｉｃ　Ｃｏｍｍｅｒｃｅ（ＩＣＥＣ）． Ｔａｉｐｅｉ，Ｔａｉｗａｎ，Ｃｈｉｎａ，２００９：３３５－３４０ ［１０］ Ｌｅｓｋｏｖｅｃ　Ｊ，Ｂａｃｋｓｔｒｏｍ　Ｌ，Ｋｕｍａｒ　Ｒ，Ｔｏｍｋｉｎｓ　Ａ．Ｍｉｃｒｏ－ ｓｃｏｐｉｃ　ｅｖｏｌｕｔｉｏｎ　ｏｆ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１４ｔｈ ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓ－ ｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ（ＫＤＤ）．Ｌａｓ　Ｖｅｇａｓ，Ｎｅｖａｄａ，ＵＳＡ， ２００８：４６２－４７０ ［１１］ Ｌｉｎ　Ｙ　Ｒ，Ｃｈｉ　Ｙ，Ｚｈｕ　Ｓ，Ｓｕｎｄａｒａｍ　Ｈ，Ｔｓｅｎｇ　Ｂ．Ａｎａｌｙｚｉｎｇ ｃｏｍｍｕｎｉｔｉｅｓ　ａｎｄ　ｔｈｅｉｒ　ｅｖｏｌｕｔｉｏｎｓ　ｉｎ　ｄｙｎａｍｉｃ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ． ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｆｒｏｍ　Ｄａｔａ （ＴＫＤＤ），２００９，３（２）：１－３１ ［１２］ Ｔａｎｇ　Ｊ，Ｓｕｎ　Ｊ，Ｗａｎｇ　Ｃ，Ｙａｎｇ　Ｚ．Ｓｏｃｉａｌ　ｉｎｆｌｕｅｎｃｅ　ａｎａｌｙｓｉｓ　ｉｎ ｌａｒｇｅ－ｓｃａｌｅ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１５ｔｈ　ＡＣＭ　ＳＩＧＫ－ ＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ Ｄａｔａ　Ｍｉｎｉｎｇ（ＫＤＤ）．Ｐａｒｉｓ，Ｆｒａｎｃｅ，２００９：８０７－８１５ ［１３］ Ｋｉｍｕｒａ　Ｍ，Ｓａｉｔｏ　Ｋ，Ｍｏｔｏｄａ　Ｈ．Ｂｌｏｃｋｉｎｇ　ｌｉｎｋｓ　ｔｏ　ｍｉｎｉｍｉｚｅ ｃｏｎｔａｍｉｎａｔｉｏｎ　ｓｐｒｅａｄ　ｉｎ　ａ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｆｒｏｍ　Ｄａｔａ（ＴＫＤＤ），２００９，３（２）： １－２３ ［１４］ Ｗａｎｇ　Ｘｉａｏ－Ｆａｎ，Ｌｉ　Ｘｉａｎｇ，Ｃｈｅｎ　Ｇｕａｎ－Ｒｏｎｇ．Ｔｈｅｏｒｙ　ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｃｏｍｐｌｅｘ　Ｎｅｔｗｏｒｋｓ．Ｂｅｉｊｉｎｇ：Ｔｓｉｎｇｈｕａ　Ｕｎｉ－ ｖｅｒｓｉｔｙ　Ｐｒｅｓｓ，２００６（ｉｎ　Ｃｈｉｎｅｓｅ） （汪小帆，李翔，陈关荣．复杂网络理论及其应用．北京：清 华大学出版社，２００６） ［１５］ Ｃｏｓｔａ　Ｌ　ｄａ　Ｆ，Ｒｏｄｒｉｇｕ