（计算机科学与技术专业论文）多关系社会网络分析和可视化系统的研究.pdf

t l 独创性( 或创新性) 声明 i i j j ij i iiii i i j r l l l ll l f l ljp ii i ii l l j j y 17 5 7 6 0 9 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：j 季二硝j 扛一 本人承担一切相关责任。 同期：丝 亚。；2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：，本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适用本授权书。 日期：2 丝：墨：壁 日期：2 灶q l t i t 噜 t 多关系社会网络分析和可视化系统的研究 摘要 传统的数据挖掘技术( 包括分类，聚类，关联分析等) 专注分析 维表的属性，却忽略了记录之间所存在的关系。另一方面，现在主要 的网络分析方法主要关注网络的拓扑结构分析而没有注意到网络中 节点本身所具有的属性。本文提出的多关系社会网络旨在通过构建异 构的网络模型来最大限度的保留原始数据的各种信息，并对多关系网 络进行进一步的研究。 本文主要对多关系社会网络做以下几方面的探讨： ( 1 ) 多关系网络建模和网络提取。在对现实数据进行多关系网 络建模之后，定义单一网络的抽取操作，从多关系网络中抽取特定意 义的单一关系网络。 ( 2 ) 多关系社会网络的实体解析。从多个数据源中收集到的数 据，只有经过集成和预处理才能被精确的知识发现模型所使用。而在 多个数据源的数据进行集成合并到同一个数据集合当中时，会产生很 多的重复记录。而这些数据并不是语义上唯一的，通常表示的是同一 个实体。正确的合并这些重复的数据是制造高质量数据的至为重要的 一部。这个过程被称之为实体解析( e n t i t yr e s o l u t i o n ) ，本文尝试在使 用属性匹配的基础上，通过使用多关系社会网络多关系的特点，提升 实体解析的准确率。 ( 3 ) 社团划分一直是研究复杂网络的一个重要手段，而目前的 社团划分算法主要是使用网络拓扑的信息进行划分。本文的另一个研 究点是研究在网络节点有属性的情况下，对网络进行社团划分。在使 用网络拓扑的基础上，通过使用节点属性，进一步提高社团划分的准 确率。 ( 4 ) 可视化，即通过提供统计或交互式视觉表现的软件系统来 帮助人们探索和解释数据，是数据挖掘过程中极为重要的一个环节。 本文也对多关系社会网络的可视化进行了研究，针对不同的网络类型 设计不同的网络视图方案，并提出“网络浏览 的概念，将“网络浏 科技文 信息可 j 霉1 盈 廖 a t h er e s e a r c ho fm u l t i r e l a t i o ns o c i a l n e t w o r kv i s u a la n a l y t i cs y s t e m a b s t r a ct t r a d i t i o n a ld a t a m i n i n gt e c h n o l o g i e s ，i n c l u d i n gc l a s s i f i c a t i o n ， c l u s t e r i n g ，a s s o c i a t i o nr u l e s ，e t c ，f o c u so na n a l y s i so ft h ep r o p e r t i e so f d i m e n s i o nt a b l e s ，b u ti g n o r et h er e l a t i o n s h i pt h a te x i s t sb e t w e e nt h e r e c o r d s o nt h eo t h e rh a n d ，n o wt h em a i nm e t h o do fn e t w o r ka n a l y s i s f o c u s e so nt h en e t w o r kt o p o l o g ya n a l y s i s ，w h i c hd i dn o tn o t i c et h a tt h e n o d ei nt h en e t w o r k sh a st h ea t t r i b u t e i nt h i sp a p e r , w eu s em u l t i - r e l a t i o n s o c i a ln e t w o r k ( m r s n ) t om o d e lt h et h er a wd a t aa n dd os o m er e s e a r c h o nm r s n i nt h i sp a p e lw ed os o m er e s e a r c ho nm r s na sf o l l o w i n g ： ( 1 ) m u l t i - r e l a t i o ns o c i a ln e t w o r km o d e l i n ga n dn e t w o r ke x t r a c t i o n w ep r o p o s et h ep r o c e s so fm o d e l i n gt h em u l t i - r e l a t i o ns o c i a ln e t w o r k f r o mt h er a wd a t a ，a n dt h e nd e f i n et h e o p e r a t o r s o fe x t r a c t i n g h o m o g e n e o u sn e t w o r k sf r o mam u l t i - r e l a t i o ns o c i a ln e t w o r k ( 2 ) e n t i t yr e s o l u t i o ni nm r s n d a t af r o mr e l e v a n ts o u r c e sm u s tb e c o l l e c t e d ，i n t e g r a t e d ，s c r u b b e da n dp r e - p r o c e s s e di n av a r i e t yo fw a y s b e f o r ea c c u r a t em o d e l sc a nb em i n e df r o mi t w h e nd a t af r o mm u l t i p l e d a t a b a s e si sm e r g e di n t oas i n g l ed a t a b a s e ，m a n yd u p l i c a t er e c o r d so f t e n r e s u l ti n t h e s ea r er e c o r d st h a t ，w h i l en o t s y n t a c t i c a l l yi d e n t i c a l ， r e p r e s e n tt h es a m er e a l - w o r l de n t i t y c o r r e c t l ym e r g i n gt h e s er e c o r d sa n d t h ei n f o r m a t i o ni sa ne s s e n t i a ls t e pi np r o d u c i n gd a t ao fs u f f i c i e n tq u a l i t y f o rm i n i n g i nt h i sp a p e r , w ep r o p o s eam e t h o dw h i c hc o m b i n e sl i n k a n a l y s i so nt h eb a s i so f t h ea t t r i b u t e m a t c hm e t h o d ( 3 ) c o m m u n i t y d e t e c t i o ni sa ni m p o r t a n tm e t h o dt oa n a l y z ec o m p l e x n e t w o r k s t h ec u r r e n tc o m m u n i t yd e t e c t i o na l g o r i t h m sm e r e l yu s et h e t o p o l o g ys t r u c t u r eo ft h en e t w o r k ，b u tn e g l e c tt h ec o n t e n to ft h en o d e i n t h i sp a p e r , w ep r o p o s ea na l g o r i t h mc a l l e dc d n aw h i c hu s en o to n l yt h e t o p o l o g yi n f o r m a t i o nb u ta l s ot h ec o n t e n to fn o d et of i n dt h ec o m m u n i t i e s i nt h en e t w o r k ) v i s u a l i z a t i o n ，w h i c hp r o v i d e si n t e r a t i v es o f t w a r es y s t e m s t oh e l p e x p l o r ea n du n d e r s t a n dt h ed a t a ，i sa ni m p o r t a n ts t e po ft h ed a t a p r o c e s s t h i s a r t i c l ea l s or e s e a r c h e st h ev i s u a l i z a t i o no f m u l t i r e l a t i o n a ls o c i a ln e t w o r k w ed e s i g nd i f f e r e n tv i e w sf o rd i f f e r e n t t y p eo fn e t w o r k s a n dw ep u tf o r w a r dt h e ”w e bb r o w s e r c o n c e p t ，a n d u s ei tt oac o n s t r u c tal a r g e - s c a l ew e b b r o w s i n gf r a m e w o r k ( 5 ) f i n a l l y , t h ea b o v er e s e a r c hr e s u l t a r ea p p l i e dt od e v e l o pa l i t e r a t u r ev i s u a la n a l y t i cs y s t e mc a l l e dl i t e r m i n e r , w h i c hi ss u p p o r t e db y ap r o j e c tc a l l e d s i c e n c ea n dt e c h o n o l g yi n f o r m a t i o ns e r v i c es y s t e m k e yt e c h n o l o g yr e s e a r c ha n da p p l i c a t i o nd e m o n s t r a t i o n ，u n d e rn a t i o n a l s c i e n c ea n dt e c h n o l o g yf u n d k e yw o r d s ：m u l t i r e l a t i o ns o c i a ln e t w o r k e n t i t y r e s o l u t i o n c o m m u n i t y d e t e c t i o n v i s u a la n a l y t i c 孽 氐 房 q 目录 第一章绪论1 1 1 研究背景l 1 2 研究内容2 1 2 1 多关系网络的建模3 1 2 2 基于多关系社会网络的实体解析3 1 2 3 多关系社会网络的社团发现3 1 2 4 多关系社会网络的可视分析3 1 2 5 多关系社会网络的应用示范4 1 3 论文组织结构。_ 4 第二章相关概念和工作。：5 2 1 网络分析方法5 2 1 1 基本概念5 2 1 1 度数和度分布_ 5 2 1 2 介数。6 2 1 3 平均距离6 2 1 4 簇系数6 2 2 实体解析6 2 3 社群发现7 2 4 可视分析9 2 5 网络分析工具1 1 2 6 d 、结13 第三章多关系网络构建与实体解析1 4 3 1 多关系社会网络建模1 4 3 2 关系网络抽取2 0 3 3 实体解析。2 2 3 3 1 概述2 2 3 3 2 多关系网络的实体解析2 3 3 4 小结3 6 第四章多关系网络的分析3 7 4 1 多关系社群发现。3 7 4 1 1 概述3 7 ：；8 z i ：! z 和4 4 4 4 5 4 6 4 6 4 9 ! ；( ) ! ；( ) ：；：； ! ；! ； 用5 6 ! ；6 ! ；7 ! ；8 ! ；9 6 ( ) 6 ：! 6 ： 6 4 6 4 6 1 ； 6 7 6 9 6 9 7 0 7 0 7 0 。7 2 7 6 7 7 氐 a 北京邮电人学硕。l 研究生学位论文 1 1 研究背景 第一章绪论 信息技术的逐步发展和企业自身的需要，产生了大量可以广泛使用的数据， 由于市场竞争的需要，迫切需要将这些数据转换成有用的信息和知识，便产生了 数据挖掘这个领域，并且引起了科学界、企业界乃至整个社会的极大关注。现在 越来越多的数据挖掘的技术被发明出来，为企业做决策时起到良好的辅助作用。 但是这些传统的数据挖掘技术通常都是注重维表中的属性进行分析，而忽略了这 些记录之间存在的联系，有时无法给出更好的分析结果。 现在关注个体之间的关系的分析方法网络分析方法一已经逐渐受到科学家 们的关注和研究，越来越多的科研工作者投身其中，使得新思想新成果不断涌现。 1 9 9 8 年6 月，康奈尔大学理论与应用力学系的博士生w 撕s 及其到时s t r o n g t z 在 n a t u r e 杂志上发表题为“小世界”网络的群体动力行为的文章【1 】，进一步 揭示了复杂网络的小世界特性，并建立了一个小世界网络模型。1 9 9 9 年1 0 月， 美国圣母大学物理系的b a r a b a s i 教授及其博士生a l b e r t 在s c i e n c e 杂志上发表了 题为随机网络中标度的涌现一文 2 】，揭示了复杂网络的无标度性质，并 建立了一个无标度的网络模型。以这两篇论文的发表为标志，复杂网络研究进入 了一个新时代。从物理学到计算机学，从i n t e r n e t 到社会网络，不同领域的科学 家们尝试搜集、建立和分析不同类型的网络 3 】，试图揭示复杂网络的所有特 点和分析他们中存在的规律。但是，到目前为止，大多数研究仅限于在构建单一 关系的网络，而且网络中节点的信息也往往被忽略。 另一方面，挖掘涉及关系数据库中的多个表( 关系) 的模一多关系数据挖掘 ( m u l t i r e l a t i o n a ld a t am i n i n g ，m r d m )【4 】分析方法被提出来，解决了传统数据分 析方法分析过程中信息丢失的缺点。多关系数据挖掘旨在发现多关系数据中的知 识。多关系数据库挖掘的任务有多种，包括关系分类、聚类、频繁式挖掘以及图 挖掘等等。多关系分类的旨在利用不同关系中的信息构成一个分类模型。多关系 聚类旨在使用元组自身的属性以及不同关系中与他们相关的元组将元组划分成 簇。多关系频繁模式挖掘旨在发现存在于不同关系中相互联系的项的模式。 图l l 表示的是一个电影数据中的关系模式。在电影数据中，通常演职人员、 电影、工作室、奖项等实体，他们之间都存在着关系，而这些关系通常是复杂的， 例如人员与人员之间存在雇佣关系或者合作关系，人员和电影之间存在着导演、 北京邮电大学硕 ：研究生学位论文 影和工作室存在制作出品之间的关系，个人、电影和奖项之间存 w o r k 4 t dw 潮h 图1 1 电影数据库中网络模式 络分析方法和多关系数据的优点，提出多关系社会网络的概念， 特点和网络建模的方法尽量的接近于现实世界，尽量减少建模过 失，并且探讨多关系社会网络的一些预处理和分析方法以及可视 文的研究切入点不同，本文的重点在于使用多关系的概念对现实 建模，主要研究内容集中在研究在多关系社会网络中的实体解析 可视化。依托国家科技支撑计划海量科技文献数据服务系统的 示范项目，主要研究多关系社会网络在文献数据的应用，当然， 于其他可以构建网络模型的应用场景中。本文的主要研究内容由 同组成。 2 一 乏 “ 幺 北京邮电大学硕 ：研究生学位论文 1 2 1 多关系网络的建模 原有的从单关系中发现模式的数据挖掘方法叫做命题学习方法或属性一值 学习方法，该方法使用命题逻辑表示知识和模式。而关系数据挖掘( r e l a t i o i nd a t a m i n i n g ，r d m ) 也称为多关系数据挖掘( m u l t i r e l a t i o nd a t am i n i n g , m r d m ) ， 是在由多个关系表构成的关系数据库中抽取模式的一个多学科交叉的领域，本文 的第一个研究点就是针对目前的数据，进行多关系网络建模的一些探讨，并研究 从多关系社会网络中抽取单一关系的社会网络。 1 2 2 基于多关系社会网络的实体解析 由于一些历史的原因或者当初设计数据库考虑不周全以及用户填写数据时 采用默认值或录入错误等原因，现存的数据会出现多条表象描述同一个实体的现 象，而这些表象本身存在着一些模糊且二义的情况，会给数据统计和分析带来很 多的错误，进行实体解析就显得尤为必要。目前实体解析的方法重在使用属性匹 配等方法，也有一些论文使用了链接分析方法，不过使用的链接都是单一关系， 所以这种方法并没有充分使用数据库中的关系模式。本文尝试使用多关系的特 点，采用属性匹配和多关系链接分析结合j a c c r a d 系数对表象相似进行评估，取 得了良好的效果。 1 2 3 多关系社会网络的社团发现 社团发现是复杂网络里的一个重要分析方法，该方法旨在挖掘网络中的一些 关系比较紧密的子团体，是网络划分和挖掘的一个重要手段。目前的方法都是对 同质网络进行社团划分，只采用网络自身结构，忽略了网络中节点本身的属性特 征，本文的另一个研究内容为融合属性特征的社团发现算法。在社团划分时，考 虑节点自身的属性。 1 2 4 多关系社会网络的可视分析 信息可视是数据挖掘中一个不能忽视的手段。可视分析，涉及到较强的可交 互性，充分调动用户的感知能力和主动性。通过让用户参与到整个分析过程，帮 助用户发现更多的知识。在多关系网络中，可视分析不再针对一种数据类型网络 进行展示，而是充分挖掘网络中的种种关系，采用协同分析的方法对数据进行呈 现，帮助用户更全面深入地分析数据。 3 内容和一些网络 第三章多关系网络建模与实体解析：本章主要介绍多关系网络的建模方法 和从多关系网络中抽取有意义的网络的方法。之后介绍实体解析的概念和常用的 方法，着重介绍在多关系社会网络中的实体解析算法，并对该算法进行结果分析 和性能评估。 第四章多关系社会网络的分析：本章的内容主要分为三部分：社群发现和 可视分析以及大规模网络的浏览解决方案。在社群发现部分，提出 c d a n ( c o m m u n i t yd e t e c t i o nw i t ha t t r i b u t eo fn o d e ) ，通过使用多关系网络中的 节点属性，进一步提高社团发现的准确率。之后主要介绍了可视分析的主要内容 以及在多社会网络中如何实现可视分析的协同。本章还特别针对网络可视视图提 出了网络浏览的概念，定义了几种网络浏览的基本操作，并给出一个大规模网络 浏览的可行解决方案。 第无章相关工具实现：本章是对前几章介绍的算法和技术的一个技术实现， 依托国家科技支撑计划海量科技文献信息服务系统的关键技术研究和示范， 设计实现了一个可视分析文献数据的软件一l i t e r m i n e r 。本章着重介绍l i t e r m i n e r 的主要设计思想和实现过程，最后通过一个示例介绍l i t e r m i n e r 的应用。 第六章论文工作总结及展望：本章总结了论文目前所取得的研究成果，并 探讨未来可以进一步深入的研究工作。 4 北京邮电人学硕i ：研究生学位论文 2 1 网络分析方法 2 1 1 基本概念 第二章相关概念和工作 一个具体的网路可抽象为由点集v 和边集e 组成的图g = 记为n = l v l ，边数记为m = i e l 。e 中每条边都有v 中一个点对 意点对与对应同一条边，则该网络称为无向网络，否则称为有向网络。如果给每 条边赋一权值，则该网络就是一个加权网络，同样，加权网络也分为无向加权网 络和有向加权网络。 鼢酶 ( a )( c ) 图2 1 不同类型的网络 ( a ) 为一个无向无权网络( b ) 为一个有向网络( c ) 为一个有向加权网络 2 1 1 度数和度分布 度( d e g r e e ) 衡量一个节点的与其他节点的连接程度，节点f 的度忽定义为与节 点f 连接的其他节点的数量。有向网络的度分为出度和入度，节点的出度指的是 该节点指向其他节点的边的数量，节点的入度是指从其他节点指向该节点的边的 数目。网络中所有的节点i 的度岛的平均值称为网络的平均度，记为 ，网络 中节点的度的分布情况可用分布函数p ( k ) 来描述，p ( k ) 表示的是一个随机选定 的节点恰好为k 的概率。完全随机的网络度分布近似为p o i s s i o n 分布，而目前大 规模网络的度服从幂率分布，自然界与社会生活中存在各种各样性质迥异的幂律 分布现象。 北京邮电人学硕j ：研究生学位论文 2 1 2 介数 介数( b e t w e e n e s s ) ：介数分为边介数和节点介数。节点的介数为网络中所有 的最短路径中经过该节点的数量比例；边的介数含义类似。为网络中经过每条 边的最短路径的数目。介数反映了相应的节点或者边在整个网络中的作用和影响 力，具有很强的现实意义。例如，在社会关系网络或技术网络中，介数的分布特 征反映了不同人员、资源和技术在相应生产关系中的地位，这对于在网络中发现 和保护关键资源和技术具有重要意义。 2 1 3 平均距离 网络中两个节点i 和j 的距离蛔定义为连接两个节点的最短路径上的边数。 网络中任意两个节点之间的最大距离的最大值称为网络的直径，记为d ，即 d 2 肾吒 网络的平均路径长度l ( a v e r a g ed i s t a n c e ) 定义为任何两个节点之间的距离 的平均值，即 k i 高酗 2 近期的研究发现，尽管许多实际的复杂网络的节点数量巨大，网络的平均路 径长度却很小。 2 1 4 簇系数 簇系数( c l u s t e r i n gc o e f f i c i e n t ) ：簇系数是专门用来衡量网络节点聚类的情况 的参数。比如在朋友关系网中，你朋友的朋友很可能也是你的朋友；你的两个朋 友很可能彼此也是朋友。簇系数就是用来度量网络的这种性质的。用数学化的语 言来说，对于某个节点，它的簇系数被定义为它所有相邻节点之间连的数目占可 能的最大连边数目的比例，网络的簇系数c 则是所有节点簇系数的平均值。 2 2 实体解析 数据清理和准备是数据挖掘过程中的第一个环节，在大多数情况下，也是最 昂贵的一个过程。从多个数据源中收集到的数据，只有经过集成和预处理才能被 6 北京邮电大学硕士研究生学位论文 精确的知识发现模型所使用。而在多个数据源的数据进行集成合并到同一个数据 集合当中时，会产生很多的重复记录。而这些数据并不是语义上唯一的，通常表 示的是同一个实体。正确的合并这些重复的数据是制造高质量数据的至为重要的 一部。这个过程被称之为实体解析( e n t i t yr e s o l u t i o n ) 、记录联合( r e c o r dl i n k a g e ) 、 目标识另l j ( o h j e c ti d e n t i f i c a t i o n ) 、记录去重( d e - d u p l i c a t i o n ) 、合并( m e r g e ) 、不确定 发现( i d e n t i t yu n c e r t a i n t y ) 、表象调和( r e f e r e n c er e c o n c i l i a t i o n ) 等。在最近的几年里， 实体解析过程受到了数据挖掘领域越来越多的关注，在k d d 2 0 0 3 年的一个 w o r k s h o p 就是专门讨论这个主体的，并且2 0 0 3k d dc u p 也有一个相关的任务。 世界上并没有不变的算法告诉我们一个数据源的什么数据对应于其他数据 源的哪些数据，而且，对应于同一个实体的多条记录会包含不同的信息，例如， 地址的拼写错误，或者属性信息的缺失等。实体算法的主要目的是在多个数据源 匹配相同的记录，并最好的合并它们。典型的实体解析算法一般分为两步：( 1 ) 比较两条记录的相似性，确定他们是否匹配，( 2 ) 合并匹配好的记录，并合并其 中的属性。 实体解析的问题首先由n e w c o m b e 【6 】等人提出，并且f e l l e g ia n ds u n t e r 提出 了一个统计的公式化【_ n 。现在大多数的方法都是基于f e u e g i s u n t e r 的模型，该 模型认为实体解析是一个分类问题。将两个实体的各个属性的相似程度打分，分 为匹配( m a t c h ) 和不匹配( n o tm a t c h ) 两类，在构建消除不一致之后，通常需要 为候选表象对建立一个独立的匹配决策函数，此时需要一个逻辑回归模型i s 】。 目前的一些方法关注于在处理海量数据库实体解析时避免二次方的比较实体。而 另一些方法在于使用主动学习技术来使标记数据的需求最小化【1 2 1 。一些学者已 经实体为解析的使用设计、比较和学习相似值的度量措施。另外也有一些规约的 方法被发明出来。 最近，一些学者指出匹配决策并不应该独立使用，例如s i n g l aa n d d o m i n g o s 【l 引，提出应该使用实体的类型类帮助发现另外一些与之相关的实体 ( 例如，两篇一样的文章，他们的作者应该也是一样的，反过来，两篇相同的作 者他们的文章对也应该是完全匹配的) 。s h e ne ta 1 1 4 】提出了一些类型的限制来 提高匹配的精确度。d a v i se ta 1 【l5 】使用规约逻辑编程技术来发现实体解析中的 关系规则，之后使用朴素贝叶斯分类器类进行合并。 2 3 社群发现 随着复杂网络结构的深入研究，人们发现许多网络中都具有一个公共的性 7 距也就越大，社区结构也就越明显。因此，在g n 算法分裂的过程中，每去掉一 条边，就计算一次q 值，当算法结束的时候，就可以得到一条q 值变化的曲线。 整个过程中q 值最大时的划分方案就是最终的社区划分结果。作为g n 算法的 一个直接扩展，n e w m a n 等人给出了在加权网络中的网络模块性的定义，从而提 出了在g n 算法框架下对加权网络的社区划分算法。g n 算法最主要的问题就是 计算需求太高，计算复杂度为o ( m 3 ) ，其性能仅足以支持一万个结点以下的中 小型网络的分析，并不能应用于大规模的实际网络。 为了改进g n 算法的性能，2 0 0 4 年n e w m a n 提出了一种快速算法f a s t1 1 8 】， 该算法一改g n 算法的分裂方式，而重新采用贪心策略指导下的层次聚类方式。 算法在开始的时候，同样把每个网络结点看作是相应独立的社区，每次都选取两 个社区凝聚成一个更大的社区，选取要合并社区的原则是能使得q 函数有最大 的增长( a q 0 ) ，并构造出树状结构。当q 函数不能再增长的时候( a q 0 ) ，停 止虚线的向上移动过程，算法结束。f a s t 算法的划分效果和准确性相比于g n 算 法有所下降，但是性能却大大地提升了。稍后，c l a u s e t 和n e w m a n 等人更进一 步改进了f a s t 算法的数据结构，使得算法的性能进一步提高，并具有o ( n l 0 9 2 加 的时间复杂度，已经可以处理a m a z o n t o m 中网页的链接关系网络，该网络包含 4 0 多万个结点和1 0 0 多万条边。 北京邮电人学硕f ：研究生学位论文 此外，从网络模块性q 的定义出发，它本身可以被看成是一个纯粹的优化问 题，而q 的最大值问题已经被证明是一个n p 完全问题。因此，d u c h 等人【2 l 】使 用极值优化算法来专门对网络模块性进行优化来启发式地寻找它的局部最优解， 整个算法的复杂度为o ( n 2l o g n ) 。t a s g i n 等人【2 2 】使用遗传算法对网络结点进行 编码，并以网络模块性作为适应度函数来进行优化，从而获得可能的社区结构划 分。p i z z u t i 2 3 】同样使用了遗传算法但是基于不同的编码方式来对网络模块性进 行优化。 而p a l l a 等【2 0 】人则从另外一个角度来发现网络中的社团，p a l l a 等人认为， 一个社团从某种意义上可以看出一些相互连通的“小的全耦合网络”的集合。这 些全耦合网络被称之为“派系”( c l i q u e ) ，而k 派系则表示该全耦合网络的节点数 为k 。如果两个k _ 派系有k - 1 个公共节点，则称前后两个k - 派系相邻。如果一个 k 派系可以通过若干个相邻的k 派系到达另一个k 派系，则称这两个社团彼此是 连通的。p a l l a 认为网络中的k 派系社团可以看成是彼此连通的k 派系构成的集 合。基于上述的思想，p a l l a 发明了c p m 方法，来进行网络中的社团发现。 2 4 可视分析 作为一项非常有用的技术，可视化已经受到了越来越多学者和商业的关注和 使用。 i s si n c 公司的w e b t a s 【硐是一款用来分析大型异构数据的分析软件，该系 统在传统的数据挖掘技术的基础上，加入了链接分析、地理信息可视和时间轴 ( t i m e l i n e ) 的表示。来自i 2i n c 公司的分析者记事本( a n a l y s t n o t e ) 2 5 】，该软件 主要是关注文本数据的人物、事件、机构、银行账户之间的联系，将这些实体用 图的方式表示出来。 o c u l u si n f oi n c 公司开发了系列多角度分析的系统g e o t i m e 【2 6 】。g e o t i m e 是一个可视化报告数据的软件，该软件使用了可交互的3 d 视图在时间和地理上 可视和跟踪事件、个体和活动。 而该公司的另一款软件t r i s ts y s t e m 【2 7 】提供了格式化、精炼、组织和查 询大规模数据的功能，该软件使用了多视图的方式可以帮助分析人员对搜索结果 进行多角度的分析，包括聚类、趋势分析、比较等分析功能。t r i s t 的检索结 果可以导入到该公司的另一款产品s a n d b o x 【2 8 】继续进行分析，该软件可以 9 北京邮电大学硕+ i ：研究生学位论文 帮助用户排序，组织和分析大规模数据，与上一款软件的目标不同，这款软件更 加注重使用计算机语言和分析功能加强用户的视觉效果，使用户更加深层次的思 考。该系统可以使用可交互的可视分析技术提供了放置、移动和分组信息的功能。 g t d 数据包含从1 9 7 0 年到1 9 9 7 年美国国内外所有经过的恐怖主义行动。 利用该数据，美国可视分析实验室西南中心开发了一个对恐怖主义行动进行5 w ( w h o ，w h a t ，w h e r e ，w h e n ，a n dw h y ) 的可视分析系统【2 9 1 ，旨在发现和揭示恐怖主 义内在的模式和关系。该系统的功能主要有( 1 ) 提供5 w 的交互式可视分析；( 2 ) 支持高层次的策略分析和单个事件的战术分析；( 3 ) 方便研究人员的研究结果和 假设的交互。 j i g s a w 3 0 】是一个分析文本中蕴含的大量实体和实体之间关系的工具。可以 帮助分析师更好的评估、分析和利用收集到的文件。其主要目标是帮助分析人员 高效而准确的理解大量文本报道里包含的信息。j i g s a w 提供了多种角度可视分析 文档的功能，从中识别重要的实体( 例如人物、地点、组织等) 和他们之间的联 系关系。系统提供了多种视图供使用者分析，包括，图视图，同历视图，散点图 视图和表格视图等。用户还可以查看经过高亮标识的文档和文档集合，总而言之， j i g s a w 就像是一个可视化的引导者，引导分析人员找到自己需要的特定文档。 v a d l 3 2 】是佐治亚理工学院花了3 年时间建立的一个数字图书馆，该图书 馆搜集了关于可视化方向的课件，资料和文档，可以帮助教室开展可视分析的课 程和帮助学生更好的开发他们使用和开发可视分析工具的能力。该系统使用 r e s u a l s m a p s 技术将搜索得到的信息更加友好的展示出来，是用户对搜索结果有 了更加深入的了解。搜索结果按照类型放在不同的区域。每个结果用一个节点表 示，不同的类型的结果用不同颜色的节点表示。点击节点可以使焦点移动到相应 的结果上。 银行系统每天产生的大量电汇记录为增加了分析电汇模式、反欺诈和反黑钱 行为的难度，而且欺诈行为随着时间都在变化，依靠传统分析电汇模式来挖掘欺 诈行为已经不再有效。为此，w i r e v i s 【3 1 】系统提供了基于关键字的协同分析。不 同的视图展示了随着时间的变化关键字和账户的关系。该系统还提供了查询由用 户提供的例子相同的模式的电汇记录。利用该系统，分析人员可以发现行为可疑 的交易。 1 0 北京邮电人学硕 ：研究生学位论文 2 5 网络分析工具 随着数据分析需求的不断增长，越来越多的针对文献信息的可视分析软件被 开发出来。 y i z h o us u n 等开发出一个名为b i b n e t m i n e r 的工具【3 4 1 ，该工具通过构建复 杂信息网络( s o p h i s t i c a t e di n f o r m a t i o nn e t w o r k ) 对文献数据进行分析，该工具的功 能主要有聚类，排名和基于研究领域的会议和作者的描述。另外，该工具也使用 了一个友好的可视分析界面。 随着网络分析方法的逐渐成熟，基于网络可视的分析系统也越来越多， n e t w o r kw o r k b e n c h ( n w b ) 是一个适用于物理、生物科学和社会科学分析的集网 络分析、建模和可视分析为一体的综合性网络分析工具1 3 6 。其构架使用的是 c l s h e l l 技术，具有分布式，松耦合，插件式服务等优点。新版本的n w b 添加 了若干新的算法来分析文献数据，目前已经支持i s i 格式，s c o p u s ，和g o o g l e s c h o l a r 等数据格式。 c i t e s p a c e 是用来分析和可视共引网络的j a v a 应用程序【3 3 】。主要是用来帮 助分析知识领域中的新趋势。它使用户可以将某个领域顺时进行“抓拍”，然后 将这些抓拍的图片连接起来。图5 2 是n w b 和c i t e s p a e e l l 的功能比较。 北京邮电人学硕，i j 研究生学位论文 f u n c t i o nn w bt o o l c i t e s p a c ei i i s i ； d o c 眦e n tc o c i t a t i o nn e t w o r k a u t h o rc o - c i t a t i o nn e t w o r k j o m l m lc o - c i t a t i o nn e t w o r k c o - a u t h o r s h i pn e m , o r k n e 似 o r ko fc o - a u t h o r si m f i r u t i o m n e t w o r ko fc o - a u f l l o r sc o m l t r i e s 盼厶r dc o - o c c u n e n c en e t w o d c s l l b i e c tc a t e g o r i e sc o - o c c u r r e n c en e m o r k c i t e dr e f e r e n c ec o o c c u r r e n c e 0 ， 0 ， 、f c l u s t e r v i e w 、 t i m e z o n e v i e w q p a t t f f m d e rn e t w 饵kq0 d e t e c td u p l i c a t en o d e sv q e r g e1 ) u p l i c a t en o d e s b e 钾v e e n n e s sc e n t r a l i t y qq e x t r a c tk c o r eq g e o s p a f i a lm a p s 图2 - 2n w b 和c i t e s p a c e l i 的比较 科研