基于地理位置的网络加权化社团发现算法

发布时间：2018-06-22 22:21

本文选题：社团发现 + 社团重叠　；参考：《东北大学》2014年硕士论文

【摘要】：自然界中存在的大量复杂系统都可以通过复杂网络加以描述,而社团结构是继小世界特性和无标度特性之后发现的最为重要的复杂网络特性。社团是网络中关联紧密的一群节点,往往具有某些共同特征,具有一定的实际物理意义。互联网是典型的复杂网络,深入研究互联网的社团结构可以帮助我们以分而治之的方式研究网络的功能及演化过程,更加准确的理解互联网的组织原则、拓扑结构等。目前针对互联网网络特性的社团发现研究还不足,传统社团发现算法并不能很好的反映互联网独有的特性。同时传统的社团发现算法大多数不能同时发现社团的重叠性和层次性。本文在局部适应度值最优化算法(LFM)思想的基础上,提出了基于共同邻居加权的社团发现算法(称之为CNW-LFM算法)。算法中通过共同邻居信息对边进行加权,其权值大小表示节点之间的紧密程度,并将适应度函数以网络中边的权值重新定义。然后在多个不同类型和不同规模的真实网络进行实验,发现CNW-LFM算法的重叠模块度高于原LFM算法,说明CNW-LFM算法优于原算法,使得社团划分结果更加合理,而且该算法可以同时发现社团的重叠性以及层次性。从而证明了结合网络特性进行加权的方法是可以提高社团结构发现的准确度以及合理性,为本文重点研究互联网社团结构打下了坚实的基础。针对互联网的宏观拓扑结构下的社团研究,在CNW-LFM算法的基础上,本文提出了基于地理位置加权的社团发现算法(称之为BGW-LFM算法)。针对互联网数据量庞大的问题,算法中提出了网络规模的缩减方法,从而明显地提高了时间效率。同时该算法充分考虑了互联网的地理特性,将地理位置信息和共同邻居信息相结合对边进行加权,边的权值依然表示节点之间联系的紧密程度。然后在多个不同规模的互联网网络进行实验,总结了算法中参数对社团划分结果的影响规律。对比实验中发现BGW-LFM算法的重叠模块度最高,其次是CNW-LFM算法,说明BGW-LFM算法使得社团划分结果更加合理。最后对比分析了社团结构的地理分布情况,发现BGW-LFM算法使得社团结构的地理分布更为紧凑。通过两方面的对比说明BGW-LFM算法使得对于互联网的社团结构发现更加准确,地理分布更为合理。而且该算法可以同时发现社团的重叠性以及层次性。
[Abstract]:A large number of complex systems in nature can be described by complex networks, and the community structure is the most important complex network characteristics found after the characteristics of the small world and the scale-free characteristics. The community is a closely connected group of nodes in the network, which often has some common characteristics and has some practical physical meaning. Network is a typical complex network. The in-depth study of the community structure of the Internet can help us to study the function and evolution process of the network in a divide and conquer way, and more accurately understand the organization principles and topology of the Internet. It can well reflect the unique characteristics of the Internet. At the same time, the traditional association discovery algorithm can not find the overlap and hierarchy of the community at the same time. On the basis of the local fitness value optimization algorithm (LFM), a community discovery algorithm based on the common neighbor weighting (called the CNW-LFM algorithm) is proposed. The weight value of the same neighbor is weighted, the weight value represents the close degree between the nodes, and the fitness function is redefined with the weight value of the edge of the network. Then the experiment is carried out in several different types and different sizes of real networks. It is found that the overlap module degree of the CNW-LFM algorithm is higher than the original LFM algorithm, indicating that the CNW-LFM algorithm is superior to the original algorithm. The method makes the division result more reasonable, and the algorithm can find the overlap and the hierarchy of the community at the same time. Thus, it is proved that the method of weighting with the network characteristics can improve the accuracy and rationality of the association structure discovery, which lays a solid foundation for the study of the interconnected community structure. On the basis of CNW-LFM algorithm, a community discovery algorithm based on geographic location weighting (called BGW-LFM algorithm) is proposed on the basis of the macro topological structure of the Internet. In view of the large amount of Internet data, a reduction method of network size is proposed in the algorithm, and the time efficiency is obviously improved. The geographical features of the Internet are fully considered, the geographical location information is combined with the common neighbor information to weigh the edges. The edge weights still represent the close degree of the connections between the nodes. Then, the experiments are carried out on the Internet networks with different sizes. The influence rules of the number of the algorithms on the results of the community division are summarized. It is found that the overlap module of the BGW-LFM algorithm is the highest, followed by the CNW-LFM algorithm, which shows that the BGW-LFM algorithm makes the community division more reasonable. Finally, the geographical distribution of the community structure is compared and analyzed. It is found that the BGW-LFM algorithm makes the geographical distribution of the community structure more compact. Through the comparison of the two aspects, the BGW-LFM algorithm makes the algorithm make the right The structure of the Internet community is more accurate and the geographical distribution is more reasonable. Moreover, the algorithm can detect the overlapping and hierarchy of the community simultaneously.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02;O157.5

【相似文献】