基于社区结构的社交网络最优路径生成方法研究

发布时间：2018-04-17 17:49

本文选题：社交网络 + 社区检测　；参考：《西安电子科技大学》2015年硕士论文

【摘要】：技术的迅速发展使得人们进入互联网时代,越来越多的人加入到社交网络中,网民的数量已经占人口总数很大的比重,并且社交网络上的应用越来越丰富,人们在社交网络上交友、娱乐、消费、工作等等,社交网络的规模迅速增大,信息量也迅速增长,结构越来越复杂。相关问题的研究吸引了各个学科领域的专家和学者,比如网络拓扑结构理解、信息传播模型、个性化推荐系统等等,在这些问题中最优路径都发挥了重要的作用。因此研究社交网络最优路径问题具有非常重要的价值和应用意义。但是传统的一般最优路径算法已经无法适应社交网络规模大、结构复杂、信息量大的特点,而近年来针对特定网络利用其特点提出的算法也无法移植到社交网络中来。传统算法的时间复杂度已经优化的比较好了,所以我们需要一种利用社交网络特点的算法来解决这个问题。在社交网络的众多特点中,社区结构特性是近年来学术者们研究的热点。通过社区检测可以将特征相似的节点聚类到一个社区内部,这对理解社交网络结构特点和研究社交网络相关问题提供了指导性的意义。本文所做的工作主要是利用社交网络社区结构的特点构建社区模型,通过模型减小搜索最优路径的范围,提高最优路径算法的效率。本文的主要创新点如下:1.提出了一种基于社区结构的最优路径模型:社区图。利用社区检测算法得到的社区信息,社区建模成社区图的一个点,社区内的边忽略,将社区间最短的边赋值给对应社区图中节点之间的边。社区图的规模远比原社交网络小的多。在进行社区检测之前,用网络中最长边的权值加上任意正整数后减去原网络边权值得到反转网络,若原网络的边长度为0则保持不变,计算反转网络的社区结构作为原网络社区结构。2.提出了一种使用社区图求解最优路径的算法,首先计算最优k社区路径,起点为源点所在的社区,终点为目标点所在的社区。然后对这些社区路径求交集并利用这个交集重构搜索子网络,子网络的节点为交集中的节点,边为原网络中对应节点之间的边。最后利用最优路径算法求得最优路径。本文选取了5种真实社交网络对算法进行了验证,选取了两种评价结果质量的指标:相对误差(aper)和时间效率(eff)。实验结果显示本文提出的算法能满足相对误差小于0.05的要求,时间效率有几百甚至几千倍的提升。3.分析了社区图最优路径数k对实验结果的影响,从理论分析和实验结果两方面对这个问题做了比较全面的介绍。增加参数k会提高最优路径的准确度但降低了算法的效率,得出该问题是一个多目标优化问题,并给出了一个符合实际应用的解决方案。
[Abstract]:With the rapid development of technology, people enter the era of Internet, more and more people join in the social network, the number of Internet users has already accounted for a large proportion of the total population, and the application of social network is more and more abundant.People make friends, entertainment, consumption, work and so on on the social network, the social network scale increases rapidly, the information quantity also grows rapidly, the structure is more and more complex.The research on related issues has attracted experts and scholars from various disciplines such as network topology understanding information dissemination model personalized recommendation system and so on. The optimal path plays an important role in these issues.Therefore, it is of great value and significance to study the optimal path problem of social networks.However, the traditional optimal path algorithms can not adapt to the large scale, complex structure and large amount of information of social networks. However, the algorithms proposed in recent years for specific networks can not be transplanted to social networks.The time complexity of the traditional algorithm has been optimized, so we need an algorithm based on the characteristics of social networks to solve this problem.Among the many characteristics of social networks, community structure is a hot topic in recent years.The nodes with similar features can be clustered into a community by community detection, which provides guidance for understanding the characteristics of social network structure and studying the problems related to social network.The main work of this paper is to make use of the characteristics of social network community structure to construct community model, reduce the scope of searching the optimal path, and improve the efficiency of the optimal path algorithm.The main innovations of this paper are as follows: 1.This paper presents an optimal path model based on community structure: community graph.Using the community information obtained by community detection algorithm, the community is modeled as a point of the community graph, and the edges in the community are ignored, and the shortest edges between the communities are assigned to the edges between the nodes in the corresponding community graph.The community map is much smaller than the original social network.Before community detection, the weight of the longest edge of the network plus any positive integer is used to subtract the weight value of the original network edge to obtain the reverse network. If the edge length of the original network is 0, the network will remain unchanged.Compute reverse network community structure as the original network community structure. 2.This paper presents an algorithm to solve the optimal path by using community graph. Firstly, the optimal k community path is calculated. The starting point is the community where the source point is, and the end point is the community where the target point is located.Then the intersection of these community paths is obtained and the search subnetwork is reconstructed using this intersection. The nodes of the subnetwork are nodes in the intersection and the edges are the edges between the corresponding nodes in the original network.Finally, the optimal path is obtained by using the optimal path algorithm.In this paper, five kinds of real social networks are selected to verify the algorithm, and two indexes to evaluate the quality of the results are selected: relative error and time efficiency.The experimental results show that the proposed algorithm can meet the requirements of relative error less than 0.05, and the time efficiency can be increased by several hundred or even thousands of times.This paper analyzes the influence of the optimal path number k of community graph on the experimental results, and gives a comprehensive introduction to this problem from two aspects: theoretical analysis and experimental results.Increasing the parameter k can improve the accuracy of the optimal path but reduce the efficiency of the algorithm. It is concluded that the problem is a multi-objective optimization problem and a practical solution is given.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.09;TP301.6

【参考文献】