复杂网络中社团结构划分的快速分裂算法

第２８卷第４期２０１１年４月

计算机应用研究

ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ

Ｖ０１．２８Ｎｏ．４

Ａｐｒ．２０１１

复杂网络中社团结构划分的快速分裂算法

张聪，沈惠璋，李峰

（上海交通大学安泰经济管理学院，上海２０００５２）

摘要：针对已有分裂算法时间复杂度较高，不适用于社团数目未知的大型网络等问题，借鉴电压谱分割算法

和ＧＮ算法的思想，提出以扩散距离为分割依据，以模块度函数为社团结构划分满意度的快速分裂算法。实验结果表明，与已有的社团结构划分算法相比，基于扩散距离的快速分裂算法能够得到高质量的社团结构，其时间复杂度较低，不仅对稀疏网络能够快速运算，对非稀疏网络更能高效求解，这进一步体现出算法具有较高的稳定性。

关键词：复杂网络；社团结构；分裂算法；模块度；扩散距离中图分类号：ＴＰｌ８１

文献标志码：Ａ

文章编号：１００１—３６９５（２０１１）０４－１２４２—０３

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１．３６９５．２０ｌｌ，０４．０１０

Ｆａｓｔｓｐｌｉｔｔｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｐａｒｔｉｔｉｏｎｉｎｇｃｏｍｍｕｎｉｔｙ

ＺＨＡＮＧ

ｓｔｒｕｃｔｕｒｅ

ｉｎｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ

Ｃｏｎｇ，ＳＨＥＮＨｕｉ—ｚｈａｎｇ，ＬＩＦｅｎｇ

（Ａｒｅａ／ＣｏｌｌｅｇｅｏｆＥｃｏｎｏｍｉｃｓ＆Ｍａｎａｇｅｍｅｎｔ，ＳｈａｎｇｈａｉＪｉｎｏｔｏｎｇ

Ａｂｓｔｒａｃｔ：Ｍｏｓｔｏｆｔｈｅｐｍｐｏｓｅｄｓｐｌｉｔｔｉｎｇａｌｇｏｒｉｔｈｍｓｉｔｙａｎｄｕｎｋｎｏｗｎ

ａｒｅ

Ｕｎｉｗｒｓｉ牡，鼬８，劬戚２０００５２，Ｃｈｉｎａ）

ｎｏｔ

ｓｕｉｔａｂｌｅｆｏｒｖｅｒｙｌａｒｇｅｎｅｔｗｏｒｋｓｂｅｃａｕｓｅｏｆｔｈｅｉｒｈｉｇｈｔｉｍｅｃｏｍｐｌｅｘ—

ｑｕａｎｔｉｔｙ

ａ

ｏｆｃｏｍｍｕｎｉｔｙｎｕｍｂｅｒ．ＲｅｆｅｒｅｎｃｉｎｇｔｈｅｖｏｌｔａｇｅｓｐｅｃｔｒｕｍｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄＧＮａｌｇｏｒｉｔｈｍ，

ｏｎ

ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄ

ｗａｓ

ｆａｓｔｓｐｌｉｔｔｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄ

ｄｉｆｆｕｓｉｏｎｄｉｓｔａｎｃｅａｎｄｔｈｅｍｏｄｕｌａｒｉｔｙｆｕｎｃｔｉｏｎ．Ｉｔｓｓｅｇｍｅｎｔａｔｉｏｎｂａｓｉｓ

ｔｈｅｄｉｆｆｕｓｉｏｎ

ｄｉｓｔａｎｃｅ，ａｎｄ

ｓｔｒｕｃｔｕｒｅ

ｔｈｅａｂｉｌｉｔｙｏｆｍｏｄｕｌａｒｉｔｙｆｕｎｃｔｉｏｎｃｏｕｌｄｆｉｎｄｔｈｅｂｅｓｔｃｏｍｍｕｎｉｔｙｎｕｍｂｅｒｉｎｌａｒｇｅｎｅｔｗｏｒｋｓ．Ｅｘ－

ｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｈａｓｎｉｎｇｃｏｍｍｕｎｉｔｙ

ｂｅｔｔｅｒｐａｒｔｉｔｉｏｎｉｎｇａｂｉｌｉｔｙａｎｄｌｏｗｅｒｔｉｍｅｃｏｍｐｌｅｘｉｔｙｔｈａｎｔｈｅｐｒｏｐｏｓｅｄｐａｒｔｉｔｉｏ—

ｃａｐａｂｌｅｏｆｆａｓｔｏｐｅｒａｔｉｏｎｆｏｒｔｈｅｓｐＩａｒｓｅｎｅｔｗｏｒｋ，ｂｕｔａｌｓｏｆｏｒｔｈｅｎｏｎ－ｓｐａｒｓｅ

