【作者】 胡心专；

【导师】 郭景峰；

【作者基本信息】 燕山大学 ， 计算机应用技术， 2016， 博士

【摘要】 生活中,社会网络的实体间存在多种关系,如:合作与竞争关系、朋友与敌人关系、支持与反对关系等等,这种同时具有正负关系的社会网络被称为符号网络。符号网络作为社交网络的特例,已成为国内外学者研究的热点之一。符号网络社区发现作为符号网络分析的基础,对预测、个性化推荐、用户特征分析等的理论研究及应用具有重要意义。目前,针对符号网络社区发现的研究主要分为两类:基于优化目标函数的方法和基于启发式的两步式方法,本文针对现有两阶段方法存在的问题,为提高社区发现的正确性和社区发现算法的稳定性,进行研究如下。首先,针对经典两阶段符号网络社区发现算法CRA,因忽略负边导致最终划分结果错误的问题,提出了一种新的两阶段融合的符号网络社区发现算法TFCRA。该算法定义了节点社区归属规则,同时考虑正负边并将两阶段进行融合以提高社区划分准确率。并通过实验验证了TFCRA算法社区划分的正确性与合理性。其次,针对当前算法中存在的稳定性差的问题,基于“两个节点具有越多的共同邻居节点的相似度值越高”的思想,将传统社会网络中节点间相似度指标扩展到符号网络中,提出一种新的基于节点间相似度的符号网络社区发现算法BNS_SNCD。该算法把共同邻居个数作为相似度指标实现社区划分,并给出了小社区合并策略以提高社区合并效率。最后,通过实验验证了BNS_SNCD算法社区划分的正确性与合理性。第三,针对当前算法通过两个节点共同邻居的个数判断相似性存在的不足,基于节点邻居之间关系的紧密性,提出另一种节点相似度符号网络社区划分算法BTCN_SNCD。该算法根据节点的贡献度和紧密度、社区重叠系数和社区密度度量指标,可以发现更紧密的初始社区结构,对重叠社区的合并,进一步保证了社区发现的准确度,并通过实验验证BTNC_SNCD算法社区划分的正确性和有效性。第四,针对当前算法需要调整带负边节点社区归属存在的问题,结合结构平衡理论提出一种新的符号网络社区发现算法SBTNS_SNCD。该算法综合考虑节点的正负度,提出节点相似度、节点参与度指标,减少由于社区内部负边太多产生的局部震荡,有助于获取更准确的社区结构,并通过实验验证SBTNS_SNCD算法社区划分的正确性和有效性。最后,在SBTNS_SNCD算法的基础上,将核心节点和外壳节点作为度量指标,提出了一种符号网络重叠社区发现算法SNOCD,与其他符号网络社区发现算法相比,SNOCD能更精确、灵活地发现重叠社区。更多还原

【Abstract】 There are many relationships among entities in social networks at present,such as cooperation and competition,friends and enemies,support and opposition,etc.The social networks with positive and negative relationships are called signed networks.As a special case of social networks,signed networks have become one of the hotest research topics for domestic and foreign scholars.The study on community detection in signed networks is the basis of network analysis,which has important influence on the prediction,personalized recommendation,and user characteristic analysis and so on.Nowadays,the research on community detection in signed networks is mainly divided into two types,the method based on optimizing objective function and two-phase method based on heuristic.Aiming at the problems of existing methods,this paper makes the following research in order to improve the accuracy of community detection and the stability of the community.Firstly,as the classical two-phase signed networks community detection algorithms,CRA can not correctly divide the network because the negative edges are ignored.The TFCRA algorithm is proposed as a new two-phase fusion signed networks community detection.To improve the accuracy of community detection,the algorithm defines the assignment rules of vertices with negative edge and converge the two phases through taking into account the positive and negative edges at the same time.The correctness and rationality of the TFCRA algorithm are verified by experiments.Secondly,aiming at the problem of poor stability in current algorithms,and based on the idea that the more common neighbors the higher similarity between vertices,we extend similarity in the traditional social network to signed networks and propose a new BNS_SNCD algorithm for the community detection in signed networks based on similarity.The algorithm represents the similarity with the number of common neighbors and divides the community based on similarity degree.And it improves the efficiency of community merger by the commbining strategy from small community to big community.Finally,the correctness and rationality of the BNS_SNCD algorithm are verified by experiments.Thirdly,in view of the problem that the current algorithms only consider the number of common neighbors,a new signed network community detection algorithm BTCN_SNCD is proposed based on the tightness of common neighbors.The algorithm takes the contribution degree,tightness among nodes and communities,overlap coefficient and community tightness as criterion,and can find more compact initial communities,and it also can merge the overlapping community.This ensures the accuracy of the community detection.The correctness and efficiency of the BTNC_SNCD algorithm are verified by experiments.Fourthly,for the local oscillation problem caused by determining the assignment of nodes with negative edge in current algorithms,a algorithm SBTNS_SNCD is proposed based on structural balance theory.Combining with the positive and negative degree,we propose a new similarity and participation degree calculation method,which can reduce the oscillation and obtain more accurate community structure.The correctness and efficiency of the SBTNS_SNCD algorithm are verified by experiments.Finally,based on the SBTNS_SNCD algorithm,we put forward the concept of core nodes and shell nodes.Combining with the idea that the shell nodes are closely related to other communities and may be overlapping nodes,the signed networks overlapping community detection algorithm SNOCD is proposed.It can accurately find the overlapping nodes,and then detect the signed networks overlapping community.Compared with other algorithms,SNOCD can be more accurate and flexible to detect the signed networks overlapping community.更多还原