社交网络的模糊进化聚类算法研究
发布时间：2018-08-22 08:52
【摘要】：Facebook、Twitter、人人网、QQ社区、新浪微博等社交网络服务平台的成功推广使关于社交网络的研究正变得日益重要和广泛。社区结构是这些社交网络的共同特性,所谓社区就是网络中的“分组”,组内联系密切,组间联系稀疏。传统的社区发现算法大多是在静态网络中发现非重叠的社区结构,但现实世界中社交网络往往随着时间不断推演而且社区结构通常可以重叠。本文在社交网络环境下,研究模糊聚类算法和演(进)化聚类算法,从而完成重叠的和动态的社区发现。聚类选取的初始点是否准确对聚类效率和质量都有影响。为在社交网络聚类时采用准确的初始点,本文基于结构洞和强弱关系理论,提出了社交网络聚类中的初始点选择算法SH_SW_IP和SH_SW_DP,这两种算法综合考虑网络中节点的重要性和节点间距离两个指标来获得聚类初始点,实验结果表明它们能以较低的时间复杂度得出较好的初始点,并能在社区数目未知的情况下给出近似的社区数目。重叠社区发现是最近的研究热点,模糊聚类是其中一个重要方法。本文扩展了强弱关系理论,并参照六度分隔理论构造一种节点相似度,结合FCM算法框架并且采用SH_SW_IP算法确定聚类初始点,重新设计一种局部最优点获取方案,从而利用该改进的FCM算法实现社交网络的模糊聚类,然后根据一定的标准设定阈值确定每个节点的类标,从而发现网络中的重叠社区结构,本文称该算法为SCCFCM算法,对比实验结果表明SCCFCM算法在发现社区重叠结构同时还可以发现每个社区的中心,而且随着数据集的增大SCCFCM算法表现出更好的健壮性。动态社区发现是最近社交网络研究中的另一个热点,演(进)化聚类算法是它的一个重要方法,遗忘因子确定是演(进)化聚类中一个必要环节。本文在社交网络中提出了节点惯性的概念,指出关键节点惯性变化规律,通过对比不同时间段的关键节点重要性得出遗忘因子的近似值,在确定了遗忘因子后利用演(进)化聚类框架改进SCCFCM算法为ESCCFCM算法,使之能够发现动态的重叠社区。对比实验结果表明ESCCFCM算法发现的社区不仅具有较高的模块度而且能表现出更好的光滑性。
[Abstract]:The successful promotion of social networking services such as Facebook Twitter, Renren's QQ community and Sina Weibo makes research on social networks increasingly important and widespread. The community structure is the common characteristic of these social networks. The so-called community is the "grouping" in the network. Most of the traditional community discovery algorithms find non-overlapping community structures in static networks, but in the real world social networks tend to evolve over time and the community structures usually overlap. In this paper, fuzzy clustering algorithm and forward clustering algorithm are studied in the social network environment, so as to achieve overlapping and dynamic community discovery. Whether the initial point of clustering selection is accurate or not has an effect on clustering efficiency and quality. In order to use accurate initial points in the clustering of social networks, this paper is based on the theory of structure hole and strong / weak relation. In this paper, the initial point selection algorithms SH_SW_IP and SHSWADS in the clustering of social networks are proposed. These two algorithms consider the importance of nodes and the distance between nodes to obtain the initial points of clustering. The experimental results show that they can get a better initial point with lower time complexity and can give the approximate number of communities when the number of communities is unknown. Overlapping community discovery is a hot topic recently, and fuzzy clustering is one of the important methods. In this paper, the theory of strong and weak relation is extended, and a node similarity is constructed by referring to the six-degree separation theory. Combining with the framework of FCM algorithm and using SH_SW_IP algorithm to determine the initial point of clustering, a local optimum acquisition scheme is redesigned. The improved FCM algorithm is used to realize the fuzzy clustering of social network, and then the threshold is set according to a certain standard to determine the class label of each node, and the overlapping community structure in the network is found. This algorithm is called the SCCFCM algorithm in this paper. The experimental results show that the SCCFCM algorithm can find the community overlap structure and the center of each community at the same time, and the SCCFCM algorithm shows better robustness with the increase of the data set. Dynamic community discovery is another hot topic in the research of social network recently. The (progressive) clustering algorithm is one of its important methods, and the determination of forgetting factor is a necessary link in the (progressive) clustering. In this paper, the concept of node inertia is put forward in social networks, and the law of inertia variation of key nodes is pointed out. By comparing the importance of key nodes in different time periods, the approximate value of forgetting factor is obtained. After determining the forgetting factor, the SCCFCM algorithm is improved to ESCCFCM algorithm by using the (progressive) clustering framework, so that it can find the dynamic overlapping community. The experimental results show that the community discovered by ESCCFCM algorithm not only has higher modularity but also has better smoothness.
【学位授予单位】：福州大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.09;TP311.13
[Abstract]:The successful promotion of social networking services such as Facebook Twitter, Renren's QQ community and Sina Weibo makes research on social networks increasingly important and widespread. The community structure is the common characteristic of these social networks. The so-called community is the "grouping" in the network. Most of the traditional community discovery algorithms find non-overlapping community structures in static networks, but in the real world social networks tend to evolve over time and the community structures usually overlap. In this paper, fuzzy clustering algorithm and forward clustering algorithm are studied in the social network environment, so as to achieve overlapping and dynamic community discovery. Whether the initial point of clustering selection is accurate or not has an effect on clustering efficiency and quality. In order to use accurate initial points in the clustering of social networks, this paper is based on the theory of structure hole and strong / weak relation. In this paper, the initial point selection algorithms SH_SW_IP and SHSWADS in the clustering of social networks are proposed. These two algorithms consider the importance of nodes and the distance between nodes to obtain the initial points of clustering. The experimental results show that they can get a better initial point with lower time complexity and can give the approximate number of communities when the number of communities is unknown. Overlapping community discovery is a hot topic recently, and fuzzy clustering is one of the important methods. In this paper, the theory of strong and weak relation is extended, and a node similarity is constructed by referring to the six-degree separation theory. Combining with the framework of FCM algorithm and using SH_SW_IP algorithm to determine the initial point of clustering, a local optimum acquisition scheme is redesigned. The improved FCM algorithm is used to realize the fuzzy clustering of social network, and then the threshold is set according to a certain standard to determine the class label of each node, and the overlapping community structure in the network is found. This algorithm is called the SCCFCM algorithm in this paper. The experimental results show that the SCCFCM algorithm can find the community overlap structure and the center of each community at the same time, and the SCCFCM algorithm shows better robustness with the increase of the data set. Dynamic community discovery is another hot topic in the research of social network recently. The (progressive) clustering algorithm is one of its important methods, and the determination of forgetting factor is a necessary link in the (progressive) clustering. In this paper, the concept of node inertia is put forward in social networks, and the law of inertia variation of key nodes is pointed out. By comparing the importance of key nodes in different time periods, the approximate value of forgetting factor is obtained. After determining the forgetting factor, the SCCFCM algorithm is improved to ESCCFCM algorithm by using the (progressive) clustering framework, so that it can find the dynamic overlapping community. The experimental results show that the community discovered by ESCCFCM algorithm not only has higher modularity but also has better smoothness.
【学位授予单位】：福州大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.09;TP311.13
【相似文献】
相关期刊论文 前10条
1 ;基于位置的手机社交网络“贝多”正式发布[J];中国新通信;2008年06期
2 曹增辉;;社交网络更偏向于用户工具[J];信息网络;2009年11期
3 ;美国:印刷企业青睐社交网络营销新方式[J];中国包装工业;2010年Z1期
4 李智惠;柳承烨;;韩国移动社交网络服务的类型分析与促进方案[J];现代传播(中国传媒大学学报);2010年08期
5 贾富;;改变一切的社交网络[J];互联网天地;2011年04期
6 谭拯;;社交网络:连接与发现[J];广东通信技术;2011年07期
7 陈一舟;;社交网络的发展趋势[J];传媒;2011年12期
8 殷乐;;全球社交网络新态势及文化影响[J];新闻与写作;2012年01期
9 许丽;;社交网络:孤独年代的集体狂欢[J];上海信息化;2012年09期
10 李玲丽;吴新年;;科研社交网络的发展现状及趋势分析[J];图书馆学研究;2013年01期
相关会议论文 前10条
1 赵云龙;李艳兵;;社交网络用户的人格预测与关系强度研究[A];第七届（2012）中国管理学年会商务智能分会场论文集（选编）[C];2012年
2 宫广宇;李开军;;对社交网络中信息传播的分析和思考——以人人网为例[A];首届华中地区新闻与传播学科研究生学术论坛获奖论文[C];2010年
3 杨子鹏;乔丽娟;王梦思;杨雪迎;孟子冰;张禹;;社交网络与大学生焦虑缓解[A];心理学与创新能力提升——第十六届全国心理学学术会议论文集[C];2013年
4 毕雪梅;;体育虚拟社区中的体育社交网络解析[A];第九届全国体育科学大会论文摘要汇编(4)[C];2011年
5 杜p，
本文编号：2196607
本文链接：https://www.wllwen.com/guanlilunwen/ydhl/2196607.html