ａｌｇｏｒｉｔｈｍ；ｍｏｄｕｌａｒｉｔｙ；ｄｉｆｆｕｓｉｏｎｄｉｓｔａｎｃｅ

ａｌｇｏｒｉｔｈｍｓ．Ｎｏｔｏｎｔｙｉｔｉｓ

ｎｅｔｗｏｒｋ，ｗｈｉｃｈｒｅｆｌｅｃｔｓｔｈｅａｌｇｏｒｉｔｈｍｈａｓｈｉｇｈｓｔａｂｉｌｉｔｙ．Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘ

ｎｅｔｗｏｒｋｓ；ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ；ｓｐｌｉｔｔｉｎｇ

’许多研究领域中的复杂系统都可以被表述成由节点或顶点集通过线或边的连接而构成的网络，如现实世界中的互联网、万维网、新陈代谢网、食物链网、神经网络、通信与分布式网络以及社会网络【ｌｊｌ。近年来在对以上网络的研究中发现它们存在一个共同的性质，称为社团结构。它是指整个网络由若干个组或簇构成，组内节点间的连接比较紧密，而组间节点的连接比较松散＿Ｊ。发现网络中的社团结构并对其进行分析是了解整个网络结构、特征和功能的重要途径，在生物学、物理学、计算机科学和社会学研究领域中都有着广泛的应用¨’４Ｊ。

网络中社团结构的划分方法主要有四类：分裂方法、凝聚方法、谱分析法和搜索方法口“引，其中分裂方法是近年来研究比较广泛的一类。计算机科学中的图分割是该类方法的研究起源。由Ｇｉｒｖａｎ等人口１提出的ＧＮ算法是一种典型的分裂方法，它的基本思想是通过不断地从网络中移除介数最大的边来达到划分网络的目的；而Ｒａｄｉｃｃｈｉ等人∞１则是利用边聚类系数代替ＧＮ算法中的边介数来作为发现社团结构的依据；Ｔｓｕｃｈ－ｉｕｒａ等人【６０引入了布朗微粒来衡量网络中两个节点之间的距离；ｚＩｌｏｎ【７舟１基于这种距离矩阵，引入了相异性指数来表示两个最相邻节点属于同一个社团的可能性大小；Ｆｏｒｔｕｎａｔｏ等人归１提出了一种利用信息中心度来划分网络的算法；赵风霞等

收稿日期：２０１０，１１－０３；修回日期：２０１０—１２－０９资助项目（２００７０２４８０５４）

人¨训在Ｆｏｒｔｕｎａｔｏ的信息中心度的基础上，提出了一种基于Ｋ—ｍｅａｎｓ聚类算法的划分方法；李峻金等人…１将社团结构划分问题转换为空间数据聚类问题，将粒子群算法应用到社团结构的划分。以上算法均可得到层次结构的社团结构，但是它们也有各自的局限，例如ＧＮ算法的边介数计算的时间复杂度较高，又需反复计算，总时间复杂度为Ｄ（ｍ２ｎ）；Ｒａｄｉｃｃｈｉ的算法则在很大程度上依赖于网络中存在的三角形数目；基于相异性的算法需重复计算距离矩阵和相邻节点的相异性指数；基于信息中心度的算法同样要反复计算移除每条边后造成的信息有效率减小的相对量；基于Ｋ—ｍｅａｎｓ聚类算法和基于粒子群算法的划分方法则需将网络结构转换为空间数据后再运算得到聚类，而这些转换过程将在不同程度上造成数据的偏差和失真。本文在分析上述算法优缺点的基础上，提出一种网络社团结构快速分裂算法。该算法借鉴电阻网络电压谱的思想，通过一系列的迭代过程，不断找到最大“电阻”或“距离”所对应的边，切断这些边。从而达到自然分割为层次社团结构的目的。

１

电压谱分割法

本算法是以ｗｕ等人ｍ１的基于电阻网络电压谱的快速谱

分割法为基础而提出的（下文简称ＷＨ算法）。下面简要介绍

基金项目：国家自然科学基金资助项目（７１０７１０９６）；高等学校博士学科点专项科研基金

作者简介：张聪（１９７５．），男，安徽阜阳人，讲师，博士研究生，主要研究方向为复杂网络、数据挖掘（ｇ＿ｅ—ｃｎ＠１６３．ｃｏｉｎ）；沈惠璋（１９５８一）。男，天津人，教授，博导，博士，主要研究方向为数据挖掘、网络安全；李峰（１９７６－），男，辽宁辽阳人．讲师，博士研究生，主要研究方向为复杂网络、数据挖掘．

第４期张聪，等：复杂网络中社团结构划分的快速分裂算法

・１２４３・

ＷＨ算法：无向加权图Ｇ＝（ｙ，Ｅ，∽，Ｖ是节点集，Ｅ是边集，ｎ

