- 无标题文档
查看论文信息

论文中文题名:

 复杂网络中重叠社区发现算法研究    

姓名:

 晁莎    

学号:

 201308425    

学科代码:

 0835    

学科名称:

 软件工程    

学生类型:

 硕士    

学位年度:

 2016    

院系:

 计算机科学与技术学院    

专业:

 软件工程    

第一导师姓名:

 贾澎涛    

第一导师单位:

 西安科技大学    

论文外文题名:

 The Research of Overlapping Community Detection Algorithms in Complex Networks    

论文中文关键词:

 社区发现 ; 重叠社区 ; 模糊逻辑 ; 标签传播 ; 隶属度    

论文外文关键词:

 Community detection ; Overlapping communities ; Fuzzy logic ; Label propagation ; Membership degree    

论文中文摘要:
在复杂网络中,包含着大量的社区结构,按照社区的特征发掘复杂网络中的社区结构的过程,被称为社区发现。目前,研究者提出了各种社区发现算法,这些算法均能有效地发现非重叠社区结构,但在社区发现领域仍然存在一些待解决的问题,例如,在复杂网络中,一些结点可能同时和多个社区的联系都很紧密或者性质都很相似,因此这些结点属于多个社区。这类重叠社区的研究更接近于真实世界,具有很强的实际研究价值和探索意义。 针对现有算法存在的问题,对重叠社区发现算法进行了研究,主要研究内容及创新点如下: (1)提出了一种基于层次链接度的标签传播算法。该算法针对标签传播算法(LPA)有两处随机选择的地方导致算法稳定性差的问题进行改进。在初始时刻将具有独立标签的初始起点根据层次链接度重新排列,然后依次更新结点的标签值,最终具有相同标签的结点将形成一个社区。实验结果表明:相比LPA算法,该算法虽然牺牲了0.0337s的平均运行时间,但算法的稳定性得到了提高,平均准确率提高了3.87%,并能够合理、有效的发现复杂网络中的层次社区结构。 (2)提出了一种基于模糊逻辑的重叠社区发现算法。该算法引入模糊逻辑理论,首先将结点之间的紧密程度转化成对应的隶属程度,然后将大部分紧密连接的结点划分至对应的非重叠社区,再对剩余边界结点重新分配,满足特定条件的结点被认定为重叠结点,而其余的结点则被划分至对应的社区中。实验结果表明:相比LFM算法,该算法可以观察到不同层次上社区的划分情况,并能够很好的发现社区结构及社区间的重叠部分,实验划分结果准确,表现出了良好的性能。 在论文的最后对全文进行总结,并提出了在论文研究过程中发现的算法改进思路以及值得进一步研究和探索的方向。
论文外文摘要:
In complex networks, it contains a lot of community structure. According to the characteristics of community structure, the mining process of community structure is called community detection. For now a large number of community detection algorithm is putting forward, and these algorithms can find the non-overlapping community structure effectively. However, there are still some unsolved problems: for example in complex network, some nodes may have the characteristics of multiple communities at the same time, that is to say, they belong to several communities. This research of overlapping communities is closer to reality and has a strong practical research value and exploration significance. To solve the problem of existing algorithms, we researched overlapping community detection algorithm. The main contents and innovations are as follows: (1) We proposed a label propagation algorithm based on hierarchy connection degrees. In order to solve the problem that label propagation algorithm(LPA) has poor stability, we improved the LPA algorithm. The initial starting point with independent labels will be rearranged according to the size of the hierarchical connection degree at the initial time. Then, update the node label value in turn. Finally, the nodes with same label will form a community. Experiments confirmed that in terms of rationality and accuracy HCD algorithm is performed better than LPA algorithm. Although it sacrificed an average running time 0.0337s, but the average accuracy improved 3.87%. (2) We proposed a overlapping community detection algorithm based on fuzzy logic. It has imported the fuzzy logic theory. First, transform the compact degree between nodes into corresponding membership degree. Then, most of closely connected nodes will be divided into the corresponding non-overlapping communities, and the remaining discrete nodes will be redistributed. Finally, the nodes that satisfies specific condition will be identified as overlapping nodes, while the rest of the nodes will be divided into the corresponding communities. The experiments confirm that compared with the classical LFM algorithm the new algorithm can effectively find the community structure and the overlapping parts among communities and can observe the community division in different hierarchy. It shows that experimental division is accurate, the result is stable, showing a good performance. At the end of this paper, we summarized the full text. Furthermore, we put forward the algorithm improvement ideas found in the process of research and further research and exploration direction.
中图分类号:

 TP301.6    

开放日期:

 2016-06-19    

无标题文档

   建议浏览器: 谷歌 火狐 360请用极速模式,双核浏览器请用极速模式