信息网络社区发现研究

《信息网络社区发现研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、文章编号：1674-7070(2010)01-0019-07信息网络社区发现研究黄发良肖南峰摘要0引言随着人们生产生活信息化的深入，Introduction信息网络的社区发现研究引起越来越多研究者的关注．在对信息网络社区发现互联网的迅猛发展极大地推动了社会信息的网络化进程，以即研究的基本概念与原理进行简单介绍的基础上，着重对各种发现方法进行分类时通讯系统、P2P信息共享网络、博客网络、邮件网络、短信网络与在分析与比较．最后，对信息网络社区发现线聊天室网络等为代表的信息网络已经深人到人们的工作、学习与技术进行了总结与展望．生活等活动中，是构成信息社区的基础环境．这些各式各样的信息网关键词信息网

2、络；社区发现；复杂网络；络承载着人们在生产生活中形成的复杂关系，从这些纷繁芜杂的关聚类系结构发现隐藏的潜在有价值的关系模式是一个非常困难而又很有中图分类号TP391．41意义的工作．文献标志码A信息网络社区发现任务的艰巨性与挑战性主要源自信息网络的复杂性：网络结构的异构性、网络规模的巨大性与网络属性的动态性．网络结构的异构性主要表现在网络节点类型的多样性，相同类型的节点构成同型网络，而不同类型的节点可以构成异质网络，类似的有网络节点间的关系可以是相同类型，也可以是不同类型，还有网络节点关系的方向性与网络节点关系重要性的度量方法的差异性等多种因素影响着网络结构；网络规模的巨大性是互联网信息网络

3、的一个重要特征，传统的社会网络由于数据收集的困难性使得其网络规模比较小，进而使得其表现出的各种特征从统计意义上讲价值不是很大，互联网与万维网的规模巨大性一方面提供了对其拓扑属性进行可靠分析的基础条件，另一方面也向分析算法的计算效率提出更高的要求；本文将网络属性定义为节点属性与节点间关系属性两个方面，信息网络始终处于一个动态的过程，新节点的加人，原有节点的退出，节点关系的建立和消失，网络属性的动态演化对算法的可扩收稿日期2009—11-09资助项目国家自然科学基金与中国民用航空展性与鲁棒性提出巨大的挑战．总局联合资助(60776816)；广东省自然科学信息网络中隐藏的知识吸引着大量来自社会学、

4、物理学与计算重点基金(8251064101000005)；福建省教育厅科研基金(JA08049)．机科学等各个不同学科领域中的科研工作者．最早是社会学家注意作者简介到社会信息网络的拓扑结构特征，将实际社会关系网络作为研究对黄发良，男，讲师，博士生，主要研究方向为智能计算及计算机应用．huangfliaIlg@163．oom象，试图从中发现隐含的社会关系和从信息网络的角度去解释社会肖南峰(通信作者)，男，博士，教授，主要研现象；物理学研究者主要从复杂网络理论的层面对包括有形实体网究智能计算及计算机应用．xiaonf@scut．edu．cn络(诸如电力网、因特网、高速公路或地铁系统及神经网络)和

5、抽象空l华南理工大学计算机科学与工程学院，广间网络(例如朋友关系网和个体合作网)在内的复杂系统的拓扑结构州。5100062福建师范大学软件学院，福州，350007属性与演化动力特征进行研究，提出了众多用以解释各种物理现象黄发良，等．信息网络社区发现研究，20HUANFMiang，eta1．Researchoncommunitydetectionininformationnetwork．的网络模型，例如小世界模型、无标度网络以及随机大增量，同时，为了避免陷人局部极小，允许有Q值网络等；随着以海量数据分析与挖掘为宗旨的数据负增量的情形，重复上述操作多次并选取其中具有挖掘技术研究的深入，计算机科学

6、家也逐步投入到最大Q增量的操作执行，得到的结果转入下一轮迭这个充满魔力的研究领域中来，并取得了很多有趣代．该算法的时间效率高(0(n2logn))，但对初始划的结论，他们主要是根据信息网络的规模巨大性等分比较敏感，常用来对其他社区发现算法的结果进特点，设计出高效率、高效用并具有一定智能的鲁棒行求精．谱二分法通过对网络邻接矩阵的Laplacian算法．矩阵L进行谱分析，来计算网络的具有小割的划分方案．网络的任何二分方案都可以用下标向量来1社区的定义表示(若节点被划分到第1个社区则元素s取值Definitionofcommunity为1，否则取值为一1)，网络的最小割可以形式化为尽管社区发现的研

7、究在复杂网络中有很长时间=4L，7(、1)／了，但到目前还没有一个公认的严格定义，在信息网若令络领域中有这样一个共识：社区内部节点连接紧密而社区间连接松散．当前的社区定义主要是从网络s=∑0l，，(2)自我参照与网络属性比较两个角度给出的．首先是式中，l，是L的第i个特征向量，则有自我参照角度，社区被定义为完全子图，这个定义所R=∑●_oA．(3)有隐含的社区内所有节点都两两相连接的限制条件式(3)中，A是L