人定义了一个用以评价网络划分满意度的指标，称为模块是节点个数，ｍ是边的条数，Ｗ＝［埘。］。。。是边的权值矩阵。假度¨“１¨（ｍｏｄｕｌａｒｉｔｙ）。模块度函数定义为

设Ｇ可以划分为两个社团Ｇ，和Ｇ２，且已知节点Ａ和日分别属于这两个社团。初始时令节点Ａ为源节点，电压值为ｌ，而节种加。叁［∞舁一ｃ黼，２】

㈤

点Ｂ为终节点，电压值为０，其他节点的电压值也为Ｏ，即Ｋ＝其中：只是指将网络划分为ｋ个社团的一种划分情况，Ｌ（∥，１，％＝０，…，Ｋ＝Ｏ。将网络中的每条边都视为一个电阻Ｒ。＝矿）＝∑。ｅＶ＇ｄｅ旷埘（１Ｊ）。模块度函数Ｑ的物理含义是：网络中埘ｉ１，整个网络就可以看做一个电阻网络，从而利用Ｋｉｒｅｈｈｏｆｆ社团内部的边的比例减去在同样的社团结构下随机连接节点定理求得各个节点的电压值。然后选取一个电压阈值Ｖ（０＜的边的比例的期望值。Ｑ值越大，说明网络的社团结构越Ｖ＜１），若节点ｉ的电压值Ｋ＞Ｖ，则认为它属于源节点Ａ所在明显。

的社团，否则属于终节点曰所在的社团。一般情况下，利用本文使用模块度函数Ｑ来衡量社团划分的结果，在网络Ｋｉｒｃｈｈｏｆｆ定理求各节点的电压，算法时间复杂度为０（ｎ３）。逐渐分裂的过程中，Ｑ值会逐渐增加，当划分为七。。个社团时ｗｕ等人进一步简化了算法，按照式（１）运算，只需迭代一定次将达到峰值，之后开始减少，那么算法的终止条件就是当Ｑ值数，使电压谱达到一定精度，就足够进行网络的一分为二。

减小时算法停止。

１

１

２．３算法描述

Ｋ

２玄（。最Ｅ匕２彘孙‰ｆｏｒ

ｉ＝３，…，ｎ（１）

本算法是一种社团划分的分裂算法，在ＷＨ算法的基础划分时，将每个节点的电压值列在电压谱中，然后只要在上提出了对所有节点都运行式（１），在迭代过程中，逐渐切断接近中间位置且电压存在最大差值的两根谱线之间划开，就可扩散距离最大的边，达到快速分割成为社团的目的。采用模块以将整个网络分为两个社团。简化后计算速度大大改善，算法度函数作为衡量最佳社团结构的标准，即通过模块度函数确定的时间复杂度为Ｄ（ｎ＋ｍ）。

最佳的社团数目。具体算法如下：

以上方法是针对二分网络的情况，对于多社团的情况，Ｗｕｉｎｐｕｔ：复杂网络Ｇ＝（Ｖ，Ｅ，Ｗ），社团数目ｋ＝１，确定最大扩散距离等人做了进一步的推广，还是以电压谱为基本运算，而后应用边所需的累计数Ｊ。

统计的方法得到多个社团。虽然该算法时间复杂度较低，但是ｏｕｔｐｕｔ：社团划分结果‰。。

ａ）对每个节点赋随机数Ｋ＝ｒａｎｄｏｒｎｆｏｒｌ＝１，…，ｒｔ。必须已知网络社团数目，这大大缩小了算法的适用范围。

ｂ）对每个节点计算式（３）。

Ｋ

２

基于扩散距离的快速分裂算法

２吉（。五Ｅ嵋２竞邑巧～ｆｏｒ括ｌ・…，－．

（３）

ｃ）通过计算网络中相连接节点的数值差的绝对值得到边的扩散距离，见式（４）。

２．１

扩散距离与算法思路

Ｄ。＝ａｂｅ（Ｋ—Ｅ）（ｉｊ）ＥＥｆｏｒｇ＝１，…，ｍ

（４）针对ＷＨ算法的限制条件，本文算法无须预先知道网络

ｄ）求本次循环中的ｍａｘ（Ｄ。），记录此边的编号ｇ。。。

ｅ）如果最近Ｊ次循环中的ｇ一不同，转到ｂ）；如果相同，即确定最

社团数目，也不需要预先设定源节点和终节点，而是在初始时大扩散距离边。

赋给每个节点随机数；迭代过程中每一步对所有节点做加权平ｆ）切断最大扩散距离边，在Ｅ中将该边删除，在Ｗ中将该权值设为０。

均运算，即所有节点都运算式（１）；然后用相邻节点差值的绝ｇ）如果当前的社团数目ｋ未增加，转到ａ）。

