复杂网络中重叠社团发现的算法探讨  

Discussion of the Algorithm Finding Overlapping Communities in Complex Networks

作　　者：屈丽娟[1] 屈宝强[1] 王玛[2] 

机构地区：[1]中国科学技术信息研究所,北京100038 [2]西安电子科技大学,西安710126

出　　处：《数字图书馆论坛》2011年第5期48-54,共7页Digital Library Forum

摘　　要：复杂网络聚类算法的研究对分析网络拓扑结构、理解其功能、发现网络中的隐藏规律以及预测网络行为具有十分重要的理论意义。目前许多寻找重叠点的算法不多，并且很多都需要比较高的时间复杂度。文章通过观察网络社团之间的相邻点与每二社团的连接边数以及定义阈值的方法对其进行了改进，最后通过期刊之间的引用关系计算期刊引用网络的相似性，构造网络图。采用基于谱的聚类算法和改进后的方法对该图进行浆类，从而验证改进算法的先进性。The study of the network clustering algorithms which aims to discover all natural network communities from given complex networks is fundamentally important for both theoretical researches and practical applications, and can be used to analyze the topological structures, understand the functions, recognize the hidden pattems, and predict the behaviors of complex networks including social networks, biological networks, World Wide Webs and so on. This paper reviews some algorithms, which finds out the overlapping points between the networks have very high time complexity. Addressing this lack, we propose an improvement method which can find some overlapping point by observing the number of edges between the neighboring community ＇ s point and every community. Finally, in order to prove the improved algorithm, this paper selects an application of joumal references and draws a network map based on the similarity calculated by the references among the journals. Then, elustering the graph with the spectral clustering algorithm and the improved method, the paper analyzes and compares the result.

关 键 词：复杂网络 聚类算法 相似性 重叠点 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]