基于层次粒化的社团发现方法研究

《基于层次粒化的社团发现方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、．．．－＇‘－护；．；／詞１．密级：保密期限：告氣乂－蔓硕±学位论文．．〕．－■．ｉ■＇■Ｉ‘，．■巧．．基于层次粒化的仕团发观方法硏究杂．挺ＲｅｓｅａｒｃｈｏｎＣｏｍｍｕｎｉｔＤｅｔｅｃｔｉｏｎＡｌｏｒｉ化ｍｙｇＢａｓｅｄｏｎＨｉｅｒａｒｃｈｉｃａｌＧｒａｎｕｌａｔｉｏｎ項－ｊ—《尝号Ｅ１３２０１０２２姓名柯望学位类别工学硕±．吉！識蓋计胃机咖ａ术指导教师赵妹完成时间２０１６年０３月答辩

2、委员会主席签名ｙＶｊ独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研巧工作及取得的研究成果。据我所知，除了文中特别加Ｗ标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得安徽大学或其他教育机构的一学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：掏蓋签字曰期：年您月奶曰学位论文版权使用授权书本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权保留并向国家有关部

3、口或机构送交论文的复印件和磁盘，允许论文被查阅和借＾阅。本人授权安徽大学可１＾１将学位论文的全部或部分巧容编入有关数据库进行检索。，可Ｗ采用影印、缩印或扫描等复制手段保存、汇编学位论文（保密的学位论文在解密后适用本授权书）学位论文作者签名：栖迎导师签名：签字日期：７４￥年每月如日签字日期；和年口日？摘要社会关系广泛存在于现实生活中，它们可ｗ抽象成各式各样的社会网络。近些年来，研究者们发现社会网络中存在的社团结构是大规模网络分析和挖掘的基础，对于分析社会系统的组织原则与动力学特征队

4、及预测系统中实体的行为具有重要的研究意义，在社会学、生物学和商业活动中具有广泛的应用前景。网络中社团结构的研究己成为一个具有重要社会价值及应用价值的课题。如何更快更好地发现社团结构或者是发现更真实的社团结构是网络社团研究中的关键问题。本文首先研究如何寻求降低社团发现算法的时间复杂度和提高社团发现的精确度间的平衡关系，然后给出精确地发现网络中实际的社团结构的新思路。作者对上述问题进行相应研究，将层次粒化方法引入社团划分方法中来，提出基于邻接粒化的社团发现算法（ＡＧＣＤＡ）和基于相容粒化的社团发现算法

5、（ＴＧＣＤＡ）ｃ本文的主要工作如下；１）首先对社团发现算法的研究现状进行详细地调研，并分析部分经典算法的优势和不足，同时将层次粒化方法引入本文中来更快更好地发现社团结构或者是发现更真实的社团结构。２）为了获取社会网络社团发现算法的复杂度和精确度间的均衡，将层次粒化的方法引入社团发现，本文提出基于邻接粒化的社团发现算法（ＡＧＣＤＡ）。该算法初始时根据网络中节点间的邻接关系对网络进行初始粒化，然后不断地对网络进行层次粒化，直到不满足粒化条件为止，最后在该粒度下求解非重叠社团结构。该算法有效地解决时

6、间复杂度和精确度难平衡的问题。实验部分在基准网络和应用网络上进行测试，并与经典的社团发现算法进行比较。基准数据集上的实验结果表明了该算法可获得高于ＬＰＡ算法７．６％的模块度和低于ＮＦＡ算法９６％的时间。因此，ＡＧＣＤＡ算法的时间复杂度较低，获取的社团模块度较高，实现了社团发现时间和精确度的均衡，总体性能更优。３）为了更加准确地发现社会网络中真实的社团结构，本文提出基于相容粒化的社团发现算法（ＴＧＣＤＡ）。该算法初始时根据网络中节点间的相容关系对网络进行初始粒化，然后不断地对网络进行层次粒化，直到网络中

7、的所有节点包含Ｉ安徽大学２０１６届硕±学位论文基于层次粒化的社团发现方法研究在一个粒子中为止，最后在具有最大相容粒化标准的粒度下求解非重叠社团结构。该算法初始粒化网络时形成若干个极大相容粒子，其保证具有高连接密度的一社团至少要包含个极大相容粒子，因而可Ｗ更准确地发现接近于网络中真实存在的社团结构。实验部分在人工数据集和基准数据集上测试ＴＧＣＤＡ算法的有效＇生ＴＧＣＤＡ算法可ＦＡ算法１７５５／１，在基准数据集上，Ｗ获得高于Ｎ．％的ＪＶＭ精确度，同样在人工数据集上也有所提高。因此对于具有真实社团结构

8、的网络，ＴＧＣＤＡ算法可Ｗ更加准确地发现网络中的社团结构。关键词：社会网络；社团结觀邻接关系；相容关系，层次粒化ＩＩＡｂｓｔｒａｃｔＡｂｓｔｒａｃｔＳｏｃａｌｒｅｌａｔｉｏｎｓｈｉｓｗｉｅｘｉｓｉｎｒｅａｌｌｉｆｅａｎｔｈｅ