基于用户亲密度与密度峰值的社区发现算法研究

发布时间：2018-01-25 20:09

本文关键词： 社会网络社区发现用户亲密度密度峰值模块度　出处：《吉林大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着信息技术的快速发展和智能硬件设备的普及,人们已经进入到了社会信息化的时代,在线社会网络的出现改变了人们的日常生活和娱乐方式,各种各样的社会网络工具层出不穷,如微博、微信、知乎等,使人与人之间进行沟通交流更加方便、快捷,拉近了人与人之间的距离,促进了在线社会网络的快速发展。在线社会网络中记录了大量用户的信息,用户与用户间的关系有的紧密有的疏远,社会网络的社区化趋势越发明显,为了更好的理解社会网络中社区结构的特征以及社区演化的规律,大量学者投入到社会网络的研究中来,社会网络中的社区发现研究可以将整个网络划分为粒度小的社区,让我们更加清晰的了解网络结构,针对社会网络中的社区发现问题,本文的主要工作如下:首先,给出了一种改进的衡量用户相似度的方法。社区发现的大部分算法可以进行有效的社区识别,但是缺点是仅仅考虑了节点之间直接的、无向的关系,然而这在真实的在线社会网络中是不合理的,只依靠节点之间直接的、无向的关系并不能准确度量节点之间的相似程度,本文充分考虑节点之间直接与间接的关系,并且考虑了关系的有向性带给度量节点之间相似性的影响,给出一种新的基于用户关系的亲密度计算方法。首先给出了关注和粉丝矩阵的生成算法、直接亲密度与间接亲密度的定义。综合考虑有向的关注关系和粉丝关系给出了直接亲密度的计算公式,然后充分考虑节点间接关系给出了间接亲密度计算方法。最后给出了能够综合衡量节点之间结构特性的用户亲密度计算方法,并且给出了计算过程。然后,对基于密度峰值和快速搜索的聚类算法进行了改进,其作为一种高效的、新颖的聚类方法,可以自动识别社区的规模,并且可以得到任意形状的簇结构。但在识别社区中心时,可能导致将同一簇结构拆分为两个簇结构,影响了算法的结果。本文将其聚类思想应用到社会网络中社区发现的研究中,并结合社会网络的特性,给出了改进后的识别社区中心的方法,使其可以更加准确的识别社区中心,给出了基于密度峰值的社区发现算法。然后将上述两种改进方法相结合,基于用户关系的亲密度计算方法得到用户亲密度矩阵,使用基于密度峰值的社区发现算法来计算用户的重要度与距离,使其属性计算更加合理,最后给出了完整的基于用户亲密度与密度峰值的社区发现算法。最后,在微博数据集和公共数据集上验证算法的结果,实验表明了算法的可行性以及有效性,算法的参数调节策略使其具有较好的灵活性,算法同样适用于无向的用户关系网络,证明了算法具有较好的泛化性。
[Abstract]:With the rapid development of information technology and the popularization of intelligent hardware, people have entered the era of social information, and the appearance of online social network has changed people's daily life and entertainment. A variety of social network tools emerge in endlessly, such as Weibo, WeChat, Zhihu and so on, making communication between people more convenient, faster and closer to the distance between people. Promote the rapid development of online social networks. Online social networks record a large number of user information, the relationship between users some close some alienated, the social network community trend is becoming more and more obvious. In order to better understand the characteristics of community structure and the law of community evolution in social networks, a large number of scholars put into the research of social networks. The community discovery research in social network can divide the whole network into small grained communities, let us understand the network structure more clearly, and find out the problem for the community in the social network. The main work of this paper is as follows: firstly, an improved method to measure user similarity is presented. Most of the algorithms of community discovery can be used for effective community identification. However, the disadvantage is that the direct and undirected relationship between nodes is considered only. However, this is unreasonable in the real online social network and only depends on the direct relationship between nodes. Undirected relationship can not accurately measure the degree of similarity between nodes. In this paper, the direct and indirect relationships between nodes are fully considered, and the influence of the directionality of relationships on the similarity between measurement nodes is considered. A new method of user relationship based affinity calculation is presented. Firstly, the algorithm of generating attention and fan matrix is given. The definition of direct affinity and indirect affinity. Considering the relationship of directed concern and fan relationship, the formula of direct affinity is given. Then, considering the indirect relationship of nodes, an indirect affinity calculation method is given. Finally, the user affinity calculation method which can comprehensively measure the structural characteristics between nodes is given, and the calculation process is given. The clustering algorithm based on peak density and fast searching is improved. As an efficient and novel clustering method, it can automatically identify the community size. The cluster structure with arbitrary shape can be obtained, but when the community center is identified, the same cluster structure may be split into two clusters. The result of the algorithm is affected. In this paper, the clustering idea is applied to the research of community discovery in social network, and the improved method of identifying community center is given according to the characteristics of social network. So that it can identify the community center more accurately, give the community discovery algorithm based on the peak density, and then combine the above two improved methods. The user affinity matrix is obtained by the user relationship based affinity calculation method. The community discovery algorithm based on the peak density is used to calculate the importance and distance of the user, which makes the attribute calculation more reasonable. Finally, a complete community discovery algorithm based on user affinity and peak density is presented. Finally, the results of the algorithm are verified on Weibo dataset and common data set. Experiments show that the algorithm is feasible and effective. The parameter adjustment strategy of the algorithm makes it more flexible, and the algorithm is also applicable to the undirected user relationship network, which proves that the algorithm has better generalization.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13

【相似文献】