对值代表每条边的扩散距离（类似于ＷＨ算法中的电位差）；果小于上次的模块度即为最大模块度，其所对应的社团结构‰。是最

ｈ）按照式（２）计算模块度ｑ，如果大于上次的模块度，转到ａ）；如

在迭代过程中，虽然网络中所有节点的值都会逐渐趋近于某个佳社团结构划分，算法终止。

固定数值，但是由于网络中节点连接的疏密不同，社团内部节２．４时间复杂度分析

点的数值会相对聚集在一起，而社团之间的节点数值则会差距从算法描述中可以看出，ａ）赋随机数的时间复杂度为０相对较大，这就是本文划分社团的基础。

（ｎ）；ｂ）～ｄ）是以边为核心的运算，时间复杂度为０（ｍ）；要找ＷＨ算法是通过计算节点电压，然后利用电位差来分割网到最大扩散距离边所需的循环次数，需要所有节点的数值扩散络的，而本文算法是利用扩散或传播的概念来划分网络的。

到比较平均的程度，这明显取决于网络的平均路径长度Ｌ；算ＷＨ算法中源节点和终节点的数值（电压）是固定不变的，本文

法最终切断边的条数在最差情况下是ｍ，但在一般情况下，切算法中所有节点的数值都在变化，这个变化其实是不断的扩散断边的条数与网络节点数和边数目是无关的，所以算法在最差或传播过程，虽然最终所有节点都会趋于一致，但是在这个过情况下的时间复杂度是０（Ｌｍ２）。需要指出的是，ＷＨ算法在

程中连接紧密的节点间的差异明显小于连接松散的节点间的二分网络时的时间复杂度应是０（加），而其在划分多社团的

差异，这个节点差异其实就是上述边的扩散距离。在迭代一定最差情况下与本算法的时间复杂度是一样的，因为计算节点电次数后，网络中的最大扩散距离的边趋于稳定，即某条边在迭压的过程实际上也是一个扩散过程，那么也是取决于网络的平代一定次数后会稳定成为最大扩散距离边（在下文中讨论迭均路径长度￡的。．当网络是稀疏网络时，ｍ一托，Ｌ—ｍ，算法的代次数问题）。切断最大扩散距离所对应的边，形成新的网时间复杂度是０（ｎ３），与ＧＮ算法的时间复杂度是一样的；当络，再进行上述初始赋值和迭代过程，再切断最大边，如此重边数目远大于节点数时，即ｍ＞＞ｎ，平均路径长度将远小于边复，会将网络逐渐分割开来。当满足算法终止条件时，即完成数目，即Ｌ＜＜ｍ，而且最终切断边的条数一般来说是远小于ｍ了划分网络社团的任务。的，那么算法的时间复杂度就约等于０（ｍ）。可见，本算法在２．２模块度函数。

边数目远大于节点数的情况下，比ＧＮ等分裂算法有较大的优所有的网络社团结构划分算法都需要一个评价准则来判势，而且时间复杂度对于网络的规模是不敏感的，对于社团结断划分得到的社团结构的合理性和有效性。因此，Ｎｅｗｍａｎ等

构较强的网络往往很快就分裂成几个独立的部分，这样就大大

２４４

计算机＆ｍ研究弟２８巷

减小Ｔ后续∞汁算＆

３实验

３’空手道僵￥部月络

ｚｎｃｈｗＭ络是社会嘲络丹析的

个＆典目艇。２０ｍ２

７０年代初期，肺ｈ叫用Ｔ两年的时间来观察美国一所大学中

的§手道俱乐部成员月的月§ｎｅ＊系．从而构造Ｔ谈网络，该俱乐部的±臂。＿校妊２月目Ｂ§提高俱乐部收费问蹲ｍＰ生Ｔ争执，结果诚俱乐部分裂成丁两个分别“±管自枝长为榱。的小俱乐部。月Ｌ中∞＃＾Ｉ自节点３３分别代丧７俱乐部±管Ⅷ《长，Ⅻ左侧∞１８个节点＃右侧∞１６十∞＾＊剖代表ｒ丹裂目的小惧乐部中纳各个成目。苴中节点３是有歧女的．々■边的《接数都是５．ＧＮ算法将节点３划＾左边的牡Ⅻ，￥文算＊将＊点３划＾☆边∞社目。ＺａｅｈⅢｒ５网络日址一步丹裂，得到６个社脚的结粜，如图Ｉ所＊，其中在分裂为３个社目时ａ值４Ⅻ最太ＨＨⅡ自ｍ社目丹＃＆∞点５

６

７“＂１７所

