硅谷杂志：复杂网络中社区识别研究 |
| 2012-07-12 14:34 作者：王梦菊 来源：硅谷网 HV： 编辑： 【搜索试试】
|
|
硅谷网7月12日消息 （原文载于《硅谷》杂志6月刊）实证研究表明，复杂网络虽然千差万别，但实际上它们大多拥有许多相似的性质。聚类效应使得网络中存在社区结构。社区识别的目标就是识别复杂网络中的社区结构，以便能更准确地揭示其隐藏结构，为后续的挖掘、分析等活动提供先决条件。首先描述复杂网络研究的国内外现状，其次阐述和介绍复杂网络社区识别方法的分类和应用实例，再次论述目前社区识别方法中存在的主要问题，最后对目前的社区识别方法进行小结和展望。
网络社区识别也经常被称作网络划分。但一般来说，网络社区识别具较之后者具有更丰富的内涵。从目前的文献来看，对于网络社区识别这一概念主要有两种理解：一是指利用某种方法将网络划分成内部联系紧密而相互之间联系稀疏的簇，二是指按照某种要求以人机交互的方式将满足要求的社区找出来。
1国内外研究现状
国外对复杂网络的研究和应用已涵盖了诸多方面和领域，如犯罪网络、反恐网络、电子商务、疫情监测、作者合作网络、蛋白质相互作用网络、基因常规网络、邮件网络、虚拟学习、作者----主题分析、社区发现、空间文本挖掘、标签系统、虚拟社区、口语处理、角色识别、博客世界、青少年关系网络、社会层次发现、电话通讯网络、推荐系统、大型程序中Bug的预测和发现等。
相比较而言，国内对复杂网络的研究起步较晚。在改革开放之后，我国的复杂网络研究只限于社会科学领域，其与计算机技术相结合也只是近几年的事。国内对复杂网络的研究相对滞后，从深度和广度两方面都与国外的研究水平有着很大的差距，而且大部分研究论文皆属于社会科学和经济管理领域，与计算机科学直接相关的研究所占比例极低，而且大多还停留在初步的理论探讨或简单应用。
2社区识别方法分类及应用实例
2.1社区识别方法分类
社区识别方法大致可以分为两大类。一类是基于图形分割的识别方法，一类是基于相似度聚类的识别方法。
在第一类中，比较有影响的识别方法有Kernighan-Lin方法、基于拉普拉斯图特征值的谱平分法、基于电阻网络电压谱的快速谱分割法、基于Normal矩阵的谱平分法、GN算法等。由于衡量网络中不同结点的相似度比较困难，所以第二类中经典算法较少。第二类算法中比较有影响的方法主要有基于凝聚思想的Concor算法。
这些方法基本都为硬方法，即网络中的每个成员只能属于一个社区。另外，这些方法中除基于Normal矩阵的谱平分法，其余方法都需要先验知识：或者需要指定社区个数或都需要指定社区规模。
2.2社区识别方法应用实例
近些年来，国外的学者从理论和实践两个方面对复杂网络进行了广泛而深入的研究和探讨。为了进行犯罪调查和防止犯罪，帮助法律执行部门和情报机构高效地从犯罪网络中进行知识发现，美国耗费三年时间开发了大型反犯罪网络工具CrimeNetExplorer，模拟实验证明该软件十分有效。“911”之后，反恐网络中的知识发现也一直是外国学者的研究目标，不但对一些恐怖袭击事件从复杂网络角度进行了分析，还证明了如果能够在事件发生之前就应用复杂网络理论对网络进行分析，完全可能阻止事件的发生，并将所有嫌犯绳之以法；另外，该文献还特别关注了网络的可视化问题。隐私保护是近年来的一个研究热点，ElenaZheleva等人对复杂网络中的隐私保护问题进行深入的研究，给出了攻击模型。研究作者合作网络也是一个重要的课题，UlrikBrandes等人利用社区识别方法对维基百科的合作结构进行探讨，提出了描述和分析作者合作结构的模型和算法。BlockModel一直是复杂网络研究领域一个重要的模型，EdoardoM.Airoldi等人提出混合成员随机块模型，新模型较老模型有了较大的改进，可应用于蛋白质相互作用网络、基因常规网络、邮件网络等。基于网页的标签系统越来越流行，CameronMarlow等人对标签系统应用于复杂网络进行了探讨。虚拟学习是教育界的一个热门话题，BartRieenties等人以复杂网络为工具研究了由学生构成的社会网络中学习动机、核心人物和边缘人物等对学习效果的影响。
国内对社区识别的研究相对落后，但在某些领域也取得了一些可喜成果。我国学者利用社区识别对人名检索结果重名消解问题进行了比较深入的研究。众所周知，人物重名现象十分普遍。搜索引擎的人名检索结果通常是多个同名人物相关网页的混合，郎君等人依据不同人物具有相同名字但却具有不同社会网络的思想，通过检索结果中共现的人名发现并拓展与检索人物相关的潜在社会网络，结合图的谱分割算法和模块度指标进行社会网络的自动聚类，在此基础上实现人名检索结果的重名消解。在人工标注的中文人名语料上进行实验，整体性能达到较好水平[1]。在社区识别方面，王慧芳等分析了传统社区发现算法的缺陷，比如其基本上属于静态分析算法，且计算复杂性使其难以适应目前网络结构的频繁变化。为改善该局限性，通过对Radicchi静态算法进行扩展，提出一种增量式的社区发现算法，并将其应用于MSNSpace链接结构分析上。该算法能在网络结构变化频繁时进行增量式计算并保证社区发现的实时性[2]。只适用于结构变化相对较小的情形是这个改进算法的最大缺陷。在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值，胡健等把超图模型以及基于此的聚类算法应用到社区结构发现领域；并将边凝聚系数的概念引入简单图的社区结构发现，提出了基于边凝聚系数的社区发现算法[3]。万雪飞等提出了一种重叠社区发现的启发式算法。该算法基于局部贡献度的思想，以度最大的节点作为初始社区，逐步把对社区贡献最大的邻节点加入社区；同时考虑了社区的重叠性，若存在对多个社区贡献都很大的边界节点，则把边界节点同时加入到这些社区中。最后利用重叠系数对所划分的社区进行调整，使社区结构更加合理[4]。郭绍忠等将邮件挖掘技术与社区识别技术相结合，提出了构建社会关系网络的方法和社团挖掘改进算法及相关优化策略。胡岚曦为了研究从人物行为引导出人物关系，提出一种基于人物行为分析发掘人物关系网络的方法。以特定领域的行为为分析对象，构建行为模型从而获取该领域的核心人物集合，再通过训练生成该领域的关系模型，最后通过社区识别结果分析技术发掘人物的领域关系网络。该方法在行政官员活动领域中进行试验，效果良好。胡贵强等提出一种多Agent模拟与网络分析相结合的方法，以便应对犯罪网络动态变化的情形。张明智等在分析人际关系网络特性的基础上，借鉴构建小世界、无标度网络的思想，提出了在危机条件下，某区域人群对当前发生的危机事件进行交流从而形成的人际关系网络模型，构建了原型系统及仿真实验分析。值得注意的研究工作是淦文燕等的基于拓扑势的社区发现研究，该研究提出的识别方法具有较高的识别准确率。
3存在的主要问题
综合来看，现存的社区识别方法还存在一些缺陷和不足，主要表现为：1）针对的网络一般为同质网络。若实际网络为异质网络则先要将其处理为同质网络，造成信息丢失，识别质量难以保证。2）识别算法不是增量算法。当网络结构发生变化（如网络添加了新结点或删除了旧结点而引起原有社区的合并或分裂）时要重新进行识别，这使得整个应用系统运行效率较低，特别是一些网络中频繁出现结点增加和删除的情况时更加如此。3）需要先验或专家知识。社区识别前需要人工指定社区数目，这个要求在许多情况下难以实现或者根本不可能实现。4）沉淀在网络中的知识未能得到合理地利用。已知社区识别结果的网络往往蕴含着具有指导意义的对同一类型网络进行社区识别的知识，现存方法尚不能对其加利用。5）针对的网络往往是单关系网络。但是，在现实世界中普遍存在的是多关系网络。6）识别结果难以理解。社区中的结点（根据具体情况需要，下文中有时也称为聚簇对象）都同等对待，这使得确定社区中的重要结点非常困难。
4小结和展望
通过对复杂网络中社区识别研究存在问题的分析，本文预测未来相关研究的热点将集中在以下几方面：
1）异质网络上的社区识别；
2）动态网络上的社区识别；
3）摆脱先验知识的社区识别，特别是基于个体中心论的社区识别；
4）多关系网络上的社区识别；
5）识别结果的可理解性；
6）具备现实合理性的社区识别，具体包括重叠社区识别以及社区成员社区归属不确定性的量化表征；
7）提供不同观察粒度的社区识别。
|
|
|
|
【对“硅谷杂志：复杂网络中社区识别研究”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
