基于图着色社区发现算法地研究.docx

硕 士 学 位 论 文基于图着色的社区发现算法研究The Research of Community Detection Algorithm Based onGraph-Coloring作 者 姓 名：学科、专业 ：李向祥计算机应用技术学号 ：0211738指 导 教 师：完 成 日 期：李敬文2014.04兰州交通大学Lanzhou Jiaotong University万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含获得 兰州交通大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解 兰州交通大学 有关保留、使用学位论文的规定。特授权兰 州 交 通 大 学 可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（必威体育官网网址的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日万方数据兰州交通大学硕士学位论文摘要随着信息时代的高速发展，人们的生活、工作和社会网络之间的联系越来越紧密，社会网络体现是一种密集的社会结构，这种社会结构已经形成了相对比较稳定的关系体系。社会网络就是将各社会个体成员(或者组织)之间通过互动的方式相连接，它所关注的是每个社会个体成员或者组织之间的互动和联系。社会网络一般都呈现出高度的社区性，这也是社会网络和随机网络之间的区别。社区发现就是根据给定的社会网络，来抽取社区。国外已经针对这个问题的研究很多，并且广泛地应用于科学家的合作、疾病的传播等方面。该那么如何在社会网络中高效地发现社区，就称为了近年来社会网络的研究热点。本文主要研究工作如下：第一，分析目前社会网络的社区划分算法。通过对各种算法进行详细的阐述和性能比较，结果表明：一方面这些算法进行合理社区划分的时间复杂度较高而且效率较低，另一方面这些算法进行合理社区划分时需要设置先验条件。第二，针对这些算法存在的主要问题，本文准备首先通过图着色算法首先求出极大团，给出就求解极大团算法的具体数据结构定义和算法基本步骤。然后根据已有的社区划分算法评价指标，提出基于图着色的极大团聚类社区发现算法。并且在经典的社会网络及大规模社会网络上对新算法进行测试，并与典型的社区发现算法作比较。实验结果表明：相比于典型的社区发现算法，新算法的优越性更明显。本文最后指出了在本文基础上进一步要进行的研究。关键词：社会网络；社区发现算法；图着色；极大团聚类论文类型：应用基础研究-I-万方数据基于图着色的社区发现算法研究AbstractWith the rapid development of the information, it making peoples life and work closelywith the social network. the social network is a social structure, which reflect to the formationof the interaction between the individual members of society or organization relatively stablerelations system, Its concern is the interaction and contact between people. Social networksare generally community- height emerged, which is the difference between social networksand random networks. Community discovery is based on a given social network to extractcommunities. Many foreign countries have been studied for this problem, and this problem iswidely used in areas of scientists’ cooperation and the spread of the disease. Therefore, inrecent years, how to efficiently detect the social ne