构成的社团时ｐ值最大，网络的层次结构在《步的分裂过程中根清楚地月现出来，如图２所示．其中罔２（ａ）是社厨数逐渐增加时模块度ｐ的变化情Ｍ，（ｈ）为分裂∞目攻结构图．（ａ）Ⅻ（ｂ）ｍ图是相对＆∞：

豁。

目¨ｃｈ３ｒｙⅢ女∞｛｝ｍｍ％＃自∞ｍⅢ＊ｉ月％

『且）

雯

（ｂＪ

月２

ｚⅡＦｈａｒ／目镕自Ｈ¨目∞目＆镕＃目＃＊Ⅸ

３

２羹垦大学撒植球联盟月镕

丰ｉ宴验研究的第＝个网络是美旨大学赣髓球联盟，障塔

十１１５十节点＆示１１５支球队，Ⅲ６１３条曲代表ｒ６１３场赛事。遗§球队破分成若干小组，姆个小组由８—１２点球队组成同组内球队之同的比赛ｇ＆组间球队之间的Ｍ赛多。

麻用本文算法得到的模块度最大时的社团结掏如图３所ｉ，此时社目数为１２，Ｑ＝ｎＨ。图４是随着井裂＊到的社目数目的增加、横块度值的变化情况。从目中Ⅱ知．Ⅱ§十Ｍ镕连渐分裂∞过程中模块度值Ｔ断韭大，但到Ｔ峰值（＆＝１２）“后，０值开始变小。按大学所处的地理位置（１２个地Ｒ）划分时ｐ＝Ｏ她，＊据ＧＮ算法得到的杜团结构与目３ｉ本一致．＃块Ⅲ也ＢＯ５４．№的Ｅ别在于节点”＊月∞社Ｅｆ目。

丹ｇＵ科目ｃｎ算法，ＦＣＭ算法、ｗＨ算法和率文算法计算美目大学橄榄球联Ⅲ网络，Ｍ得豹结果如表Ｉ所ｍ。从※十∞散据日ｍ看出，本文算＊划分＃Ⅻ∞№确率较高。

＾

目４｝ｔ目＆一＊＊＆＊＊目

ｍＬ＊＃＊＊＊ｍｍ＃Ｅ口目＊¨％※＂№

４结束语

￥ｉ借鉴电ｎ、谱分割算法的思想．设１｛Ｔ一种杜目结构蚓丹的快速分裂方法。算法通过｛断地切断扩散距离最太的边宴现社团分裂，“模块度自数作自评价标准得到最佳的杜目结构。与ｅ有的社Ⅷ划分舟※算法目№奉算法时日复杂睦鞍低，划分杜周的准确率高．能够在结构未Ⅻ的大型网络中得到高Ⅲ茸的社Ⅲ结构参考女献：

Ｉ

ＪＥ十Ｍ，｝№，Ｈ＊｝￡女月＃ｇ＊＆＃＆目【Ｍｎ￥：＊

［２】ＭｗＭ…Ｅ

｝＾｝ｍ＊＃．蹦

ＪＭＤｄｕｌ∞…ａｎｄ

ｎ帆㈣ｔｖ。ｌ…＂ｉｎ

ｎｅｔｗｍ

ｓ

。Ｊ

Ｊ

Ｐ—ｅｄｉｎｇ

ｏｆ

ｔｈｅ

ＮⅫｏｎａ｛ＡＣａｄｅｍｙｏｆ

ｓｃＩ—ｓ

ｄ

ｔ№

ＵｎｉｔｅｄＳｔｅｔｅｓｏｆＡｒｎｅｎｃａ

２０００

１０３１２３）：８５７７

８５８２

［３ｌＧＩＸ、『ＡＮＭ，、ＥｗＭ＾ＮＭＲ

Ｊ（碥ｍｕｎｉｌｙ

ｍ……ｍｉｎ州】ｄａｄ

ｓ啪ｍ％“ｔｈｅ州Ｓ自㈣ｆ

ｈｄ。目ｃｍｎＨｗ。＾｝［Ｊ

ｐ眦ｅｅｄｉｎｇｏｆｔｈｅＮａＩ啪ａＩ＾ｏａｄｅｍｙｏｌ

Ａｍｅｒｈ２００２，∞（１２）７８２［

７８２６

：４］ＧＬＥＩＳＥＲｎ

Ｄ＾ＮｏＮＬ

ｃ………ｃ【……【Ｊ］Ａｄｖａｎ嘴

［５］ＩＩＡＤ［（．Ｃｆｌｌ－【，＾ｓⅢＩＩ＾…．ＣＥＣＣＯＮＩｉｎ∞ｎ口ｅｘ∞ｍ

２．００３

６（４）：５６５

５７３

ｌｄＰｎｌ＿々。……¨ｎｔＩ…ｉｎ

Ｆ．ｗ“啪ｎｉｎｇ““

