链路预测和符号网络社区检测研究

发布时间：2018-10-05 16:12

【摘要】：近年来随着以互联网为代表的网络信息技术的迅速发展,人类社会已经迈入了复杂网络时代。在生活中很多复杂的系统可以抽象成复杂网络,进而转换成图的形式进行研究,社区结构作为网络中的一个重要性质,近年来引起了越来越多人的研究。理解网络的社区结构,不仅有助于分析网络的拓扑结构,而且有重要的实用价值,例如在社交网络中可以找出同属于一个社区但没有连接的用户,互相推荐为好友。链路预测作为复杂网络与信息科学联系起来的重要桥梁之一,受到了越来越多的关注。链路预测的相关研究不仅能够推动网络科学和信息科学理论上的发展,而且有巨大的实际应用价值,例如可以指导蛋白质相互作用实验、进行在线社交推荐等。然而现在的大多数链路预测算法只考虑了网络的局部信息或路径信息,而网络的社区结构信息一般很少考虑到。本文中提出了一种考虑网络社区结构的基于动力学的链路预测算法,进而将这种算法应用到复杂网络的链路预测上,也研究了有符号网络上的结构信息,提出了一种基于模块度的改进的有符号网络社区检测算法。本文的主要工作如下:1.为了研究复杂网络的结构性质对链路预测结果的影响,主要是复杂网络聚类系数和链路预测之间的关系,分别在不同的网络模型上进行试验,实验结果表明复杂网络链路预测结果随着网络聚类系数的增大而提高,在聚类系数相同的情况下BA网络越容易预测。2.在Kuramoto模型的基础上,把连续的相位微分方程改成离散的相位微分方程,提出了一种基于相位相似度的链路预测算法。由于在真实的社会网络中同一个社区不存在边的两个节点相位相似度值比较大,而不同社区之间存在边的两个节点相位的相似度比较小,因此单纯的相位相似度的链路预测算法效果还是不理想,为了克服这一缺点,本文中把相位的相似度和共同邻居结合,即把网络的社区结构信息和网络的局部信息相结合,提出了一种基于网络社区结构的动力学的混合的链路预测算法,分别在真实的网络和人工生成的网络上进行试验,并将与已有的链路预测算法对比,证明了本文中所提出的方法有效性。3.提出一种符号网络的社区检测算法。在已有符号网络的模块度基础上,基于有符号网络的性质,定义了一种专门针对符号网络的相似度函数。根据节点之间的相似度函数找出最适合合并的节点即彼此之间相似度最大的节点进行合并,在判断节点是否能合并及合并的终止条件时,通过已有符号网络的模块度,定义了一种新的判断两个节点能否进行合并的条件,把文章提出的算法应用到真实网络和人工生成的网络中都取得了比较好的效果,证明了提出算法的有效性。
[Abstract]:In recent years, with the rapid development of network information technology represented by the Internet, human society has entered a complex network era. In life, many complex systems can be abstracted into complex networks and then transformed into graphs for study. As an important property of network, community structure has been studied by more and more people in recent years. Understanding the community structure of the network not only helps to analyze the topology of the network, but also has important practical value. For example, we can find users who belong to the same community but have no connection in the social network, and recommend each other as friends. As one of the important bridges between complex network and information science, link prediction has attracted more and more attention. The related research of link prediction can not only promote the development of network science and information science, but also have great practical application value, such as guiding protein interaction experiment, online social recommendation and so on. However, most of the existing link prediction algorithms only consider the local information or path information of the network, while the community structure information of the network is rarely considered. In this paper, a dynamic link prediction algorithm considering the network community structure is proposed, which is applied to the link prediction of complex networks, and the structural information of signed networks is also studied. An improved community detection algorithm based on modularity is proposed. The main work of this paper is as follows: 1. In order to study the influence of the structural properties of complex networks on the results of link prediction, the relationship between clustering coefficients and link prediction of complex networks is mainly studied, and the experiments are carried out on different network models. The experimental results show that the link prediction results of complex networks increase with the increase of network clustering coefficients, and the BA network is easier to predict with the same clustering coefficient. On the basis of Kuramoto model, the continuous phase differential equation is changed into discrete phase differential equation, and a link prediction algorithm based on phase similarity is proposed. In a real social network, the phase similarity of two nodes with no edge in the same community is relatively large, while the similarity between two nodes with edge in different communities is relatively small. Therefore, the link prediction algorithm with pure phase similarity is still not ideal. In order to overcome this shortcoming, this paper combines the phase similarity with the common neighbor, that is, combining the community structure information of the network with the local information of the network. In this paper, a hybrid link prediction algorithm based on dynamics of network community structure is proposed, which is tested on real network and artificial network, and compared with existing link prediction algorithms. The method proposed in this paper is proved to be effective. A community detection algorithm based on symbolic network is proposed. Based on the modularity of existing symbolic networks and the properties of signed networks, a similarity function is defined for symbolic networks. According to the similarity function between nodes, the nodes that are most suitable for merging, that is, the nodes with the greatest similarity between each other, are found to merge. When judging whether the nodes can be merged and the termination conditions of the merging, the modularity of the existing signed network is adopted to determine whether the nodes can be merged or not. This paper defines a new condition to judge whether two nodes can be merged, and applies the proposed algorithm to real network and artificial generated network, and proves the effectiveness of the proposed algorithm.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O157.5;TP393.09

【相似文献】