基于矩阵分解的重叠社区探测研究

《基于矩阵分解的重叠社区探测研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分巧号：ＴＰ３９单位代码：１０１拍２０１３５３２０８４研巧生学号：密级：公开戀巧林大学硕古単位絶文单术学位（）基于矩辟分巧的重》社区探测研究ＲｅｓｅａｒｃｈｏｎＯｖｅｒｌａｉｎＣｏｍｍｕｎｉｔＤｅｔｅｃｔｉｏｎｐｐｇｙＢａｓｅｄｏｎＭａｔｒｉｘＦａｃｔｏｒｉｚａｔｉｏｎ作者姓名：贾錫专业：计巧机应用技术研究方向：巧据巧巧与商务智能指导教师：黄试教授培养单位：计算化科学与技术学晓２０１６年５月未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子版本的任何单位和个人，均不得对

2、本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编等有碍作者著作权的商业性使用（但纯学术性使用不在此限）。否则，应承担侵权的法律责任。吉林大学硕±学位论文原创性声明本人郑重声明：所呈交的硕±学位论文，是本人在指导教师的指导下，独立进行研巧工作所取得的成果。除文中己经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均己在文中明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：曰期：２０１６年户月３｜＾曰基于矩阵分解的重

3、叠社区探测研究ResearchonOverlappingCommunityDetectionBasedonMatrixFactorization作者姓名：贾娜专业名称：计算机应用技术指导教师：黄岚教授学位类别：工学硕士答辩日期：2016年5月24日摘要摘要基于矩阵分解的重叠社区探测研究复杂网络是对现实世界系统的抽象。现实世界的个体被抽象为复杂网络的节点，个体之间的联系被抽象为按某种规则连接的边。经过大量实验证明，复杂网络与随机网络不同，具有小世界性、无标度性和结构性。复杂网络的节点成簇状分布，每一个簇成为一个社区。社区是由具有相同背景或者相似属性的节点组成。社区结

4、构普遍存在于现实世界的复杂网络中，例如科学家协作网、交通网络、社交网络、神经网络和蛋白质网络等等。社区结构是复杂网络的重要拓扑属性，研究社区结构有助于揭示复杂网络潜在的信息，因此吸引了各个领域的越来越多的学者专家的研究，成为新的研究热点。目前社区发现研究取得了丰硕的成果，据不完全统计将近一百多种社区发现算法被提出。根据社区是否重叠社区发现算法可以分为重叠社区发现算法和非重叠社区发现算法。非重叠社区发现算法中一个节点属于仅能够属于一个社区。在真实的复杂网络中普遍存在一个节点被多个社区共享现象，即社区之间存在重叠，例如在蛋白质网络中，一种蛋白质能够承担多种功能；在社交

5、网络中，一个人可以属于学校、同事、朋友、家人等多个社区。由于重叠社区更贴近真实的复杂网络结构，因此重叠社区发现成为复杂网络领域新的研究热点。自2005年Palla等人在PANS会议上首次提出了社区重叠现象，重叠社区发现研究成果如雨后春笋般涌现。重叠社区发现算法按照网络划分结果可以分为模糊重叠社区发现算法和非模糊重叠发现算法。非模糊重叠发现算法，例如CPM算法、LC算法等，能够明确划分网络的社区结构，但不能评估节点与社区的隶属强度。模糊重叠社区发现算法，例如FCM（fuzzyc-means）算法、SPAEM算法等，能够提供评估节点与社区的隶属强度，却不能够明确划分社

6、区结构。2013年，ZhongyuanZhang等人提出了SBMF模型，该模型能够结合两类算法的优点，弥补两类算法的不足。SBMF模型不仅能够明确划分网络的社区结构，还能提供节点与社区的隶属强度。并且，SBMF模型还能判别重叠节点和离群节点。但是，SBMF模型没有考虑重叠节点与多个社区相连，使得重叠节点与各个社区的隶属强度降低，导致潜在的重叠节点被误划分成为离群节点。为弥补SBMF模型这一缺陷，我们提出了基于遗传算法的拓展矩阵分解模型（ESBMF）。改进的ESBMF模型，采用遗I摘要传算法计算节点与社区的隶属强度的最优修正值，来明确网络的社区结构。评价社区划分结果

7、的优劣是社区发现的重要步骤。本文采用拓展模块度EQ作为评价指标。EQ主要用来衡量社区结构模块性高低，EQ值越大社区结构模块性越高。为衡量ESBMF模型的性能，本文采用四个经典真实数据集作为实验数据集，包括空手道社交网络数据集、海豚网络数据集、美国政治图书数据集和美国橄榄球联盟数据集，并与经典的LC算法和SBMF模型进行比较，实验结果证明，ESBMF模型划分的网络结构与真实的网络结构更贴近，模块性更高。关键词：重叠社区发现，矩阵分解,评价指标,遗传算法IIAbstractAbstractResearchonOverlappingCommunityDetectionB

8、asedo