TCMA：改进型L-shell局部社团挖掘算法及其实验研究

发布时间：2018-05-28 15:05

本文选题：复杂网络 + 社团挖掘　；参考：《吉林大学》2017年硕士论文

【摘要】：近些年来人类在科技领域的发展取得了骄人的成绩,尤其是在互联网领域的发展,更是令大家有目共睹。网络科技突飞猛进发展,特别是在移动互联网方面的发展更使得人们的工作和生活方式有了质的变化。自从移动互联网问世以后,我们每一个人的生活、工作方式等等在各个方面和领域都已经离不开互联网。这就充分说明了互联网已经和我们的生活紧密的融合在一起,形成了一个不可分割的整体。众所周知,在Web2.0的网络时期最突出的发展就是社交网络的横空问世以及给人们生活与工作方式带来的巨大改变。在这之后无论任何人,不分年龄,行业,国籍等每一个人都可以在互联网上公平,快速的获取与发布消息。这突如起来的生活方式,让人们有种诸葛亮在世的感觉,每一位网民都拥有了“不出茅庐而知天下事”能力和思维的方式。特别是后来社交网络中产生的社交软件,比如新浪微博、腾讯的QQ和微信以及国外的社交软件Twitter等各类各样的社交软件,使得全世界每一个角落的网民都被紧密的连接在了一起。我们可以把网络看成一张能够把全球都覆盖的网,在这张巨大的网络中,我们每一个网络的使用者都可以被视为网路的一个节点。我们相互之间通过网络工具进行通信等操作。现在已经发展到了大数据时,在大数据时代互联网中的数量更加的复杂和庞大,大数据时代的数据量是比以往任何时期都要多,可以说是比以往所有数据的总和还要多。在大数据时代网络数据之所以这么庞大,主要就是得益于网络科学技术飞速的发展。这些海量的丰富数据信息,不只能够反映出大家的生活圈子,对过去的事情进行总结,更加可以通过这些海量的数据对将来即将可能发生的事情进行相应的推测和预言。这就使得对互联网的研究更加有着实际意义与使用价值了。本文通过对已有的社团网络的发现算法进行深入的研究与分析,并对基于局部社团挖掘算法的L-shell算法进行了改进,将寻找待挖掘社团中节点的过程中加入了节点对之间信任关系的判断。通过此思想可以大幅度的提升社团发现算法的效率和准确性。另外本文的算法是具有针对性的社团挖掘算法的设计,主要就是针对具有信任关系模型的网络模型进行社区的挖掘。这样设计的目的就是通过信任关系挖掘出来的社团,该社团内部的节点之间都有一定的相似性和共性,所以更具有实用价值和意义,可以进行针对性的信息推送等活动。虽然已经有好多关于社团挖掘算法的研究,但是在大多数情况下找到一个社交网络中社团结构的准确度本身就是一个NP难问题,尤其是在网络结构中的节点数达到了数以十万计,百万计的时候,网络的结构就会变得相当复杂,这个时候如果还是从全网对社团进行划分的话,是毫无意义的并且算法的效率也会降低,而且准确率也不高,根本就不能有效地反映出真实的社团情况。而如果从局部社团挖掘算法的角度对社区进行划分的话就不一样了,如果通过一个起始节点将该节点的社团挖掘出来,这样挖掘出来的社团更加具有研究价值。所以最近几年之中对社团挖掘进行局部挖掘的算法就一直是学术界热衷研究的点。社区发现算法的本质指的就是对某一个节点进行聚类的一个过程,把那些彼此之间关联度较高的节点合在一起,这样就获得了相应的社团结构。本文的工作安排主要包含以下几个方面:对社团挖掘算法进行研究分析,主要是局部社团挖掘算法中的L-shell算法(下文有相关介绍)与R算法(下文有相关介绍)进行了详细的分析研究。然后对L-shell算法进行了相应的改进,由于本文的算法是针对具有信任关系模型网络进行社区划分的,所以同时也对社团中节点间信任关系相关的知识做了大量的研究和分析。然后就是对改进后的L-shell算法,就是指基于信任关系的社团挖掘算法(Community mining algorithm based on trust relation,下文简称TCMA)进行代码设计与实现。然后对TCMA算法进行实验结果分析。
[Abstract]:In recent years, human beings have made remarkable achievements in the development of science and technology, especially in the field of Internet. The development of network technology has developed rapidly, especially in the development of mobile Internet, which has made the people's work and lifestyle changed qualitatively. Since the advent of the mobile Internet, Every one of us lives, work, and so on in all aspects and fields. This has fully demonstrated that the Internet has merged closely with our lives to form an inseparable whole. As we all know, the most prominent development in the time of the Web2.0 network is the cross question of the social network. The world and the great changes in the way people live and work. After that, everyone, regardless of age, industry, nationality, can get fair, quick access to and release news on the Internet. This way of life makes people feel Zhu Geliang's living feeling, every netizen has "no". The way of thinking and ability, especially the social software that comes from social networks, such as Sina micro-blog, Tencent QQ and WeChat, and social software Twitter abroad, has made every corner of the world close together. As a network that can cover all over the world, in this huge network, every user of our network can be regarded as a node of the network. We communicate with each other through network tools. Now, when large data are developed, the number of the Internet is more complex and Pang in the large number of times. In big data age, the amount of data is much more than ever before. It can be said to be more than the sum of all the data in the past. In the big data age network data is so huge that it is mainly due to the rapid development of network science and technology. These massive data are not only able to reflect the life circle of everyone. This will make the research of the Internet more practical and useful. This paper makes a thorough research and Analysis on the discovery algorithm of the existing community network. In addition, the L-shell algorithm based on local association mining algorithm is improved. In the process of finding the nodes in the mining community, the trust relationship between the nodes is added. Through this idea, the efficiency and accuracy of the association discovery algorithm can be greatly improved. In addition, this algorithm is a pertinent association mining algorithm. The design is mainly for the mining of the community with the model of the trust relationship model. The purpose of this design is to dig out the community through the trust relationship, and there are some similarities and generalities among the nodes within the community, so it has more practical value and significance, and can carry on the specific information push and so on. Although there has been a lot of research on association mining algorithms, in most cases, finding the accuracy of community structure in a social network is a NP difficult problem, especially in the network structure, the number of nodes is up to one hundred thousand, and the structure of the network becomes quite complex when it is million. If we divide the community from the whole network, it is meaningless and the efficiency of the algorithm will be reduced, and the accuracy is not high, it can not effectively reflect the real community situation. And if the local community mining algorithm point of view of the community is different, if a starting section is passed. In recent years, the algorithm of mining local mining for community mining has been a hot topic in academic circles. The essence of community discovery algorithm refers to a process of clustering one node, and the other is the same. The nodes with higher correlation degree are combined together, thus the corresponding community structure is obtained. The work arrangement of this paper mainly includes the following aspects: the research and analysis of the association mining algorithm, mainly the L-shell algorithm in the local association mining algorithm (the following related introduction) and the R algorithm (following the related introduction) are detailed. Then, the L-shell algorithm is improved. Because the algorithm is based on the community division of the model network with trust relationship, a lot of research and analysis are made on the knowledge related to the trust relationship among the nodes in the community. Then, the improved L-shell algorithm is based on trust. The association mining algorithm (Community mining algorithm based on trust relation, hereinafter referred to as TCMA) is used to design and implement the code. Then the experimental results of the TCMA algorithm are analyzed.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13;O157.5

【相似文献】