ｅｔｍｒＬ５【Ｊ】ｐｒⅫｅｄｉｎｇ

＾∞ｄ

ｅ｜｜＿ｖ

ｕｎｎｅｄ

１０１（９）・２６５８姗

ｏｆ勘…ｓ“｛ｈｅ

９蝴ｆ＾…２００４

ｏｆｔｈｅＮｅｆｏＭｌ

（Ｔ＃＊１２５０Ⅲ）

・１２５０・

计算机应用研究第２８卷

然后根据社区成员在群体中的角色和地位，绘制如图ｌ所示的小世界社区网络关系图。

阴《苫

Ｚ

１２

瑗测用户已评分项日的数目

图３参数ｚ对ＭＡＥ的影响图４ＭＡＥ对比

５结束语

在社区网络中根据基于内容的个性化推荐算法提供用户

图Ｉ小世界社区网络关系图

有可能感兴趣的信息，不但方便了用户查看，而且还提高了用户查看内容的效率和质量，同时也为企业带来了丰厚的经济利润。使用社区网络分析技术加快了相同兴趣用户的挖掘，小世界社区网络验证了本文提出的解决方案，通过实验结果发现这种算法优于协同过滤算法。在衡量社区网络内容相似性的过程中，加上关键字分析或语义分析，将是本文接下来的研究目标。参考文献：

［１］刘耀庭．社交网络结构研究［Ｄ］．杭州：浙江大学，２００８．［２］ＹＯＵＮＧ

ｐｒｉｖａｃｙ

Ａ

这个图形清晰地反映用户是处于“核心参与者”或“边缘参与者”的地位，以及用户与用户之问的关系。小世界社区网络中有１５个用户，关系数据库中的数据表示这１５个用户之间的相互联系和互动关系。小世界社区网络的密度为０．５０２８、距离是０．６５３、度中心性和接近中心性分别为０．６１２２和０．５２９１。以小世界社区网络关系数据库中的关系为依据，建立关系矩阵，并将该数据命名为ｃｏｕｍｍｕｎｉｔｙ。把ｃｏｕｍｍｕｎｉｔｙ数据导入ＵＣＩＮＥＴ６．０，通过ＳＮＡ得到小世界社区网络中相同兴趣用户聚类结果，如图２所示，发现用户２、１、３在同一个聚类簇中即有共同的兴趣。

Ｉ

７

２

３

Ｌ，ＱＵＡＮ—ＨＡＡＳＥＡ．ＩｎｆｏｒｍａｔｉｏｎｒｅｖｅｌａｔｉｏｎａｎｄＩｎｔｅｍｅｔ

ｏｎ

ｃｏｎｃｅｒｎｓｓｏｃｉａｌｎｅｔｗｏｒｋｓｉｔｅｓ：ａ

ｃａｓｅ

ｓｔｕｄｙｏｆｆａｃｅｂｃｏｋＣｏｍｍｕｎｉｔｉｅｓａｎｄ

［ｃ］／／Ｐｏｍｏｆｔｈｅ

４ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ｏｎ

：２

２ｌ

ｎ

８

Ｔｅｃｈｎｏｌｏｇｉｅｓ．ＮｅｗＹｏｒｋ：ＡＣＭ

ｐｒ－－％，２００９：２６５－２７４．

ｆｏｒ

［３］ＬＩＹｕｎｇ—ｍｉｎｇ，ＨＳＩＡＯＨａｎ—ｗｅｎ．Ｒｅｃｏｍｍｅｎｄｅｒｓｅｒｖｉｃｅ

ｗｏｒｋｂａｓｅｄ

ｓｅｃｉａｌ

ｎｅｔ－

ａｐｐｌｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｅ

ｏｆｔｈｅ１ｌｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅ－

６¨ｎ

５

３¨７

４８６

ｒｅｎｃｅｏｎ

Ｅｌｅｃｔｒｏｎｉｃ

Ｃｏｍｍｅｒｃｅ．ＮｅｗＹｏｒｋ：ＡＣＭＰｒｅｓｓ，２００９：３７８・

３８１．

９”３５

［４］ＷＡＬＴＥＲＦＥ，ＢＡＴＩ＇ＩＳ，１１０ＮＳ，ＳＣｆＩＷＥｒｒＺＥＲＦ．Ａｍｏｄｅｌｏｆ

ｔｒｕｓｔ・ｂａｓｅｄｒｅｃｏｍｍｅｎｄａｔｉｏｎ

ｓｙｓｔｅｍ

ｏｎ

ａ

ａ

ｓｏｃｉａｌ

ｎｅｔｗｏｒｋ［Ｊ］．Ａｕｔｏｎｏ－

ｍ儿２

４●

ｍｏｕｓＡｇｅｎｔｓａｎｄＭｕｌｔｉ・ａｇｅｎｔｓ

加¨堙Ｕ

Ｓｙｓｔｅｍｓ，２００６，１６（１）：５７—７４．

ｎｅｔｗｏｒｋｉｎｔｈｅ

［５］ＷＵＨｕｉ－ｊｕ，ＴＩＮＧ

Ｉ

Ｈ，ＷＡＮＧＫａｉ－ｙｕ．Ｃｏｍｂｉｎｉｎｇｓｏｃｉａｌ

ｔｏ

图２用户兴趣聚类树

４．２算法验证

根据小世界社区网络用户规模和用户信息结合ＭＡＥ评价方法，首先进行相似度阈值ｚ的优化，以提高内容相似性算法效率。实验结果如图３所示，当ｚ一０．４３时，ＭＡＥ最小。

协同过滤算法是目前应用最为广泛的个性化推荐算法。由于ＭＡＥ的值越小，推荐精度越高，且推荐精度随着预测用户评分数目的增多而提高。由图５可以发现，本文提出的研究方案（简称为ＴＢＣ）在社区网络中推荐内容的精度更高。

（上接第１２４４页）ｆ６１

ＴＳＵＣＨＩＵＲＡＨ，ＯＧＡＴＡＭ．ＴＡＮＡＫＡＹ，以ａ１．Ｅｌｅｃｔｒｏｎｉｃｓｔａｔｅｓ

ａｎａｌｙｓｉｓａｎｄＷｅｂｍｉｎｉｎｇｔｅｃｈｎｉｑｕｅｓ

ｄｉｓｃｏｖｅｒｉｎｔｅｒｅｓｔ

ｇｒｏｕｐｓ

ｂｌｏｇｓｐａｃｅ［Ｃ］／／Ｐｒｅｃｏｆｔｈｅ４ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ＣｏｍｐｕｔｉｎｇＩｎｔｅｍａｔｉｏｎ

ｏｎＩｎｎｏｖａｔｉｖｅ

ａｎｄＣｏｎｔｒ０１．２００９：１１８０－１１８３．

［６］曾春，邢春晓，周立柱．个性化服务技术综述［Ｊ］．软件学报，２００２，

１３（１０）：１９５２—１９６１．

［７］ＢＡＬＡＢＡＮＯＶＩＣＭ，ＳＨＯＨＡＭＹ．Ｃｏｎｔｅｎｔ．ｂａｓｅｄｃｏｌｌａｂｏｍｔｉｖｅ

ｍｅｎｄａｔｉｏｎ［Ｍ］．ＮｅｗＹｏｒｋ：ＡＣＭＰｒｅｓｓ，１９９７：６６－７２．

ｌ＇ｃｃｏｍ．

［８］ＨＥＲＬＯＣＫＥＲＪ，ＫＯＮＳＴＡＮＪ．Ｅｖａｌｕａｔｉｎｇｃｏｌｌａｂｏｒａｔｉｖｅｆｉｌｔｅｒｉｎｇ

ｏｍｍｅｎｄｅｒ

ｒｅｃ—

ｓｙｓｔｅｍｓ［Ｊ］．ＡＣＭＴｒａｎｓ

ｏｎ

ＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍｓ，

２００４．２２（１）：５－５３．

ｏｆ

Ａｍｅｄｃａ，２００７，１０４（３９）：１５２２４－９．

Ｖ

［１３］ＢＬＯＮＤＥＬ

ｕｎｆｏｌｄｉｎｇｏｆＳｔａｔｉｓｔｉｃａｌ

１０００８．

Ｄ，ＧＵＩＬＬＡＵＭＥＪＬ，ＬＡＭＢＩＯＴｒＥＲ，ｅｔａ１．Ｆａｓｔ

ｈｉｅｒａｒｃｈｉｅｓ

ｉｎ

ｈｉｇｈ－Ｔｅｓｕｐｅｒｃｏｎｄｕｃｔｏｒｓｂａｓｅｄ

ｍｏｄｅｌ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＢ，２００３，６８（１）：０１２５０９．

ａｒｏｕｎｄ

ａｖｏｒｔｅｘｃｏｒｅ

ｉｎ

ｏｎ

ｔｈｅｔ－Ｊ

ｃｏｍｍｕｎｉｔｙｌａｒｇｅ

ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌｏｆ

Ｍｅｃｈａｎｉｃｓ：Ｔｈｅｅｒｙ

ａｎｄ

Ｅｘｐｅｎｍｅｎｔ，２００８，１０：

ｆ７］ｆ８１

９

Ｈａｉ－ｊｕｎ．ＮｅｔｗｏｒｋｌａｎｄｓｃａｐｅｆｒｏｍａＢｍｗｎｉａｎｐａｒｔｉｃｌｅ’ｓｐｅｒ－

ｓｐｅｃｔｉｖｅ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００３，６７（４）：０４１９０８．

ＺＨＯＵＺＨＯＵ

Ｈａｉ－ｊｕｎ．Ｄｉｓｔａｎｃｅ。ｄｉｓｓｉｍｉｌａｒｉｔｖｉｎｄｅｘ．ａｎｄｎｅｔｗｏｒｋｃｏｎｍｆｌｕ－

ｎｉｔｙｓｔｒｕｃｔｕｒｅ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００３，６７（６）：０６１９０１．

ＦＯＲＴＵＮＡＴｅＳ．ＬＡＴｅＲＡＶ，ＭＡＲＣＨＩＯ磁Ｍ．Ａｍｅｔｈｏｄｔｏｆｉｎｄ

ｃｏｍｍｕｎｉｔｙ

［１４］ＮＥＷＭＡＮＭＥＪ．Ｆｉｎｄｉｎｇｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｉｎｎｅｔｗｏｒｋｓｕｓｉｎｇ

ｔｈｅｅｉｇｅｎｖｅｃｔｏｍｏｆｍａｔｒｉｃｅｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００６，７４（３）：

０３６１０４．

ｓｔｒｕｃｔｕｒｅｓｂａｓｅｄ

ｏｎ

ｉｎｆｏｒｍａｔｉｏｎｃｅｎｔｒａｌｉｔｙｆＪ］．ＰｈｙｓｉｃａＩ

ＲｅｖｉｅｗＥ．２００４．７０（５）：０５６１０４．

［１０］赵凤霞，谢福鼎．基于Ｋ—ｍ∞ｎｓ聚类算法的复杂网络社团发现新

方法［Ｊ］．计算机应用研究，２００９，２６（６）：２０４１—２０４３，２０４９．［１１］李峻金。向阳，牛鹏，等．一种新的复杂网络聚类算法［Ｊ］．计算

机应用研究，２０１０，２７（６）：２０９７—２０９９．

『１２１ＳＡＬＥＳ．队ＲＤＯＭＲ．ＧＵＩＭＥＲＡＡ。ＭＯＲＥＩＲＡＡ．ｅｔａ１．Ｅｘｔｒａｃ．

ｒｉｎｇｔＩＩｅｈｉｅｒａｒｃｈｉｃａｌ

［１５］ｗｕＦａｎｇ，ＨＵＢＥＲＭＡＮＢＡ．Ｆｉｎｄｉｎｇｃｏｍｍｕｎｉｔｉｅｓｉｎｌｉｎｅａｒｔｉｍｅ：

ａｐｈｙｓｉｃｓａｐｐｒｏａｃｈ［Ｊ］．ＴｈｅＥｕｒｏｐｅａｎＰｈｙｓｉｃａｌＪｏｕｒｎａｌＢ，２００４，３８（２）：３３１・３３８．

［１６］ＮＥＷＭＡＮＭＥＪ，ＧＩＲＶＡＮＭ．Ｆｉｎｄｉｎｇａｎｄｅｖａｌｕａｔｉｎｇｃｏｍｍｕｎｉｔｙ

ｓｔｒｕｃｔｕｒｅｉｎｎｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００４，６９（２）：

０２６１１３．

［１７］ＣＬＡＵＳＥＴＡ，ＮＥＷＭＡＮ

ｓｔｒｕｃｔｕｒｅ

ｉｎ

ｖｅｒｙ

ＭＥ

Ｊ，ＭＯＯＲＥＣ．Ｆｉｎｄｉｎｇｃｏｍｍｕｎｉｔｙ

ｌａｒｇｅ

ｎｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００４。７０

ｏｒｇａｎｉｚａｔｉｏｎ

ｏｆｃｏｍｐｌｅｘ

ｓｙｓｔｅｍｓ［Ｊ］．Ｐｒｏｃｅｅｄ・

ｉｎｇｏｆｔｈｅＮａｔｉｏｎａＩＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓｏｆｔｈｅＵｎｉｔｅｄＳｔａｔｅｓ

（６）：０６６１１１．

［１８］ＮＥＷＭＡＮＭＥＪ．Ｆａｓｔａｌｇｏｒｉｔｈｍｆｏｒｄｅｔｅｃｔｉｎｇｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ

ｉｎｎｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００４，６９（６）：０６６１３３．

复杂网络中社团结构划分的快速分裂算法

作者：作者单位：刊名：英文刊名：年，卷(期)：

张聪， 沈惠璋， 李峰， ZHANG Cong， SHEN Hui-zhang， LI Feng上海交通大学,安泰经济管理学院,上海,200052计算机应用研究

APPLICATION RESEARCH OF COMPUTERS2011,28(4)

本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyyyj201104010.aspx